下载文档原格式
《编译原理》课后习题答案第5章《编译原理》课后习题答案第5章.pdf《编译原理》课后习题答案第5章.pdf第5章自顶向下语法分析方法第1题对文法G[S] S→a|∧|(T) T→T,S|S(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。
(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。
(3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。
(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。
答案：(1) 对(a,(a,a)的最左推导为：S(T) (T,S) (S,S) (a,S) (a,(T)) (a,(T,S)) (a,(S,S)) (a,(a,S)) (a,(a,a))对(((a,a),∧,(a)),a) 的最左推导为：S(T) (T,S) (S,S) ((T),S) ((T,S),S) ((T,S,S),S) ((S,S,S),S) (((T),S,S),S) (((T,S),S,S),S) (((S,S),S,S),S) (((a,S),S,S),S) (((a,a),S,S),S) (((a,a),∧,S),S) (((a,a),∧,(T)),S)(((a,a),∧,(S)),S)《编译原理》课后习题答案第5章.pdf《编译原理》课后习题答案第5章.pdf(((a,a),∧,(a)),S) (((a,a),∧,(a)),a)(2) 改写文法为：0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε非终结符FIRST集FOLLOW集S {a,∧,(} {#,,,)} T {a,∧,(} {)} N {,,ε} {)}对左部为N的产生式可知：FIRST （→, S N）={，} FIRST （→ε）={ε} FOLLOW （N）={)}由于SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是LL(1)的。
第五章自顶向下语法分析方法1．对文法G[S]S→a|∧|(T)T→T,S|S(1)给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。
(2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。
(3)经改写后的文法是否是LL(1)的？给出它的预测分析表。
(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。
解：(1) (a,(a,a))的最左推导为S→(T)→(T,S)→(S,S)→(a,(T))→(a,(T,S))→(a,(S,a))→(a,(a,a))(((a,a),∧,(a)),a)的最左推导为S→(T)→(T,S)→(S,a)→((T),a)→((T,S),a)→((T,S,S),a)→((S,∧,(T)),a)→(((T),∧,(S)),a) →(((T,S),∧,(a)),a)→(((S,a),∧,(a)),a)→(((a,a),∧,(a)),a)(2)由于有T→T,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/[S]:S→a|∧|(T)T→SUU→，SU|ε分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序。
(1) 对于每个非终结号U，编写一个相应的子程序P(U)；(2) 对于规则U::=x1|x2|..|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：IF CH IN FIRST(x1) THEN P(x1)ELSE IF CH IN FIRST(x2) THEN P(x2)ELSE ......IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序；P(xj)为相应的子程序。
(3) 对于符号串x=y1y2...yn;p(x)的含义为：BEGINP(y1);P(y2);...P(yn);END如果yi是非终结符，则P(yi)代表调用处理yi的子程序；如果yi是终结符，则P(yi)为形如下述语句的一段子程序IF CH=yi THEN READ(CH) ELSE ERROR即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中，否则表明出错。
习题第5章自顶向下语法分析方法一课本练习部分（第99-101页）5.15.45.6（2）（3）（4）5.7（1）（3）（5）参考答案：5.1（1）S =>（T）=>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) => (a,(a,S)) => (a,(a,a))S => (T) => (T,S) => (S,S) => ((T),S) => ((T,S),S) => ((T,S,S),S) =>((S,S,S),S) => (((T),S,S),S) => (((T,S),S,S),S)=> (((S,S),S,S),S) => (((a,S),S,S),S) => (((a,a),S,S),S)=>(((a,a), ∧,S),S) =>(((a,a), ∧,(T)),S) =>(((a,a), ∧,(S)),S) => (((a,a), ∧,(a)),S) => (((a,a), ∧,(a)),a)（2）改写文法如下：S→a|∧|(T)T→ST’T’→,ST’|ε递归子程序为：S() {if(SYM==’a’)P(a);else if(SYM==’∧’)P(∧);else if(SYM==’( ’) {GetSym();P(T);match(’) ’）；｝else Error();}T() {P(S)；P(T’)；}T’() {if(SYM==",") {match(",");？？？P(S);P(T');}else if(SYM==(")")return;else error();}(3)FIRST(S)={a∧(} FOLLOW(S)={#,)}FIRST(T)={a∧(} FOLLOW(T)={)}FIRST(T')={,} FOLLOW(T')={)}SELECT(S→a)={a}SELECT(S→∧)={∧}SELECT(S→(T))={(}SELECT(T→ST')={ a∧(}SELECT(T'→,ST')={,}SELECT(T'→ε}={)}由于相同左部的SELECT集的交集为空，所以所改写的文法是LL(1)的。
写出该文法的预测分析表：或者4.证明：FT(S)={a,b};FT(C)={a,b};FT(A)={a,b};FT(B)={a,b};FW(S)={#};FW(C)={$,a,b};FW(A)={$,a,b};FW(B)={$,a,b};ST(C->Ba)={b};ST(C->aB)={a};ST(A->a)={a};ST(A->aC)={a};ST(A->Abb)={b};ST(B->b)={b};ST(B->bC)={b};ST(B->aBB)={a};由于：ST(A->a)={a}∩ST(A->aC)={a}≠￠ST(B->b)={b}∩ST(B->bC)={b}≠￠所以为非LL(1) 文法。
若通过提取公共左因子来改写文法为：S->C$C->bA|aBA->aD|bAAB->bD|aBBD->C|ε由于左部为D的规则式的选择集相交：ST(D->C)={a,b};ST(D->ε)={a,b,$};故也不是LL(1)文法。
5.6（2）B有相同左因子，所以该文法不是LL(1)的。
先将A的规则代入S的规则： S→BaB|B提左因子B，得 S→B(aB|ε)引入非终结符E及其规则得： S→BEE→aB|ε再将D的规则代入B的规则： B→db|b|d|ε提左因子d得： B→d(b|ε)|b|ε引入非终结符F及其规则得： B→dF|b|εF→b|ε故文法变换为： S→BEB→dF|b|εE→aB|εF→b|ε由于 SELECT(B→ε)={a,#}SELECT(E→ε)={#}SELECT(F→ε)={a,#}故B，E和F的各自规则两两不相交，变换后的文法是LL(1)文法。
递归下降子程序此略。
注意：若直接提取左因子D： B→D(b|ε)并改写为 B→DHH→b|ε则文法改写为：S→ABA→Ba|εB→DEE→b|εD→d|ε但因为SELECT(A→Ba)⋂ SELECT(A→ε)≠￠故此，仅直接提取左因子，文法仍不是LL(1)的。
（3）SELECT集为：ST(S->aAaB)={a}ST(S->bAbB)={b}ST(A->S)=first(S)={a b}ST(A->db)={d}ST(B->bB)={b}ST(B->a)={a}因相同左部产生式的SELECT集不相交，所以为LL（1）文法。
递归下降子程序为：S(){if(SYM==a){GetSym();P(A);match(a);P(B);}else if(SYM==b){GetSym();P(A);match(b);P(b);} }A(){if(SYM==d){GetSym();match(b);}else P(S);}B(){if(SYM==b){GetSym();P(B);}else if(SYM==a) GetSym();}（4）因为文法具有左递归，所以不是LL(1)的。
改写该文法：S→i|(E)E→SE'E'→+SE'|-SE'|ε计算SELECT集:SELECT(S→i)={i}SELECT(S→(E))={(}SELECT(E→SE')={i(}SELECT(E'→+SE')={+}SELECT(E'→-SE')={-}SELECT(E'→ε)={)}由此可以看出此文法是LL(1)的。
构造相应的递归下降识别器：P(S) {if(SYM==i)match(i);else if(SYM=="(") {match("(");P(E);match(")");}}P(E) {P(S);P(E');}P(E') {if(SYM=="+") {match(+);P(S);P(E');} else if(SYM=="-") {match(-);P(S);P(E');}else if(SYM==")")returnelse error();}7．消除了左递归，提取了左公因子并不一定是LL(1)的。
（1）改写文法得：A→baB|εB→baBbb|bb|a消除公共左因子得:A→baB|εB→bB'|aB'→aBbb|b求其First集和Follow集：计算SELECT(A→baB)={b}SELECT(A→ε}={#}SELECT(B→bB'}={b}SELECT(B→a}={a}SELECT(B'→aBbb}={a}SELECT(B'→b}={b}由此可见所改写的文法是LL(1)的。
(3)改写文法得：S→Aa|bA→babA'A'->aabA'|ε求以上状态的First集和Follow集：SELECT(S→Aa)={b}SELECT(S→b)={b}由此可见，此文法不是LL(1)的。
（5)可以看出A有公共左因子。
消去得：S→Ab|aaA→aA'A'→A|ε此时，已经消除了左递归，并且没有了公共左因子。
但是 SELECT(S→Ab)={a}SELECT(S→aa)={a}显然文法不是LL(1)的。
二补充部分B5.1 设有文法G：A→(A)A|ε（1）求非终结符A的FIRST集和FOLLOW集；（2）说明G是LL(1)文法；（3）写出相应的递归下降子程序。
B5.1（1）FIRST(A)={ ( } FOLLOW(A)={ #，) }（2）因为 SELECT(A→(A)A)={ ( }SELECT(A→ε)={ #，) }规则的SELECT集互不相交，故文法是LL(1)文法。
（3）文法A→(A)A|ε的递归下降子程序：A() {if(SYM==‘(‘) { GetSym(); A(); match(‘)’); A(); }else if(SYM!=’#’ && SYM!=’)’) ERROR();？？？？？}B5.2 对于简化的C声明文法G：declaration→type var-listtype→ int | floatvar-list→identifier , var-list | identifier其中，非终结符（斜体）集为{declaration，type ，var-list ，identifier（其规则省略） }，终结符集为{ int， float，,（逗号） }（1）提取规则的公共左因子；（2）为所得文法的非终结符求FIRST集和FOLLOW集；（3）说明所得文法是LL(1)文法；（4）为所得文法构造预测分析表（LL(1)分析矩阵）；（5）写出输入串 int x,y,z的分析过程。
B5.2对于文法declaration→type var-listtype→ int | floatvar-list→identifier , var-list | identifier（1）提取公共左因子：var-list→identifier（, var-list | ε）（2）FIRST(declaration) = {int, float}FIRST(type) = {int, float}FIRST(var-list) = { identifier }FOLLOW(declaration) = { # }FOLLOW(type) = FIRST(var-list) = { identifier }FOLLOW(var-list) = FOLLOW(declaration) = { # }（3）只有type不止一个候选式：int | float，且Select集不相交，故文法是LL(1)的。
（4）文法简记为：D → TVT → i | f （i和f分别为int和float的简记符）V → IX （I为identifier的简记符）X → ,V | ε（5B5.3 对于文法G：A→aAa|ε（1）说明该文法不是LL(1)文法；（2）假设某人构造A的递归子程序为void A（）{if（SYM == a）{GetSym（）；A();if (SYM == a) GetSym（）；else ERRPR();}else if (SYM != #) ERROR;}说明该子程序不能正确运行。
