《编译原理 | 您所在的位置:网站首页 › 编译原理第二版第四章答案 › 《编译原理 |
4.2 上下文无关文法
**4.2.7节中L={a^nb^n|n>=1}怎么用文法表示?
S -> aAb
A -> ab|
ε
4.2.1 1) E -> EE* -> EE+E* -> aa+a* 左到右依次a 2) 与1)一样,只是最后一步右到左依次a 3) E E E * E E + id id id 4)无二义性,但是怎么证明呢? 5)+*组成的后缀表达式 4.2.3 如果是正则表达式,可以采用4.2.7的方法转成文法 1) (0*1+)* 根据DNF推出: S -> 0A S -> 1S S -> ε A -> 1S 2) S -> ABA A -> BB B -> 0|1|ε 4.2.4 对于A->X[Y]Z,可以表示为 A->XBZ B->Y|ε 对于A->X{YZ},可以表示为 A->XB B->CC C->YZ|ε 4.2.5 stmt -> if expr then stmt [ else stmt ] | begin stmt{; stmt} end 4.2.6 基本的正则表达式还剩*,表示为A->Z*,可以改写为: A->BB B->Z|ε 4.2.7 1) 建立一个集合表示所有非“无用符号”集合T,开始置为所有终结符号 集合A表示所有推导式,默认不打标记 for(所有没有打标记的A中推导式) { if( 如果右边只有T中符号集合) { 将这个表达式打标记 表达式左边符号加入集合T } if(一个循环结束没有新的表达式被打标记) 循环退出 } 将开始符号加入T 2)非“无用符号”集合T会依次加入{0, B, S},所以A是无用符号 4.2.8 读懂这道题费了好大劲,不知到是因为最后一道题了还是比较晚了(2012-12-20 22:49,离世界末日不远了) 1)前2行不变,后面改为: option -> A1|A2|...|An A1 -> a1|b1 ... An -> an|bn 2)又花了一段时间读懂了这个题目,生成的串固定长度n,不考虑Aa1|Aa2...|Aan 其中a1有n种选择(A1-An),a2有剩下的n-1种.....an为剩下的一种。 这些产生式一共包括n!个长度为n的产生式,即O(n!*n)
如果有一个O(n*2^n)的产生式序列,那么可能是n个长度为2^n的产生式,具体构造方法没想出来 4.3 设计文法 4.3.1 1)没有左公因子 2)有左递归,不能自顶向下语法分析 3) rexpr -> rterm | E1 E1 -> +rterm | ε rterm -> rfactor | F1 F1 -> rfactor | ε rfactor -> rprimary | P1 P1 -> * | ε rprimary -> a|b 4)目前没有左递归、左公因子,可以自顶向下语法分析 4.3.3 考虑 if E1 then if E2 else if E3 then MATCHED1 else MATCHED2 if E3 then MATCHED1 else MATCHED2不能确定跟前面两个if中的哪个匹配 4.4 自顶向下的语法分析 4.4.1 1)S -> 0S1 | 01 S -> 0T T -> S1|1 FIRST(S) = {0} FIRST(T) = {0,1} FOLLOW(S) = {1,$} FOLLOW(T) = {1,$} 01$SS->0T TT->S1T->1 4.4.2 S -> SS+ | SS* | a 提取左公因子 S -> SST|a T -> +|* 消除左递归S -> aX X -> STX |ε T -> +|* FIRST(S) = {a} FIRST(X) = {a} FOLLOW(S) = {+,*,$} FOLLOW(X) = {+,*,$} 提取左公因子 a+*$SaX XSTXεεεT +*4.4.5 感觉可以识别aaaaaa,为啥不行呢? aaaaaa aSa aaaaa Sa aaaaa aSaa 如果可以向前看4个输入符号,则可以识别aaaaa,否则,会继续采用S -> aSa aaaa Saa aSaaa aaa aSaaaa aa Saaaa aSaaaaa a Saaaaa 需要回溯,回溯到一定程度就可以识别 4.4.6 1)如果产生式左边只能生成ε,则将其在文法中所有出现的地方删除即可 否则,就是类似T -> X | ε,这种情况下,将T在其他推导中出现的地方用这两个替换 这样有可能粗先左递归或左公因子。 2) S -> aSbS => S -> aaSbSbaSbS | abSaSbbSaS | aSbS S -> bSaS => S -> baSbSaaSbS | bbSaSabSaS | bSaS S -> ε 综合得到S -> aaSbSbaSbS | abSaSbbSaS | aSbS | baSbSaaSbS | bbSaSabSaS | bSaS 4.4.7 1)如果有A=》B,则将B进行替换,替换为B可推导得到的表达式 2)E -> E+T | T T -> T*F | F F->(E) | id 进行替换如下: T -> T*F | (E) | id E -> E+T | T*F | (E) | id 3)一步推导得到的环可以直接删除,如果是多步,不失一般性,假设为2步,由于文法中不存在ε,所以必然存在这样的推导: A->B B->A,我们可以爱用上面方法将B去掉,并去掉一步环。 4.4.8 根据4.4.7不难得到,但是得到的结果有左递归 4.4.9 如果n*n的表能够构造成功直到j-i=n-1,说明串在这个语言中 4.5 自底向上的语法分析 4.5.1 S -> 0S1 | 011)000111 最右推导:S -> 0S1 -> 00S11 -> 000111 最中间的01 2)00S11 最右推导: S -> 0S1 ->00S11 中间的0S1 4.5.2 S -> SS+ |SS* | a 1)SS+A*+ SS+ 2)SS+a*a+ SS+ 3)aaa*a++ a 4.5.3 1) $ 000111$ $0001 11$ $00S 11$ $00S1 1$ $0S 1$ $0S1 $ $S $ 2) aaa*a++ Saa*a++ SSa*a++ SSS*a++ SSa++ SSS++ SS+ S 4.6 LR语法分析技术介绍:简单LR技术4.6.1 1) 0,0S,00S.... 2) 4.6.2 S -> SS+| SS* | a 采用图4-33中算法处理 (1) S`->S (2) S -> SS+ (3) S -> SS* (4) S -> a 01 0S2 0a3 1S4 3+5 3* S`->.S S->.SS+ S->.SS* S->.a S`->S. S->S.S+ S->S.S* S->.a 1$ = accept S->a.S->SS.+ S->SS.* S->SS+.S->SS*.采用算法4.46 FOLLOW(S) = {+, *,a $} FOLLOW(+)={+, *, a} FOLLOW(*)={+, *, a} FOLLOW(a)={+, *, a} a+*$S0s2 11s2 acc32r4r4r4 3 s4s5 4r2r2r2 5r3r3r3 没有发现哪个ACTION既有归约又有移入操作,应该是SLR文法 4.6.3 栈符号输入动作0 aa*a+$移入02aa*a+$归约S->a01Sa*a+$移入012Sa*a+$归约S->a013SS*a+$移入0135SS*a+$归约S->SS*01Sa+$移入012Sa+$归约S->a013SS+$移入0134SS+$归约S->SS+01S$接收
对于下面两题 LL(1)文法特点:需要满足4.4.3中的三个条件 SLR(1)文法特点:在输入某个表示串以后,有移入/规约冲突或规约/规约冲突 LL文法是LR文法的一个真子集,而不是SLR的 4.6.5 S`->S S -> AaAb | BbBa A ->ε B ->ε 构造LR(0)自动机 0 S`->.S S->.AaAb S->.BbBa A->.ε B->.ε 1 0S S`->S 没法继续构造下去 4.6.6 FIRST(SA)与FIRST(A)都包含{a}。所以不是LL(1)的 4.6.7 1) S -> Aibi n个 Ai -> ajAi n^2-n个 Ai -> aj n^2-n个 2)考虑其中某个i和j index项集 贡献数量 0S`->.S S->.Aibi Ai->.ajAi Ai->.aj 1S`->.S S->.A1b1 ... S->.Anbn A1->.a2A1... A1->.anA1... ... An->.a1An... An->.an-1An1 0->SS`->S.1S`->S.2 0->AiS->Ai.binn个S->Ai.bi3 0->ajAi->aj.Ai Ai->aj. Ai->.ajAi Ai->.aj n对于a1 A2->a1.A2... An->a1.An A2->.ajA2 A2->.aj ...an4 2->biS->Aibi.nn个S->Aibi.5 3->Ai, 6AiAi->ajAi.n*(n-1)对于a1 输入A2...An6 3->aj,6->ajAi->aj.Ai Ai->.ajAi Ai->.ajn*n对于a1 输入a1,a3...an A2->aj.A2 A2->aj.这样算下来是2n*n+2n+2 结果应该是2^n+n^2+n,看来我算错了,求高手指点 如果势2^n那说明状态数量太多了,手工构造太困难了,做4.6练习过程感觉中间太容易出错了(手动计算的情况) 4.6.8 4.6.9 index项集 0S'->.S S->.AS S->.b A->.SA A->.a 1 0->SS'->S. A->S.A A->.SA A->.a->$ accept2 0->AS->A.S S->.AS S->.b A->.SA A->.a 3 0->a 1->a 2->a 5->a 7->aA->a. 4 0->bS->b. 5 1->S 5->S 7->SA->S.A A->.SA A->.a 6 1->A 5->A 7->AA->SA. 7 2->SS->AS. A->S.A A->.SA A->.a 8 2->A 8->AS->A.S S->.AS S->.b 9 8->SA->AS. FIRST(A)、FIRST(S)、FOLLOW(A)、FOLLOW(S)都是{a,b},7可能有冲突,因为当前状态输入a的情况下,不能确定按S->AS.规约还是移入a。 4.7 更强大的LR语法分析器学习编译原理真是个痛并快乐的过程,网上说龙书翻译的还行,个人感觉也是如此,只是学习的时候如果希望从头读一遍就理解是不可能的,通常要看3-4次才能理解,而且每次阅读的时候都会有新的收获。 学习4.7.5的时候怎么都想不明白例4.64怎么得出的自发向前看符号,再回头看一遍4.7,并且手动构造下LR项集族,马上明白了。 学习这一节最重要的是理解4.7.2开头对于算法4.53的解释,明白了以后这一节基本也就没问题了 为理解4.7.5中算法执行过程,构造例4.6的规范LR项集族 index项集GOTO0S`->.S ,$ S->.L=R ,$ S->.R ,$ L->.*R ,= L->.id ,= R->L ,$ 1 2 3 4 5 6 7 8 8 4.7.1 FIRST(S) = {a} S'->S S->SS+ S->SS* S->a 构造LR项集族如下 index项集GOTO0S`->.S , $ S->.SS+ ,a S->.SS* ,a S->.a ,a 1 0->SS'->S. ,$ S->S.S+ ,a/+ S->S.S* ,a/* S->.a ,a/+/* 2 0->aS->a. ,a 3 1->SS->SS.+ ,a/+ S->SS.* ,a/* S->.A ,a/+/* 4 1->aS->a. ,a/+/* 5 3->+S->SS+. ,a/+ 6 3->*S->SS*. ,a/* LALR项集族只需要将上面2/4合并即可 4.7.3 算法4.6.3前后看了至少5遍,稍微有了些理解 INIT120S'->.S$$$1S'->S. S->S.S+ S->S.S*aaa2S->a.aaa3S->SS.+ S->SS.* a/+/*a/+/*4S->SS+. a/+5S->SS*. a/* 4.7.4/4.7.5 类似例4.58 index项集GOTO0S`->.S ,$ S->.L=R ,$ S->.R ,$ L->.*R ,= L->.id ,= R->L ,$ 1 2 3 4 5 6 7 8 8 |
CopyRight 2018-2019 实验室设备网 版权所有 |