编译原理第五章答案

编译原理-第5章-习题与答案2第五章习题5-1 设有文法G[S]：S→A/ A→aA∣AS∣/(1) 找出部分符号序偶间的简单优先关系。

(2) 验证G[S]不是简单优先文法。

5-2 对于算符文法G[S]：S→E E→E-T∣T T→T*F∣F F→-P∣P P→(E)∣i(1) 找出部分终结符号序偶间的算符优先关系。

(2) 验证G[S]不是算符优先文法。

5-3 设有文法G′[E]：E→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i）进行简单优先分析的过程。

题图5-3 文法G′[E]的简单优先矩阵5-4 设有文法G[E]：E→E+T|TT→T*F|FF→(E)|i其相应的算符优先矩阵如题图5-4所示。

试给出对符号串（i+i）进行算符优先分析的过程。

题图5-4 文法G[E]的算符优先矩阵5-5 对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(0)分析表，并判断哪些是LR(0)文法。

(1) S→aSb∣aSc∣ab(2) S→aSSb∣aSSS∣c(3) S→A A→Ab∣a5-6 下列文法是否是SLR(1)文法？若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。

(1) S→Sab∣bR R→S∣a(2) S→aSAB∣BA A→aA∣B B→b(3) S→aA∣bB A→cAd∣ε B→cBdd∣ε5-7 对如下的文法分别构造LR(0)及SLR(1)分析表，并比较两者的异同。

S→cAd∣b A→ASc∣a5-8 对于文法G[S]:S→A A→BA∣ε B→aB∣b(1) 构造LR(1)分析表；(2) 给出用LR(1)分析表对输入符号串abab的分析过程。

5-9 对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。

(1) S→A A→AB∣ε B→aB∣b(2) S→aSa∣a第5章习题答案25-1 解：(1) 由文法的产生式和如答案图5-1(a)所示的句型A／／a／的语法树，可得G中的部分优先关系如答案图5-1(b)所示。

