2024年5月25日发(作者：)

第4章语法分析习题答案

1．判断

（1）由于递归下降分析法比较简单，因此它要求文法不必是LL(1)文法。(× )

（2）某些左递归文法可能是LL(1)文法。(× )

（3）任何LL(1)文法都是无二义性的。(√)

（4）存在一种算法，能判定任何上下文无关文法是否是LL(1) 文法。(√)

（5）算符优先分析过程和规范归约过程都是最右推导的逆过程。

(× )

（6）每一个SLR(1)文法都是LR(1)文法。(√)

（7）任何一个LL(1)文法都是一个LR(1)文法，反之亦然。(× )

（8）由于LALR是在LR(1)基础上的改进方法，所以LALR的能力强于LR(1)。(× )

（9）所有LR分析器的总控程序都是一样的，只是分析表各有不同。(√)

（

10

）算符优先分析法很难完全避免将错误的句子得到正确的归约。(√)

2．文法G[E]：

E→E+T|T

T→T*F|F

F→(E)|i

试给出句型(E+F)*i的短语、简单短语、句柄和最左素短语。

答案：

画出语法树，得到：

短语: (E+F)*i ，(E+F) ，E+F ，F ，i

简单短语: F ，i

句柄: F

最左素短语: E+F

3．文法G[S]：

S→SdT | T

T→T

G→(S) | a

试给出句型(SdG)

答案：

画出语法树，得到：

短语：(SdG)

简单(直接)短语：G 、a

句柄：G

最左素短语：SdG

4．对文法G[S]提取公共左因子进行改写，判断改写后的文法是否为LL(1)文法。

S→if E then S else S

S→if E then S

S→other

E→b

1

答案：

提取公共左因子；文法改写为：

S→if E then S S'|other

S'→else S| 

E→b

LL(1)文法判定：

① 文法无左递归

② First(S)={if,other}, First(S')={else, }

First(E)={b}

Follow(S)= Follow(S')={else,#}

Follow(E)={then}

First(if E then S S')∩First(other)= 

First(else S)∩First()= 

③First(S')∩Follow(S')={else}不为空集

故此文法不是LL(1)文法。

5．对于给定文法G[bexpr]：

bexpr→bexpr or bterm | bterm

bterm→bterm and bfactor | bfactor

bfactor→not bfactor|(bexpr) |true |false

（1）用EBNF改写该文法，消除左递归。

（2）试用类C语言为其构造一个递归下降分析程序。

答案：

（1）用EBNF改写该文法，消除左递归：

bexpr→bterm {or bterm }

bterm→bfactor {and bfactor}

bfactor→not bfactor | (bexpr) | true |false

（2） 用类C语言写出其递归下降分析程序

bexpr(){

bterm();

while (sym == ”or”){

getsym();

bterm();

}

}

bterm(){

bfactor();

while (sym == ”and”){

getsym();

bfactor();

}

}

bfactor(){

if (sym == ”not”){

2