《操作系统r.docx》由会员分享，可在线阅读，更多相关《操作系统r.docx（4页珍藏版）》请在三一文库上搜索。
1、第四章语4.1考虑文法RR |R | RR | R* | (R) | a | b请注意第一个直竖是符号或而不是两个候选式之间的分隔符号。(a) 试说明此文法生成在符号a和b之上的所有正规表达式。(b) 试说明此文法是二义性的。(c) 试构造一个等价的无二义性文法，此文法给岀*、连接和|等运算符号的优先级和结合规那么，有关约定见节。解：(a)对于文法RRR | RR | R* | (R) | a | b，包含非终结符、*、(、)、a、b，由正规表达式的定义，显然，由该文法产生的语言即相当于在字母类X=a, b上的正规表达式所表示的语言。对等于任意在符号a，b之上的正规表达式 X，设X中符号、*、
2、(、)的个数共有n个。对n用归纳法证 明X可由该文法生成。1)假设 n=0那么X=a或X=b，可由R a或R b生成2)不妨设n = K时，X可由文法生成。那么n=K+1时，假设X = r | s，贝U r，s中的运算符个数均小于等于K即r与s均可由文法生成。X可由R R、R生成此外，对于 X = ( r )或X = r*均成立 n = K+1时结论也成立综上所述，此文法生成在 a, b之上的所有正规表达式。(b) 考虑语句ab*，由此文法可得岀以下两棵不同的分析树。所以，此文(c)对以上所给 以优先级及 法G如下：R1法是二义性的。文法消除二义性， 并加结合规那么的考虑， 得文R2R3R|R
3、1 | R1R1R2 | R2R3* | R3(R) I a | b显然，此文法满足*，结合T优先级递减的优先级要求及以上运算的左结合规那么，并且文法G、无二义性，满足题中所示要求。4.2试分析下面给岀的if then else语句的文法，它的提岀原本是为了矫正dangling else (悬而未决的一else )文法的二义性：stmt if expr then stmt | matched-stmtmatched-stmt if expr then matched-stmt else stmt | other 试说明此文法仍然是二义性的。解:考虑句子 if E1 then if E2 the
4、n S1 else if E3 then S2 else S3 ，它具有两种如下所示的分析树:(1)stmtifexprE1the n stmt那么上面给岀的ifthen else文法仍是二义性的。4.3对于下面的每一个语言试设计一个文法。试问其中哪些语言是正规的?(a) 使得在每一个 0后至立即跟随一个 1的由0和1组成的符号串的全体。(c) 具有不同数目的 0和1的由0和1组成的符号串的全体。解：(a) S 0A | 1S | eA 1S(c) S 1A | 1E | 0AA | 0B | 0E | 1BBA 1A | 1E|0AAB 0B|0E|1BBE 0E1|1E0| e其中是正规的
5、。4.6 试从文法 S (L) | aL L,S | S中消除左递归。并为之构造一个预测分析器。请说明句子(a,(a,a)上的分析器的动作解：将所给文法消除左递归得G:S (L) | aL SLL ,SL | 实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下 面构造预测分析表：根据文法G 有FIRST(s) = ( , a )FOLLOW(S) = ,: FIRST(L) = ( , a )FOLLOW(S) = 非终结符号输入符号丄)JaSS ( L )S aLL SLL SLLL L ,SLFIRST(L ) = ： ：FOLLOW(L ) = 按以上结果
6、，构造预测分析表M如下:文法G是LL(1)的，因为它的分析表不含多重定义入口预测分析器对输入符号串(a, (a, a)做岀的分析动作如下:栈输入输岀$S(a, (a, a)$)L(a, (a, a)$S (L)$)La, (a, a)$)L )a, (a, a)$LSL $)L )a, (a, a)$S a$)L ,(a, a)$)L ),(a, a)$L,SL$)L )(a, a)$)L )L(a, a)$S (L)$)L )La, a)$)L )L )a, a)$LSL $)L )L )a, a)$S a$)L )L ,a)$)L )L S,a)$L,SL:$)L )L )a)$)L )L
7、 )a)$S a$)L )L )$)L )$L，:$)L )$)$L$(a)计算下面文法GS的 nullable, FIRST 和 Follow 集。S uBDzB Br | wD EFEy | Fx | (b) 构造这个文法的LL(1)分析表(c) 给岀这个文法不是LL(1)的证据;(d) 尽可能少地修改此文法，使其成为能产生相同语言的LL(1)文法.解：(a) nullable = D, E, FFIRST(S) = u FIRST(B) = w FOLLOW(S) = FOLLOW(B) = r, x, y FIRST(D) = x, y, e FOLLOW(D) = z FIRST(E) = y, eFOLLOW(E) = x, z FIRST(F) = x, e FOLLOW(F) = z (b)该文法的LL(1)分析表为：非终结符uZrwxy$SS uBDzBB BrB wDD EFD EFD EFD EFEE eE yE eFF eF xF e(c)因为MB, w有两个产生式 B Bv, B w 且 FIRST(Bv)=FIRST(w) = w 所以不是LL(1)的。(d) 消除左递归即可S uBDzB wB B rB | eD EF