编译原理与实践作业答案

作业题:

2.1(a,c,d), 2.8(a,c,d), 2.12, 3.3, 3.4, 4.8, 4.12

5.8(a,b,c), 5.12, 6.7, 6.8, 6.13 7.4, 7.15

第二章作业： 2．1 (a) a | a[a-z]*a

(c) [1-9][0-9]* (d) [0-9]*[02468]

2.8（a）

Start a a [b-z] [b-z]

a

正则表达式中丢了单独a的情况的比较多，另外有些同学在有NFA到DFA的转化过程

中，不能够正确的确定最终的状态，造成有两个终结状态的情况。 （c）

Start [0-9]

[1-9]

（d）

问题比较多，建议同学画出DFA图生成的全部过程。

2.12

3．4

a a a b a bb b a a b b b a （c）.rewrite this grammar to establish the correct precedences for the operator.

rexp -> rexp “|” rexp1 | rexp1 rexp1 -> rexp1 rexp2 | rexp2 rexp2 -> rexp3 * | rexp3 rexp3 -> (rexp) | letter 左结合 4．8

（a） 消除左递归

lexp -> atom | list atom -> number | identifier list -> (lexp-seq) lexp-seq -> lexp lexp-seq’ lexp-seq’ -> lexp lexp-seq’ | ?

first (lexp)= { number ,identifier,( } first (atom)= { number, identifier } first (list) = { ( }

first (lexp-seq)= { number ,identifier,( } first (lexp-seq’)= { number ,identifier,( , ?}

follow(lexp)= { $,),number,identifier,(} follow (atom)= { $,), number,identifier,( } follow (list) = {$,), number,identifier,(} follow (lexp-seq)= { )} follow (lexp-seq’)= { )} M[N,T] lexp atom list lexp-seq lexp-seq’

4.12

(a) LL（1）文法不会是二义的，因为它的分析表的每个入口是唯一的。就不会是二义文法

了。

(b) 二义文法也不可能是LL（1）的，否则在LL（1）的parsing table 中会产生各种冲突。 非二义的文法不一定是LL（1）的，因为二义文法是非LL（1）文法的一个因素，但不是唯一的因素。如一些带有左递归的文法也不是LL（1）文法。

number lexp->atom atom->number lexp-seq’ lexp-seq’ identifier lexp->atom atom->identifier lexp-seq’ lexp-seq’ ( lexp->list list -> (lexp-seq) -> lexp-seq’ lexp-seq’ ? ) lexp $ lexp-seq -> lexp lexp-seq -> lexp lexp-seq lexp-seq’ -> lexp lexp-seq’ -> lexp lexp-seq’ -> lexp lexp-seq’ -> 第五章作业 5．12 s’ ?s

s?a A d | b B d | a B e | b A e A?c B?c c·, e A?B? c·, d A c b s’ ?s·,$ s’ ?·s,$ s?·a A d,$ s ?·b B d ,$ s?· a B e,$ s? ·b A e,$ a A?c·, d B?c·, e c s ?b·B d ,$ s? b·A e,$ A?·c, e B?·c, d B B s?a·A d,$ s?a·B e,$ A?·c, d B?·c, e s?aB·e,$ s?aBe·,$ A s?aA·d,$ s? bA·e,$

5.8 Consider the following grammar

declaration -> type var-list type -> int | float

var-list -> identifier, var-list | identifier

(a) declaration -> type var-list

type -> int | float

var-list -> var-list, identifier | identifier

s?aAd·,$ s?bAe· ,$ s?bB·d,$ s?bBd·,$