19.算符优先分析中的可归约串是指(最左素短语)。 20.(自下而上)语法分析的关键问题是精确定义可归约串的概念。
四、简答
1.给出上下文无关文法的定义。
一个上下文无关文法G是一个四元式(VT,VN,S,P),其中: VT是一个非空有限集,它的每个元素称为终结符号;
VN是一个非空有限集,它的每个元素称为非终结符号,VT∪VN=Φ; S是一个非终结符号,称为开始符号;
P是一个产生式集合(有限),每个产生式的形式是P→α,其中,P∈VN,α∈(VT∪*
VN)。
开始符号S至少必须在某个产生式的左部出现一次。
2.给出正规式与正规集的递归定义。
(1)ε和Φ都是∑上的正规式,它们所表示的正规集分别为{ε}和Φ; (2)任何a∈∑,a是∑上的一个正规式,它所表示的正规集为{a};
(3)假定U和V都是∑上的正规式,它们所表示的正规集分别记为L(U)和L(V),那么,
*
(U|V)、(U·V)和(U)也都是正规式,它们所表示的正规集分别为L(U)∪L(V)、L(U)L(V)(连
*
接积)和(L(U))(闭包)。
仅由有限次使用上述三步骤而得到的表达式才是∑上的正规式。仅由这些正规式所表示的字集才是∑上的正规集。
3.设文法G为: S→aAcB|BdS A→BaB|aBc|a B→aScA|cAB|b
对于输入串aacabccb,给出最左推导。
S=>aAcB=>aaBccB=>aacABccB=>aacaBccB=>aacabccB=>aacabccb
4.设文法G为: S→BA A→BS|d B→aA|bS|c
对于输入串adccd,给出最左推导。
S=>BA=>aAA=>adA=>adBS=>adcS=>adcBA=>adccA=>adccd
5
5.证明:文法G:
P→PaP|PbP|cP|Pe|f 为二义文法。
对于文法G定义的句子fbfbf,有两棵不同的语法树:
P P P b P P b P
P b P f f P b P
f f f f
所以该文法是二义文法。
6.证明:文法G:
P→S+S|S*S|i|(S) 为二义文法。
对于文法G定义的句子i+i*i,有两棵不同的语法树:
S S S * S S + S
S + S i i S * S
i i i i
所以该文法是二义文法。
7.给定正规文法G:
S→aS|bA|b a b A→aS
S a A 请构造与之等价的有限自动机。
b f 6
8.给定正规文法G: S→aA
A→bA|aB|b B→aA
请构造与之等价的有限自动机。
b
a b F S A a a
B
9.对下面给出的NFA确定化。
a b
a b a
S A F a a b a 1 2 3 a 4a
10.对下面给出的NFA确定化。 a
S a A
a a Bb 7
a
a 3 2
1 a b a
4b 或
a a
2 a 1 b a
3b
11.对下面给出的DFA最小化。 b a A a a
a
S b B Db b
C a
b
1 a 2 a a
3b
8