自下向上语法分析——算符优先分析法

首先看一下什么是算符文法

算符文法

设有文法G，若G中没有形如U —> …VW…的规则，其中VW为非终结符，则称G为算符文法。
两个重要性质：
1，在算符文法中任何句型都不含两个相邻的非终结符
2，若Ab或bA出现在算符文法的句型B中，其中A是非终结符，b是终结符，则B中任何含b的短语必含有A。

定义任何两个终结符号之间的优先关系

设G是一个算符文法，a和b是任意两个非终结符，P、Q、R是非终结符，则有：
1，a = b(即a跟b的优先级一样）当前仅当含有形如P —> …ab…或P—>…aQb的规则
2，a < b(即a比b的优先级低）当前仅当含有形如P —> …aR…的规则，且R可以推导出b…或者Qb
3，a > b(即a比b的优先级高）当前仅当含有形如P —> …Rb…的规则，且R可以推导出…a或者…aQ

这里解释一下2和3，在2和3当中，对于2来说，R是一个非终结符，当出现b的时候，要先规约为R，这样才能形成aR的形式，所以b要比a早规约，所以b的算符优先级比a的高。同理得3.

而且这里要注意一下，P —> …aR…，且R可以推导出b…或者Qb，在这里，b是要出现在第一个字符或着前面只能非终结符。

算符优先文法的定义

设有一个不含空字符串的算符文法，如果任意两个非终结符号对（a，b）在上面三种优先关系中只有一种关系成立，则是算符优先文法。

算符优先关系表的构造

为什么要构造FIRSTVT和LASTVT呢？
构建这个是为了方便我们算出算符优先关系表。
看一下这道题目：

如何构建呢？第一步就是求他们的FIRSTVT和LASTVT。

对于这个的求解应该问题不是很大，要是前面的自顶向下有学好的话，跟first和follow差不多。

这里需要理解一下，应该也不是很难，对于相等的来说是比较简单的，而对于小于的话，因为非终结符在终结符的右边，则T的FIRSTVT应该要比该终结符优先级高，参考我前面的解释。

这里对于符号说明一下：
E—>$E$

最左素短语

算符优先文法使用最左素短语来刻画可规约串。
什么是短语？这个你应该要自己了解一下。

素短语是指至少包含一个终结符，并且除自身外不再包含其他的素短语。而最左素短语是指在最左边的素短语。

最左素短语求法

对于这个性质，我们解释一下。比如有abc这三个，假如a优先级小于b，那么b就要比a先规约，假如c优先级小于b，那么b就要比c先规约。所以b作为最左素短语，应该最先被规约。

算符优先分析算法

当我们理解了上面的几个概念之后，再来看这个算法会变得非常简单。我们每次只需要从左向右，找最左素短语就可以了。
我们建立一个栈，如果栈顶的终结符号和待输入的符号之间的优先关系是小于或着等于的话，表示栈顶符号串未形成最左素短语，此时压入待输入符号。如果优先关系是大于的话，说明已经找到最左素短语的尾巴了，再从栈顶开始，寻找最左素短语的头。如何两个终结符号间不存在优先关系，则进行报错处理。

优先函数的构造

可以看到在上面那个文法当中，终结符号的优先关系用一个矩阵表示，当有n个终结符时，需要（n + 1）的平方的内存单元，占用了大量内存资源。因此，我们一般使用优先函数来代替优先矩阵。对于n个终结符，只需要2 * （ n + 1）个内存单元存放优先函数。

优先函数f和g的定义

当a < b时，令f(a) < g(b)
当a = b时，令f(a) = g(b)
当a > b时，令f(a) > g(b)
这里要说明一下，前面的比较是比较两个终结符的优先关系，是没有具体数值意义的。而后面两个函数的比较是具体数值的大小。

优先函数的构造方法

方法一：Floyd方法
1,对所有终结符（包括$）a,令f(a) = g(a) = 0；（或着其他任何整数）
2,对所有终结符a和b，
如果a > b,而f(a) <= g(b),则令f(a) = g(b) + 1。
如果a < b,而f(a) => g(b),则令g(b) = f(a) + 1。
如果a = b,而f(a) != g(b),则令f(a) = g(b) = max( f(a), g(b) )。
3,重复执行2知直到过程收敛，重复过程中，若f(a)或g(b)的值大于2 * n，则不存在优先函数。

算符优先分析法的局限性

由于忽略了非终结符在归约过程中的作用，可能导致把本来不是句子的输入串误认为是文法句子。

参考资料

《编译原理 第四版》作者：刘铭 徐兰芳 骆婷