编译原理典型例题
编译原理典型案例
1.对于文法G[S]
S →(L)
S→aS
S→a
L →L,S
L→S
(1) 画出句型(S,(a)) 的语法树；
(2) 写出上述句型的所有短语、直接短语、句柄和素短语。
解答
这类题目重点考查语法树、推导、短语、直接短语、句柄和素短语等基本概念。在句型中寻找短语、直接短语、句柄的方法：
(1) 画出句型对应的语法树。句型(S,(a)) 的语法树如下图所示
(2) 在该语法树中寻找短语、直接短语、句柄。首先我们看短语的定义：令G是一个文法，S是文法的开始符，假设α,β,δ是文法G的句型，如果有
S*?αAδ且A+?β
则称β是句型αβδ相对于非终结符A的短语。如果有A?β，则称β是句型αβδ相对于规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。根据短语的定义可知，以非终结符A为根的子树的叶结点从左到右排列就是相对于非终结符A的短语；如果子树只有两代，则短语就是直接短语；最左边的两代子树的所有叶结点从左到右排列，就是该句型的句柄。素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语。
从语法树中我们可以找到：
短语：a，S，(a)，S, (a)，(S, (a))
直接短语：a，S
句柄：S
素短语：a
2. 写一个上下文无关文法，使其语言能被5整除且不以0开头的无符号整数集合（如{5，10，15}）
解答
能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。句子的结构分为三种：
其中，A 代表可以出现在个位上的数字，只能是0或5；
B 代表可以出现在开始位上的数字，除了0以外，其他数字都可以；
C 代表可以出现在中间位上的数字。0-9所有数字都可以。 于是，A →0 | 5
B →1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
C →0 | B
写文法时，先描述一位数结构，于是有产生式S →5。对于两位数和多位数，都是以B 开头和以A 结尾，于是有产生式S →DA 。用非终结符D 推导出两位数和多位数中除个位数字以外的数字。对与多位数，由于中间位可以是许多位，必须使用递归技术来描述其结构。于是有产生式： D →DC
D →B
因此，所求文法为G[S]：
S →5 S →DA D →DC D →B
A →0 | 5
B →1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
C →0 | B
3. 写一个文法G , 使其语言为 不以0开头的偶数集。
解答
不以0开头的偶数集数字的结构分为三种：一位数、两位数和多位数。
其中，A 代表可以出现在个位上的数字，可以是2，4，6，8，但不能是0；
B 代表可以出现在开始位上的数字，除了0以外，其他数字都可以；
C 代表可以出现在中间位上的数字。0-9所有数字都可以。 于是，A →2 | 4 | 6 | 8
B →0 | A
C →1 | 3 | 5 | 7 | 9 | A
D →0 | C
写文法时，先描述一位数结构，于是有产生式S →A 。对于两位数和多位数，都是以C 开头和以B 结尾，于是有产生式S →CE 。用非终结符E 推导出两位数和多位数中除个位数字以外的数字。对与多位数，由于中间位可以是许多位，必须使用递归技术来描述其结构。于是有产生式：
E →CE E →B
因此，所求文法为G(S)：
S→A | CE E →CE | B A →2 | 4 | 6 | 8 B →0 | A
C →1 | 3 | 5 | 7 | 9 | A
D →0 | C
4. 考虑下面的程序： …
procedure P(x, y, z);
begin y:=y+1; z:=z+x end; begin a:=2;
b:=3;
P(a+b, a, a); print a end.
试问，若参数传递的方式分别采用传值、传地址、得结果和传名时，程序执行后输出 a 的值是什么?
解答
所谓传值是调用段把实在参数的值计算出来，被调用段把这些值抄进自己的形式参数中，像使用局部名一样使用这些形式单元。对形式参数的任何运算不影响实参的值。
上面过程P 调用的的参数传递过程如下图所示。
但过程P 无法改变实参a 的值。因此，程序执行后输出 a 的值是 2。
所谓传地址是把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一个相应的单元，称为形式单元。形式单元将用来存放相应实在参数的地址。过程体对形式参数的任何引用或赋值都被处理成对形式单元的间接访问。
过程调用后，形参x 的形式单元指向存a+b 值的临时变量的地址，形参y 的形式单元指向变量a 的地址，形参z 的形式单元指向变量b 的地址。形参通过指针可以间接访问实参。
执行y:=y+1; 后，实在参数的变化：
执行z:=z+x; 后，实参的变化：
因此，程序执行后输出 a 的值是 8。
所谓得结果是每个形式参数对应两个单元，第一个单元存放实参的地址，第二个单元存放实参的值。在过程体中对形参的任何引用或赋值都被处理成对第二个形式单元的直接访问，但在过程工作完成返回之前必须把第二个单元的内容存放到第一个单元所指的那个实参单元之中。
执行y:=y+1; 后，实参和的形参的变化：
执行z:=z+x; 后，实参和的形参的变化：
过程工作完成返回之前必须把第二个单元的内容存放到第一个单元所指的那个实参单元之中。实参和的形参的变化：
因此，程序执行后输出 a 的值是 7。
(4) 所谓传名是在进入调用段之前不对实在参数预先进行计值，而是过程中每当使用到相应的形参时才对它实行计值。因此,在实现时通常都把实参处理成型个子程(称为参数子程序),每当过程体中使用到相应形参时就调用这个子程序。
因此，过程体执行y:=y+1;语句，实现时处理成为：
a=a+1;
过程体执行z:=z+x;语句，实现时处理成为：
a=a+(a+b);
执行上述两语句后，a的值是9。因此，程序执行后输出a的值是9。
综上所述程序执行时a的输出：
(1)传值：2
(2)传地址：8
(3)得结果：7
(4)传名：9
5. 已知文法G[S]
S→S*aP | aP | *aP
P→+aP | +a
(1)将文法G[S]改写为LL(1)文法G?[S]；
(2)构造文法G?[S]的预测分析表。
解答
构造文法的预测分析表，通常应当按下列步骤进行：
(1) 消除文法的左递归
(2) 对消除左递归后的文法，提取左公因子。
(3) 对经过上述改造后的文法，计算它的每个非终结符的FIRST 和FOLLOW集合。
(4) 根据FIRST 和FOLLOW集合构造预测分析表。
消除直接左递归方法：假设关于非终结符P的规则为
P→Pα|β
其中，β不以P打头。把P的规则改写为如下非直接左递归形式：
P→βP ?
P→αP ?|
文法G[S] 消除直接左递归方法后，文法变为G?[S]：
S→a P S? | *a P S?
S?→*a P S? | ε
P→+a P | +a
提公共左因子的方法：假设关于非终结符A的规则为
A→δβ1| δβ2|…| δβn|γ1| γ2|…| γm
其中，每个γ不以δ开头。把A的规则改写为如下形式：
A→αA?| γ1| γ2|…| γm
A?→β1|β2|…|βn
于是，文法G?(S) 提公共左因子后，文法变为G??[S]
S→a P S? | *a P S?
S?→*aP S? | ε
P→+a P?
P?→P | ε
计算每个非终结符的FIRST 和FOLLOW集合：
a. 计算非终结符X的FIRST方法：
(1)若有产生式X→a…，则把a加入到FIRST(X)中；
(2)若X→ε也是一条产生式,则把ε也加到FIRST(X)中；
(3)若X→Y…是一个产生式且Y∈VN，则把FIRST(Y)中的所有非ε元素都加到FIRST(X)中；若X→Y1Y2…YK 是一个产生式，Y1,Y2,…,Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1,FIRST(Yj)都含有ε，则把FIRST(Yj)中的所有非ε元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)( j=1,2,…,K)均含有ε，则把ε加到FRIST(X)中。
根据计算非终结符的FIRST方法的第一点，有
FIRST(S)={a，*}
FIRST(S?)={*}
FIRST(P)={+}
FIRST(P?)={}
根据计算非终结符的FIRST方法的第二点，有
FIRST(S)={a，*}
FIRST(S?)={*，ε}
FIRST(P)={+}
FIRST(P?)={ ε}
根据计算非终结符的FIRST方法的第三点，有
FIRST(S)={a，*}
FIRST(S?)={*，ε}
FIRST(P)={+}
FIRST(P?)={+，ε}
b. 计算非终结符X的FOLLOW方法：
(1)对于文法的开始符号S,置#于FOLLOW(S) 中；
(2).若Ａ→αBβ是一个产生式，则把FIRST(β)\{ε}加至FOLLOW(B)中；
(3)若Ａ→αB是一个产生式,或Ａ→αBβ是一个产生式而β?ε(即ε∈FIRST(β))，则把FOLLOW(A)，加至FOLLOW(B)中。
根据计算非终结符的FOLLOW方法的第一点，有
FOLLOW(S)={#}
FOLLOW(S?)={}
FOLLOW(P)={}
FOLLOW(P?)={}
根据计算非终结符的FOLLOW方法的第二点，有
FOLLOW(S)={#}
FOLLOW(S?)={#}
FOLLOW(P)={*，#}
FOLLOW(P?)={*，#}
根据FIRST 和FOLLOW集合构造预测分析表方法：
(1)对文法G的每个产生式Ａ→α执行第二步和第三步；
(2)对每个终结符a∈FIRST(α)，把Ａ→α加至M[A,a]中；
(3)若ε∈ FIRST(α)，则对任何b∈FOLLOW(A)，把Ａ→α加至M[A,b]中；
(4)把所有无定义的M[A,a]标上“出错标志”。
构造预测分析表方法如下：
6. 设文法G(S):
S→(T) | aS | a
T→T,S | S
⑴消除左递归和提公共左因子；
⑵构造相应的FIRST和FOLLOW集合；
⑶构造预测分析表。
解答
(1)消除左递归和提公共左因子，文法变为G?[S]
S →(L) | aS?
S?→S |ε
L→SL?
L?→,SL? |ε
此文法没有公共左因子
(2) 构造相应的FIRST和FOLLOW集合
FIRST(S)={a，(}
FIRST(S?)={a，(，ε}
FIRST(L)={a, (}
FIRST(L?)={,, ε}
FOLLOW(S)={,, ), #}
FOLLOW(S?)={,, ), #}
FOLLOW(L)={ )}
FOLLOW(L?)={ )}
(3) 构造预测分析表
7. 设文法G[S]
S →(A)
S →a
A→A+S
A→S
(1) 构造每个非终结符的FIRSTVT和LASTVT集合；
(2) 构造优先关系表；
解答
对于这类题目，关键是准确掌握FIRSTVT和LASTVT集合的定义和构造方法。
FIRSTVT(P)={a|P+?a…或P+?Qa...，a∈VT而Q∈VN}
即，对于非终结符P，其往下推导所可能出现的首个算符。
LASTVT(P)={a|P+?…a或P+?...aQ，a∈VT而Q∈VN}
即，对于非终结符P，其往下推导所可能出现的最后一个算符。
构造FIRSTVT和LASTVT集合的方法
(1)构造FIRSTV集合
若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P)；
若有a∈FIRSTVT(Q)，且有产生式P→Q…，则a∈FIRSTVT(P)。
(2)构造LASTVT集合
若有产生式P→…a或P→…aQ，则a∈LASTVT(P);
若有a∈LASTVT(Q)，且有产生式P→…Q，则a∈LASTVT(P)。
对于文法G[S]，构造它的每个非终结符的FIRSTVT和LASTVT集合：
FIRSTVT(S)={a, ( }
FIRSTVT(A)={+, a, ( }
LASTVT(S)={a, )}
LASTVT(A)={+, a, )}
构造算符优先关系表方法：
(1) …=…关系
直接看产生式的右部，若出现了
P →…ab…或P→…aQb，则a=b
(2)?<…关系
求出每个非终结符P的FIRSTVT(P)
若P→…aR…，则?b∈FIRSTVT(R)，a (3)?>?关系 求出每个非终结符P的LASTVT(P) 若P→…Rb…，则?a∈LASTVT(B)，a>b 对于文法G[S]，构造它的算符优先关系表如下： 8. 设文法G（S）： S→T | S∨T T→U |T∧U U→i |-U (1) 计算FIRSTVT 和LASTVT； (2) 构造优先关系表。 解答 (1)对于文法G[S]，构造它的每个非终结符的FIRSTVT和LASTVT集合。 FIRSTVT(S)={∨, ∧, i, - } FIRSTVT(T)={∧, i, -} FIRSTVT(U)={i, -} LASTVT(S)={∨, ∧, i, - } LASTVT(T)={∧, i, -} LASTVT(U)={i, -} (2) 构造优先关系表。 9. 下面映射if语句的文法G[S]是算符优先文法吗？如果是，则构造算符优先关系表。如果不是，则说明理由。 G[S] S→iBtS S→iBtSeS S→a B→b 解答 对于文法G[S]，它是一个二义性文法。因为存在句子ibtibtaea有两个不同的最左推导S? iBtS? ibtS? ibtiBtSeS? ibtibtSeS? ibtibtaeS? ibtibtaea S? iBtSeS? ibtSeS? ibt iBtSeS? ibtibtSeS? ibtibtaeS? ibtibtaea 由于算符优先文法一定不是二义性文法，所以文法G[S]不是算符优先文法。 10. 设有如下的基本块 T1:=A+B T2:=5 M:=T2*4 T3:=C-D T4:=M+T3 L:=T1*T3 T4:=A+B N:=T4 (1)画出该基本块的DAG图； (2)假设只有L，M 和N 在基本块之后还要引用，写出优化后的四元式序列。 解答 在构造基本块的DAG图时，必须注意两个方面：一是对于已知的常量要进行计算；二是对同一变量进行多次定值时，最后一次定值是基本块中该变量的最终变量。由于基本块有语句T2：=5，可知T2是已知量。所以，语句M：=T2 * 4 可计算出M 的值来，即，M也转为常量（M = 20）。一方面，变量T4进行了两次操作，基本块执行完时，最后一次给T4的定才是T4的最终结果。活跃信息是针对变量而言的。如果一个变量在基本块之后不再被引用，则称该变量是非活跃的（或称为非活跃变量），反之称之为活跃的（或称为活跃变量）。变量的活跃信息对代码优化和代码生成都有非常重要的指导意义。 当DAG图构造出来后，根据题目所给的条件从DAG图中计算出活跃变量的结果即可。本是中只要计算出变量L、M和N的结果就行了。 基本块对应的DAG图如下： 按照构造其结点的顺序，重新写成四元式序列G ? T1=A+B T4=T1 N=T4 T2=5 M=20 T3=C-D L=T1*T3 由于只有L ，M 和N 在基本块之后还要引用，T1、T2、T3和T4都不会引用，于是重新写出优化后的四元式序列为： N:=A+B M:=20 T3:=C-D L:=N*T3 11. 把语句 while a>0 ∧b>0 do if x>y then b:=b-1 else a:=a-1; 翻译为四元式序列。 解答 对于这类题目，关键是准确掌握语句的语动作。 作为条件控制的布尔式的翻译： 把A or B 解释成if A then true else B 把A and B 解释成if A then B else false 把not A解释成if A then false else true 布尔表达式赋予两种“出口” ：一是“真”出口；一是“假”出。 假设四元式序列从100开始编号。 表达式a>0 翻译为： 100 (j>，a，0，_) 101 (j，_，_，_) 继续翻译表达式a>0 ∧b>0，由于是与运算，100号语句应转跳到102号语句，102号语句为“真”出口，101号语句和103号语句为“假”出，四元式序列为： 100 (j>，a，0，102) 101 (j，_，_，_) 102 (j>，b，0，_) 103 (j，_，_，_) 继续翻译语句while a>0 ∧b>0 do if x>y … while语句中的逻辑表达式的“真”出口应转跳到其循环体的第一个四元式标号，即104号语句。 100 (j>，a，0，102) 101 (j，_，_，_) 102 (j>，b，0，104) 103 (j，_，_，_) 104 (j>，x，y_) 105 (j，_，_，_) if语句中的逻辑表达式的“真”出口为104号语句，应转跳到then 中的第一个四元式标号，“假”出口为105号语句，应转跳到else 中的第一个四元式标号。then 中语句翻译完，应转跳出去。 100 (j>，a，0，102) 101 (j，_，_，_) 102 (j>，b，0，104) 103 (j，_，_，_) 104 (j>，x，y_) 105 (j，_，_，_) 106 (-，b，1，T1) 107 (:=，T1，_，b) 108 (j，_，_，_) 109(-，a，1，T2) 110 (:=，T2，_，a) while语句中循环体翻译完，应转跳到while语句的第一个四元式标号，即100号语句。while语句中的逻辑表达式的“假”出口应转跳到while语句后的第一个四元式标号。 100 (j>，a，0，102) 101 (j，_，_，112) 102 (j>，b，0，104) 103 (j，_，_，112) 104 (j>，x，y_) 105 (j，_，_，_) 106 (-，b，1，T1) 107 (:=，T1，_，b) 108 (j，_，_，100) 109(-，a，1，T2) 110 (:=，T2，_，a) 111 (j，_，_，100) 12. 已知文法G[S]及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么？ 解答 对于这类题目，首先画出句子acab对应的语法树。每当用一个产生式归约时，则执行相应的语义动作。句子acab对应的语法树为： 第一个归约的产生式是A→c，它相应的语义动作为print “4”。所以，产生输出4。 第二个归约的产生式是S→a，它相应的语义动作为print “2”，产生输出2。 第三个归约的产生式是A→AS，它相应的语义动作为print “3”，产生输出3。 最后归约的产生式是S→aAb，它相应的语义动作为print “1”，产生输出1。 因此，输入acab, 输出是4231。 * 编译原理复习题 一．简答题： 1) 什么是句子？ 什么是语言? 解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T * ），则称x 是文法的一个句子。 语言——语言是句子的集合。 或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │ S x,x ∈V T * } 。 2) DFA 与NFA 有何区别 ? 解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个 开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么? 解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接 推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么? 解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图 归约到文法的开始符号。 5) 一个上下文无关文法G 包括哪四个组成部分？ 解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？ 解答:关键是寻找句柄。 7)在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。 8）什么是属性文法？ 答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属 性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过 程中，完成语义规则所描述的动作，从而实现语义处理。 一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。 其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。 9）语法制导翻译 语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。 语法制导翻译(Syntax-Directed Translations)： –一个句子的语义翻译过程与语法分析过程同时进行。 在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息， 语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义 属性值。 10）词法分析的主要任务是什么？ 解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫 描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属 11)图示运行时存储空间的划分（分为哪几个区）。 解答: 一般分为静态区和动态区： 程序代码区、静态数据区、栈区和堆区 12)常用的中间语言种类有哪几种？ 解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。 13）文法G所描述的语言是什么的集合？ 解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。 14）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？ 解答: 2型文法叫上下文无关文法。 15）常见的动态存贮分配策略有哪两种？ 解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。 16）语法分析的任务是什么？ 第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题 第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12． 《编译原理》第一次作业参考答案 一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？ 1.b*(ab*ab*)* 所有含有偶数个a的由a和b组成的字符串. 2.c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串. 答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串. 说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”. 二、设字母表∑={a,b}，用正则表达式（只使用a，b， ，|，*，+，？）描述下列语言： 1.不包含子串ab的所有字符串. b*a* 2.不包含子串abb的所有字符串. b*(ab?)* 3.不包含子序列abb的所有字符串. b*a*b?a* 注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容. ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ 《编译原理》第二次作业参考答案 一、考虑以下NFA： 1.这一NFA接受什么语言（用自然语言描述）？ 所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串. 2.构造接受同一语言的DFA. 答案一（直接构造通常得到这一答案）： 答案二（由NFA构造DFA得到这一答案）： 二、正则语言补运算 3.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串. 1.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串. 《编译原理》习题答案： 第一次： P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？ 答：被翻译的程序称为源程序； 翻译出来的程序称为目标程序或目标代码； 将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序； 把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序； 解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行； 编译程序是将高级语言写的源程序翻译成目标语言的程序。 关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。 P14 3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。 P14 4、语法分析和语义分析有什么不同？试举例说明。 答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。 P15 5、编译程序分遍由哪些因素决定？ 答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。 补充： 1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？ 答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。 补充： 2、赋值语句：A：= 5 * C的语法和语义指的是什么？ 答：语法分析将检查该语句是否符合赋值语句规则，语义是指将 5 * C 的结果赋值为 A 。第二次作业： P38 1、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。 T2T1＝{011，0010，0111，01010，100111，1001010} T1*＝{ε，11，010，1111，11010，01011，010010……} T2+＝{0，01，1001，00，001，01001，010，0101……} 编译 原理 课后题答案 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/******************************** E E F T E + T F F T +i i i E E F T E -T F F T -i i i E E F T +T F F T i i i *i+i+i i-i-i i+i*i *****************/ P36-9 句子iiiei 有两个语法树： S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ???????? P36-10 /************** ) (|)(|S T T TS S →→ ***************/ P36-11 /*************** L1: ε ||cC C ab aAb A AC S →→→ L2: 第1章引言 1、解释下列各词 源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 （结果程序）一般可由计算机直接执行。 低级语言：机器语言和汇编语言。 高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目 标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言）， 然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。 2、什么叫“遍” 指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。 3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。 词法分析：输入源程序，进行词法分析，输出单词符号。 语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。 中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。 优化：对中间代码进行优化处理。 目标代码生成：把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别 编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。 5、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗 编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。 6、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。 1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么? 1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。 1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。 1.5试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。 第一章习题解答 1.解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将 源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。 2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成 程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 3.解：C语言的关键字有：auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。上述关键字在C语言中均为保留字。 4.解：C语言中括号有三种：{}，[]，（）。其中，{}用于语句括号；[]用于数组；（）用于函数（定 义与调用）及表达式运算（改变运算顺序）。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。 5.略 第二章前后文无关文法和语言 21设有字母表A1={a,b,…,z}，A2={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1 (A1∪A2)*中的全部长度不大于3的符号串。 <编译原理>历年试题及答案 一．（每项选择 2 分，共 20 分）选择题 1．将 编译程序分成若干个“遍”是为了_b__。 a.提 高程序的执行效率 b.使程序的结构更加清晰 c. 利用有限的机器内存并提高机器的执行效率 d. 利用有限的机器内存但降低了机器的执行效率 2．构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译方 法 d.以上三项都是 3．变量应 当 c＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持 有左值也不持有右值 4．编译程序绝大多数时间花在 _d___上。 a.出错处理 b.词法分析 c.目标代码 生成 d.管理表格 5．词法分析器的输 出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c.单词 的种别编码和自身值 d.单词自身值 6．正规式 MI 和 M2 等价是指__c__。 a. MI 和 M2 的状态数相等 b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等 d. Ml 和 M2 状态数和有向弧条数相等7．中间代码生成时所依据的是—c。 a．语法规则 b．词法规则c．语义规则 d．等价变换规则 8．后缀式 ab+cd+/可用表达式__b_来表示。 a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 9．程序所需 的数据空间在程序运行前就可确定，称为____c_＿管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10.堆式 动态分配申请和释放存储空间遵守___d____＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 二（每小题 10 分，共 80 分）简答题 1.画出编译程序的 总体结构图，简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 中南大学网络教育课程考试复习题及参考答案 编译原理 一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 ( ) 3.已经证明文法的二义性是可判定的。 ( ) 4.每个基本块可用一个DAG表示。 ( ) 5.每个过程的活动记录的体积在编译时可静态确定。 ( ) 6.2型文法一定是3 型文法。 ( ) 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 ( ) 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是 2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题： 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 14.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。 15.预测分析程序是使用一张（）和一个（）进行联合控制的。 16.常用的参数传递方式有（），（）和（）。 17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。 18.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 19.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。 20.一个句型的最左直接短语称为句型的（）。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（）文法。 22.对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( )策略。 1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 答案：S→AB|B A→a|aA B→bBc|bc 2．给出下面语言的相应文法 L1={a n b n c m d m| m,n≥1，n为奇数，m为偶数}。 答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化） (一)相应的正规式为(a|b)*ab(a|b)* (二)①与此正规式对应的NFA为 答案；在自己写的纸上 4、对下面的文法G: E→TE’E’→+E|εT→FT’T’→T|ε F→PF’F’→*F’|εP→(E)|a|b|∧ （1）证明这个文法是LL(1)的。 考虑下列产生式: E’->E|ε T’->T|ε F’->*F’ |ε P->(E) |∧a|b FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. 计算这个文法的每个非终结符的FIRST和FOLLOW。（8分） 答案：FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#} FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} （3）构造它的预测分析表。（6分） 答案；在手机上 写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。 答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 给出下面语言的相应文法 L1={a n b n a m b m|n,m≥0} 给出下面语言的相应文法 答案：S→AB|A|B|∑ A→aAb|ab B→aBb|ab 第1章引论 第1题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2） 源程序：源语言编写的程序称为源程序。 （3） 目标程序：目标语言书写的程序称为目标程序。 （4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。 第3题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功 编译原理习题 Revised as of 23 November 2020 一、填空题: 1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理 . 1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称为编译程序. 1-03.编译方式与解释方式的根本区别在于是否生成目标代码 . 1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序 . 1-05.对编译程序而言,输入数据是源程序 ,输出结果是目标程序 . 1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段和运行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: 编译阶段 , 汇编阶段和运行阶段 . 1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 1-09.编译方式与解释方式的根本区别为是否生成目标代码。 2-01.所谓最右推导是指：任何一步αβ都是对α中最右非终结符进行替换的。 2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 2-03.产生式是用于定义语法成分的一种书写规则。 2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈*} 。 V T 2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。 *),则称x是文法2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T 的一个句子。 3-01.扫描器的任务是从源程序中识别出一个个单词符号。 4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。 4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。 4-03.递归下降法不允许任一非终极符是直接左递归的。 4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。 4-05.递归下降分析法是自顶向上分析方法。 4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。 编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。但要求至少要按照作业题的范围复习。) 一选择题 1．编译的各阶段工作都涉及。 [A]词法分析[B]表格管理 [C]语法分析 [D]语义分析 2．型文法也称为正规文法。 [A] 0 [B] 1 [C] 2 [D] 3 3．文法不是LL(1)的。 [A]递归 [B]右递归 [C]2型 [D]含有公共左因子的 4．文法E→E+E|E*E|i的句子i*i+i*i有棵不同的语 法树。 [A] 1 [B] 3 [C] 5 [D] 7 5．文法 S→aaS|abc 定义的语言是。 [A]{a2k bc|k>0} [B]{a k bc|k>0} [C]{a2k-1bc|k>0} [D]{a k a k bc|k>0} 6．若B为非终结符，则 A→.B为。 [A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目 7．同心集合并可能会产生新的冲突。 [A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约 8．代码优化时所依据的是。 [A]语法规则 [B]词法规则 [C]等价变换规则 [D]语义规则 9．表达式a-(-b)*c的逆波兰表示（@为单目减）为。 [A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-* 10．过程的DISPLAY表是用于存取过程的。 [A]非局部变量[B]嵌套层次 [C]返回地址 [D]入口地址 二填空题 1．词法分析阶段的任务式从左到右扫描字符流，从而逐个识别一个个的单词。 2．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是。 3．最右推导的逆过程称为规范归约，也称为最左归约。 4．符号表的每一项是由名字栏和两个栏目组成。 在目标代码生成阶段，符号表是的依据。 三判断题（认为正确的填“T”，错的填“F”） 【】1．同心集的合并有可能产生“归约/归约”冲突。 【】2．一个文法所有句子的集合构成该文法定义的语言。【】3．非终结符可以有综合属性，但不能有继承属性。 【】4．逆波兰表示法表示表达式时无需使用括号。 【】5．一个有穷自动机有且只有一个终态。 【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。 四解答题 1．给定文法G和句型(T+F)*i+T, G: E→E+T|T T→T*F|F F→(E)|i （1）画出句型的语法树； （2）写出句型的全部短语、简单短语和句柄。 解：（略） 2．设有文法G：S→S+S|S*S|i|(S)。 （1）对于输入串i+i*i 给出一个最左推导； （2）该文法是否是二义性文法？请证明你的结论。 解：（1）i+i*i的最左推导： S => S+S => i+S => i+S*S => i+i*S => i+i*i （2）该文法是二义性的。因为对于句子i+i*i可以画出两棵语法树（语法树略）。 3．给出语言{a m b m c n|m≥1,n≥0}的上下文无关文法（2型）。 第四章语义分析和中间代码生成 4.1 完成下列选择题： (1) 四元式之间的联系是通过实现的。 a. 指示器 b. 临时变量 c. 符号表 d. 程序变量 (2) 间接三元式表示法的优点为。 a. 采用间接码表，便于优化处理 b. 节省存储空间，不便于表的修改 c. 便于优化处理，节省存储空间 d. 节省存储空间，不便于优化处理 (3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。 a. ┐AB∨∧CD∨ b. A┐B∨CD∨∧ c. AB∨┐CD∨∧ d. A┐B∨∧CD∨ (4) 有一语法制导翻译如下所示： S→bAb {print″1″} A→(B {print″2″} A→a {print″3″} B→Aa) {print″4″} 若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为。a. 32224441 b. 34242421 c. 12424243 d. 34442212 【解答】 (1) b (2) a (3) b (4) b 4.2 何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。 【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。 用语法制导翻译(SDTS)生成中间代码的要点如下： (1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。 (2) 注意地址返填问题。 (3) 不要遗漏必要的处理，如无条件跳转等。 例如下面的程序段： if (i>0) a=i+e-b*d; else a=0; 在生成中间代码时，条件“i>0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。此外，按语义要求，当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成i+e的代码，再生成b*d的中间代码，最后才产生“-”运算的中间代码，这种顺序不能颠倒。 4.3 令S.val为文法G[S]生成的二进制数的值，例如对输入串101.101，则S.val= 5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则，G(S)如下： G[S]: S→L.L|L 第八章 语法制导翻译和中间代码生成 1．给出下面表达式的逆波兰表示(后缀式)： (1) a*(-b+c) (4) (A ∧B) ∨(?C ∨ D) (7) if(x+y)*z=0 then s ∶=(a+b)*c else s ∶=a*b*c 解(1) ab-c+* (4) AB ∧C ?D ∨∨ (7) xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else 运算） 2. 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。 答案：三元式 (1) (+ a, b) (2) (+ c, d) (3) (* (1), (2)) (4) (- (3), /) (5) (+ a, b) (6) (+,(5),c) (7) (- (4), (6)) 间接三元式 间接三元式序列 间接码表 (1) (+ a, b) (1) (2) (+ c, d) (2) (3) (* (1), (2)) (3) (4) (- (3), /) (4) ￥ = := * := + x y z s + c x a b s * c * a b (5) (- (4), (1)) (1) (6) (- (4), (5)) (5) (6) 四元式 (1) (+, a, b, t1) (2) (+, c, d, t2) (3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5) (6) (+, t5, c, t6) (6) (-, t4, t6, t7) 3. 采用语法制导翻译思想，表达式E 的"值"的描述如下： 产生式 语义动作 (0) S ′→E {print E.VAL} (1) E →E1+E2 {E.VAL ∶=E1.VAL+E2.VAL} (2) E →E1*E2 {E.VAL ∶=E1.VAL*E2.VAL} (3) E →(E1) {E.VAL ∶=E1.VAL} (4) E →n {E.VAL ∶=n.LEXVAL} 如果采用LR 分析法，给出表达式(5 * 4 + 8) * 2的语法树并在各结点注明语义值VAL 。 4. 假如习题3中表达式E 的“值”有两种类型：整型和实型。语义处理增加"类型匹配检查"，请给出相应的语义描述。 S ’ * E1 E2 E0 E3 2 E5.V AL=5 8 5 * E5 E6 + E4 4 E6.V AL=4 E4.V AL=8 E3.V AL=20 E1.V AL=28 E2.V AL=2 E0.V AL=56 Print(56) 第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。 一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a)编译原理复习题2017(含试卷)
编译原理(清华大学第2版)课后习题答案
编译原理作业答案
王汝传编译原理习题答案
编译原理_第三版_课后答案
编译原理作业参考答案
哈工大编译原理习题及答案
编译原理试题及答案(期末复习版).pdf
编译原理复习题及参考答案
编译原理复习题--有答案版
编译原理课后习题答案-清华大学-第二版
编译原理习题
编译原理复习例题
编译原理教程课后习题答案——第四章
编译原理第8章作业及习题参考答案
编译原理习题及答案(整理后)