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