明了多少个id。 48．识别文法G的活前缀的DFA如下图所示，补充完成状态I2和I5，然后根据该图构造SLR（1）分析表。
G：(0) P'→P (1) P→aPb (2) P→Q (3) Q→bQc
(4) Q→bSc (5) S→Sa (6) S→a
P I1 :P'→P. I2 : I4 :P→aPI0 :P'→.P a P P→.aPb b P→.Q I7 :P→aP a Q→.bQc b Q→.bSc I8 :Q→bQ Q b 图1 Q I5 : c I3 :P→Q. I9 :Q→bQ Q 43．给出表达式-a*b+b*c+d/e的语法树和三
b 元式序列。 I10 :Q→bS S 44．证明下面文法S→AaAb|BbBa A→ε I6 : S→a. S→S.a a B→ε，是LL（1）文法，但不是SLR（1）
c 文法。 I11 :Q→bS a 45．现有文法G[S] I12 : S→Sa. S→a|ε|(T) T→T,S|S 请给出句子（a,(a,a)）的最左、最右推 导，并指出最右推导中每一个句型的句柄。 46．将下图的DFA最小化。 49．给出表达式（a+b）*(c+d/e)的语法树
和四元式序列。
1 a b 50．构造文法S→AaAb|BbBa A→ε Bb a →ε，的预测分析表。 0 3 4 a
b b a b 2 51．写出C语言标识符集（字母或下划线开
头的由字母、数字、下划线构成的串）的正a 规式。 47．设有如下文法：P→D 53．假设第一个四元式的序号是100，写出
D→D；D|id：T|proc id；布尔表达式a
D； 54．设有如下文法：
T→real|integer G[E]：E→EWT|T
给出一个语法制导定义，打印该程序一共声 T→T/F|F
16
F→（E）|a|b|c W→+|-
证明符号串a/(b-c)是句子。
55．对于下列文法 G[S]： S→Sb|bA A→aA|a （1）构造一个与G等价的LL（1）文法G′。 （2）对于文法G′,构造相应的LL（1）分析表。
56．构造下述文法的SLR（1）分析表。
G[S]：S→（A） A→ABB|B B→b 58．写出赋值语句X= -(a+b)/(c-d)-(a+b*c)的逆波兰表示。 59．为文法
G[S]：S→（L）|a L→L，S|S
写一语法制导定义，它输出句子中括号嵌套的最大层次数。
60．2．已知文法G[S]如下：构造该文法的LR（0）分析表。
G[S]：S→BB B→aB|b g卷答案 1解：
256aXa1ab3bb4baaYa3aX?1?a?2bY2解：最左推导：N ? ND ? NDD ? DDD ? 5DD ? 56D ? 568
最右推导：N ? ND ? N8 ? ND8? N68 ? D68 ? 568 3解： G[S]：S→aA|bB A→aS|bC|b B→bS|aC|a C→bA|aB|ε
5解： abcd- -*efgh- - i*$$
6解：对于该文法求其FIRST集如下： FIRST(S) = {a, b, c}; FIRST(A) = {a, b, c, d}; FIRST(B) = {a, b, c}。 求其FOLLOW集如下：
FOLLOW(S) = {a, b, c, d, #}; FOLLOW(A) = {a, b, c, d, #}; FOLLOW(B) = {a, b, c, d, #}。
由A → BS | d 得： FIRST(BS) ∩ FIRST(‘d’) = {a, b, c} ∩ {d} = Φ 由B → aA| bS | c 得
FIRST(aA) ∩ FIRST(bS) ∩ FIRST(c) = {a} ∩{b}∩ {c} =Φ
由于文法G[S]不存在形如β→ε的产生式，故无需求解形如FIRST(α) ∩ FOLLOW(A)的值，也即文法G[S]是一个LL(1)文法。
7解：短语：P、P+T、i、E+i、(E+i )、P+T+(E+i )；
直接短语：P、i； 句柄：P；
8解：G[A′]：A→aA′
A′→ABl | ε B→dB′
B′→bB′| ε 1 (j＞,x,y,3) 9解：
2 (j,_,_,5) 3 (=,1,_,m) 4 (j,_,_,6) 5 (=,0,_,m) 6: 10解：
a0b1?2解：
a4b
17
11解：对照自动机的定义M=(S,Σ,f,So,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。 先画出NFA M相应的状态图，如下图所示。 aabb（1）A→aABl （2）A→a （3）B→Bb （4）B→d
I0：S→．A A→．aABl a A→．a I1：S→A． XYb I {x} {y} {x,y} Ia {x,y} — {x,y} Ib I2：A→a．ABl A A→a． A→．aABl A→．a I3： A→aA．Bl dB→．Bb B→．d B {y} {x,y} {x,y} a 将转换矩阵中的所有子集重新命名，形成下表所示的状态转换矩阵，即得到 f 字符 状态 0 1 2 I5： A→aAB．l B→B．b b I7： B→Bb． First（A）={a}follow（A）={#，d} （B）={l} 2 First（B）={d}follow1 — SLR（1）分析表如下：2 2 a b a 0 1 2 3 4 5 6 7 S2 S2 2 b d l R4 S6 R3 # ACC R2 R1
M′=({0,1,2},{a,b},f,0,{1,2})，
M′状态转换图如下图所示。
a 02a, b bb
1
（注意：本题由于集合的命名和先后顺序不同，可能最终结果不同。） 12解：拓广文法 （0）S→A
R2 S4 R1 S7 13 解：1 (j＞,x,y,3) 2 (j,_,_,5) 3 (=,1,_,m) 4 (j,_,_,7) 5 (+,x,y,T1) 6 (=, T1,_,m) 7:
14解：消除左递归：
G(S): S ? (L) | a L ? SL’
18
S L L’
构造FIRST集，如下： 用子集法构造状态转换矩阵，如下表所示。 （1）FIRST(S) = {(, a}
I Ia Ib （2）FIRST(L) = {(, a}
{x} {1} - （3）FIRST(L’) = {,, ε} {1} {2} {3}
{2} {1} - 构造FOLLOW集如下：
{3} - {4} （1）FOLLOW(S) = {#, ,, )} {4} {Y} {5} （2）FOLLOW(L) = {)}
{5} - {4} （3）FOLLOW(L’) = {)} {Y} - -
LL(1)分析表 将状态分为终态集{Y}和非终态集
( ) a , # {X,1,2,3,4,5} S ? (L) S ? a X,1,2,3,4,5｝a={1,2,1,_,Y,_} 因为｛L ? SL’ L ? SL’ 所以非终态集分为{X,1,2},{3,5},{4}
L’ ? L’ 因为 {X,1,2}b={_,3,_},所以分为 ε ? ,SL’ 最后得到集合{X,2},{1},{3,5},{4},{Y}重
新命名为1，2，3，4，5得到最小化的DFA M′17证明： 该文法产生的语言是a的个数和状态转换矩阵和状态转换图如下图所示。 b的个数相等的串的集合。该文法二义，例 如句子abab有两种不同的最左推导。 I Ia Ib 1 2 _ 2 1 3 S?aSbS?abS?abaSbS?ababS?abab 3 - 4
4 5 3 S?aSbS?abSaSbS?abaSbS?ababS?5 - _ abab
（注意：本题由于集合的命名和先后顺序不
18解：100 (j<,a,b,102)
同，可能最终结果不同。）
101 (j,_,_,107)
21解：编译程序的总体框图如下所示：
102 (j>,c,d,104) 103 (j,_,_,106) 词法分析器表出104 (+,y ,z ,t) 单词符号105 (=,t ,_ ,x) 语法分析器格106 (j,_,_,100) 语法单位错语义分析与中间代码107: 生成器19解： 先画出正规式相应的NFA M状态四元式处管图，如下图所示。 优化段 四元式理理2 5 目标代码生成器
a X a 1 a b 3 b b 4 b L’ ? , SL’| ε
a 1 a （1）词法分析器，又称扫描器，它接受a 输入的源程序，对源程序进行词法分析，识Y 别出一个个单词符号，其输出结果是二元式19
目标代码
(单词种别，单词自身的值)流。
（2）语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的句子。
（3）语义分析及中间代码生成器，按照语义规则对语法分析器归约出（或推导出） S ( L ) L , S 的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。
（4）优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。
（5）目标代码生成器，把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件直接相关的机器能识别的语言，即目标程序，才能在机器上运行。
（6）表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断和表格打交道。
（7）出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。 22解：
(1) 句型(S, (a))的语法树如下图所示：
S ( L ) S a
(2) 从语法树中可以找到（3分）
短语：a; (a); S; S,(a); (S, (a))
直接短语： a; S 句柄： S 23解：
S→ ε| aA|bB A→ b| bS| aAA B→ a| aS| bBB 24解：（1）逆波兰式： abc-*@d+ 其中使用@代表一目减运算 （2）四元式： ① (-, b, c, T1) ② (*, a, T1, T2) ③ (@, T2, _, T3) ④ (+, T3, d, T4) 25 解：
(1) (j>, A, B, 3) (2) (j, _, _, 11) (3) (j>, C, D, 5) (4) (j, _, _, 8) (5) (*, Y, Z, T1) (6) (=, T1, _, X) (7) (j, _, _, 1) (8) (+, Y, Z, T2) (9) (=, T2, _, X) (10) (j, _, _, 1) (11) 26解：（1）0*(0|10)*0* 或者 (0|10)* （2）
①NFA （2分）
20