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}
表中空白处填error，表示调用错误处理程序
4)根据步骤3）编写预测分析程序
下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。
repeat
X=当前栈顶符号;a=当前输入符号；
if X∈ＶT∪{#} then
if X=a then
if X≠# then {将X弹出,且前移输入指针}
else error
else
if M[X,a]=Y1Y2…Y k then
{将X弹出;依次将Y k…Y2Y1压入栈；
输出产生式X→Y1Y2…Y k }
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
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
)
分成一组。根据文法的算符优先关系表，画出如下的有向图。
优先函数如下：
用算符优先分析法分析句子(a,(a,a))
另外2个句子的分析略。
(也可不必如上面先构造优先矩阵在分析，亦可直接分析)
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)如下:
= {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*,F→·a, F→·b} I
={E'→E·, E→E·+T}
I
1
={E→T·, T→T·F, F→·F*, F→·a, F→·b}
I
2
={T→F·, F→F·*}
I
3
={F→a·}
I
4
={F→b·}
I
5
={E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}
I
6
={T→TF·, F→F·*}
I
7
={F→F*·}
I
8
={E→E+T·, T→T·F, F→·F*, F→·a, F→·b}
I
9
求FOLLOW集：
FOLLOW(E)={＋, ＄}
FOLLOW(T)={＋, ＄, a, b}
FOLLOW(F)={＋, ＄, a, b, *}
