《编译原理题库——综合题》由会员分享，可在线阅读，更多相关《编译原理题库——综合题（107页珍藏版）》请在金锄头文库上搜索。
1、第 1 页共 6 页编译原理 A 卷已知文法 A-aAd|aAb| 判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。解：增加一个非终结符 S/后，产生原文法的增广文法有： S-A A-aAd|aAb| 下面构造它的 LR(0)项目集规范族为： 从上表可看出,状态 I0 和 I2 存在移进-归约冲突，该文法不是 LR(0)文法。对于 I0 来说有：FOLLOW(A)a=b,d,#a=，所以在 I0 状态下面临输入符号为 a 时移进，为 b,d,#时归约，为其他时报错。对于I2 来说有也有与 I0 完全相同的结论。这就是说，以上的移进 -归约冲突是可以解
2、决的，因此该文法是SLR(1)文法。 其 SLR(1)分析表为： 第 2 页共 6 页对输入串 ab#给出分析过程为： 编译原理 B 卷构造下述文法 GS 的自动机： S-A0 A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式 S-A0，A-A0|S1 中没有字符集 VT 的输入，所以不是确定的自动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把 S?A0 代入产生式 A?S1 有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入 S-A0 有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为：由于状态 A 有
3、 3 次输入 0 的重复输入，所以上图只是 NFA，下面将它确定化： 下表由子集法将 NFA 转换为 DFA:第 3 页共 6 页由上表可知 DFA 为：编译原理 C 卷6(20 分)已知上下文无关文法：S L=R | RL *R | idR L(1) 请构造非终结符的 FIRST 和 FOLLOW 集合。 （5 分）(2) 构造该文法的 LL(1)分析表。该文法是 LL(1)文法吗？（15 分7. （20 分）考虑以下文法：S AA BA | B aB| b证明该文法是 LR（1）的。(1)证明它是 LR(1)文法；(2)构造它的 LR(1)分析表。7（20 分）阅读下面的 LEX 程序，并
4、回答：（1）该程序完成了什么功能？（2）修改该程序，使之能够计算输入的标识符个数。（直接改在试题上）LEX程序如下：%# include int num_int = 0;int num_float = 0;第 4 页共 6 页int num_line = 0;int num_id = 0;%digit 0-9integer +-?digit+flt +-?digit+.digit+letter a-zA-zid letter(letter|digit)*%integer num_int+ ;flt num_float+ ;n num_line+ ;. ;id num_id+;%main()yy
5、lex() ;printf(“n%d integers, %d floating point numbers, %d lines, %d identifiers.n”,num_int, num_float, num_line, num_id) ;C 卷答案6 解：(1) 根据 L *R | id，可得到 FIRST(L)=*, id；根据 R L，可得到 FIRST(R)= FIRST(L)=*, id；根据 S L =R | R，可得到 FIRST(S)= FIRST(L) FIRST(R)=*, id；S 是开始符号，所以有$ FOLLOW(S)；又根据 S L =R，可得到= FOLLO
6、W(L)；又根据 S L =R | R，可得到 FOLLOW(S)FOLLOW(L)；又根据 L *R，可得到 FOLLOW(L)FOLLOW(R)；又根据 R L，可得到 FOLLOW(R)FOLLOW(L)；所以有 FOLLOW(S)=$，FOLLOWL= FOLLOWR=$, =。(2) 构造 LL(1)分析表如下：* = id $第 5 页共 6 页S S L =RS RS L =RS RL L *R L idR R L R L由于分析的表目中存在冲突，该文法不是 LL(1)文法。7. （20 分）考虑以下文法：S AA BA | B aB| b证明该文法是 LR（1）的。(1)证明它
7、是 LR(1)文法；(2)构造它的 LR(1)分析表；第 6 页共 6 页7答：该程序完成的功能：计算整数、浮点数的个数，统计行数，并分别输出。修改见程序。编译原理 D 卷7、证明下面文法是 SLR(1)但不是 LR(0)的。S A第 7 页共 6 页AAbbBaBaAc aaAb8、证明下面的文法是 LL(1)的但不是 SLR(1)的。S AaAb BbBaAB1.构造表达式（4*7+1 ）*2 的附注语法树。四、 （20 分）设文法 GS为S aAcB 问：1、该文法是否为算符文法，为什么？A Ab|b 2、构造算符优先关系表。B d 3、该文法是否可改造为 LL（1）文法，为什么？五、
8、（本题 20 分）设文法 G 为： E eAf|eBgA aA|aB Bb|a对于输入串 eaaaf，采用 LR（0） 、LL（1） 、SLR（1）等方法中合适的一种进行分析。六、 （25 分）有作控制用的布尔表达式文法 GE及其语义动作如下：1、 构造 SLR（1）分析表（若不是 SLR(1)）的，则说明理由）2、 分析布尔式 abb c d # f then s1 else s23、有正规文法 GS： (12 分)SaA|bB AbS|b BaS|a (1)构造对应的正规式 R，使得 L(R)=L(G)。 (3 分)(2)构造对应的 NFA 状态图，使得 L(M)=L(R)。 (3 分)(
9、3)将所得 NFA 确定化为 DFA。 (3 分)(4)将所得 DFA 最小化。 (3 分)4、对表达式文法 GE： (16 分)E E - TT T T FF F ( E )a(1)判断 GE是否为 LL(1)文法。若不是，改造为 LL(1)文法。(8 分)(2)构造预测分析表，并对输入串 w=a-aa#进行预测分析。(8 分)三、应用题参考答案（共 50 分）1、 （1 ）证明(3 分)：因为存在推导序列：E=T+E=T+T+E=T+T*F+E=T+T*F+T=T+T*F+F=T+T*F+i，即有 E=*T+T*F+i 成立，所以，T+T*F+i 是文法的一个句型。（2）语法树（3 分）：
10、第 15 页共 6 页（3）句型分析（7 分）：该句型相对于 E 的短语：T+T*F+i、T*F+i 和 i ；相对于 T 的短语有：T*F 和i，相对于 F 的短语有 i。相对于 TT*F 的直接短语：T*F,相对于 Fi 的直接短语：i。句柄：T*F 。(4) 该句型的所有素短语：T*F 和 I；T*F 为最左素短语。(3 分)2、if af then s1 else s2 生成的三地址代码/ 四元式序列如下：(6 分)(1) if a f goto (7)(6) goto (p+1)(7) s1 对应的四元式序列(p) goto (q)(p+1) s2 对应的四元式序列(q)3、(1)
11、代入后有 S 的规则右部 =a（bS|b）|b(aS|a)=ab（S|）|ba（S|）=（ab|ba） （S|）,故对应的正规式 R=(ab|ba)(ab|ba)* 。 (3 分)(2)对应的 NFA 状态图如下左图所示： (3 分)(3)将所得 NFA 确定化为 DFA 状态图如上右图所示： (3 分)(4)将所得 DFA 最小化：首先根据是否终态划分为非终态集 P1=S,A,B和终态集 P2=Z；然后对 P1 根据 a 弧划分为 P11=S,P12=A，P13=B。可见原 DFA 已是最小化的 DFA。 (3 分)4、 (1)计算 GE的 SELECT 集如下：(2 分)SELECT(E
12、E T )=(，a SELECT(E T )=(，aSELECT(T T F)=(，a SELECT(T F)=(，aSELECT(F ( E )=( SELECT(F a)=a 由于 SELECT(E E T ) SELECT(E T )=(，a；SELECT(T T F) SELECT(T F)=(，a；SELECT (F ( E )SELECT (F a) = (a =故 GE不是 LL(1) 文法。(1 分)对 GE的 E E T 和 T T F 两条规则消除左递归后变为： (2 分)ET E E T E| T F T T F T F ( E )a计算消除左递归后 GE的 SELECT
13、 集如下：(2 分)SELECT(E T E)=(，a SELECT(E T E)= SELECT(E)=#，) SELECT(T F T)=(，aSELECT(T F T)= SELECT(T)= ，# ，)SELECT(F( E )=( SELECT(Fa)=a第 16 页共 6 页由于 SELECT(E T E)SELECT (E) =SELECT (T F T) SELECT (T) =SELECT (F ( E )SELECT (F a) = =故消除左递归后的 GE是 LL(1) 文法。(1 分)（2）根据消除左递归后的 GE的 SELECT 集构造预测分析表如下：(3 分)对输入
14、串 w=a-aa#的分析过程如下表所示（注意：规则右部以逆序入栈）：(5 分)二、设=0 ，1上的正规集 S 由倒数第二个字符为 1 的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的 DFA。(8 分)三、写一个文法使其语言为 L(G)= anbmambn | m,n1。(6 分)四、对于文法 G(E): (8 分)ET|E+TTF|T*FF(E)|i1. 写出句型(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄和素短语。 ETF( E )E + TFiTT * F第 17 页共 6 页五、设文法 G(S)：(12 分)(|*)BA|Si1 构
15、造各非终结符的 FIRSTVT 和 LASTVT 集合；2 构造优先关系表和优先函数。(12 分)六、设某语言的 do-while 语句的语法形式为 (9 分)S do S(1) While E其语义解释为：针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作.七、(8 分)将语句if (A0) then while C0 do C:=C+D翻译成四元式。(8 分)八、(10 分) 设有基本块如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)画出 DAG
