该习题中主要存在的问题是递归下降法方面的。可能是因为书上没有给出详细的说明。
一般来讲,递归下降法的做法是这样的:
对应于每个非终结符号,多存在一个对应的过程。这个过程又可以分为几个部分,每一部分对应于这个非终结符号的一个规则。这些部分是选择语句的一个分支。
1:对于一个规则的右部X1X2...Xm,该部分语句的结构就是下面的句子的顺序组合。
如果Xi是非终结符号,句子是对Xi过程的调用。
如果Xi是终结符号,那么句子就是
if(sym = xi) then getsymbol
else Error.
将这些句子顺序组合后的复合语句可以处理这个规则。处理空规则的语句是空语句。
2:上面的符合语句是选择语句的分支。编写对应于非终结符号的过程还需要添加判断使用哪个规则的代码。这些代码可以通过
LL(1)的预测分析表来生成。但是,一般的情况都会有所省略。
a:当该非终结符号只有一个规则的时候,可以直接将对应的复合语句。
b:如果符号有多个规则,那么要使用LL(1)的预测分析表,并通过sym
的值来确定要执行哪个复合语句。有些时候可以使用规则的第一个符号来确定执行哪个语句,但是这并不是一定可行的。
c:对于有空规则的非终结符号,要确定何时使用空规则。这需要小心处理。需要计算Follow(U),特别要注意U::=X1X2...Xm(只有一个规则)
和U::=X1X2...Xm|空(一个普通规则和一个空规则)。
d:使用LL(1)的分析表的时候,基本的做法是:如果有A[U,x1]=A[U,x2]=...
=A[U,xm]='A::=X1X2...Xn',那么就有对应的语句
if(sym = x1 or sym = x2 or,.,or sym = xm)
then S;
其中S是处理X1X2...Xn的复合语句。这样可以使用if...then...else结构将这样的语句联系起来,整个的过程就形如:
if(sym = x11 or sym = x12 or,.,or sym = x1m)
then S1
else if (sym = x21 or sym = x22 or,.,or sym = x2m)
then S2
else ...
else if(sym = xk1 or sym = xk2 or,.,or sym = xkm)
then Sk
else error;
也可以将最后的选择语句(最后三行)改为
Sk;
这种写法不会影响程序的在正确性,但是会延迟错误的报告。