编译原理-语法分析-预测分析表

一、预测分析表

一张二维表M[A,a]，存储着每个非终结符号和终结符号（以及串尾符号$）的映射关系A->a。对于确定的A和a，可以确认其分析动作。

在非递归预测分析中，根据栈顶的非终结符号和当前指针指向的输入字符，确定下一步的程序动作。

二、预测分析表的构造

1、first集合的构造

first集合，即是对于一个任意的文法符号（包含终结符和非终结符），其可以推导出的所有字符串的首字符的集合。

对于终结符号，直接有first(x)=x

对于非终结符号：

首先将其产生式中能直接产生出非终结符号的式子中的首字母加入进来。即，形如A->a，A->aA的产生式。其次，将首个非终结符所能产生的所有终结符号加入进来。即，形如A->B，B->b的产生式。再次，如果A所推导出的产生式串中前i-1个非终结符号都有产生式，那么第i个非终结符号就可以当作收个非终结符号来处理。

可以不断循环这个算法，直到集合稳定。在解决较为简单的问题时，可以根据产生式复杂程度顺序写出其first集合，从而简化运算。

2、follow集合的构造

follow集合仅仅服务于非终结符号。它包含了该文法中全部的能推导出形如Aa产生式的跟随在A之后的终结符。此外，如果该文法可推到出形如S->A的产生式，那么也被加入到follow集合中。

3、根据first和follow集合构建预测分析表

对于文法G中的每一个产生式(A->a)：

首先，对于所有非终结符号a的first(a)，把A->a放入M[A,a]中。

其次，如果first(a)中含有，那么对于follow(A)中的每一个终结符b，把A->放入M[A,b]。

至此，预测分析表构造完毕。