如何在LL(1)语法分析器中处理运算符优先级问题

现有文法的问题 #

你目前消除左递归后的文法是无优先级区分的，所有加减乘除运算符会按照从左到右的顺序归约，解析1 + 2 * 3时会被计算为(1+2)*3 = 9，无法满足乘法优先的需求。要实现运算符优先级，你需要先重构文法结构，把不同优先级的运算符拆分到不同的非终结符中，再分别做左递归消除。

支持优先级的LL(1)文法实现 #

第一步：拆分不同优先级的非终结符 #

按照运算符优先级从低到高拆分3层非终结符：

• E：加减级别的表达式（最低优先级，左结合）
• T：乘除级别的表达式（中等优先级，左结合）
• F：原子因子（最高优先级，这里就是整数INT）

原始的优先级文法为：

E -> E + T | E - T | T
T -> T * F | T / F | F
F -> INT

第二步：分别消除左递归 #

对每层左递归分别消除后得到最终LL(1)文法：

E  -> T E'
E' -> + T E' | - T E' | ε
T  -> F T'
T' -> * F T' | / F T' | ε
F  -> INT

这个文法的结构天然嵌入了优先级逻辑：所有加减运算必须先等右侧的乘除表达式T完全解析完成后才能归约，自然实现了乘法优先于加法。

以1 + 2 * 3为例的解析流程 #

你可以按以下逻辑实现解析与求值：

1. 起始非终结符E先调用T解析第一个运算单元：
   • T调用F匹配INT 1，后续token为+不属于乘除运算符，T'返回空，本次T的求值结果为1
2. 进入E'匹配到+运算符，先调用T解析右侧的运算单元：
   • T调用F匹配INT 2，后续token为*，进入T'匹配*
   • T'调用F匹配INT 3，后续无有效token，T'返回空，本次T的求值结果为2 * 3 = 6
3. E'归约计算1 + 6 = 7，后续无有效token返回空，最终表达式求值结果为7，符合优先级要求。

内容的提问来源于stack exchange，提问作者ishaangupte