下载文档原格式
《编译原理》课后习题答案第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中，否则表明出错。
第五章自顶向下语法分析方法课前索引【课前思考】为了了解自顶向下<自上而下）分析的一般过程和问题，请学员首先回顾在"文法和语言"一章中介绍的有关基本概念：◇句子、句型和语言的定义是什么？◇什么叫最左推导？◇什么叫最右推导和规范推导？◇什么叫确定的自顶向下语法分析？◇自顶向下语法分析是从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。
◇确定的自顶向下语法分析中用的是哪种推导？◇在确定的自顶向下语法分析过程中，当以同一个非终结符为左部的产生式有多个不同右部时，如何选择用哪个产生式的右部替换当前的非终结符？◇确定的自顶向下语法分析对文法有何限制？【学习目标】确定的自顶向下分析方法虽对文法有一定的限制，但因为实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。
要求学员通过本章的学习后达到以下要求：◇能够对一个给定的文法判断是否是LL(1>文法；◇能构造预测分析表；◇能用预测分析方法判断给定的输入符号串是否是该文法的句子；◇能对某些非LL(1>文法做等价变换：①消除左递归②提取左公共因子可能会变成LL(1>文法。
这样可扩大自顶向下分析方法的应用。
【学习指南】确定的自顶向下分析因为实现方法简单、直观、便于手工构造，因此，仍是目前常用的语法分析方法之一，尤其对小型编译器的实现较为适合。
对初学编译技术的学员也较容易入门。
确定的自顶向下分析要求文法是LL(1>的，所以，能否用确定的自顶向下分析方法构造语法分析器，首先必须对所给文法进行判断。
由此构造LL(1> 分析器的关键问题是对文法的LL(1>判别。
而判断LL(1>文法时用到文法符号串的开始符号集合<FIRST集）和非终结符的后跟符号集合<FOLLOW集）的计算。
本章的学习要求学员对给定的文法能熟练、准确地计算出产生式右部符号串的开始符号集合和每个非终结符的后跟符号集合，只有这两个集合的元素计算准确无误，才能对LL(1>文法的判断得出正确结论，从而正确构造LL(1>分析表。
第五章⾃顶向下语法分析⽅法第五章⾃顶向下语法分析⽅法教学要求１．掌握：计算FIRST集、FOLLOW集、SELECT集，LL（1）⽂法的概念２．理解：不确定/确定的⾃顶向下分析法３．了解：该分析⽅法的基本思想5.1 确定的⾃顶向下分析思想确定的⾃顶向下分析⽅法，⾸先要解决从⽂法的开始符号出发，如何根据当前的输⼊符号唯⼀地确定选⽤哪个产⽣式替换相应⾮终结符往下推导，或构造⼀颗相应的语法树。
1:⾸符号集:设G=(VN,VT,P，S)是上下⽂⽆关⽂法 :FIRST（α）={a|α=>aβ,a∈VT, α, β∈V*} 若α=>ε则规定ε∈FRIST（α）2:后继符号集:FOLLOW（A）={a |S =>µAβ且 a∈FRIST（β），µ∈V*，β∈V+ }若S =>µAβ ,且β=>ε，则#∈FOLLOW(A)3:选择集合SELECT：给定上下⽂⽆关⽂法的产⽣式A→αA ∈VN, α∈V* ，若α≠>ε，则：SELECT(A→α)=FIRST（α）如果α=>ε，则：SELECT(A→α)=FIRST（α）-{ε}∪FOLLOW（A）4:LL（1）⽂法：⼀个上下⽂⽆关⽂法是LL（1）⽂法的充分必要条件是，对每个⾮终结符A的两个不同产⽣式，A→α或A→β满⾜SELECT(A→α)∩SELECT(A→β)= φ其中，α、β不能同时=>ε注意:第⼀个L表明⾃顶向下分析是从左到右扫描输⼊串，第⼆个L表明分析过程中将⽤最左推导，1表明只需向右看⼀个字符便可决定如何推导即选择哪个产⽣式。
5.2 LL（1）⽂法的判别判别⽂法是否是LL（1）⽂法，对任何⽂法计算需计算FIRST、FOLLOW和SELECT集合，进⽽判别⽂法是否为LL（1）⽂法。
举例说明判断LL（1）⽂法的步骤。
1.计算FIRST集1）.若X∈V T,则FIRST(X)={X}2）.若X∈VN,且有产⽣式X→a…，a是终结符，则把a加⼊到FIRST(X)中;若X→ε也是⼀条产⽣式,则把ε也加到FIRST(X)中. 3）.若X→Y…是⼀个产⽣式且Y∈VN,则把FIRST(Y)中的所有⾮ε元素都加到FIRST(X)中;若X →Y1Y2…YK 是⼀个产⽣式,Y1,Y2,…,Y(i-1)都是⾮终结符,⽽且,对于任何j,1≤j ≤i-1, FIRST(Yj)都含有ε (即Y1..Y(i-1) =>* ε ),则把FIRST(Yj)中的所有⾮ε元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,…,K)均含有ε,则把ε加到FRIST(X)中.4）反复使⽤1)~3)直到每个符号的FIRST集不再增⼤为⽌FIRST集的求法有两种：⼀是根据定义，⼆是⽤关系图求得。
习题第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;}说明该子程序不能正确运行。
