资源描述：
《编译原理第五章 作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理习题解答页7/7第五章自顶向下语法分析方法1．对文法G[S]Sàa
2、∧
3、(T)TàT,S
4、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))à
5、(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
6、∧
7、(T)TàSUUà，SU
8、ε分析子程序的构造方法对满足条件的文法按如
9、下方法构造相应的语法分析子程序。(1)对于每个非终结号U，编写一个相应的子程序P(U)；(2)对于规则U::=x1
10、x2
11、..
12、xn,有一个关于U的子程序P(U),P(U)按如下方法构造：IFCHINFIRST(x1)THENP(x1)ELSEIFCHINFIRST(x2)THENP(x2)ELSE......IFCHINFIRST(xn)THENP(xn)ELSEERROR其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序；P(xj)为相应的子程序。(3)对于符号串x
13、=y1y2...yn;p(x)的含义为：BEGINP(y1);P(y2);...P(yn);END如果yi是非终结符，则P(yi)代表调用处理yi的子程序；如果yi是终结符，则P(yi)为形如下述语句的一段子程序IFCH=yiTHENREAD(CH)ELSEERROR即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中，否则表明出错。(4)如果文法中有空规则U::=EPSILON,则算法中的语句IFCHINFIRST(xn)THENP(xn)编译原理习题解答页7/7ELSEERR
14、OR改写为：IFCHINFIRST(xn)THENP(xn)ELSEIFCHINFOLLOW(U)THENRETURNERROR(5)要分析一个OrgStr,应在该串的后面加上一个串括号'#',并从子程序P(S)(S为文法的开始符号)开始，如果中途没有产生错误，并且最后CH='#',则说明OrgStr串合法，否则该串不合法。对每个非终结符写出不带回溯的递归子程序如下：charCH;//存放当前的输入符号voidP_S()//非终结符S的子程序{if(CH==’a’)READ(CH);//产生式Sàa
15、elseif(CH==’^’)READ(CH);//产生式Sà^elseif(CH==’(’)//产生式Sà(T){READ(CH);P_T();IF(CH==’)’)THENREAD(CH)elseERROR}elseERR;}voidP_T()//非终结符S的子程序{if(IsIn(CH,FIRST_SU))//FIRST_SU为TàSU的右部的FIRST集合{P_S();P_U();}}voidP_U()//非终结符U的子程序{if(CH==’,’)//产生式Uà，SU{READ(CH);P_
16、S();P_U();}else//产生式Uàε{if(IsIn(CH,FOLLOW_U))//FOLLOW_U为U的FOLLOW集合return;elseERR;}}(3)判断文法G/[S]是否为LL(1)文法。各非终结符的FIRST集合如下：FIRST(S)={a,∧,（}FIRST(T)=FIRST(S)={a,∧,（}FIRST(U)={，,ε}各非终结符的FOLLOW集合如下：FOLLOW(S)={#}∪FIRST(U)∪FOLLOW(T)∪FOLLOW(U)={#,，,)}FOLLOW(T
17、)={)}FOLLOW(U)=FOLLOW(T)={)}每个产生式的SELECT集合如下：编译原理习题解答页7/7SELECT(Sàa)={a}SELECT(Sà∧)={∧}SELECT(Sà(T))={(}SELECT(TàSU)=FIRST(S)={a,∧,（}SELECT(Uà，SU)={，}SELECT(Uàε)=FOLLOW(U)={)}可见，相同左部产生式的SELECT集的交集均为空，所以文法G/[S]是LL(1)文法。文法G/[S]的预测分析表如下：a∧
