编译原理题库综合题.doc

编译原理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完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。 其SLR(1)分析表为： 对输入串ab#给出分析过程为： 构造下述文法 G[S] 的自动机： 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次输入0的重复输入，所以上图只是NFA，下面将它确定化： 下表由子集法将NFA转换为DFA: 由上表可知DFA为：S → L=R | R L → *R | id R → L 请构造非终结符的FIRST和FOLLOW集合。（5分） 构造该文法的LL(1)分析表。该文法是LL(1)文法吗？（15分 7. （20分）考虑以下文法： S → A A → BA | ε B → aB| b 证明该文法是LR（1）的。 (1)证明它是LR(1)文法； (2)构造它的LR(1)分析表。 7．（20分）阅读下面的LEX程序，并回答： （1）该程序完成了什么功能？ （2）修改该程序，使之能够计算输入的标识符个数。（直接改在试题上） LEX程序如下： %{ # include stdio.h int num_int = 0; int num_float = 0; int num_line = 0; int num_id = 0; %} digit [0-9] integer [+\-]?{digit}+ flt [+\-]?{digit}+\.{digit}+ letter [a-zA-z] id {letter}({letter}|{digit})* %% {integer} num_int++ ; {flt} num_float++ ; \n num_line++ ; . ; {id} num_id++; %% main() { yylex() ; 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，可得到=(FOLLOW(L)； 又根据S → L=R | R，可得到FOLLOW(S)(FOLLOW(L)； 又根据L → *R，可得到FOLLOW(L)(FOLLOW(R)； 又根据R → L，可得到FOLLOW(R)(FOLLOW(L)； 所以有FOLLOW(S)={$}，FOLLOW{L}= FOLLOW{R}={$, =}。 (2) 构造LL(1)分析表如下： * = id $ S S → L=R S → R S → L=R S → R L L → *R L → id R R → L R → L 由于分析的表目中存在冲突，该文法不是LL(1)文法。 7. （20分）考虑以下文法： S → A A → BA | ε B → aB| b 证明该文法是LR（1）的。 (1)证明它是LR(1)文法； (2)构造它的LR(1)分析表； 7答：该程序完成的功能：计算整数、浮点数的个数，统计行数，并分别输出。 修改见程序。 编译原理D卷 7、证明下面文法是SLR(1)但不是LR(0)的。 S→A A→Ab∣bB