作业题:
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·,$ (b) decl -> type vlist
type -> int
type ->float 7 vlist -> vlist, id vlist -> id
Decl-> . type vlist type->.int type ->.float 6 0
decl -> type. vlist 1 vlist -> . vlist , id 2 vlist -> .id
id vlist -> vlist, .id id 4 vlist -> id. 3
5 follow(decl)= { $ }, follow(type)= { id } follow(vlist)= { $, , }
(c ) construct the SLR(1) parsing table for the rewritten grammar state 0 1 2 3 4 5 6 7 6.7
input int 6 float 7 id 3 5 r2 r3 , 4 r5 r4 $ r1 r5 r4 goto type 1 Decl vlist 2 vlist -> vlist, id. type vlist decl -> type vlist. vlist -> vlist. , id , type -> float. type->int.