编译原理题库

1、Tiange's reference第一章?什么是编译器？?编译程序的结构分为几个阶段，各阶段的任务是什么？?遍、编译前端及编译后端的含义？?编译程序的生成方式有哪些？第二章?1. 写一文法，使其语言是偶正整数的集合。?要求：（1）允许 0打头 （2） 不允许 0 打头解：（ 1）允许 0 开头的偶正整数集合的文法Et NT|DTt NT|DNtD|1|3|5|7|9Dt0|2|4|6|8（2）不允许 0 开头的偶正整数集合的文法E t NT|DT t FT|GN t D|1|3|5|7|9D t 2|4|6|8F tN|0G tD|02.证明下述文法 G表达式是二义的。表达式 =a|

2、（表达式）| 表达式运算符表达式运算符：=+卜|*|/解：可为句子 a+a*a 构造两个不同的最右推导 :最右推导 1表达式表达式 运算符 表达式表达式 运算符 a表达式 * a表达式 运算符 表达式 * a表达式运算符 a * a表达式 + a * aa + a * a最右推导 2表达式表达式 运算符 表达式表达式 运算符表达式运算符表达式表达式 运算符表达式运算符 a表达式 运算符表达式 * a表达式运算符 a * a表达式 + a * aa + a * a3. 给出生成下述语言的上下文无关文法：（1） anbnambm| n ， m>=0（2） 1n0m1m0n| n ， m>

3、;=0 解： （ 1） anbnambm| n ，m>=0StAAAt aAb| eTiange's reference(2) 1nOmlmOn| n , m>=04 1S0|A 2 0A1| £第三章1、构造一个DFA它接收刀=a, b上所有满足下述条件的字符串：字符串中的每个a都有至少一个b直接跟在其右边。解:(b*abb*)*已知刀=a, b，根据题意得出相应的的正规式为: 根据正规式画出相应的DFA M如下图所示用子集法将其确定化Xa2341b65IIaIbX,1,2,3,Y42,345,6,1,2,3,Y|2,342,35,6,1,2,3,Y46,1,2

4、,3,Y6,1,2,3,Y46,1,2,3,YIIaIb0121一3212314414由DFA得状态图 顺序重新命名DFA M第四章练习1 :文法GV:V t N|NE E t V|V+E是否为LL(1)文法，如不是，如何将其改造成LL(1)文法。解:LL(1)文法的基本条件是不含左递归和回溯(公共左因子)，而GV中含有回溯，所以先消Tiange's referenceV ' t£ |E 't£ |+E除回溯得到文法 G V:G ' V :V t NVE t VE' ENt i由LL(1)文法的充要条件可证G V是LL(1)文法练习2

5、:有文法 Gs:S t ba A t BS|d B t aA|bS|c (1)证明文法G是LL(1)文法。 构造LL(1)分析表。A的任何两个不同产生式ATa |(3) 写出句子adccd的分析过程解：(1) 一个LL(1)文法的充要条件是：对每一个非终结符有下面的条件成立: FIRST( a ) A FIRST( 3 )=;若 B * s ,则有 FIRST( a ) A FOLLOW(A) 对于文法Gs:S t ba a t BS|d Bt aA|bS|c其FIRST集如下：FIRST(B)=a, b, c; FIRST(A)=a, b, c, d; FIRST(S)=a, b, c。其F

6、OLLOW如下：首先，FOLLOW(S)=#;对 St BA有：FIRST(A) s 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ;对 At BS有：FIRST(S) s 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ;对 Bt aA 有：FOLLOW(B加入 FOLLOW(A),即 FOLLOW(A)=a, b, c, d ;对 Bt bS 有：FOLLOW(B加入 FOLLOW(S),即 FOLLOW(S)=#, a, b, c, d ;由 At BS|d 得：FIRST(BS)A FIRST(d) = a, b, c A d=;由 Bt aA|bS|c 得：FIRST(aA)A FIRST(bS) A FIRST(c) =a A b A c=。由于文法Gs不存在形如3Ts的产生式，故无需求解形如FIRST( a ) A FOLLOW(A的值。也即，文法 GS是一个LL(1)文法。(2)由 Gs:S t BAA t BS|d B t aA|bS|c的FIRST(B)=a, b, c;FOLLOW(B)=a, b, c, d ;FIRST(A)=a, b, c, d;FOLLOW(A)=a, b, c, d ;FIRST(S)=a, b, c。 FOLLOW(S)=#, a, b, c, d 可构造LL(1)预测分析表