编译原理与实践：预测分析过程揭秘

1.分析栈

预测分析程序使用分析栈实现句子的分析。分析栈用来存放句子分析过程中所产生的文法符号序列。此外，在各种分析技术的实现中，通常总是约定在输入符号串后面放置符号‘#’，作为输入的结束标识。符号‘#’称为右端标志符号，不是文法符号。

自上而下的语法分析从文法开始符号出发，预测分析程序也是从将S放入分析栈开始。因此，分析开始时，栈和输入串的初始情形为

符号栈 输入串

#S w#

分析程序通过将栈顶的非终结符号替换为合适的候选式推进分析。在一系列成功的推导或匹配动作后，分析栈中已经没有了任何可以进行推导的非终结符，或与输入符号相匹配的终结符，而且输入串中的各个符号也得到了匹配。那么，分析栈最终将形成如下情形

符号栈 输入串

# #

句子的结束符相匹配，表示分析成功。需要注意，为了判断是否得到成功分析的情形，初始时将右端标志符号先于文法的开始符号放入了分析栈中。换句话说，为句子增加了#，也需要为推导句子的开始符号后面增加#。

2.预测分析表

预测分析表是一个M[A，a]形式的二维表格，其中A为非终结符，a是终结符或‘#’。分析表的垂直维度包含对应文法所有的非终结符，水平维度列举了文法所有的终结符以及右端标志符‘#’。表格中的表项M[A，a]中存放着一条关于A的产生式，表明当A面临输入符号a的推导时，所应采用的候选式。以表达式文法（G4.1）为例，其分析表如表4-1所示。

表4-1　文法的预测分析表

表格项M[A，a]中也可能存放一个“出错标志”，指出A根本不该面对输入符号a，也就是a的出现是语法错误。在表4-1中，空白格均暗含“出错标志”。

3.分析过程

分析程序初始化时，将‘#’压入栈底，然后压入文法开始符号，使得S位于栈顶，准备开始后续的推导动作。预测分析程序分析过程中，将重复弹出栈顶符号，根据栈顶符号X与当前输入符号a，决定所应采取的分析动作。

(www.xing528.com)

预测分析程序工作过程

当栈顶符号是非终结符号时，则将其替换为分析表中相应的候选式而实现后续的推导和匹配动作。需要注意，为了实现最左推导，需要将候选式的各个符号按逆序压入栈中，保证处于最左侧的文法符号先被弹出栈顶。当栈顶符号是终结符号时，则判断是否与当前的输入符号相匹配。因此，每当弹出栈顶符号X之后，分析程序都将执行下述四种可能的动作之一。

（1）若X=a=‘#’，则分析成功而结束。

（2）若X=a≠‘#’，则将X从分析栈顶弹出，让a指向下一个输入符号。

（3）若X是一个非终结符，则查看分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先将X弹出分析栈顶，然后，将产生式的右部符号串按逆序逐一推进分析栈。若右部符号为ε，则意味着什么也不入栈。

（4）其他情况，即X∈VT，且X≠a；或者X∈VN，且M[A，a]中存放着“出错标志”，则调用出错处理程序error。

依据上述过程，构造预测分析程序的总控程序如算法4.2所示。由于需要不断地弹出栈顶符号完成相应的动作，因此程序的主体是一个循环语句。循环体的内部将根据栈顶符号的不同情况完成推导或匹配动作，因此由分支语句构造。如果在分析过程中构造语法分析树，可以在将每个非终结符或终结符压入栈中时，构造树中相应的结点。

算法4.2 预测分析程序。

LL（1）分析法控制程序

依据算法4.2，对输入符号串i+i*i进行预测分析的过程如表4-2所示。

表4-2　i+i*i的分析过程

注意，左递归的消除并不会改变待识别的语言，但却改变了文法和语法分析树。这种改变导致了分析程序的构造变得复杂化。例如，表达式文法经过消除左递归之后输入串的语法分析不再能够表达左结合性了。分析程序仍应该构造恰当的左结合性语法分析树。可以采用的策略是，由于产生式形式为E→TE和E→+TE，针对TE将E左侧的T生成的子树作为参数传递给E的子程序，作为E生成的加法运算的左操作数。