龙书 第四章课后作业答案

P1774.14 为练习4.3的文法构造一个预测语法分析器 bexpr→bexpr or bterm|bterm

bterm→bterm and bfactor | bfactor

bfactor→not bfactor|(bexpr)|true |false 解1 非递归方法 1) 消除左递归

①bexpr→bterm A ②A→or bterm A ③A→ε

④bterm→bfactor B ⑤B→and bfactor B ⑥B→ε

⑦bfactor→not bfactor ⑧bfactor→(bexpr) ⑨bfactor→true ⑩bfactor→false

2) 求first集 与 follow集

针对以同一非总结符开头的产生式右部求first集 如果该非终结符能产生ε 则需要求其follow集

①bexpr→bterm A first(bterm A)= {not,(,true,false}

②A→or bterm A first(or bterm A)={or}

③A→ε follow(A）=follow(bexpr)= {$, )}

④bterm→bfactor B first(bfactor B)={not,(,true,false} ⑤B→and bfactor B first(and bfactor B)={and}

⑥B→ε follow(B）=follow(bterm)=first(A)

因为first(A)= {or , ε} 包含ε

所以follow(B）=follow(bterm)

=first(A) ∪follow(A）-{ε}={or, $, )}

⑦bfactor→not bfactor first(not bfactor)={not} ⑧bfactor→(bexpr) first((bexpr))={(} ⑨bfactor→true first(true)={true} ⑩bfactor→false first(false)={false} 3) 根据步骤2）画预测分析表 or and not bexpr ( ① ) true ① false ① $ ③ ⑥ ② ⑥ ⑤ ① ③ ⑥ A bterm B ④ ④ ④ ④ ⑦ ⑧ ⑨ ⑩ bfactor 表中空白处填error，表示调用错误处理程序

4) 根据步骤3）编写预测分析程序

下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。 repeat

1

X=当前栈顶符号;a=当前输入符号； if X∈ＶT∪{#} then

if X=a then

if X≠# then {将X弹出,且前移输入指针} else error

else

if M[X,a]=Y1Y2…Yk then

{将X弹出;依次将Yk…Y2Y1压入栈； 输出产生式X→Y1Y2…Yk }

else error

until X=#

注：

如果考虑错误恢复，上面的预测分析表还显得简单，应该将每个非总结符的follow集作为同步(sync)记号，便于错误恢复。具体留给感兴趣的同学深入研究

解2：递归下降方法

①消除给定文法中的左递归，并提取公因子： bexpr→bterm {or bterm } bterm→bfactor {and bfactor}

bfactor→not bfactor | (bexpr) | true |false ② 用类Pascal语言写出其递归预测分析器 PROCEDURE bexpr; BEGIN Bterm

WHILE (lookahead =='or') BEGIN

match ('or'); bterm; END; END;

PROCEDURE bterm; BEGIN

2

bfactor;

WHILE (lookahead =='and'); BEGIN

match ('and'); bfactor; END; END;

PROCEDURE bfactor; BEGIN

if (llokahead=='not') then BEGIN match ('not'); bfactor; END

else if (lookahead=='(') then BEGIN match ('('); bexpr; match(')'); END

else if (lookahead =='true') then match ('true)

else if (lookahead=='false') then match ('false'); else error; END;

P1784.24 图4-60给出了练习4.1中文法的算符优先关系，利用这些优先关系分析练习4.1(b)的句子。 S→(L)|a L→L,S|S

解：

对每个终结符或＄建立符号f与g，把f(和g)

分成一组。根据文法的算符优先关系表，画出如下的有向图。

3

优先函数如下：

用算符优先分析法分析句子(a,(a,a))

另外2个句子的分析略。

4

(也可不必如上面先构造优先矩阵在分析，亦可直接分析)

P1794.35 考虑下面文法 E→E+T|T T→TF|F F→F*|a|b

a） 试为该文法构造SLR语法分析表

解：

该文法的拓广文法G'为 (0) E' → E (1) E → E+T (2) E → T (3) T → TF (4) T → F (5) F → F* (6) F → a (7) F → b

其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下: I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I1 ={E'→E·, E→E·+T}

I2 ={E→T·, T→T·F, F→·F*, F→·a, F→·b} I3 ={T→F·, F→F·*} I4 ={F→a·} I5 ={F→b·}

I6 ={E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I7 ={T→TF·, F→F·*} I8 ={F→F*·}

I9 ={E→E+T·, T→T·F, F→·F*, F→·a, F→·b}

求FOLLOW集：

FOLLOW(E)={＋, ＄}

FOLLOW(T)={＋, ＄, a, b} FOLLOW(F)={＋, ＄, a, b, *}

5

本文来源：https://www.bwwdw.com/article/tngt.html