从FIRSTVT/LASTVT到优先关系表：算符优先分析的核心构造实战

1. 算符优先分析法的核心概念第一次接触算符优先分析时很多人会被FIRSTVT、LASTVT这些术语搞得晕头转向。其实理解起来并不复杂我们可以把文法中的符号想象成参加拔河比赛的两支队伍——终结符是场上队员非终结符是替补队员。而FIRSTVT和LASTVT就是帮我们找出每个替补队员非终结符最可能派上场的首发队员终结符和压轴队员终结符。举个例子假设有个产生式E→ET|T这里的E就像个固执的教练总是先派E上场最后也是E在场上。但真正决定比赛胜负的其实是那些终结符和*。我们需要知道的是当E作为替补时它最可能派出哪些终结符打头阵FIRSTVT又会保留哪些终结符在最后关头出场LASTVT。2. FIRSTVT集合的实战计算2.1 直观理解FIRSTVTFIRSTVT(P)就是非终结符P能推导出的所有符号串中第一个终结符的集合。想象你是个语法分析器看到非终结符P时你需要预测它会产生什么样的终结符打头阵。计算规则很简单找P的所有产生式右部如果右部以终结符a开头a∈FIRSTVT(P)如果右部以非终结符Q开头那么FIRSTVT(Q)⊆FIRSTVT(P)2.2 具体计算步骤让我们用经典表达式文法来演示E→ET | T T→T*F | F F→(E) | i计算FIRSTVT(E)看E→ET第一个符号是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→ii∈FIRSTVT(F)所以FIRSTVT(F){(,i} 回代到TFIRSTVT(T){*,(,i}回代到EFIRSTVT(E){,*,(,i}3. LASTVT集合的实战计算3.1 理解LASTVTLASTVT(P)就是非终结符P能推导出的所有符号串中最后一个终结符的集合。继续用拔河比赛的比喻这就是每个非终结符的王牌终结符。计算规则找P的所有产生式右部如果右部以终结符a结尾a∈LASTVT(P)如果右部以非终结符Q结尾那么LASTVT(Q)⊆LASTVT(P)3.2 具体计算步骤继续用之前的文法计算LASTVT(E):E→ET最后一个∈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} 回代到TLASTVT(T){,),i} 回代到ELASTVT(E){,,),i}4. 构造优先关系表4.1 优先关系规则有了FIRSTVT和LASTVT我们就可以按照以下规则填表ab当产生式中有...ab...或...aQb...的形式ab当产生式中有...aR...且b∈FIRSTVT(R)ab当产生式中有...Rb...且a∈LASTVT(R)4.2 实战填表示例以E→ET为例看E是终结符E是非终结符根据规则3LASTVT(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. 典型应用场景算符优先分析最适合处理表达式求值场景数学表达式解析简单脚本语言的解释器配置文件解析正则表达式引擎我在实现一个公式计算器时就采用了这种方法相比递归下降更简洁特别是处理运算符优先级时非常直观。比如处理类似12*3^4这样的表达式时优先关系表能自动确保指数运算先于乘法乘法先于加法。