编译原理样卷及答案
- 格式：doc
- 大小：2.94 MB
- 文档页数：7
. . . .
. 资料. .. .
一、简答题（每题4分，共24分）
1、 构造一个文法G，使得：L(G)={(m)m|m>0}
解答：G[S]: s-> ()|(S)
2、 构造一个正规式，它接受={0，1}上符合以下规则的字符串： 串有且只有2个1的0、
1字符串全体。
解答：0*10*10*
3、 消除文法G[S]中的直接左递归和回溯
S→ (L) | aS | a
L→ L，S | S
解答：
S→ (L) | aS'
S'→ S |ε
L→ S L'
L'→，S L'|ε
4、 文法G[S]是乔姆斯基几型文法？
S → ABS | AB
AB → BA
A → 0
B → 1
解答：1型文法/上下文有关文法
5、按Thmopson算法构造与正则表达式 (1*|0) *等价的NFA。
解答：略
6、设计一个状态转换图，其描述的语言规则为：如果以a开头，则其后是由a、b组成的
任意符号串；如果以b开头，则其后是至少包含一个a的由a、b组成的任意符号串。
解答：略
二、（本题10分）对于文法G[E]：
. . . .
. 资料. .. .
E→ET+|T
T→TF* | F
F→F^ | a
(1) 给出句子FF^^*的最左推导和语法树；
(2) 给出句子FF^^*的短语、直接短语和句柄。
解答： (1) 2分： 句子FF^^*的最左推导 2分： 句子FF^^*的语法树
E=>T=>TF*=>FF*=>FF^*=>FF^^*
(2) 3分:句子FF^^*的短语
FF^^*、FF^^*、F、F^、F^^
2分:句子FF^^*的直接短语
F、F^
1分:句子FF^^*的句柄
F
三、（本题15分）构造与下列NFA等价的最小化DFA。
解答：（1）10分：构造与NFA等价的DFA
. . . .
. 资料. .. .
（2）5分：对DFA最小化
首先，将所有的状态集合分成子集： k1={0,1,2,4} k2={3,5}
四、（本题15分）对下列文法G[S]：
s→eT|RT
T→DR|ε
R→dR|ε
D→a|bd
(1) 写出文法G[S]每个非终结符的FIRST集和FOLLOW集；
(2) 判断文法G[S]是否LL(1)文法（注：必须给出判断过程，否则不得分）；
(3) 写出文法文法G[S]的预测分析表。
解答：（1）8分：每个First集合和FOLLOW集合各1分
. . . .
. 资料. .. .
(2) 2分： 判断文法G[S]是LL(1)文法。
对于产生式s→eT|RT：FIRST(eT)∩FIRST(RT)- ε={e}∩{a,b,d}=Φ
FIRST(eT)∩FOLLOW(S)={e}∩{#}=Φ
对于产生式T→DR|ε： FIRST(DR)∩FOLLOW(T)={a,b}∩{#}=Φ`
对于产生式R→dR|ε： FIRST(dR)∩FOLLOW(R)={d}∩{a,b,#}=Φ
对于产生式D→a|bd： FIRST(a)∩FIRST(bd)={a}∩{b}=Φ
所以，对于文法G[S]是LL(1)文法。
(3) 5分：文法G[S]的预测分析表。
五、（本题18分）已知文法G[S]：
S → r D
D → D ，i | i
(1) 画出识别文法活前缀的完整DFA，并判断该文法是否LR(0)文法(必须说明判断依据)；
(2)构造该文法的SLR(1)分析表，并判断该文法是否SLR(1)文法(必须说明判断依据)。
解答：
(1) 8分：画出识别文法活前缀的完整DFA
FIRST集 FOLLOW集
s→eT |RT { e } { a, b, d, ε} #
T→DR |ε {a, b} { ε} #
R→dR |ε { d } { ε} a,b,#
D→a |bd { a} { b} D,#
. . . .
. 资料. .. .
文法拓展并对产生式编号：
（0）S' →S （1）S → r D （2）D → D ，i （3）D → i
(2) 2分：判断该文法不是LR(0)文法
对于状态3，项目集中存在“移进-规约”冲突，所以该文法不是LR(0)文法。
(3) 6分：构造该文法的SLR(1)分析表
状态
ACTION GOTO
r ， i # S D
0 S2 1
1 acc
2 S4 3
3 S5 r1
4 r3 r3
5 S6
6 r2 r2
(4) 2分：判断文法是SLR(1)分析表
回答1： 因为SLR(1)分析表不存在冲突，所以文法是SLR(1)分析表。
回答2： 对于状态3， FOLLOW(S)∩{,}=(#)∩{,}=Ф，“移进-规约”冲突可以用
SLR(1)方法解决，所以文法是SLR(1)分析表。
六、（本题8分）文法G[E]的LR分析表如下图所示：
(1) E →E+T (2) E →T (3)T →T*F
(4) T →F (5) F →(E) (6)F →i
写出对输入串 i * i + i的LR分析过程 (即状态，符号，输入串的变化过程)。
. . . .
. 资料. .. .
解答:
七、（本题10分）写出下列语句的四元式序列
if(y>z && (c
while(a>b)
x=x+y*a;
else
. . . .
. 资料. .. .
m=m+n;
解答：
1 (j>, y, z, 3)
2 (j , -,-, 13)
3 (j<,c,d, 7)
4 (j,-,-, 5)
5 (j>,m,n, 7)
6 (j,-,-, 13)
7 (j>,a,b, 9)
8 (j,-,-,13/16)
9 (*,y,a,t0)
10 (+,x,t0,t1)
11 (=,t1,-,x)
12 (j,-,-, 7)
13 (j,-,-, 16)
14 (-,x,1,t5)
15 (=,t5,-,x)
16 ..........