第五章2．对下面的文法G：E→TE/E/→+E|εT→FT/T/→T|εF→PF/F/→*F/|εP→(E)|a|b|^(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。

(2)证明这个方法是LL(1)的。

(3)构造它的预测分析表。

(4)构造它的递归下降分析程序。

解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。

FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(E/)={+,ε}FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(T/)=FIRST(T)∪{ε}={(,a,b,^,ε};FIRST(F)=FIRST(P)={(,a,b,^};FIRST(F/)=FIRST(P)={*,ε};FIRST(P)={(,a,b,^};FOLLOW集合有：FOLLOW(E)={),#};FOLLOW(E/)=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};//不包含εFOLLOW(T/)=FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F/)=FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};FOLLOW(P)=FIRST(F/)∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε(2)证明这个方法是LL(1)的。

各产生式的SELECT集合有：SELECT(E→TE/)=FIRST(T)={(,a,b,^};SELECT(E/→+E)={+};SELECT(E/→ε)=FOLLOW(E/)={),#}SELECT(T→FT/)=FIRST(F)={(,a,b,^};SELECT(T/→T)=FIRST(T)={(,a,b,^};SELECT(T/→ε)=FOLLOW(T/)={+,),#};SELECT(F→PF/)=FIRST(P)={(,a,b,^};SELECT(F/→*F/)={*};SELECT(F/→ε)=FOLLOW(F/)={(,a,b,^,+,),#};SELECT(P→(E))={(}SELECT(P→a)={a}SELECT(P→b)={b}SELECT(P→^)={^}可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。

第一章1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？ 【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。

这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。

从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。

（在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。

这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。

在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。

因此，编译对源程序的处理是先翻译，后执行。

）1.3 请画出编译程序的总框图。

如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？ 【解答】编译程序总框图如图1-1所示。

作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。

总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。

第二章2.1 正规式M1和M2等价是指：M1和M2所识别的语言集相等。

2.2 什么是扫描器？扫描器的功能是什么？【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

第五章语法制导翻译及中间代码生成5.1说明属性文法与属性翻译文法有何异同?5.2考虑下面的属性文法：Z →sXattribution:Z.a=X.c;X.b=X.a；Z.p=X.b；Z →t Xattribution：X.b=X.d;Z.a=X.b;X →uattribution:X.d=1;X.c=X.d;X →Vattribuion:X.c=2;X.d=X.c;(1) 上述文法中的属性哪些是继承的?哪些是综合的?(2) 上述文法中的属性依赖是否出现了循环?5.3为什么说S属性文法一定是L属性文法?反之结论亦正确吗?5.4将下列中缀式改写为逆波兰式。

(1) -A*(B+C)↑(D-E)(2) ((a*d+c)/d+e)*f+g(3) a+x≤4∨(C∧d*3)(4) a∨b∧c+d*e↑f(5) s=0; i=1;while (i＜=100) {s+=i*i; i++;}5.5将下列后缀式改写为中缀式。

(1) abc*+(2) abc-*cd+e/-(3) abc+≤a0＞∧ab+0≠a0∧∨(4) ab＜p1 BZ xab-c↑= p2 BR gh=↑↑p1p25.6设已给文法G［E］：E →E+T | -T | TT →T*F | FF →P ↑F | PP →(E) | i试设计一个递归下降分析器，要求此分析器在语法分析过程中，将所分析的符号串翻译成后缀式。

5.7设已给布尔表达式文法G［Z］：Z →EE →T{∨T}T →F{∧F}F → F | (E) | b试设计一个递归下降分析器，它把由G［Z］所描述的布尔表达式翻译为四元式序列。

5.8(1) 利用54节所给的属性翻译文法将赋值语句：X=A*(B+C)+D翻译成四元式序列，给出语法制导的翻译过程。

(2) 利用55节所给的属性翻译文法将布尔表达式：A∧(B∨(C∨D F))翻译成四元式序列，给出语法制导的翻译过程。

(3) 利用56节所给的属性翻译文法将语句：while A＜C∧B＞0 doif A=1 then C∶=C+1else while A＜=D do A∶=A+2翻译成四元式序列，给出语法制导的翻译过程。

《编译原理》习题参考答案（六）第五章5.4 为下列类型写类型表达式：(a) 指向实数的指针数组，数组的下标从1到100。

(b) 两位数组（即数组的数组），他的行下标从1到10，列下标从1到20。

(c) 函数，他的定义域是从整数到整数的指针的函数，它的值域是从一个整数和一个字符组成的纪录。

Solution:(a) array ( 1 . . 100 , pointer ( real ) )(b) array ( 1 . . 10 , array ( 1 . . 20 , type ) )(c) ( integer →pointer(integer) )→record((i : integer) * ( c : char )) 假定作为值域的记录类型的两个域分别叫i和c。

5.6 下列文法定以字面常量表的表。

符号的解释和图5.2文法的那些相同，增加了类型list，它表示类型T的元素表。

→ D ; EP→ D ; D | id : TD→ list of T | char | integerTE→ ( L ) | literal | num | id→ E , L | EL写一个类似5.3节中的翻译方案，以确定表达式( E )和表( L )的类型。

P→ D ; ED→ D ; DD→ id : T { addtype ( id.entry , T.type ) }T→ char { T.type := char }T→ integer { T.type := integer }T→ list of T1 { T.type := list ( T1.type ) }E→ literal { E.type := char }E→ num { E.type := integer }E→ id { E.type := lookup ( id.entry ) }E→ ( L ) { E.type := list ( L.type ) }L→E{L.type:=E.type}L→ E , L1 { L.type := if L1.type = E.type then E.typeelse type_error }5.16 对下面的每对表达式，找出最一般的合一代换：(a) α1 → ( α2 →α1 )(b) array ( β1 ) → ( pointer( β1 ) →β2 )(c) γ1 →γ2(d) δ1 →(δ1 →δ2 )Solution:S(α1) = array ( β1 ) S(α2) = pointer ( β1 ) S(β2) = array ( β1 ) (a)(c):S(γ1) = α1 S(γ2) = α2 → α1 (a)(d):S(α1) = S(α2) = S(δ1) = S(δ2) = α (b)(c):S(γ1) = array ( β1 ) S(γ2) = pointer ( β1 ) → β2 (b)(d): 无 (c)(d):S(γ1) = δ1 S(γ2) = δ1 → δ25.17 仿效例5.5，推到下面map 的多态类型: map: ∀ α . ∀ β . ( ( α → β ) * list ( α ) ) → list ( β ) map 的ML 定义是 fun map ( f , l ) = if null ( l ) then nilelse cons ( f ( hd ( l ) ) , map ( f , tl ( l ) ) );在这个函数体中，内部定义的标识符的类型是： null : ∀α . list (α ) → boolean ; nil : ∀α . list (α ) ;cons : ∀α . ( α * list (α ) ) → list (α ) ;hd:∀α . list (α ) →α;∀α . list (α ) → list (α ) ;tl:Solution:行定型断言代换规则(1) f : α( Exp Id )(2) l : β( Exp Id )(3) map : γ( Exp Id )(4) map ( f , l ) : δγ = ( α * β ) →δ(Exp Funcall)(5) null : list (α0) → boolean ( Exp Id ) 和( Type Fresh )(6) null ( l ) : boolean β = list (α0) (Exp Funcall)(7) nil : list (α1) ( Exp Id ) 和( Type Fresh )(8) l : list (α0) 由（2）可得(9) hd : list (α2) →α2( Exp Id ) 和( Type Fresh )(10) hd ( l ) : α0α2 = α0(Exp Funcall)(11) f ( hd ( l ) ) : α3α = α0→α3( Exp Id )(12) f : α0→α3由（1）可得(13) tl : list (α4)→ list (α4) ( Exp Id ) 和( Type Fresh )(14) tl ( l ) : list (α0) α4 = α0(Exp Funcall)(15) map : ((α0→α3)*list(α0))→δ由（3）可得(16) map ( f , tl ( l ) ) : δ(Exp Funcall)(17) cons : α5 * list(α5) → list(α5) ( Exp Id ) 和( Type Fresh ) (18) cons (…) : list (α3) α5 = α3 , δ=list(α3) (Exp Funcall)(19) if : boolean *α6 * α6→α6( Exp Id ) 和( Type Fresh )(20) if (…) : list (α1) α6 = α1 , α3 = α1(Exp Funcall)(21) match : α7 *α7 →α7( Exp Id ) 和( Type Fresh ) (22) match (…) : list (α1) α7 = list (α1) (Exp Funcall)至此有map : ( (α0→α1)*list(α0) )→list(α1)所以map : ∀α . ∀β . ( ( α→β ) * list ( α ) ) → list ( β )5.18 假定类型名link和cell如5.5节那样定义，下面的表达式中，那些结构等价？那些名字等价？(a) link(b) pointer ( cell )(c) pointer ( link )(d) pointer ( record ( ( info : integer ) * ( next : pointer ( cell ) ) ) ) Solution:(a)、(b)、(d)结构等价，无名字等价。

练习5.1解答：输入(4*7+1)*2n,带注释的分析树如下：练习5.2解答: (1)根据表5.3中的语法制导定义建立表达式((a)+(b))的分析树和语法树(2)根据图5.17的翻译模式构造((a)+(b))的分析树和语法树练习5.3解答:设置下面的函数和属性：expr1||expr2:把表达式expr2拼写在表达式expr1后面。

deletep(expr):去掉表达式expr左端的‘（’和右端的‘)’。

E.expr,T.expr,F.expr:属性变量，分别表示E，T，F的表达式。

E.add,T.add,F.add,属性变量，若为true，则表示其表达式中外层有‘＋’号，否则无‘＋’号。

E.pmark,T.pmark,F.pmark,属性变量，若为true，表示E,T,F的表达式中左端为‘（’，右端是‘）’。

语法制导定义如下：产生式语义规则E -> E1 +T if(T.pmark==true)THEN E.expr=E1.expr||'+'||deletep(T.expr) ELSE E.expr:=E1.expr||'+'||T.expr;E.add:=true;E.pmark:=false;E -> T if(T.pmark==true)THEN E.expr:=deletep(T.expr)ELSE E.expr:=T.expr;E.add:=T.add;E.pmark:=false;T -> T1*F T.expr:=T1.expr||'*'||F.expr; T.add:=false;T.pmark:=false;T -> F T.expr:=F.expr; T.add:=F.add;T.pmark:=F.pmark;F -> (E) if(E.add==false)THEN BEGINF.expr:=E.expr;F.add:=false;F.pmark:=false;ENDELSE BEGINF.expr:='('||E.expr||')';F.add:=true;F.pmark:=true;END;F -> id F.expr:=id.lexval;F.add:=false;F.pmark:=false;练习5.4解答: (1)语法制导定义如下：产生式语义规则E -> E1+T if(E1.type==int) AND (T.type==int) THEN E.type:=intELSE E.type:=real;E -> T E.type:=T.type;T -> num T.type:=int;T -> num.num T.type:=real;(2)设E.pf和T.pf分别是E和T的前缀形式，||是两个字符串的连接，语法制导定义如下：产生式语义规则E -> E1+T if(E1.type==int) AND (T.type==int)THEN E.type:=intELSE BEGINE.type:=real;if(E1.type==int) AND (T.type==real)THEN E1.pf:='inttoreal'||E1.pfELSE if(E1.type==real)AND(T.type==int)THEN T.pf:='inttoreal'||T.pfEND;E.pf:='+'||E1.pf||T.pf;E -> T E.type:=T.type; E.pf:=T.pf;T -> num T.type:=int; T.pf:=int.lexval;T ->num.numT.type:=real; T.pf:=real.lexval;练习5.5解答: (1)用综合属性决定s.val的语法制导定义：产生式语义规则S -> L S.val:=L.val;S ->L1.L2S.val:=L1.val+L2.val*L2.p;L -> B L.val:=B.val; L.p:=2-1;L -> L1B L.val:=L1.val*2+B.val; L.p:=L.p*2-1;B -> 0 B.val:=0;B -> 1 B.val:=1;注：L.p表示恢复L.val的因子。

编译原理教程第五版课后答案第一章：引言问题1答：编译器是一种将高级编程语言源代码转换为目标机器代码的软件工具。

它由多个阶段组成，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成等。

问题2答：编译器的主要任务包括以下几个方面： - 词法分析：将源代码划分为词法单元，如标识符、关键字、操作符等。

- 语法分析：根据语法规则，将词法单元组成语法树。

- 语义分析：对语法树进行语义检查，如类型匹配、变量声明等。

- 中间代码生成：将语法树转换为中间代码表示形式。

- 代码优化：对中间代码进行优化，以提高程序的效率。

- 代码生成：将优化后的中间代码转换为目标机器代码。

第二章：词法分析问题1答：词法单元是编译器在词法分析阶段识别的最小的语法单位，它由一个或多个字符组成。

常见的词法单元包括关键字、标识符、常量和运算符等。

问题2答：识别词法单元的方法包括以下几种： - 正则表达式：通过正则表达式匹配字符串，识别出各类词法单元。

- 有限自动机：构建有限状态自动机，根据输入字符的不同状态转移，最终确定词法单元。

- 递归下降法：使用递归下降的方式，根据语法规则划分出词法单元。

第三章：语法分析问题1答：语法分析是编译器的一个重要阶段，它的主要任务是根据给定的语法规则，将词法单元序列转换为语法树。

语法分析有两个主要的方法：自顶向下的分析和自底向上的分析。

问题2答：自顶向下的分析是从文法的起始符号开始，根据语法规则逐步向下展开，直到生成最终的语法树。

常见的自顶向下的分析方法包括LL(1)分析和递归下降分析。

问题3答：自底向上的分析是从输入串开始，逐步合并词法单元，最终生成语法树。

常见的自底向上的分析方法包括LR分析和LALR分析。

第四章：语义分析问题1答：语义分析的主要任务是对语法树进行语义检查和类型推断。

语义分析阶段会检查变量的声明和使用是否合法，以及类型是否匹配等。

问题2答：常见的语义错误包括变量未声明、类型不匹配、函数调用参数不匹配等。

第5-7章课后作业（含答案）1、将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。

G[S]：S→bSAe|bA A→Abd | dc | a【解】：G[S]：S→bS’S’→SAe|AA→(dc|a)A’A’→bd A’ |ε2、有文法G[S]：S→ABf A→BbS|e B→dAg|ε证明文法G是LL(1)文法，并构造预测分析表【解】：①计算FIRST、FOLLOW、SELECT集由上表可知：该文法中，所有相同左部不同右部的产生式SELECT集两两相交均为空集，所以该文法为LL(1)文法。

3、已知文法G[S]：S→(A)│a│b A→AcS│S 构造文法的算符优先矩阵，并判断该文法是否是算符优先文法。

【解】：①拓展该文法：S’→#S# S→(A)│a│b A→AcS│S②计算FIRSTVT与③计算算符优先关系：# =# ( = )# < FIRSTVT(S) ( < FIRSTVT(A) c< FIRSTVT(S)LASTVT(S) > # LASTVT(A) > ) LASTVT(A) > c④构造算符优先矩阵⑤因为该文法G为2型文法，且不含空产生式，没有形如 U …VW…的产生式，其中V,W∈V所以 G 为算符文法；又因为G 中任意两个终结符间至多有一种算N，符优先关系存在(算符优先矩阵无冲突，见上表)，所以G 为算符优先文法。

4、课后习题P122：4(2)已知文法：S→S;G|G G→G(T)|H H→a|(S) T→T+S|S求句型a(T+S);H;(S) 的短语、直接短语、句柄、素短语与最左素短语。

【解】：①该句型的对应的语法树如下：②短语： a T+S H (S) a(T+S);H a(T+S);H;(S)直接短语： a T+S H (S)句柄：a素短语： a T+S (S)最左素短语：a5. 给定文法G[A]：A→(A)│a，构造出该文法的LR(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中，否则表明出错。

第五章语法分析—自下而上分析本章要点1. 自下而上语法分析法的基本概念：2. 算符优先分析法；3. LR分析法分析过程；4. 语法分析器自动产生工具Y ACC；5. LR分析过程中的出错处理。

本章目标掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。

本章重点1．自下而上语法分析的基本概念：归约、句柄、最左素短语；2．算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理；3．LR分析器：（1）LR(0)项目集族，LR(1)项目集簇；（2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造；（3）LR分析的基本原理，分析过程；4．LR方法如何用于二义文法；本章难点1. 句柄的概念；2. 算符优先分析法；3. LR分析器基本；作业题一、单项选择题：1. LR语法分析栈中存放的状态是识别________的DFA状态。

a. 前缀；b. 可归前缀；c. 项目；d. 句柄；2. 算符优先分析法每次都是对________进行归约：(a)句柄（b）最左素短语(c)素短语(d)简单短语3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。

a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法；4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LL(1)分析法属于自顶向下分析；a. 深度分析法b. 宽度优先分析法c. 算符优先分析法d. 递归下降子程序分析法5. 自底向上语法分析采用分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。

a. 递归b. 回溯c. 枚举d. 移进－归约6. 一个LR(k)文法，无论k取多大，。

a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定二义性；7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LR分析法属于自底向上分析。

Lw.《编译原理》课后习题答案第一章第 1 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第 2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

盛威网（）专业的计算机学习网站1《编译原理》课后习题答案第一章目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

第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的句子。

答案：也可由预测分析表中无多重入口判定文法是LL(1)的。

的。

是文法的句子。

可见输入串（a,a）#是文法的句子。

第3题已知文法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLM分析表。

判断G是否是LL(1)文法，如果是，构造LL(1)分析表。

第7题对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。

法进行改写，并对改写后的文法进行判断。

(１)A→baB|εB→Abb|a(2) A→aABe|aB→Bb|d(3) S→Aa|bA→SBB→ab答案：答案：(１)先改写文法为：先改写文法为：0) A→baB1) A→ε→ε2) B→baBbb3) B→bb4) B→a再改写文法为：再改写文法为：0) A→baB1) A→ε→ε2) B→bN3) B→a4) N→aBbb5) N→b文法： A→aABe|a B→Bb|d（2）文法：提取左公共因子和消除左递归后文法变为： 提取左公共因子和消除左递归后文法变为：0) A→a N1) N→A B e2) N→ε3) B→d N14) N1→b N15) N1→ε（3）文法：）文法： S→Aa|b A→SB B→ab种改写：第1种改写：得： 用A的产生式右部代替S的产生式右部的A得：S→SBa|b B→ab消除左递归后文法变为：消除左递归后文法变为：0) S→b N1) N→B a N2) N→ε3) B→a b的。

