编译原理陈火旺版第四章课后题答案 |
您所在的位置:网站首页 › 计算机组成原理第六版课后答案第四章第二节 › 编译原理陈火旺版第四章课后题答案 |
下面答案仅供参考!
目前修改了第三题的部分问题。 1.考虑下面文法G1: S→a∣∧∣(T) T→T,S∣S (1) 消去 Q 的左递归。然后,对每个非终结符,写岀不带回溯的递归子程序。 (2) 经改写后的文法是否是LL(1)的?给出它的预测分析表。 2.对下面的文法G: P→(E)lalblΛ (1)计算这个文法的每个非终结符的FIRST和FOLIOW.
(3)构造它的预测分析表。 (4)构造它的递归下降分析程序。 3.下面文法中,哪些是LL(1)的,说明理由。 (1)S→Abc A→a∣ε B→b∣ε 这里是不是写错了,应该是S→ABc?,下图答案是以S→ABc为准。 看了一下网上流传的答案,基本上都是first(S)={a,b,c}和下图结果一样,如果是S->Abc的话,那么first(S)={a,b}。 下图答案是以S→Abc为准 (2)S→Ab A→a∣B∣ε B→b∣ε (3)S→ABBA A→a∣ε B→b∣ε (4)S→aSe∣B B→bBe∣C C→cCe∣d 4. 对下面文法: Expr→-Expr Expr→(Expr)∣Var ExprTail→-Expr∣ε Var→id VarTail VarTail→(Expr)∣ε (1) 构造 LL(1)分析表。 (2) 给出对句子 id - -id((id))的分析过程。 构造文法的预测分析表,通常应当按下列步骤进行: (1) 消除文法的左递归(包括所有直接左递归和间接左递归); (2) 对消除左递归后的文法,提取左公因子; (3) 对经过上述改造后的文法,计算它的每个非终结符的 FIRST 集合和 FOLLOW 集合 ⑷ 根据 FIRST 集合和 FOLLOW 集合构造预测分析表: 第1步对文法G的每个产生式A→α执行第1步和第3步; 第2步对每个终结符a∈FIRST(α),把A→α加至M[A,a]中; 第3步若ε∈FIRST(α),则对任何b∈FOLLOW(A)把A→α加至M[A,b]中; 第4步把所有无定义的M[A,a]标上“出错标志”。 解答: (1)计算每个非终结符的FIRST集合和FOLLOW集合如下: FIRST(Expr)={-,(,id} FIRST(ExprTail)={-,ε} FIRST(Var)={id} FIRST(VarTail)={(,ε} FOLLOW(Expr)={),#} FOLLOW(ExprTail)={),#} FOLLOW(Var)={-,),#} FOLLOW(VarTail)={-,∣,#} 构造其预测分析表如下: -id()#ExprExpr→- ExprExpr→Var ExprTailExpr→-( Expr)ExprTailExprTail→-ExprExprTail→εExprTail→εVarVar→id VarTailVarTailVarTail→εVarTail→(Expr)VarTail→εVarTail→ε(2)句子id--id((id))的分析过程如下: 步骤 符号栈 输入串 所用产生式 0 # Expr id--id((id)) # 1 # ExprTail Var id--id((id)) # Expr→Var ExprTail 2 # ExprTail VarTail id id--id((id)) # Var→id VarTail 3 # ExprTail VarTail --id((id)) # 4 # ExprTail --id((id)) # VarTail→ε 5 # Expr - --id((id)) # ExprTail→-Expr 6 # Expr -id((id)) # 7 # Expr - -id((id)) # Expr→-Expr 8 # Expr id((id)) # 9 # ExprTail Var id((id)) # Expr→Var ExprTail 10 # ExprTail VarTail id id((id)) # Var→id VarTail 11 # ExprTail VarTail ((id)) # 12 # ExprTail ) Expr ( ((id)) # VarTail→(Expr) 13 # ExprTail ) Expr (id)) # 14 # ExprTail ) ) Expr ( (id)) # 15 # ExprTail ) ) Expr id)) # 16 # ExprTail ) ) ExprTal Var id)) # Expr→Var ExprTail 17 # ExprTail ) ) ExprTail VarTail id id)) # Var→id VarTail 18 # ExprTail ) ) ExprTail VarTail )) # 19 # ExprTail ) ) ExprTail )) # VarTail→ε 20 # ExprTail ) ) )) # ExprTail→ε 21 # ExprTail ) ) # 22 # ExprTail # 23 # # ExprTail→ε suc 5. 把下面文法改写为 LL(1)的: Declist→Declist;Decl∣Decl Decl→IdList:Type IdList→IdList,id∣id Type→ScalarType∣array(ScalarTypeList) of Type ScalarType→id∣Bound..Bound Bound→Sign IntLiteral∣id Sign→+∣-∣ε ScalarTypeList→ScalarTypeList,ScalarType∣ScalarType 答:本题目主要考査学生理解和运用消除文法的左递归、提取左公共因子等算法的能力, 为判断文法是否是 LL(1)文法,还要计算文法的 FIRST 集合和 FOLLOW 集合。 消除文法的左递归的基本思想是,将文法规则中的左递归结构变换成等价的右递归结构。 提取左公因子的算法,是对包含公共左因子的产生式候选,反复提取左因子,就能够 把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。 消除文法的左递归、提取左公共因子后,再计算文法的各非终结符00的首符集 FIRST( X)和随符集 FOLLOW( X),然后根据 LL(1)文法的充分必要条件(即 LL(1)文法 的定义)来判断文法是否是 LL(1)文法。 首先消除左递归,得到文法G(Declist): Declist→Decl Declist’ Declist’→;Decl Declist’∣ε Decl→IdList:Type IdList→id IdList’ IdList’→,id List’∣ε Type→ScalarType∣array(ScalarTypeList) of Type ScalarType→id∣Bound..Bound Bound→Sign IntLiteral∣id Sign→+∣-∣ε ScalarTypeList→ScalarType ScalarTypeList’ ScalarTypeList’→,ScalarType ScalarTypeList’∣ε 显然,改造后的文法没有左公共因子,计算每个非终结符的FIRST集合和FOLLOW集合如下: FIRST(Declist)={id} FIRST(Declist’)={;,ε} FIRST(Decl)={id} FIRST(IdList)={id} FIRST(IdList’)={;,ε} FIRST(Type)={id,+,-,IntLiteral,array} FIRST(ScalarType)={id,+,-,IntLiteral} FIRST(Bound)={id,+,-,InLiteral} FIRST(Sign)={+,-,ε} FIRST(ScalarTypeList)={id,+,-,IntLiteral } FIRST(ScalarTypeList’)={,,ε} FOLLOW(Declist)={#} FOLLOW(Declist’)={#} FOLLOW(Decl)={id,;} FOLLOW(IdList)={:} FOLLOW(IdList’)={:} FOLLOW(Type)={id,;} FOLLOW(ScalarType)={id,;,),,} FOLLOW(Bound)={id,;,)’,’..} FOLLOW(Sign)={IntLiteral} FOLLOW(ScalarTypeList)={)} FOLLOW(ScalarTypeList’)={)} 显然,改造后的文法是 LL(1)的。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |