编译原理试题 下载本文

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