资源描述：
《编译原理题库-综合题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理A卷已知文法A->aAd
2、aAb
3、ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有：S'->AA->aAd
4、aAb
5、ε下面构造它的LR(0)项目集规范族为：从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可
6、以解决的，因此该文法是SLR(1)文法。其SLR(1)分析表为：对输入串ab#给出分析过程为：编译原理B卷构造下述文法G[S]的自动机：S->A0A->A0
7、S1
8、0该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式S->A0，A->A0
9、S1中没有字符集VT的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0
10、A01
11、0=A(0
12、01)
13、0=0(0
14、01)*。代入S->A0有该文法的正规式：0(0
15、01)*0，所以，改写该文法为确定的自动机为：由于状态A有
16、3次输入0的重复输入，所以上图只是NFA，下面将它确定化：下表由子集法将NFA转换为DFA:由上表可知DFA为：编译原理C卷6．(20分)已知上下文无关文法：S→L=R
17、RL→*R
18、idR→L(1)请构造非终结符的FIRST和FOLLOW集合。（5分）(2)构造该文法的LL(1)分析表。该文法是LL(1)文法吗？（15分7.（20分）考虑以下文法：S→AA→BA
19、εB→aB
20、b证明该文法是LR（1）的。(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表。7．（20分）阅读下面的LEX程序，并回答：（1）该程序完成了什么功能？（2）
21、修改该程序，使之能够计算输入的标识符个数。（直接改在试题上）LEX程序如下：%{#includeintnum_int=0;intnum_float=0;intnum_line=0;intnum_id=0;%}digit[0-9]integer[+-]?{digit}+flt[+-]?{digit}+.{digit}+letter[a-zA-z]id{letter}({letter}
22、{digit})*%%{integer}num_int++;{flt}num_float++;num_line++;.;{id}nu
23、m_id++;%%main(){yylex();printf(“%dintegers,%dfloatingpointnumbers,%dlines,%didentifiers.”,num_int,num_float,num_line,num_id);}C卷答案6解：(1)根据L→*R
24、id，可得到FIRST(L)={*,id}；根据R→L，可得到FIRST(R)=FIRST(L)={*,id}；根据S→L=R
25、R，可得到FIRST(S)=FIRST(L)ÈFIRST(R)={*,id}；S是开始符号，所以有$ÎFOLLOW(S)；又
26、根据S→L=R，可得到=ÎFOLLOW(L)；又根据S→L=R
27、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$SS→L=RS→RS→L=RS→RLL→*RL→idRR→LR→L由于分析的表目中存在冲突，该文法不是LL(1)文法。7.（20分）考虑以下文法：S→AA→BA
28、εB→aB
29、b证明该
30、文法是LR（1）的。(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表；7答：该程序完成的功能：计算整数、浮点数的个数，统计行数，并分别输出。修改见程序。编译原理D卷7、证明下面文法是SLR(1)但不是LR(0)的。S→AA→Ab∣bBaB→aAc∣a∣aAb8、证明下面的文法是LL(1)的但不是SLR(1)的。S→AaAb∣BbBaA→εB→ε1.构造表达式（4*7+1）*2的附注语法树。四、（20分）设文法G[S]为SaAcB问：1、该文法是否为算符文法，为什么？AAb
31、b2、构造算符优先关系表。Bd3、该文法是否可改造为LL
32、（1）文法，为什么？五、（本题20分）设文法G为：EeAf
33、eBgAaA
34、aBBb
35、a对于输入串eaaaf，采用LR（0）、LL（1）、SLR（1）等方法中合适的一种进行分析。六
