预测分析表构造方法-编译原理与实践

预测分析表是预测分析的核心。对于任意的文法G，构造其预测分析表M[A，a]的基本思想与LL（1）分析法相对应，包含如下两种情形。

（1）对于产生式A→α，a∈FIRST（α），那么，当A呈现于分析栈栈顶，且a是当前输入符号时，α应被当作是A唯一合适的全权代表。因此，M[A，a]中应放进产生式A→α。

（2）当ε∈FIRST（α）时，如果面临的输入符号a（包括#）属于FOLLOW（A），则认为A可以进行自动匹配，应将A→α放在M[A，a]中。

由上所述，为了构造预测分析表M，需要构造文法符号的FIRST集和FOLLOW集。

1.FIRST集的构造

FIRST集中的元素是文法符号能够推导出的符号串的首个终结符。设文法的任一文法符号X，X∈（VT∪VN），通过使用算法4.3中的规则，直至再没有新的终结符号或ε加入FIRST集合中，可以构造出FIRST（X）集。

算法4.3 构造文法符号X的FIRST集合。

（1）若X∈VT，则FIRST（X）={X}。

（2）若X∈VN，且有产生式X→a…，则将a加入FIRST（X）中；特别地，如果X有产生式X→ε，则将ε也加入FIRST（X）中。

（3）若X→Y…是一条产生式，其中Y∈VN，则将FIRST（Y）中的所有非ε符号都加到FIRST（X）中。

（4）若X→Y1Y2…Yk是一条产生式，其中Y1…Yi-1都是非终结符，而且对于任何j（1≤j≤i-1），FIRST（Yj）都含有ε，即Y1…Yi-1⇒*ε，则将FIRST（Yi）中的所有非ε元素都加到FIRST（X）中；特别地，如果对于任何j（j=1，2，…，k），FIRST（Yj）均含有ε，即Y1…Yi-1⇒*ε，则将ε加到FIRST（X）中。

依据算法4.3，可以对文法G的任何符号串α∈（VT∪VN）*，构造集合FIRST（α）。设α=X1X2…Xn，那么

（1）若α=ε，则FIRST（α）={ε}。

（2）若α≠ε，则FIRST（α）=FIRST（X1）\{ε}；

（3）若X1…Xi-1⇒*ε，则将FIRST（Xi）\{ε}加至FIRST（α）中；特别是，X1…Xn⇒*ε，则将ε也加至FIRST（α）中。

2.FOLLOW集的构造

FOLLOW中的元素是句型中会紧跟在非终结符后出现的终结符号。对于文法G的每个非终结符A构造FOLLOW（A）的方法是连续使用下面的规则，直至再没有新的终结符号可以被加入任何FOLLOW集合中为止。

算法4.4 构造文法符号的FOLLOW集合。

（1）对于文法的开始符号S，置#于FOLLOW（S）中。

（2）若A→αBβ是一条产生式，则将FIRST（β）\{ε}加至FOLLOW（B）中。

（3）若A→αB是一条产生式；或A→αBβ是一条产生式，且ε∈FIRST（β）（即β⇒*ε），则将FOLLOW（A）加至FOLLOW（B）中。

例4.8 构造文法（G4.2）每个非终结符的FIRST和FOLLOW集合。

3.构造预测分析表(www.xing528.com)

在对文法G的每个非终结符A及其任意候选α都构造出FIRST（α）和FOLLOW（A）之后，便可以利用其来构造G的分析表M[A，a]。对于产生式A→α，如果a∈FIRST（α），则将A→α放入M[A，a]中。当ε∈FIRST（α）时，如果a∈FOLLOW（A），则将A→α放在M[A，a]中。构造分析表M的方法如算法4.5所示。

算法4.5 构造文法的预测分析表。

（1）对文法G的每条产生式A→α，执行第2步和第3步；

（2）对每个终结符a∈FIRST（α），将A→α加至M[A，a]中；

（3）若ε∈FIRST（α），则对任何b∈FOLLOW（A），将A→α加至M[A，b]中；

（4）将所有无定义的M[A，a]标上“出错标志”。

文法G的预测分析表M不含多重定义，当且仅当G是LL（1）文法。

例4.9 构造文法（G4.2）的预测分析表。

依次扫描各个产生式，执行算法的第2步和第3步，如下所示。

对于E→TE，FIRST（TE）={（，i}，则置M[E，（]和M[E，i]为E→TE；

对于E→+TE，FIRST（+TE）={+}，则置M[E，+]为E→+TE；

对于E→ε，FOLLOW（E）={），#}，则置M[E，）]和M[E，#]为E→ε；

对于T→FT，FIRST（FT）={（，i}，则置M[T，（]和M[T，i]为T→FT；

对于T→*FT，FIRST（*FT）={*}，则置M[T，*]为T→*FT；

对于T→ε，FOLLOW（T）={+，），#}，则置M[T，+]、M[T，）]和M[T，#]为T→ε；

对于F→（E），FIRST（（E））={（}，则置M[F，（]为F→（E）；对于F→i，FIRST（TE）={i}，则置M[F，i]为F→i。

最终可得表4-1所示的预测分析表。

例4.10 构造if语句文法的预测分析表。

首先构造文法各非终结符的FIRST集和FOLLOW集。然后依次扫描各个产生式，执行算法的第2步和第3步，可得表4-3所示的预测分析表。

表4-3　if语句文法的预测分析表

表4-3中的项目M[S，else]包括两项内容，这与悬挂else二义性对应。此时，倾向于使用产生式S→else S而不是S→ε，这正好与最近嵌套规则对应。通过这样的修改，表格变为没有二义性的。于是可以直接使用这个文法进行分析，就像是一个LL（1）文法。