编译原理典型案例1. 对于文法G[S]S FL)St aSSt aL t l,SL t S⑴画出句型(S,(a))的语法树；(2)写出上述句型的所有短语、直接短语、句柄和素短语解答这类题目重点考查语法树、推导、短语、直接短语、句柄和素短语等基本概念在句型 中寻找短语、直接短语、句柄的方法：(1)画出句型对应的语法树句型 (S,(a))的语法树如下图所示Sa(2)在该语法树中寻找短语、直接短语、句柄首先我们看短语的定义： 令G是一个文法，S是文法的开始符，假设 a , 3 , 3是文法G的句型，如果有* +S= a A 3 且 A = 3则称3是句型a 3 3相对于非终结符 A的短语如果有 A : 3 ,则称3是句型a 3 3相对于规则At 3的直接短语一个句型的最左直接短语称为该句型的句柄 根据短语的定义可知，以非终结符 A为根的子树的叶结点从左到右排列就是相对于非终结符 A的短语；如果子树只有两代，则短语就是直接短语； 最左边的两代子树的所有叶结点从左到右排列， 就是该句型的句柄素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短 语处于句型最左边的素短语为最左素短语从语法树中我们可以找到：短语：a, S, (a), S, (a), (S, (a))直接短语：a, S句柄：S素短语：a2. 写一个上下文无关文法，使其语言能被 5整除且不以0开头的无符号整数集合（如 {5 ,10, 15}）解答能被5整除的数从形式上看，是以 0, 5结尾的数字串。
题目要求不以 0开头，注意0不是该语言的句子句子的结构分为三种：- 3 -- # -B A 两位数- # -- # -其中，A代表可以出现在个位上的数字，只能是 0或5；B代表可以出现在开始位上的数字，除了0以外，其他数字都可以;- # -C代表可以出现在中间位上的数字 0-9所有数字都可以1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Ct 0 | B写文法时，先描述一位数结构，于是有产生式 S t 5对于两位数和多位数，都是以 B开头和以A结尾，于是有产生式 St DA用非终结符 D推导出两位数和多位数中除个位数 字以外的数字对与多位数，由于中间位可以是许多位，必须使用递归技术来描述其结构于是有产生式：D t DCD t B因此，所求文法为 G[S]:S t 5St daD t DCD t BA t 0 | 5Bt 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Ct 0 | B3. 写一个文法G,使其语言为 不以0开头的偶数集解答不以0开头的偶数集数字的结构分为三种：一位数、两位数和多位数一位数C B 两位数D B 多位数其中，A代表可以出现在个位上的数字，可以是2, 4, 6, 8,但不能是0;B代表可以出现在开始位上的数字，除了0以外，其他数字都可以;C代表可以出现在中间位上的数字。
0-9所有数字都可以0 | ACt 1 | 3 | 5 | 7 | 9 | AD t 0 | C写文法时，先描述一位数结构，于是有产生式 StA对于两位数和多位数，都是以 C开头和以B结尾，于是有产生式 StCE用非终结符 E推导出两位数和多位数中除个位数 字以外的数字对与多位数，由于中间位可以是许多位，必须使用递归技术来描述其结构于是有产生式：Et CEEt b因此，所求文法为 G(S):StA | CEEt CE | BAt 2 | 4 | 6 | 8Bt 0 | ACt 1 | 3 | 5 | 7 | 9 | AD t 0 | C4. 考虑下面的程序：procedure P(x, y, z); begin y:=y+1; z:=z+x en d; begin a:=2; b:=3;P(a+b, a, a);print aen d.试问，若参数传递的方式分别采用传值、传地址、得结果和传名时，程序执行后输出 a的值是什么？ 解答所谓传值是调用段把实在参数的值计算出来，被调用段把这些值抄进自己的形式参数 中，像使用局部名一样使用这些形式单元对形式参数的任何运算不影响实参的值上面过程P调用的的参数传递过程如下图所示。
过程调用前过程调用后a+b=5a=2b=3x=5y=2z=3- 5 -- # -但过程P无法改变实参a的值因此，程序执行后输出 a的值是2所谓传地址是把实在参数的地址传递给相应的形式参数 在过程段中每个形式参数都有一个相应的单元，称为形式单元形式单元将用来存放相应实在参数的地址 过程体对形式参数的任何引用或赋值都被处理成对形式单元的间接访问过程调用前过程调用后过程调用后，形参x的形式单元指向存 a+b值的临时变量的地址， 形参y的形式单元指 向变量a的地址，形参z的形式单元指向变量 b的地址形参通过指针可以间接访问实参执行y：=y+1;后，实在参数的变化：- # -执行z:=z+x;后，实参的变化:- 6 -- # -因此，程序执行后输出 a的值是&所谓得结果是每个形式参数对应两个单元， 第一个单元存放实参的地址， 第二个单元存放实参的值在过程体中对形参的任何引用或赋值都被处理成对第二个形式单元的直接访 问，但在过程工作完成返回之前必须把第二个单元的内容存放到第一个单元所指的那个实参 单元之中过程调用前过程调用后- # -- # -执行y:=y+1;后，实参和的形参的变化:- # -执行z:=z+x;后，实参和的形参的变化:过程工作完成返回之前必须把第二个单元的内容存放到第一个单元所指的那个实参单 元之中。
实参和的形参的变化:因此，程序执行后输出 a的值是74)所谓传名是在进入调用段之前不对实在参数预先进行计值， 而是过程中每当使用到相应的形参时才对它实行计值因此 ，在实现时通常都把实参处理成型个子程 (称为参数子程序),每当过程体中使用到相应形参时就调用这个子程序因此，过程体执行 y:=y+1;语句，实现时处理成为：a=a+1;过程体执行z:=z+x;语句，实现时处理成为:a=a+(a+b);执行上述两语句后，a的值是9因此，程序执行后输出 a的值是9综上所述程序执行时 a的输出：(1) 传值： 2(2) 传地址：8(3) 得结果：7⑷传名： 95. 已知文法G[S]St S*aP | aP | *aPPt +aP | +a(1) 将文法G[S]改写为LL(1)文法G?[S];⑵ 构造文法G?S]的预测分析表解答构造文法的预测分析表，通常应当按下列步骤进行：(1) 消除文法的左递归(2) 对消除左递归后的文法，提取左公因子3) 对经过上述改造后的文法，计算它的每个非终结符的 FIRST和FOLLOW集合4) 根据FIRST和FOLLOW集合构造预测分析表消除直接左递归方法：假设关于非终结符 P的规则为Pt Pa | 3其中，3不以p打头。
把p的规则改写为如下非直接左递归形式：Pt 3 P ?Pt a P ?| ；文法G[S]消除直接左递归方法后，文法变为 G?S]:STa PS? | *cPS?S?t *aPS? | &Pt +aP|+a提公共左因子的方法：假设关于非终结符 A的规则为At § 3 1| 5 3 2|…| S 3 n| y 1| 丫 2| …| 丫 m其中，每个丫不以§开头把A的规则改写为如下形式：At a A?| y 1| Y 2|…| 丫 mA?t 3 1| 3 2|…13 n于是，文法 G?(S)提公共左因子后，文法变为 G??S]STa PS? | *cPS?S?f*aPS? | £Pt +aP?P?t P | £计算每个非终结符的 FIRST和FOLLOW 集合:a.计算非终结符X的FIRST方法：(1) 若有产生式 X—；a…,则把a加入到FIRST(X)中；(2) 若X》；也是一条产生式，则把；也加到FIRST(X)中；(3) 若X—；丫…是一个产生式且 Y-VN，则把FIRST(Y)中的所有非：元素都加到FIRST(X) 中；若X >Y1Y2-YK 是一个产生式，Y1,Y2,…,Yi -1都是非终结符，而且，对于任何 j, 1 Wjw i-1,FIRST(Yj)都含有，则把FIRST(Yj)中的所有非；元素都加到FIRST(X)中；特别是，若所有的 FIRST(Yj)( j=1,2, …,K均含有"则把；加到FRIST(X)中。
根据计算非终结符的FIRST(S)={a , *} FIRST(S ?={*} FIRST(P)={+} FIRST (P?={} 根据计算非终结符的FIRST(S)={a , *}FIRST(S?={* , 4 FIRST(P)={+} FIRST (P?={ 4 根据计算非终结符的FIRST方法的第一点，有FIRST方法的 第二点，有FIRST方法的第三点，有FIRST(S)={a , *}FIRST(S?={* , 4FIRST(P)={+}FIRST (P?={+ , 4b.计算非终结符X的FOLLOW方法：(1) 对于文法的开始符号 S,置#于FOLLOW(S)中；(2) .若At a BB是一个产生式，则把 FIRST( 3 )\{ }加至FOLLOW(B)中；(3) 若At a B是一个产生式，或At a B 3是一个产生式而 3」(即「FIRST( 3 ))，则把 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的每个产生式At :执行第二步和第三步；⑵对每个终结符 a FIRST(：)，把At 加至M[A,a]中；⑶若；■ FIRST(：)，则对任何 b FOLLOW(A)，把At :.加至 \[[A,b] 中;(4) 把所有无定义的M[A,a]标上出错标志” 构造预测分析表方法如下：*+a#SSt *a PS?Sra PS?S?S?t *aPS?S?t£PPt +aP?P?P?t£P?t pP?t£6. 设文法G(S):St (T) | aS | aTt t,S | S⑴消除左递归和提公共左因子；⑵ 构造相应的FIRST和FOLLOW 集合；⑶构造预测分析表。
解答(1) 消除左递归和提公共左因子，文法变为 G?S]S t (L) | aS?S?t s | £Lt SL?L?t ,SL? | £此文法没有公共左因子(2) 构造相应的 FIRST和FOLLOW 集合FIRST(S)={a , (}FIRST(S?)={a , (, s}FIRST(L)={a, (}FIRST(L?)={,, s}FOLLOW(S)={,, ), #}FOLLOW(S?)={,, ), #}FOLLOW(L)={ )}FOLLOW(L?)={ )}(3)构造预测分析表()a#SS t (L)S t aS?S?S?t sS?t £S?t sS?T £S?T £LL t SL?L t SL?L?t ,sl?L?L?T £7. 设文法G[S]S >(A)S j aA —• A+SA ■■ 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,，贝U a FIRSTVT(P)；若有 a FIRSTVT(Q)，且有产生式 P—；Q,，贝U a FIRSTVT(P)2) 构造LASTVT 集合若有产生式 P—；, a或 P >, aQ,贝U a LASTVT(P);若有 a LASTVT(Q)，且有产生式 P—；, Q,贝U a LASTVT(P)对于文法G[S]，构造它的每个非终结符的 FIRSTVT和LASTVT集合：FIRSTVT(S)={a, ( }FIRSTVT(A)={+, a, ( }LASTVT(S)={a, )}LASTVT(A)={+, a, )}构造算符优先关系表方法：(1),=,关系直接看产生式的右部，若出现了P t…ab…或P t…aQb,贝V a=b⑵?<,关系求出每个非终结符 P的FIRSTVT(P)若 Pt …aR…，则一b€ FIRSTVT(R) , a?关系求出每个非终结符 P的LASTVT(P)若 Pt …Rb…，贝y -a€ LASTVT(B) , a>b对于文法G[S]，构造它的算符优先关系表如下：a+r ()「a>>+<><>(<<<=)>>8. 设文法G( S):St T|SvTTt u |T 人 UU t i |-U(1) 计算 FIRSTVT 和 LASTVT ;(2) 构造优先关系表。
解答(1) 对于文法 G[S]，构造它的每个非终结符的 FIRSTVT和LASTVT集合FIRSTVT(S)={ V, A, i, - }FIRSTVT(T)={ A, i, -}FIRSTVT(U)={i, -}LASTVT(S)={ V, A, i, - }LASTVT(T)={ A, i, -}LASTVT(U)={i, -}(2) 构造优先关系表iVA-S.>.>VV..>V.V.AV..>.>V.-V..>.>V.9. 下面映射if语句的文法G[S]是算符优先文法吗？如果是，则构造算符优先关系表如果 不是，则说明理由G[S]S》iBtSS—； iBtSeSS > aB >b解答对于文法G[S]，它是一个二义性文法因为存在句子 ibtibtaea有两个不同的最左推导S ： iBtS ： ibtS二 ibtiBtSeS二 ibtibtSeS二 ibtibtaeS二 ibtibtaeaS : iBtSeS : ibtSeS : ibt iBtSeS二 ibtibtSeS ： ibtibtaeS= ibtibtaea由于算符优先文法一定不是二义性文法，所以文法 G[S]不是算符优先文法。
10. 设有如下的基本块T1:=A+BT2:=5M:=T2*4T3:=C-DT4:=M+T3L:=T1*T3T4:=A+BN:=T4（1） 画出该基本块的（2） 假设只有L，MDAG 图；和N在基本块之后还要引用，与出优化后的四兀式序列解答在构造基本块的 DAG图时，必须注意两个方面：一是对于已知的常量要进行计算；二 是对同一变量进行多次定值时，最后一次定值是基本块中该变量的最终变量 由于基本块有语句T2 : =5，可知T2是已知量所以，语句 M : =T2 * 4可计算出 M的值来，即，M也 转为常量（M = 20 ）一方面，变量 T4进行了两次操作，基本块执行完时，最后一次给 T4的定才是T4的最终结果活跃信息是针对变量而言的如果一个变量在基本块之后不再被 引用，则称该变量是非活跃的（或称为非活跃变量），反之称之为活跃的（或称为活跃变量） 变量的活跃信息对代码优化和代码生成都有非常重要的指导意义当DAG图构造出来后，根据题目所给的条件从 DAG图中计算出活跃变量的结果即可本是中只要计算出变量 L、M和N的结果就行了基本块对应的DAG图如下：n3Ln3T3n3n3T1,T4,N+T2n1n2Mn6n4n5n7按照构造其结点的顺序，重新写成四元式序列 G?T1=A+BT4=T1N=T4T2=5M=20T3=C-DL=T1*T3由于只有L, M和N在基本块之后还要引用,T1、T2、T3和T4都不会引用，于是重新写出优化后的四元式序列为:N:=A+BM:=20T3:=C-DL:=N*T311.把语句while a>0A b>0 doif x>ythe n b:=b-1else a:=a-1;翻译为四兀式序列。
解答对于这类题目，关键是准确掌握语句的语动作while-do语句的语义动作if-the n-else语句的语义动作作为条件控制的布尔式的翻译:把A or B解释成把A and B解释成把n ot A解释成布尔表达式赋予两种 出口” ：一是 真"出口;if A then true else Bif A then B else falseif A then false else true•是假”出假设四元式序列从100开始编号表达式 a>0 翻译为：100 （j> ， a， 0，_）101 （j，_，_，_）继续翻译表达式 a>0 A b>0,由于是与运算，100号语句应转跳到102号语句，102号语 句为“真”出口， 101 号语句和 103 号语句为“假”出，四元式序列为：100 （j>， a， 0， 102）101 （j ， _， _， _）102 （j>， b， 0， _）103 （j ， _， _， _） 继续翻译语句 while a>0 A b>0 doif 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 中的第一个四元式 标号， “假”出口为 1 05号语句， 应转跳到 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]及相应翻译方案St aAb{print“1”}St a{pri nt“ 2”}At as{pri nt“ 3”}At c{print“ 4 ”}输入acab,输出是什么?解答对于这类题目，首先画出句子 acab对应的语法树。
每当用一个产生式归约时，则执行相应的语义动作句子 acab对应的语法树为：S第一个归约的产生式是 第二个归约的产生式是 第三个归约的产生式是A^c，它相应的语义动作为 print 所以，产生输出 4S^a，它相应的语义动作为 print 2” 产生输出2At AS，它相应的语义动作为 print 3”产生输出3最后归约的产生式是St aAb，它相应的语义动作为print 1” 产生输出1 18 -因此，输入 acab,输出是4231 # -。