从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时，你需要预测它会产生什么样的终结符打头阵。

计算规则很简单：

1. 找P的所有产生式右部
2. 如果右部以终结符a开头，a∈FIRSTVT(P)
3. 如果右部以非终结符Q开头，那么FIRSTVT(Q)⊆FIRSTVT(P)

2.2 具体计算步骤

让我们用经典表达式文法来演示：

E→E+T | T T→T*F | F F→(E) | i

计算FIRSTVT(E)：

1. 看E→E+T：第一个符号是E（非终结符），跳过；第二个符号是+（终结符），所以+∈FIRSTVT(E)

2. E→T：第一个符号是T（非终结符），需要FIRSTVT(T)

   计算FIRSTVT(T)：

   1. T→TF：第一个∈FIRSTVT(T)
   2. T→F：需要FIRSTVT(F)

   计算FIRSTVT(F)：

   1. F→(E)：第一个(∈FIRSTVT(F)
   2. F→i：i∈FIRSTVT(F)

   所以FIRSTVT(F)={(,i} 回代到T：FIRSTVT(T)={*,(,i}

回代到E：FIRSTVT(E)={+,*,(,i}

3. LASTVT集合的实战计算

3.1 理解LASTVT

LASTVT(P)就是非终结符P能推导出的所有符号串中，最后一个终结符的集合。继续用拔河比赛的比喻，这就是每个非终结符的"王牌终结符"。

计算规则：

1. 找P的所有产生式右部
2. 如果右部以终结符a结尾，a∈LASTVT(P)
3. 如果右部以非终结符Q结尾，那么LASTVT(Q)⊆LASTVT(P)

3.2 具体计算步骤

继续用之前的文法：

计算LASTVT(E):

1. E→E+T：最后一个+∈LASTVT(E)
2. E→T：需要LASTVT(T)

计算LASTVT(T):

1. T→TF：最后一个∈LASTVT(T)
2. T→F：需要LASTVT(F)

计算LASTVT(F):

1. F→(E): 最后一个)∈LASTVT(F)
2. F→i: i∈LASTVT(F)

所以LASTVT(F)={),i} 回代到T：LASTVT(T)={,),i} 回代到E：LASTVT(E)={+,,),i}

4. 构造优先关系表

4.1 优先关系规则

有了FIRSTVT和LASTVT，我们就可以按照以下规则填表：

1. a=b：当产生式中有...ab...或...aQb...的形式
2. a<b：当产生式中有...aR...，且b∈FIRSTVT(R)
3. a>b：当产生式中有...Rb...，且a∈LASTVT(R)

4.2 实战填表示例

以E→E+T为例：

1. 看E+：

   • +是终结符，E是非终结符
   • 根据规则3，LASTVT(E)中的每个元素>+
   • LASTVT(E)={+,,),i}，所以+,,),i > +

2. 看+T：

   • +是终结符，T是非终结符
   • 根据规则2，+ < FIRSTVT(T)中的每个元素
   • FIRSTVT(T)={*,(,i}，所以+ < *, + < (, + < i

3. 对于E→(E)：

   • (=)（因为中间只隔了一个非终结符E）
   • 同时( < FIRSTVT(E)={+,*,(,i}
   • LASTVT(E) > )

4.3 完整优先关系表

| | < | | < | < | <

( | < | < | = | < | < | < ) | > | | > | > | > | >

• | > | < | > | > | > | >

• | > | < | > | < | > | < i | > | | > | > | > | >

5. 验证算符优先文法

5.1 验证条件

一个文法是算符优先文法，当且仅当：

1. 是算符文法（没有两个相邻的非终结符）
2. 任何两个终结符之间至多存在一种优先关系

5.2 验证过程

检查我们的优先关系表：

• 每个格子最多只有一个关系符号
• 没有两个相邻非终结符的产生式

因此这个文法是算符优先文法。

6. 实际应用中的注意事项

在实际实现算符优先分析时，有几个容易踩坑的地方：

1. 边界处理：别忘了处理句子开头和结尾的#号
2. 优先级冲突：如果发现表格中有单元格存在多个关系，需要修改文法
3. 非终结符处理：在分析过程中，非终结符可以被视为"透明"的，只关注终结符之间的关系
4. 错误恢复：当遇到不存在的优先关系时，要有良好的错误处理机制

7. 与其他分析方法的比较

与LL分析相比，算符优先分析：

• 优点：可以处理更多左递归文法，特别适合表达式分析
• 缺点：不能处理所有文法，且归约时可能产生非语法结构的中间形式

与LR分析相比：

• 优点：实现简单，手动计算方便
• 缺点：分析能力较弱，现在多用LR分析替代

8. 典型应用场景

算符优先分析最适合处理表达式求值场景：

• 数学表达式解析
• 简单脚本语言的解释器
• 配置文件解析
• 正则表达式引擎

我在实现一个公式计算器时就采用了这种方法，相比递归下降更简洁，特别是处理运算符优先级时非常直观。比如处理类似"1+2*3^4"这样的表达式时，优先关系表能自动确保指数运算先于乘法，乘法先于加法。