简单优先分析法
1.基本概念
通过语法树来理解这三个概念更加简单：
文法G1[S]：
S→AB
A→bB
A→Aa
B→a
B→Sb
-
短语：若S=*=>αAδ且A=+=>β，则称β是相对于非终结符A的句型αβδ的短语。
即：语法树中以非终结符的作为根的子树的叶子所组成的字符串。
如：ba是相对于非终结符A的句型AB的短语。句型baSb的短语有ba，a，Sb，baSb。
-
直接短语：若S=*=>αAδ且A=>β，则称β是相对于非终结符A的句型αβδ的直接短语。
即：语法树中以非终结符的作为根的子树，它的孩子都是叶子，没有其他子树。
如：Sb是相对于非终结符B的句型AB的短语。句型baSb的短语有a，Sb。
-
句柄：位于句型最左边的直接短语称为该句型的句柄。
即：位于语法树中最左边的直接短语。
如：句型baSb的句柄是a。
2.优先关系定义
-
X和Y优先级相等，表示为
X=·Y，当且仅当G中存在产生式规则A=>···XY···。解读：X、Y的优先级相同，当XY存在一个句柄之中，它们将同时被归约。表现在语法树中S=·b。
-
X优先级小于Y，表示为
X<·Y，当且仅当G中存在产生式规则A=>···XB···，B=+=>Y···。解读：X优先级小于Y，当XY存在一个句型中时，它们将不可能出现在同一个句柄中，Y一定比X先被规约。表现在语法树中b<·a。
-
X优先级大于Y，表示为
X>·Y，当且仅当G中存在产生式规则A=>··BD···，B=+=>···X，D=*=>Y···。解读：X优先级大于Y，当XY存在一个句型中时，它们将不可能出现在同一个句柄中，X一定比Y先被规约。表现在语法树中a>·S。
- X和Y的优先级为空，表示在文法的任何句型中都不会出现该符号对相邻出现的情况。
注意：以上优先关系之间不具有对成性。
3.简单优先文法定义
一个文法是简单优先文法，需要满足以下两个条件：
- 在文法符号集中V，任意两个符号之间必须之后一种优先关系存在。（显然满足）
- 在文法中，两个产生式不能有相同的右部。
4.简单优先分析法的操作步骤
-
将输入输入串a1a2···an#依次压栈，不断比较栈顶符号ai和下一个待输入符号aj的优先级，若ai>·aj则进行下一步，否则重复此步骤。
解读：停止条件是ai>·aj表示前面输入串一定比后面先归约，所以只需要在前面找句柄就行了。
-
栈顶符号ai即为句柄尾，从此处向左寻找句柄头ak，满足ak-1<·ak。
解读：从后向前找ak-1<·ak表示ak之前的输入串一定比ai···ak后归约，由此确定现在就是要归约ai···ak。
由句柄ai···ak在文法中寻找右部为ai···ak的产生式；找到则将句柄替换为相应左部，找不到则说明该输入串不是该文法的句子。
重复以上步骤直到归约完成。
5.实例
由于还是以上面的例子不满足简单优先文法定义（b和b的优先关系不唯一），这里我们用另一个文法来举例。
文法G2[S]：
S→bAb ①
A→(B ②
A→a ③
B→Aa) ④输入串为b(aa)b#
- 首先我们做出文法符号的优先关系矩阵：
| S | A | B | a | b | ( | ) | # | |
|---|---|---|---|---|---|---|---|---|
| S | ||||||||
| A | = | = | ||||||
| B | > | > | ||||||
| a | > | > | = | |||||
| b | = | < | < | |||||
| ( | < | = | < | < | ||||
| ) | > | > | ||||||
| # |
这里#比其相邻所有符号的优先性都要小。
- 然后按照简单优先分析法进行归约：
| 步骤 | 栈S | 当前输入符 | 输入串剩余部分 | 动作 |
|---|---|---|---|---|
| 1 | # | b | (aa)b# | 移进 |
| 2 | #b | ( | aa)b# | 移进 |
| 3 | #b( | a | a)b# | 移进 |
| 4 | #b(a | a | )b# | 归约③ |
| 5 | #b(A | a | )b# | 移进 |
| 6 | #b(Aa | ) | b# | 移进 |
| 7 | #b(Aa) | b | # | 归约④ |
| 8 | #b(B | b | # | 归约② |
| 9 | #bA | b | # | 移进 |
| 10 | #bAb | # | 归约① | |
| 11 | #S | # | 接受 |
其语法树如下：
