-
编译原理
A
简要说明语义分析的基本功能。
2.
考虑文法
G[S]:
S →
(T) | a+S | a
T → T,S | S
消除文法的左递归及提取公共左因子。
3
试为表达式
w+(a+b)*(c+d/(e-10)+8)
写
出相应的逆波兰表示。
4.
按照三种基本控制结构文法将下面的语
< br>句翻译成四元式序列：
、 分别对应 <
br>∧
：S→aSb|Sb|b，对句子 0
while (A
∧
B
{
if (A ≥ 1) C=C+1;
else while (A ≤ D)
A=A+2;
}
。
5.
已知文法
G[S]
为
S
→
aSb|Sb|b
，试
证明文法
G[S]
为二义文法。
A
答案
1<
/p>
答：
语义分析的基本功能包括
:
确定类型、
类型检查、
语义处理和某些静态语
义检
查。
2
解：消除文法
G[S]
的左递归：<
/p>
S→(T) | a+S | a
T→ST′
T′→,ST′| ε
提取公共左因子：
S→(T) | aS′
S′→+S | ε
1.
T→ST′
T′→,ST′| ε
3
答：
w a b + c d e
10 - / + 8 + * +
4
答：该语句的四元式序
列如下
(
其中
E1
E2
和
E3
A
＜
C
B
＜
D
、
A≥1
和
A≤D，
并且关系运算符优先级高
)
：
100 (j<,A,C,102)
101
(j,_,_,113)
102 (j<,B,D,104)
103 (j,_,_,113)
104
(j=,A,1,106)
105 (j,_,_,108)
106 (+, C, 1, C)
107
(j,_,_,112)
108 (j≤,A,D,110)
109 (j,_,_,112)
110 (+, A, 2, A)
111
(j,_,_,108)
112 (j,_,_,100)
113
5
答：证明：
由文法
G[S]
aabbbb
对应的两棵
语法树为：
因此，文法
G[S]
为二义文法。
编译原理
B
什么是句子？
什么是语言
?
2.
写一文法，
使其语言是偶正整数的集合
,
要求：
(1)
允许
0
打头；
(2)
不允许
打头。
3.
已知文法
G[E]
为：
E→T|E+T|E
-T
T→F|T*F|T/F
F→
（
E
）
|i
①
该文法的开始符号
（识别符号）
是什么？
②
请给出该文法的终结符号集合
VT
和非
终结符号集合
VN
。
③
找出句型
T+T*F+i
的所有短
语、
简单短
语和句柄。
4.
构造正规式相应的
NFA :
1(0|1)*101
。
5.
写出表达式
(a
＋
b*c)/(a
＋
b)
－
d
的逆波
兰表示和三元式序列。
1
1.
B
卷答案
1
答：
(1)
设
G
是一个给定的文法，
S
是文法
的开始符号，
如果
S
x(
其中
x
∈
VT*),
则称
x
是文法的一个句子。
(2)
设
G[S]
是给定文法，则由文法
G
所定义
的语言
L(G)
可描述为：
L(G)
＝{x│S
x,x
∈
VT*}
。
b)
④
(/
，②，③
)
⑤
(
－，④，
d)
编译原理
C
1
．
(10
分
)
对下列错误信息，
请指出可能是
编译的哪个阶段（词法分析
、语法分析、语
义分析、代码生成）报告的。
（
1
）
else
没有匹配的
if
（
2
）
数组下标越界
2
解：
（
3
）
使用的函数没有定义
(1)G[
S]=({S,P,D,N},{0,1,2,…,9
（
4
）
在数中出现非数字字符
},P,S)
（
5
）函数调用时实参与形参类型不一
致。
P:
2
．
(15
分
)
< br>构造一个
DFA
，
它接收
Σ={0,1}
S->PD|D
上所有满足如下条件的字符串：
每个
1
都有
P->NP|N
0
直接跟在右边。并给出该语言的正规式
D->0|2|4|6|8
3
．<
/p>
(10
分
)
为下面的语言设计文法：
N->0|1|2|3|4|5|6|7|8|9
m
n
（
1
）
{
a
b
,
其中
m
?
n
}
*
(2)G[S]=({S,P,R,D,N,Q },{0,
1,2,…,9},
（
2
）
{
w
|
w
?
{
a
,
b
}
，
< br>w
的长度为奇数
}
P,S)
证明
E
+
T
*
（<
/p>
id
）
是文法的一个句型，指
P:
出该句型的所有短语、直接短语和句柄。
S->PD|P0|D
5
．
(15
分
)
给定文法：
P->NR|N
E
→
E
+
T
| E
-
T |T
R->QR|Q
T
→
T
*
F | T
/
F |F
D->2|4|6|8
F
→
(
E
)
|
id
N->1|2|3|4|5|6|7|8|9
C
卷答案
Q->0|1|2|3|4|5|6|7|8|9
1
答案：（每小题
2
分）
3
解：
①
<
/p>
该文法的开始符号
（识别符号）
是
（
1
）
语法分析
E
。
（
2
）
语法分析
②该文法的终结符号集合<
/p>
VT={+
、
-
、
*
、
/
、<
/p>
（
3
）
语义分析
（、）、
< br>i}
。
非终结符号集合
VN={E
、
T
、<
/p>
（
4
）
词法分析
F}
。
（
5
）
语义分析
③句型
T+T*F+I
的短语为
i
、
T*F
、
第一个
T
、
2
答案：
*
*
*
T+T
*F+i;
简单短语为
i
、
T*F
、
第一个
T;<
/p>
句
按题意相应的正规表达式是
(0
10)
0
，或
*
*
*
柄为第一个
T
。
0
(0
| 10)
0
，构造相应的
DFA
。
4
解：
1(0|1)*101
对应的
NFA
为
3
答案：（每小题
10
分）
（
1
）考虑在先产生同样数目的
a,b
，然后再
5
解：逆波兰表示：
abc*
＋
ab
生成多余的
a
。以下是一种解法：
＋
/d
－
S
→
aSb
|
aS
|
ε
三元式序列：
①
(*
，
b
，
c)
（
2
）
A
→
aB
|
bB
②
(
＋，
a
，①
)
③
(
＋，
a
，
B
→
aA
|
bA
|
ε
2
不仅仅是一个字符串，它还具有属性和值。
4
解：
<
/p>
（
1
）
、
1
＋
1*2
↑
*1
↑
2 = 2*2
↑
*1
↑
2 =
< br>↑
*1
↑
↑↑
< br>2 =
E
?
E
?
T
?
E
< br>?
T*F
?
E
< br>?
T*
(
E
)
?
E
?
T
*
(
4
T<
/p>
)
?
E
2 =
4
?
T
*
(<
/p>
F
)
?
E
?
T
*
(id)
5
证明
E
+
T<
/p>
*
（
id
）
是文法的一个句型，
指出该句型的所有短语、直接短语和句柄。
答
：
rm
rm
rm
rm
，
短语：
id
，<
/p>
（
id
）
，
T
*
（
id
）
，
E
+
T
*<
/p>
（
id
）
。
直接短语：
id
。
句柄是
id
。
编译原理
D
卷
3
、何谓“标识符”
，何谓“名字”<
/p>
，两者的
区别是什么？
4
、令
＋、
*
和↑代表加、乘和乘幂，按如
下的非标准优先级和结合性质的约定，
计算
1
＋
1*2
↑
*1
↑
2
的值：
< br>
（
1
）
、
优先顺序
（从高至低）
为＋、
*
和
↑，同级优先采用左结合。
（
2
）
、优先顺序为↑、＋、
*
，同级优
先采用右结合。
6
、
令文法
G
6
为
N
→
D
∣
ND
，
D
→
0
∣
1
∣
2
∣
3
∣
4
∣
5
∣
6
< br>∣
7
∣
8
∣
9
（
1
）
、
G
6<
/p>
的语言
L(G
6
)
是什么？
（
2
）
、给出句子
< br>0127
、
34
和
568
的最
左推导和最右推导。
7
、写一个文法，使其语言是奇数集，且每
个奇数不以
0
开头。
8
、令文法为
E
→
T
∣
E+
T
∣
E-T
T
→<
/p>
F
∣
T*F
∣<
/p>
T/F
F
→
(E)
∣
i
（
1
）
1
）
给出<
/p>
i+i*i
、
i*(i+i)
的最左推
导和最右推导；
给出
i+i+i
、
i+i*i
和
i-i-i
的语法树。
9
、
证明下面的文法是二义的：
S
→
iSeS
∣
iS
∣
i
11
、给出下面语言的相应文法：
<
/p>
L
n
n
i
1
={a
b
c
∣
n
≥
1
，
i
≥
0}
，
L
i
n
n
2
={a
b
c
∣
n
≥
1
，
i
≥
0}
L
n
n
m
m<
/p>
3
={a
b
a<
/p>
b
∣
n
，
m
≥
0}
L
={1
n
0
m
1
m
0
n
4
∣
n
，
m
≥
0}
3
解：标识符是高级语言中定义的字符串，
一般是以英
文字母
（包括大小写字母）
或下
划线开
头的，
由数字、字母和下划线组成的
一定长度的字符串，它只是
一个标志，
没有
（
2
< br>）
其他含义。名字是用标识符表示的，但名字
rm
（
2<
/p>
）
、
1
＋
1*2
rm
↑
*1<
/p>
↑
2 =
6
解：
<
/p>
（
1
）
、
L(G
6
)
是由
0
到
9
这
10
个数字组
成的字符串。
（
2
）
、句子
0127
、
< br>34
和
568
的最左推
导：
N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01D
D=>012D=>0127
N=>ND=>DD=>3D=>34
N=>ND=>NDD=>DDD=>5DD=>56D=>568
句子
01
27
、
34
和
568
的最右推导：
N=>ND=>N7=>ND7=>N27=>ND27=>N127=>
D
127=>0127
N=>ND=>N4=>D4=>34
N=>ND=>N8=>ND8=>N68=>D68=>568
7
解：
G(S)
：
A
→
2
∣
4<
/p>
∣
6
∣
8
∣
D
B
→
A
∣
0
C
→
CB
∣
A
D
→
1
∣
3
∣
5
∣
7
∣
9
S
→
CD
∣
D
8
解：
最左推导为：
E
=>
E+T
=>
T+T
=>
F+T
=>
i+T
=>
i+T*F
=> i+F*F
=> i+i*F => i+i*i
E
=>
T
=>
T*F
=>
F*F
=>
i*F
=>
i*(E)
=> i*(E+ T) => i*(T+
T)
=>
i*(F+
T)
=>
i*(i+
T)
=>
i*(i+
F) => i*(i+ i)
最右推导为：
E
=>E+T
=>E+T*F
=>E+T*i
=>E+F*i
=>E+i*i => T+i*i =>
F+i*i => i+i*i
E => T =>
T*F => F*F => F*(E) =>
F*(E+T) => F*(E+
F) => F*(E+ i)
=>
F*(T+i)
=>
F*(F+i)
=>
F*(i+i)
=> i*(i+ i)
语法树：
3
（
E
E
+
T
4
、
<
/p>
将图
3.18
的（
a
）和
（
b
）
分别确定化和
最小化。
E
E
a
E
+
T
0
F
E
E
a
，
b
a
-
(a)
-
1
T
F
T
+
T
F
F
i
T
T
*
F
i
F
i
i
a
F
i
b
0
a
F
i
i
i
2
b
b
3
a
i
a
9
解
：考虑句子
iiiei
，存在如下两个最右
a
推导：
b
S=>iSeS=>iSei=>iiSei=>iiiei
1
4
S=>iS=>iiSeS=>iiSei=>iiiei
b
b
由此该文法是二义的。
a
11
解：
(b)
L
1
的文法：
S
→
AC
；
A
→
aAb
∣
ab
；
C
→
cC
∣ε
L
2
的
文法：
S
→
AB
；
A
→
aA
∣ε；
B
→
bBc
5
、
构造一个
< br>DFA
，它接受∑
={0
，
1}
上所有
∣
bc
满足如下条件的字符串：
每个
1
都有
0
直接
L
3
的文法：
S
→
AB
；
A
→
aAb
∣ε；
B<
/p>
→
aBb
跟在右边。
、
∣ε
6
、
给定右
线性文法
G
：
L
4
的文法：
S
→
1S0
∣
A
；
A
→
0
A1
∣ε；
S
→
0S
∣
1S
∣
1A
∣
0B
A
→
1C
∣
1
编译原理
E
卷
B
→
0C<
/p>
∣
0
1
、
构造下列正规式相应的
DFA
C
→
0C
∣
1C
∣
0
∣
1
1(0
∣
1)*101
求出一个与
G
等价的左线性文法。
1(101
0*
∣
1(010)*1)*0
<
/p>
文法
G
对应的状态转换图如下所示：
0*10*10*10*
0
，
1
<
/p>
(00
∣
11)*((01
∣
10)(00
∣
11)*
(01
∣
10)(00
∣
11)*)*
1
1
2
、
给出下面正规表达式：
A
S
（
1
）
以
01
结尾的二进制数串；
（
2
）
能被
5
整除的十进制整数；
0
1
0
包含奇数个
1
或奇数个
0<
/p>
的二进制数串；
B
0
3
、
对下面
情况给出
DFA
及正规表达式：
（
1
）
{0
，
1}
上不含
子串
010
的所有串。
4
5
a
0
，
1
C
0
，
1
Z
E
卷答案
2
解：
<
/p>
(1)
、
1(0
∣
1)*101
第一步：根据正规
式构造
NFA
，先引入
初始状态
X
和终止状态
Y
：<
/p>
X
1(0
∣
1)*101
Y
再对
该转换图进行分解，
得到分解后的
NFA
如下图：
0
1
ε
ε
X
1
2
1
第二步：
对
NFA
进行确定化，
获得状态
转换矩阵：
状态
{X}
{1
，
2
，
3}
{2
，
3}
{2
，
3
，
4
}
{2
，
3
，
5}
{2
，
3
，
4
，
Y
}
0
?
{2
，
3}
{2
，
3}
{2
，
3
，
5
}
{2
，
3}
{2
，
3
，
5}
首先根据是否终止状态将所有状态分
为两个集合
{0
，
1
，
2
，
3
，
4}
和
{5}
，这里集
合
{5}
已经不
可划分，只需考虑集合
{0
，
1
，
2
，
3
，
4}
。
{0
，
1<
/p>
，
2
，
3
，
4}
0
={2
，
4
，
-}
，
{0
，
1
，
2
，
3
，
4}
1
={1
，
3
，
5}
因为
{1
，
3
，
5}
和<
/p>
{2
，
4
，
-}
不在一个集
合里面，所以需要对集合<
/p>
{0
，
1
，
2
，
3
，
4}
进行进一步的划分，检查其中的所有状态。
状态
0
不能接受字符
0
，需要把状态
0
划分
出来；另
外，只有状态
4
读入字符
1
后进入
状态
5
，因此将状
态
4
划分出来，划分的结
果为
4
个集合：
{0}
，<
/p>
{1
，
2
，
3}
，
{4}
，<
/p>
{5}
。
<
/p>
检查集合
{1
，
2
，
3}
，
{
1
，
2
，
3}
0
={2
，
4
}
，不属于同一个集合，因此要对集合
{1
，
2
，
3}
进行进一步划分，划分结果为
5
个集
合：
{0}
，
{1
，
2}
，
{3}
< br>，
{4}
。
1
，
{5}
0
1
Y
5
，
4
{1
，
3
检查集合
2}
，
{1
2}
0
={2}
，
{1
，
2}
1
=3
，
不需要进行进一步划
分。
所以最终划分结果
为
5
个集合：
{0}
，
{1<
/p>
，
2}
，
{3}
，
{4}
，
{
5}
。
所
以，最终所求
DFA
如下图示：
0
1
{
1
，
2
，
3}
0
{2
，
3
，
4}
{2
，
3
，
4}
{2
，
3
，
4
}
1
3
1
0
1
1
0
1
4
1
3
解：
（<
/p>
1
）以
01
结尾
的二进制数串；
(1
︱
0)*01
。
（
2
）能被
5
整除的十进制整数；
(1
︱
2
︱
3
︱
4
︱
5
︱
6
︱
7
︱
8
︱
9)
(0
︱
1
︱
2
︱
3
︱
4
︱
5
︱
6
︱
7
︱
8
︱
9)*(0
︱
5)(0
︱
1
5
4
5)
。
0
（
3
）包含奇数个
1
或奇数个
0
的二进制数
1
串；
1*0
（
1
︱
01*0
）
*
︱
0*1
（
0
︱
10*1
）
*
。
4
解：
（
1
）
、直接写出满足条件的正规表达
5
{2
，
3
，
4
，
Y}
{2
，
3
，
4}
0
5
根据转换矩阵获得相应的
DFA
：
0
1
0
0
1
2
1
3
0
0
1
1
第
三步：化简该
DFA
，获得最简的
DF
A
即为所求。
式。考虑满足条件的字符串中的
1<
/p>
：在串的
开始部分可以有
0
个或多个
1
，串的尾部也
可
以有
0
个或多个
1
，但串的中间只要出现
1
则至少在两个以上，所以满足条件
的正规
表达式为
1*(0
∣
111*)*1*
。
5
解：
（
1
）
、
图
（
a
）
中为一个
NFA
，<
/p>
所以需要
先对它进行确定化，
得到
DFA
，
然后再对
D
FA
进行最小化。
首先进行确定化，如下两个表所示：
所求的
DFA
如下图所示：
1
0
S
0
A
1
1
B
状态
a
b
{0}
{0
，
1}
{1}
{0
，
1}
{0
，
1}
{1}
{1}
{0}
?
状态
a
b
0
1
2
1
1
2
2
0
6
根据状态转换矩阵得到如下图所
示的
DFA
：
a
b
a
2
b
0
1
a
题意，该
DFA
接受的字符串由
0
和
1
组成，
并且每个
1
的后面都有
0
直接跟在右边，
因
此，可以将该字符串理解为由
0
和
10
构成
的串，则相应的
正规表达式就是
(0
︱
10)*
。
第二步：构造
NFA
。首先得出下图：
化简后的
DFA
为：
X
(0
︱
10)*
Y
a
b
a
然后对上图进行分解后得到如下
图所
示的
NFA
。
2
2
0
1
X
ε
1
ε
0
<
/p>
（
2
）
、题中所
给即为一个
DFA
，不需要
确定化，只
对它进行最小化即可。
首先将状态
划分为两个集合
{{0
，
1}
，
{2
，
3
，
4
，
5}}
。
有
{0
，
1}
a
={1}
，
{0
，
1}
b
={2
，
4}
和
{2
，
3
，
4
，
5}
a
={1
，
3
，
0
，
5}
，
{2
，
3
，
4
，
5}
b
< br>={2
，
3
，
< br>4
，
5}
，所以可以进一步划分
为
{{0
，
1
}
，
{2
，
4
}
，
{3
，
5
}}
，然后有
{0
，
< br>1}
a
={1}
，
{0
，
1}
b
={2
，
4}
，
{2
，
4}
a
={1
，
0}
，
{2
，
4}
b
={3
，
5}
，
{3
，
5}
a
={3
，
5}
，
{3
，
5}
b
={2
，
4}
。因
此，最后划分结果是
{{0
，
1}
，
{2
，
4}
，
{3
，
5}}<
/p>
。
最小化后
的
DFA
如下图所示：
a
b
a
b
b
0
第三步：确定化，得到
DFA
。确定化
结
果如表
14.1
所列；
给状态编号，
得到表
14.2
所示的状态转换矩阵：
a
1
2
0
6
解：第一步：写出正规表达式。根据
状态
0
{1
，
Y}
{1
，
Y}
{1
，
Y}
0
1
1
1
1
{2}
{2}
?
1
2
2
{X
，
1
，<
/p>
Y}
{1
，
Y}
{2}
状态
0
1
2
表
14.1
状态转换矩阵
表
14.2
新的状态转换矩阵
7
根据
状态转换矩阵得到
DFA
如下图所
示：
0
1
1
2
第四
步：
对该
DFA
进行最小化。其分析<
/p>
过程如下：
{0
，
1}
，
{2}
{0
，
1}
0
={1}
，
{0
，
1}
1
={2}
{0
，
1}
，
{2}
最小化后的
DFA
如图所示，
该
DFA
即为
所求。
0
1
0
0
0
0
0
1
2
0
1
0
1
1
0
1
0
3
0
4
1
还可以对上图的
DFA
进行化简，状态
3
和
4
可以合
并，化简后的
DFA
如下图所示：
0
，
1
0
0
0
1
S
A
1
0
B
T
1
1
1
对状态转换图进行确定化，
得到状态转换矩
阵：
状态
{S}
{S
，
B}
{S
，
A}
{S
，
B
，
C
，
Z}
{S
，
A
，
C
，<
/p>
Z}
状态
0
1
2
3
4
1
3
1
3
3
不难
看出，该
DFA
接受的语言是
{0
，
1}
0
上包含
00
或
11
的
字符串。根据化简后的
1
DFA
，我
们可以写出相应的左线性文法
G
’：
{S
，
B}
{S
，
A}
T0
∣
T1
{S
，
B
，
C
，
Z}
T
→
A0
∣
{S
B1
，
∣
A}
A
→
B0<
/p>
∣
{S
，
B}
{S
0
，
A
，
C
，
Z}
{S
，
B
，<
/p>
C
，
Z}
<
/p>
B
→
A1
∣
{S
1
，
A
，
C
，
Z}
卷
A
，
C
，
Z}
{S<
/p>
，
B
，
C
，
Z}
编译原理
F
{S
，
1
、考
虑下面的文法
G
1
：
< br>
0
1
S
→
a
∣∧∣
2
(T)
T
→
T
，
S
∣
S
2
（
1
）消去
G
1
的左递归。然后对每个非
4
终结符，写出不带回溯的递归子程序。
4
（
2<
/p>
）
经改写后的文法是否是
LL(1)
的？
4
给出它的预测分析表。
（
2
）计算每个非终结符的
FIRST
集合
和
FOLLOW
集合：
FIRST
（
S
）
={a
，∧，
( }
FIRST
（
T
）
={a
，∧，
( }
FIRST
（
T
’）
={
，
，ε
}
8
给状态编号，得到新的状态转换矩阵：
根据状态转换矩阵获得
DFA
如下：
FOLLOW
（
S
）
={ )
，’，’，
#}
FOLLOW
（
T
）
={ ) }
FOLLOW
（
T
’）
={ ) }
从而可见改造后的文法符合
LL(1
)
文法
的充分必要条件，所以是
LL(
1)
的。
该文法的预测分
析表
S
T
T
’
a
S->a
T->S
T
’
^
S->^
T->S
T
’
(
S->(T)
T->S
T
’
（
1
）
（
2
）
（
3
）
（
4
）
2
、对下面的文法
< br>G
：
E
→
TE
’
E
’→
+E
∣ε
T<
/p>
→
FT
’
T
’→
T<
/p>
∣ε
F
→
PF
’
F
’→
*F
’∣ε
P
→
(E)
∣
a
∣
b
∣∧
<
/p>
计算这个文法的每个非终结符
的
FIRS
T
和
FOLLOW
。
< br>
（
1
）
证明这个文法是
LL(1)
的。
构造它的预测分析表。
构造它的递归下降分析程序。
3
、下面文法中，哪些是
LL(1)
的，说明
理由。
（
1
）
、
S
→
Abc
A
→
a
∣ε
B
→
b
∣ε
（
2
）
、
S
→
Ab
A
→
a
∣
B
∣ε
B
→
b
∣ε
（
1
）
（
3
）
、
（
2
）
S
→
ABBA
A
→
a
∣ε
（
3
）
B
→
b
∣ε
（
4
）
（
4
）
、
S
→
aSe
∣
B
<
/p>
B
→
bBe
∣<
/p>
C
C
→
cCe
∣
d
4
、对下面文法：
Expr
→
-Expr
Expr
→
(Expr)
∣
Var
ExprTail
→
-Expr
∣ε
Var
→
id VarTail
)
,
#
VarTail
→
(Expr)
∣ε
（
、构造
LL(1)
1
）
分析表。
（
2
）
、
给出对句子
id--id((id))
T<
/p>
’
->
ξ
T->,S T
’
的分析
过程。
1
、令文
法
G
1
为
E
→
E+T
∣
T
T<
/p>
→
T*F
∣
F
F
→
(E)
∣
i
证明
E+T*F
是它的一个句型，指出这个
句型的所有短语，直接短语和句柄。
2
、考虑下面的表格结构文法
G
2
：<
/p>
S
→
a
∣∧∣
(T)
T
→
T
，
S
∣
S
给出
(a
，
(a
，
a))
和
(((a
，
a)
，
∧，
(a))
，
a)
的最左和最右推导。<
/p>
指出
(((a
，
a)
，
^
，
(a))
，
a)
的规范归约及
每一步的句柄。根据这个规范归约，给
出
“移进
-
归约”
的过
程，
并给出它的语
法树自下而上的构造过程。
< br>
3
、
（
1
）计算练习
2
文法
G
2
的
FIRSTVT
和
LASTVT
。
（
2
）计算
G
2
的优先关系。
G
2
是一个算
符优先文法吗？
（
3
）给出输入串（
a
，
（
a
，
a
）
）的算符
优先分析过程。
4
、考虑文法：
S
→
AS<
/p>
︱
b
A
→
SA
︱
a
列出这个文法的所有
LR(0)
项
目。
构造这个文法的
LR(0)
项目集
规范族及识别活前缀的
DFA
。
这个文法是
SLR
的吗？若是，
构造出它的
SLR
分析表。
这个文法是
LALR
或
LR(1)
的
9
吗？
F
卷答案
1
答：解：
（
1
）按照
T
、
S
的顺序消除左递归，得
到文法：
?
G
’
(S)
S
→
a
∣∧∣
(T)
T
→
ST
’<
/p>
T
’→，
ST
’
∣ε
对于非终结符
S,T,
T
’的递归子程序
如下：
Procedure S;
Begin
If
sym
=
‘
a
’
or
sym
=
‘
^
’
Then advance
Else if sym =
‘
(
‘
（
2
）
Then begin
Advance
T;
If
sym
=
’
)
’
Then advance
Else error
End
Else error
Ends;
Procedure T;
Begin
S; T
’
;
Ends;
Procedure
T
’
Begin
If sym =
‘
,
’
Then begin
Advance
S;
T
’
Ends
ends;
2
解：
（<
/p>
3
）
1
）
计算每个非终结符的
FIRST
集
合和
FOLLOW<
/p>
集合如下：
FIRST
（
E
）
={(
，
a
，
b
，∧
}
FIRST
（
E
’）
={+
，ε
}
FIRST
（
T
）
={(
，
a
，
b
，∧
}
FIRST
（
T
’
）
={(
，
a
，
b
，∧，ε
}
FIRST
（
F
）
={(
，
a
，
b
，∧
}
FIRST
（
< br>F
’）
={*
，ε
}
FIRST
（
P
）
={(
，
a
，
b
，∧
}
FOLLOW
（
E
）
={#
，
)}
F
OLLOW
（
E
’）
< br>={#
，
)}
FOLLOW
（
T
）
={+
，
)
，
#}
FOLLOW
（
T
’）
={+
，
)
，
#}
FOLLOW
（
F
）
={(
，
a
，
b
，∧，
+
，
)
，
#}
FOLLOW
（
F
’）
={(
，
a
，
b
，∧，
+
，
)
，
#}
FOLLOW
（
P
）
={*
，
(
，
a
，
b
，∧，
+
，
)
，
#}
本文法是
LL ( 1
)
文法。
证明：
通过观察可知文法中不含有<
/p>
左递归，满足
LL
(1)
文法定义的第一个条
件。
考虑下列产生式：
E
’→
+E
∣ε
T
’→
T
∣ε
< br>F
’→
*F
’∣ε
P
→
< br>(E)
∣
a
∣
< br>b
∣∧
因为：
F
IRST
（
+E
）
∩
FIRST
（ε）
={+}
∩
{
ε
}=
?
FIRST
（<
/p>
E
’）∩
FOLLOW
< br>（
E
’）
={+}
∩
{#
，
)}=
?
FIR
ST
（
T
）∩
FIRST
（ε）
={(
，
a
，
b
，
∧
}
∩
{
ε
}=
?
FIRST
（
T
’）∩
FOLLOW
（
T
’）
={(
，
a
，
b
，∧
}
∩
{+
，
)
，
#}=
?
FIRST
（
*F
’）∩
FIRST
（ε）
={*}
∩
{
< br>ε
}=
?
FIRST
（
F
’）∩
FOLLOW
（
F
’）
={*}
∩
{(
，
a
，
b
，∧，
+
，
)
，
#}=
?
FIR
ST
（
（
E
）
）
∩
FIRST
（
a
）
∩
F
IRST
（
b
）
∩
FIRST
（∧）
=
?
所以该
文法是
LL(1)
文法。
构造其预测分析表：
10
（
P; F
’
;
End
Procedure
F
’
b
+
*
(
)
a
^
E
E
?
T
E
’
Begin
E
?
T
E
’
E
?
T
E
’
E
?
T
E
’
?
E
’
E
’
?
+E
E
’
ξ
If sym =
‘
*
’
T
T
?
FT
’
T
’
Then begin
?
FT
’
<
/p>
T
?
FT
’
T
?
FT
’
?
ξ
T
’
T
’
T
’
?
ξ
T
’
?
T
T
’
?
T
Advance
T
’
?
T
T
’
?
T
F
F
?
PF
’
F
?
PF
’
F
’
P
?
PF
’
<
/p>
F
?
PF
’
End
F
’
F
’
?
ξ
F
’
F
’
?
ξ
F
’
?
ξ
F
’
?
ξ
F
’
< br>?
ξ
F
’
?
ξ
End;
?
*F
’
Procedure P
P
P
?
(E)
P
?
a
P
?
b
P
?
^
Begin
If
sym =
‘
a
’
or
sym
=
（
4
）
构造其递归下降分析程序：
‘
b
‘
or sym =
‘
^
Procedure E;
Then acvance
Begin
Else if sym =
‘
(
‘
T
E
’
Then
begin
End
Advance
E
Procedure
E
’
If
sym
=
Begin
‘
)
‘
If
sym =
‘
+
’
Then
Then begin
advance
Acvance
Else
E
error
End
End
End
Else error
End;
Procedure T
3
解：
Begin
（
1
）
该文法不含左递归，计算每个
F T
’
非终结符的
FIRST
集合和
FOL
LOW
集合如下：
End
FIRST
（
S
）
={a
，
b
，
c}
FIR
ST
（
A
）
=
{a
，ε
}
Procedure
T
’
FIRST
（
B
）
={b
，ε
}
Begin
< br>FOLLOW
（
S
）
={#}
If sym
∈
first ( T )
FOLLOW
（
A
）
={b
，
c}
Then T
Else
if
sym
=
‘
*
’
then
FOLLOW
（
B
）
={c}
可见该文法满足
LL(1)
文法的三个条
error
件，是
LL(1)
文法。
End
（
2
）
该文法不含左递归，计算每个
非终结
符的
FIRST
集合和
FOLLOW<
/p>
集合如下：
Procedure
F
FIRST
（
S
）
={a
，
b}
Begin
FIRST
（
A
）
={a
，
b
，ε
}
If sym
∈
first ( P )
11
预
测
分析表
#
E
’
->
ξ
T
’
?
ξ
F
’
?
ξ
FIRST
（
B
）
={b
，ε
}
FOLLOW
（
S
）
={#}
FOLLOW
（
A
）
={b
}
FOLLOW
（
B
）
={b}
考虑
A
→<
/p>
a
∣
B
∣ε，因
为
FIRST
（
B
）∩
FOLLOW
（
A
）
={b}
≠?，
所以该
文法不是
LL(1)
文法。
（
3
）
该文法不含左递归，计算每个
非终结符的
F
IRST
集合和
FOLLOW
集合如下
：
FI
RST
（
S
）
={a
，
b
，ε
}
FIRST
（
A
）
={a
，ε
}
FIRST
（
B
）
={b
，ε
}
FOLLOW
（
S
）
={#}
FOLLOW
（
A
）
={a
，
b
，
#}
FOLLOW
（
B
）
={a
，
b
，
#}
考虑<
/p>
A
→
a
∣ε
和
B
→
b
∣ε，
因为
FIR
ST
（
a
）
∩
FOLLOW
（
A
）
={a}
≠?
FIRST
（
b
）
∩
FOLLOW
（
B
）
={b}
≠?
所以该文法不是
LL(1)
文法。
（
4
）
该文法不含左递归，计算每个
非终结符的
F
IRST
集合和
FOLLOW
集合如下
：
FI
RST
（
S
）
={a
，
b
，
c
，
d}
FIRST
（
B
）
={b
，
c
，
d}
FIRST
（
C
）
< br>={c
，
d}
FOLLOW
（
S
）
={e
，
#}
FOLLOW
（
B
）
={e
，
#}
FOLLOW
（
C
）<
/p>
={e
，
#}
可见该文法满足
LL(1)
文法的三个
条
件，是
LL(1)
文法。
1
解：因为
E=>E+
T=>E+T*F
，所以
E+T*F
是
该文法的一个句型。
短语：
E+T*F
，
T*F
直接短语：
T*F
句柄：
T*F
2
解：
步骤
（
1<
/p>
）最左推导：
0
S=>(T)=>(T
，
S)=>(S
，
S)=>(a
，
S)=>(a
，
1
(T))=>(a
，
(T
，
S))=>(a
，
(S
，
S))=> (a
2
，
(a
，
S))=>(a
，
(a
，
a))
3
S=>(T)=>(T
，
S)=>(S
，
S)
=>((T)
4
，
S)=>((T<
/p>
，
S)
，
S)=
>((T
，
S
，
S)
，
S)=>((S
5
，
S
，
S)
，
S)=>(((T)
，
S
，
S)
< br>，
S)=>(((T
，
S)
，
S
，
S)
，
S)=>(((S
，
S)
，
S
，
S)
，
S)=>(((a
，
S)
，
S
，
S)
，
S)=>(((a
，
a)
，
S
，<
/p>
S)
，
S)=>(((a
，
a)
，∧，
S)
，
S)=>(((a
，
a
)
，∧，
(T))
，
< br>S)=>(((a
，
a)
，∧，
(S))
，
S)=>(((a
，
a)
，
∧，
(a))
，
S)=>(((a
< br>，
a)
，∧，
(a))
，
a)
最右推导：
S=>(T)=>(T
，
S)=>(T
，
(T))=>(T
，
(T
，
S))=>(T
，
(
T
，
a))=>(T
，
(S
，
a))=>(T
，
(a
，
a))=>(S
，
(a
，
a))=> (a
，
(a
，
a))
S=>(T
，
S)=>(T
，
a)=>(S
，
a)=>((T)
，
a)=>((T
，
S)
，
a)=>(
(T
，
(T))
，
a)=>((T
，
(S))
，
a)=>((T
，
(a))
，
a)=>((T
，
S
，
(a))
，
a)=
>((T
，∧，
(a))
，
a)=>((S
，∧，
(a))
< br>，
a)=>(((T)
，∧，
(
a))
，
a)=>(((T
，
S)
，∧，
(a))
，
a)=>(((T
，
a)
，
∧，
(a))
，
a)=>(((S
，
a)
，∧，
(a))
，
a)=>
(((a
，
a)
，∧
，
(a))
，
a)
< br>（
2
）
(((a
，
a)
，
^
< br>，
(a))
，
a)
的规范归约如
下：
(((a
，
a)
，
∧，
(a))
，
a)
(((S
，
a)
，∧，
(a))
，
a)
(((T
，
a)
，∧，
(a))
，
a)
(((T
，
S)
，∧，
(a))
，
a)
(((T)<
/p>
，∧，
(a))
，
a)
((S
，∧，
(a))
，
a)
((T
，∧，
(a))
，
a)
((T
< br>，
S
，
(a))
，
a)
((T
，
(a))
，
a)
((T
，
(
S))
，
a)
((T
，
(T))
，
a)
((T
，
S)
，
a)
((T)
，
a)
(S
，
a)
(T
，
S)
(T)
“移进—归约”过程：
栈
#
#(
#((
#(((
#(((a
#(((S
输入串
(((a
，
a)
，∧，
(a))
，
a)#
((a
，
a)
，∧，
< br>(a))
，
a)#
(a
，
a)
，∧，
(a)
)
，
a)#
a
，
a)
，∧，
(a))
，
a)#
，
a)
，∧，
(a))
，
a)
#
，
a)
，∧，
(a))
，
a)#
12
动作
预备
进
进
进
进
归
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#(((T
#(((T
，
#(((T
，
a
#(((T
，
S
#(((T
#(((T)
#((S
#((T
#((T
，
#((T
，∧
#((T
，
S
#((T
#((T
，
#((T
，
(
#((T
，
(a
#((T
，
(S
#((T
，
(T
#((T
，
(T)
#((T
，
S
#((T
#((T)
#(S
#(T
#(T
，
#(T
，
a
#(T
，
S
#(T
#(T)
#S
，
a)
，∧，
(a))<
/p>
，
a)#
a)
，∧，
(a))
，
a)#
)
，∧，
(a))
，
a)#
)
，∧，
(a))
，
a)#
)
，∧，
(a))
，
a)# <
/p>
，∧，
(a))
，
a)#
，∧，
(a))
，
a)#
，∧，
(a))
，
a)#
∧，
(a))
，
a)#
，
(a))<
/p>
，
a)#
，
(
a))
，
a)#
，
< br>(a))
，
a)#
(a))
，
a)#
a))
，
a)#
))
，
a)#
))
，
a)#
))
，
a)#
)
，
a)#
)
，
a)#
)
，
a)#
，
a)#
，
a)#
，
a)#
a)#
)#
)#
)#
#
#
归
进
进
归
归
进
归
归
进
进
归
归
进
进
进
归
归
进
归
归
进
确定化的结果见转换矩阵表：
归
S
归
{0
，<
/p>
2
，
5
，
7
，
10}
{1<
/p>
，
2
，
5
，
7
，
8
，
10}
进
{1
，
2
，
5
，
7
，
8
，
10}
{2
，
5
，
7
，
8
，
10}
进
{2
，<
/p>
3
，
5
，
7
，
10}
{2<
/p>
，
4
，
5
，
7
，
8
，
10}
归
{2
，
5
，
7
，
8
，
10}
{2
，
5
，
7
，
8
，
10}
归
{2
，
3
，
5
，
7
，
9
，
10}
{2
，
4
，
5
，
7
，
8
，
10}
进
{2
，
4
，
5
，
7
，
8<
/p>
，
10}
{2
，
5
，
7
，<
/p>
8
，
10}
归
{11}
?
{6}
?
（
3
）
、不是
SLR
文法。
I
3
、
I
6
、
I
7
有“移进—归约”冲突。
I
3
：
FOLLOW(S
’
)={#}
不包含
a
，
b
。
I
6
：
FOLLOW(S)={#
，
a
，
b}
包含
a
，
b
；
“移
进—归约”冲突无法消解。
I
7
：
FOLLOW(A)={a
，
b}
包含
a
，
b
；
“移
进—归约”冲突消解。
所以不是
SLR
文法。
编译原理
G
卷
1
．构造正规表达式
a(aa)*bb
(bb)*a(aa)*
的
NFA
。
13
1
S
7
S
ε
ε
10
ε
8
ε
A
ε
0
ε
2
ε
a
A
ε
ε
d
3
S
5
6
A
{2
，
3
，
5
，
7
{2
，<
/p>
3
，
5
，
7
{
，
3
，
5
，
7
，
{2
，
3
< br>，
5
，
7
{2
，
3
，
5
，
7
?
?
{2
，<
/p>
3
，
5
，
7
4
解：
<
/p>
（
1
）
、
0.S
’→·
S
1.S
’
→
S
·
2.S
→·
AS 3.S
→
A
·
S 4.S
→
AS
·
5.S
→·
b
6.S
→
b
·
7.A
→·
SA 8.A
→
S
·
A 9.A
→
SA
·
10.A
→·
a 11.A
→
a
·
（
2
）
、
构造识别活前缀的
NFA
如下图所
示：
2
．构造
正规表达式
((a|b)*|aa)*b
的
NFA
。
（
13
分）
2
．令文法
G[N]
< br>为
G[N]:
N
→
D|ND
D
→
0|1|2|3|4|5|6|7|8|9
给出句子
568
的最左、最右推导。
3
．给出字母表Σ
={a,
b}
上的同时只有奇数
个
a
和奇数个
b
的所有串的集合的正规文
法；
5.
表达式
a*b-c-d$$e$$f-g-h*i
中，运算符
的优先级由高到低依次为
-
、
*<
/p>
、
$$
，且均为
右
结合，请写出相应的后缀式。
6
．判断文法
G[S]: S
→
BA
A
→
BS | d
B
→
aA| bS | c
是否为
LL(1)
文法
.
7
．对于文法
G[E]:
E
→
E+T | T
T
→
T+P | P
P
→
(E) | i
写出句型
P+T+(E+i)
的所有短语、直接
短语、句柄。
8
．已知文法
G[A]:
A
→
aABl|a
B
→
Bb|d
试给出消除左递归和回溯与
G[A]
等价
的
LL(1)
文法
G[A
′
]
< br>；
9
．将下面的语句翻译成四元式序列：
if
(x
＞
y) m= 1;
else m=0;
10
．将以下
DFA
最小化。
（
8
分）
2
b
a
X
a
1
?
Y
11
．设
M=({x,y},
{a,b}, f, x, {y})
为一
非确定的有限自动机
，其中
f
定义如下：
f(x,a)={x,y}
f{x,b}={y}
f(y,a)=
Φ
f{y,b}={x,y}
试
构
造
相
应
的
确
定
有
限
自
动
< br>机
M
′。
（
12
分）
12
．试构造下述文法的
SLR(1)
分析表。
G[A]:
A
→
aABl|a
B
→
Bb|d
13
．将下面的语句翻译成四元式序列：
（
< br>7
分）
if (x
＞
y) m= 1;
else m=x+y;
14.
试构造下述文法的
LL(1)
分析表。
（
15
分）
G[S]: S
→（
L
）
|a
L
→
L
，
S|S
17
．已知文法
G[S]: S
→
aSbS|bSaS|
ε
< br>
试证明
G[S]
是二义文法
18
．将下
面的语句翻译成四元式序列：
<
br>M 21 <
br>，且 26 <
br>上所 1 <
br>’ <
br>：
while(a
if
(c
＞
d) x=y+z
19
．构造正规表达式
a(aa)*b
b(bb)*a
的最
小化的确定有限自动机
′。
．
画出编译程序的总体结构图，
简述各部
分的主要功能。
22
．对于文法
G(S)
：
S
→
(L) | aS |
a
L
→
L, S | S
(1)
画出句型
(S,
(a))
的语法树。
(2)
写出上述句型的所有短语、直接
短语和句柄。
23
．构造一文法，使其描述的语言
L
= {
ω
|
ω
∈
(a, b)
*
ω
中含有相同个数的
a
和
b}
。
24
．分别给出表达式
–
(a*(b-c))+d
的逆
波兰表示和四元式表示。
25
．把下列语句翻译为四元式序列：
while (A > B)
if (C > D)
X = Y * Z
else
X = Y + Z
．构造一个
DFA
，它接受Σ
=
{0,
1}
有满足如下条件的字符串：
每个
后面都有
0
直接跟在右边。
27
．已知文法
G(S)
：
14
S
→
S*aP| aP| *aP
P
→
+aP| +a
(1)
将文法
G(S)
改写为
LL(1)
文法
G<
/p>
’
(S)
；
(2)
写出文法
G
(S)
的预测分析表。
28
．已知文法
G(S)
S
→
aS | bS | a
(1)
构造识别该文法所产生的活前缀
的
DFA
；
(2)
判断该文法是
LR(0)
还是
SLR(1)
，
A
?
d
36
．
将下
图所示的确定有限自动机
(DFA)
最
小化。其中，
X
为初态，
Y
为终态。
a
a
X
b
2
1
b
a
b
3
a
Y
b
并构造所属文法的<
/p>
LR
分析表。
29
．将下图所示的非确定有限自动机
(NFA)
变换成等价的确定有限自动机
(DFA)
。
其中，
X
为初态，
Y<
/p>
为终态。
b
a
2
?
a
1
b
a
X
a
Y
b
b
3
4
b
?
a
?
30
．
对正
规式
(a|b)*abb
构造其等价的
NFA
。
31
．
下面
的文法产生
0
和
1
的串，即二进
制的正整数，
请给出决定每个二进制数的值<
/p>
（十进制形式）的语法制导定义。
32
．把算术表达式
?
(
< br>a
+
b
)
?
(
c
+
d
)
+
(
e
+
f
)
翻译成等价的四元式序列（序号
从
0
开
始）
。
33
．设有文法
G[S]:
S
→
a|
（
T
）
|
?
T
→
T,S|S
试给出句子
(a,a,a)
的最左推导。
34
．已知文法Ｇ：
S
→
( L |
a
L
→
S ,
L | )
判断是不是
LL
（<
/p>
1
）文法，如果是请构造文
法
Ｇ
的预测分析表，如果不是请说明理
由。
35
．文法
S
?
A a | b A c |
d c | b d a
37
．
请画
出识别无符号十进制整数的状态转
换图
38
．设有文法
G[S]:
S
→
S*S|S+S|(S)|i <
/p>
该文法是否为二义文法
,
并说明理由？<
/p>
40
．
把下列
语句翻译为四元式序列
（四元式
序号从
1
开始）
：
while (A > B)
if (C > D)
X = Y * Z
else
X = Y + Z
41.
构造下面文法的
LL
（
1
）分析表。
G[D]: D
?
TL
T
?
int | real
L
?
id R
R
?
, id R |
?
42
．<
/p>
给定文法
S
→
a
S|bS|a
，
下面是拓广文法
和识别
该文法所产生的活前缀的
DFA
。判断
该文法是否是
SLR(1)
文法：如果是构造其
SLR(1)
分析表，如果不是请说明理由。
(1)
将
文法
G(S)
拓广为
G(S
’
)
：
(0)S
’→
S
(1)S
→
aS
(2)S
→
bS
(3)S
→
a
(2)
识别该文法所产生的活前缀的
DFA
如图
1
所示。
15
明了多少个
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
I
1
:
P'
→
P
.
I
2
:
I
4
:
P
→
aP
I
0
:P'
→
.
P
a
P
P
→
.aPb
b
P
→
.Q
I
7
:P
→
aP
a
Q
→
.bQc
b
Q
→
.bSc
I
8
:
Q<
/p>
→
bQ
Q
b
图
1
c
:
Q
I
5
I
3
:P
→
Q.
I
9
:
Q<
/p>
→
bQ
Q
43
．
给
出表达式
-a*b+b*c+d/e
的语法树和三
b
元式序列。
I
10
:
Q
→
bS
S
44
．证明下面文法
S
→
AaAb|BbBa
A
→ε
I
6
:
S
→
a.
S
→
S.a
a
B
→ε，是
LL
（
1
）文法，但不是
SLR
（
1
）
c
文法。
I
11
:
Q
→
bS
a
45
．现有文法
G[S]
I
12
:
S
→
Sa.
S
→
a|
ε
|
(T)
T
→
T,S|S
请给出句子
（
a,(a,a)
）
的最左、
最右推<
/p>
导，并指出最右推导中每一个句型的句柄。
46
．将下图的
DFA
最小化。
49
．给出表达式（
a+b
）
*(c+d/e)
的语法树
和四元式序列。
1
a
b
50
．构造文法
< br>S
→
AaAb|BbBa
A
→ε
B
b
a
→ε，的预测分析表。
0
3
4
a
b
b
a
b
2
51
．
写出
C
语言标识符集
（字母或下划线开
头的由字母、数字、下划线构成
的串）的正
a
规式。
47<
/p>
．设有如下文法：
P
→
< br>D
53
．假设第一个四元式的序号是
< br>100
，写出
D
→
D
；
D|id
：
T|proc
id
；
布
尔表达式
<
br>∧
a
∨
c
d>e
的四元式序列。
D
；
54
．设有如下文法：
T
→
real|integer
G[E]
：
E
→<
/p>
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]
：<
/p>
S
→（
A
）
A
→
ABB|B
B
→
b
5
8
．
写出赋值语句
X=
-(a+b)/(c-d)-(a+b*c)
的逆波兰表示。
59
．为文法
G[S]
：
S
→（
L
）
|a
L
→
L
，
S|
S
写一语法制导定义，它输出句子中括号
嵌套的最大层次数。
6
0
．
2
．已知文法
G[S]
如下：构造该文法的
LR
（
0
）分析表。
G[S]
：
S
→
< br>BB
B
→
aB|b
g
卷答案
1
解：
2<
/p>
5
6
a
X
a
1
a
b
3
b
b
4
b
a
a
Y
a
3
a
X
?
1
?
a
?<
/p>
2
b
Y
2
解：
最左推导：
N
?
ND
?
NDD
?
DDD
?
5DD
?
56D
?
568
最
右
推
导
：
N
?
ND
?
N8
?
ND8
?
N68
?
D68
?
568
3
解：
G[S]
< br>：
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
< br>、
P+T
、
i
< br>、
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
解：
a
0
b
1
?
2
解：
a
4
b
17
11
解：
对照自动机的定义
M=(S,
Σ
,f,So,Z)
< br>，
由
f
的定义可知
f(x,a)
、
f(y,b)
均为多值函
数，因此
M
是一非确定有
限自动机。
先画出
NFA
M
相应的状态图，如下
图所示。
a
a
b
b
（
1
）
A
→
aABl
（
2
）
A
→
a
（
3
）
B
→
Bb
（
4
）
B
→
d
I0
：
S
→．
A
A
→．
aABl
a
A
→．
a
I1
：
S
→<
/p>
A
．
X
Y
b
I
{x}
{y}
{x,y}
I
a
{x,y}
—
{x,y}
I
b
I2
：
A
→
a
．
ABl
A
A
→
a<
/p>
．
A
→．
aABl
A
→．
a
I3
：
A<
/p>
→
aA
．
Bl
d
B
→．
Bb
B
→．
d
B
{y}
{x,y}
{x,y}
a
将转
换矩阵中的所有子集重新命名，
形成下
表所示的状态转换矩阵，
即得到
f
字符
状态
0
1
2
I5
：
A
→
aAB
．
l
B
→
B<
/p>
．
b
b
I7
：
B<
/p>
→
Bb
．
First
（
A
）
={a}follow
（
A
）
={#
，
d}
（
B
）
={l}
2
First
< br>（
B
）
={d}follow<
/p>
1
SLR
（
1
）分析表如下：
—
a
b
0
1
2
3
4
5
6
7
2
a
S2
S2
2
2
b
S7
d
R2
S4
R1
l
R4
S6
R3
#
ACC
R2
R1
M
′
=({0,1,2},{a,b},f,0,{1,2})
，
M
′状态转换图如下图所示。
a
0
2
a, b
b
b
1
（注意：
本题由于集合的命名和先后顺序不
同，可能最终结果不同。
）
12
解：拓广文法
（
0
）
S
→
A
13
解：
1
(j
＞
,x,y,3)
2
(j,_,_,5)
3 (=,1,_,m)
4
(j,_,_,7)
5
(+,x,y,T
1
)
6 (=,
T
1
,_,m)
7:
14
解：消除左递归：
G(S): S
?
(L) | a
L
?
SL
’
18
S
L
L
’
构造
FI
RST
集，如下：
用子集法构造状态转换矩阵，如下表所示。
（
1
）
FIRST(S) = {(, a}
I
I
a
I
b
（
2
）
FIRST
(L) = {(, a}
{x}
{1}
-
（
3
）<
/p>
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)
分析表
< br>将
状
态
分
为
终
态
集
{
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
’
因为
<
/p>
{X,1,2}b={_,3,_},
所以分为
< br>
ε
?
,SL
’
最后得到集合
{X,2},{1},{3,5},{4},{Y
}
重
新命名为
1
，
2
，
3
，
4
，
5
得到最小化的
DFA
M
< br>′
17
证明：
该文法产生的语言是
a
的个数和
状态转换矩阵和状态转换图如下图所示。
b
的个数相等的串的集合。该文法二义，例
如句子
abab
有两种不同的最左推导。
I
I
a
I
b
1
2
_
2
1
3
S
?
aSbS
?
abS
?
abaSbS
?
ababS
?
abab
3
-
4
4
5
3
S
?
aSbS
?
abSaSbS
?
abaSbS
?<
/p>
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
状态<
/p>
四元式
处
管
图，
如下图所示。
优化段
四元式
理
理
2
5
目标代码生成器
目标代码
a
a
b
b
（
1
）词法分析器，又称扫描器，它接受
a
b
b
a
输入的源程序，对源程序进行词法分析，识
X
1
3
4
Y
别出一个个单词符号，
其输出结果是
二元式
19
L
’
?
,
SL
’
|
ε
a
1
a
(
单词种别，单词自身的值
)
流。
（
2
）语法分析器，对单词符号串进行语
法分析（根
据语法规则进行推导或归约）
，
识别出程序中的各类语法单位，
最终判断输
入串是否构成语法上正确的句子。
< br>
（
3
）语义分析及中间代码生
成器，按照
语义规则对语法分析器归约出（或推导出）
S
(
L
)
L
,
S
的语法单位进行语义分析并把它们翻译成
< br>一定形式的中间代码。
编译程序可以根据不
同的需要选择
不同的中间代码形式，
有的编
译程序甚至没有中间代码形式，<
/p>
而直接生成
目标代码。
（
4
）优化器对中间代码进行优化处理。
一般最初生成的中间代码执行效率都比较
低，
因此要
做中间代码的优化，其过程实际
上是对中间代码进行等价替换，
使程序在执
行时能更快，并占用更小的空间。
（
5
）目标代码生成器，把中间代码翻译
成目标程序。
中间代码一般是一种与机器无
关的表示
形式，
只有把它再翻译成与机器硬
件直接相关的机器能识别的语
言，
即目标程
序，才能在机器上运行。
（
6
）表格管理模块保持一系列的表格
，
登记源程序的各类信息和编译各阶段的进
展状况。
编译程序各个阶段所产生的中间结
果都记录在表格中，
所需要的信息也大多从
表格中获取，
整个编译过程都在不断
和表格
打交道。
（
< br>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,
T
1
)
②
(*, a,
T
1
,
T
2
)
③
(@, T2, _,
T
3
)
④
(+,
T
3
, d,
T
4
)
25
解：
(1) (j>, A,
B, 3)
(2) (j, _, _, 11)
(3) (j>, C, D, 5)
(4) (j, _, _, 8)
(5) (*, Y, Z,
T
1
)
(6) (=,
T
1
, _, X)
(7)
(j, _, _, 1)
(8) (+, Y, Z,
T
2
)
(9) (=,
T
2
, _, X)
(10)
(j, _, _, 1)
(11)
26
解：
（
1
）
0*(0|10)*0*
或者
(0|10)*
（
2
）
①
NFA
（
2
分）
20
-
-
-
-
-
-
-
-
-
上一篇：(完整版)cfa一级公式
下一篇：HACMP7配置