从FIRSTVT/LASTVT到优先关系表：算符优先分析的核心构造实战
1. 算符优先分析法的核心概念
第一次接触算符优先分析时，很多人会被FIRSTVT、LASTVT这些术语搞得晕头转向。其实理解起来并不复杂，我们可以把文法中的符号想象成参加拔河比赛的两支队伍——终结符是场上队员，非终结符是替补队员。而FIRSTVT和LASTVT就是帮我们找出每个替补队员（非终结符）最可能派上场的首发队员（终结符）和压轴队员（终结符）。
举个例子，假设有个产生式E→E+T|T，这里的E就像个固执的教练，总是先派E上场，最后也是E在场上。但真正决定比赛胜负的其实是那些终结符（+和*）。我们需要知道的是：当E作为替补时，它最可能派出哪些终结符打头阵（FIRSTVT），又会保留哪些终结符在最后关头出场（LASTVT）。
2. FIRSTVT集合的实战计算
2.1 直观理解FIRSTVT
FIRSTVT(P)就是非终结符P能推导出的所有符号串中，第一个终结符的集合。想象你是个语法分析器，看到非终结符P时，你需要预测它会产生什么样的终结符打头阵。
计算规则很简单：
- 找P的所有产生式右部
- 如果右部以终结符a开头，a∈FIRSTVT(P)
- 如果右部以非终结符Q开头，那么FIRSTVT(Q)⊆FIRSTVT(P)
2.2 具体计算步骤
让我们用经典表达式文法来演示：
E→E+T | T T→T*F | F F→(E) | i计算FIRSTVT(E)：
看E→E+T：第一个符号是E（非终结符），跳过；第二个符号是+（终结符），所以+∈FIRSTVT(E)
E→T：第一个符号是T（非终结符），需要FIRSTVT(T)
计算FIRSTVT(T)：
- T→TF：第一个∈FIRSTVT(T)
- T→F：需要FIRSTVT(F)
计算FIRSTVT(F)：
- F→(E)：第一个(∈FIRSTVT(F)
- F→i：i∈FIRSTVT(F)
所以FIRSTVT(F)={(,i} 回代到T：FIRSTVT(T)={*,(,i}
回代到E：FIRSTVT(E)={+,*,(,i}
3. LASTVT集合的实战计算
3.1 理解LASTVT
LASTVT(P)就是非终结符P能推导出的所有符号串中，最后一个终结符的集合。继续用拔河比赛的比喻，这就是每个非终结符的"王牌终结符"。
计算规则：
- 找P的所有产生式右部
- 如果右部以终结符a结尾，a∈LASTVT(P)
- 如果右部以非终结符Q结尾，那么LASTVT(Q)⊆LASTVT(P)
3.2 具体计算步骤
继续用之前的文法：
计算LASTVT(E):
- E→E+T：最后一个+∈LASTVT(E)
- E→T：需要LASTVT(T)
计算LASTVT(T):
- T→TF：最后一个∈LASTVT(T)
- T→F：需要LASTVT(F)
计算LASTVT(F):
- F→(E): 最后一个)∈LASTVT(F)
- F→i: i∈LASTVT(F)
所以LASTVT(F)={),i} 回代到T：LASTVT(T)={,),i} 回代到E：LASTVT(E)={+,,),i}
4. 构造优先关系表
4.1 优先关系规则
有了FIRSTVT和LASTVT，我们就可以按照以下规则填表：
- a=b：当产生式中有...ab...或...aQb...的形式
- a<b：当产生式中有...aR...，且b∈FIRSTVT(R)
- a>b：当产生式中有...Rb...，且a∈LASTVT(R)
4.2 实战填表示例
以E→E+T为例：
看E+：
- +是终结符，E是非终结符
- 根据规则3，LASTVT(E)中的每个元素>+
- LASTVT(E)={+,,),i}，所以+,,),i > +
看+T：
- +是终结符，T是非终结符
- 根据规则2，+ < FIRSTVT(T)中的每个元素
- FIRSTVT(T)={*,(,i}，所以+ < *, + < (, + < i
对于E→(E)：
- (=)（因为中间只隔了一个非终结符E）
- 同时( < FIRSTVT(E)={+,*,(,i}
- LASTVT(E) > )
4.3 完整优先关系表
| 终结符 | # | ( | ) | * | + | i |
|---|
| | < | | < | < | <
( | < | < | = | < | < | < ) | > | | > | > | > | >
- | > | < | > | > | > | >
- | > | < | > | < | > | < i | > | | > | > | > | >
5. 验证算符优先文法
5.1 验证条件
一个文法是算符优先文法，当且仅当：
- 是算符文法（没有两个相邻的非终结符）
- 任何两个终结符之间至多存在一种优先关系
5.2 验证过程
检查我们的优先关系表：
- 每个格子最多只有一个关系符号
- 没有两个相邻非终结符的产生式
因此这个文法是算符优先文法。
6. 实际应用中的注意事项
在实际实现算符优先分析时，有几个容易踩坑的地方：
- 边界处理：别忘了处理句子开头和结尾的#号
- 优先级冲突：如果发现表格中有单元格存在多个关系，需要修改文法
- 非终结符处理：在分析过程中，非终结符可以被视为"透明"的，只关注终结符之间的关系
- 错误恢复：当遇到不存在的优先关系时，要有良好的错误处理机制
7. 与其他分析方法的比较
与LL分析相比，算符优先分析：
- 优点：可以处理更多左递归文法，特别适合表达式分析
- 缺点：不能处理所有文法，且归约时可能产生非语法结构的中间形式
与LR分析相比：
- 优点：实现简单，手动计算方便
- 缺点：分析能力较弱，现在多用LR分析替代
8. 典型应用场景
算符优先分析最适合处理表达式求值场景：
- 数学表达式解析
- 简单脚本语言的解释器
- 配置文件解析
- 正则表达式引擎
我在实现一个公式计算器时就采用了这种方法，相比递归下降更简洁，特别是处理运算符优先级时非常直观。比如处理类似"1+2*3^4"这样的表达式时，优先关系表能自动确保指数运算先于乘法，乘法先于加法。