第五章习题解答5.1 设一NDPDA识别由下述CFG定义的语言，试给出这个NDPDA的完整形式描述。

S→SASCS→εA→AaA→bC→DcDD→d5.2 消除下列文法的左递归：① G[A]:A→BX∣CZ∣WB→Ab∣BcC→Ax∣By∣Cp② G[E]:E→ET+∣ET–∣TT→TF*∣TF/FF→(E)∣i③ G[X]:X→Ya∣Zb∣cY→ Zd∣Xe∣fZ→X e∣Yf∣a④ G[A]:A→Ba|Aa|cB→Bb|Ab|d5.3 设文法G[<语句>]：<语句>→<变量>: = <表达式>|if<表达式>then<语句>|if<表达式>then<语句>else<语句> <变量>→i<表达式>→<项>|<表达式>+<项><项>→<因子>|<项>*<因子><因子>→<变量>|′(′<表达式>′)′试构造该文法的递归下降子程序。

5.4 设文法G[E]：E→ TE'E'→ + E∣εT→ FT'T'→ T∣εF→ PF'F'→ *F∣εP→ (E)∣ a∣^①构造该文法的递归下降分析程序；②求该文法的每一个非终结符的FIRST集合和FOLLOW集合；③构造该文法的LL（1）分析表，并判断此文法是否为LL（1）文法。

5.5 设文法G[S]：S→ SbA∣aAB→ SbA→ Bc①将此文法改写为LL（1）文法；②求文法的每一个非终结符的FIRST集合和FOLLOW集合；③构造相应的LL（1）分析表。

5.6 设文法G[S]：S→ aABbcd∣εA→ ASd∣εB→ SAh∣eC∣εC→ Sf∣Cg∣εD→ aBD∣ε①求每一个非终结符的FOLLOW集合；②对每一个非终结符的产生式选择，构造FIRST集合；③该文法是LL（1）文法。