左递归算术表达式文法的语法修改及解析无限递归概率问询

现有含两类运算符（addop、mulop）的正则文法，其中addop优先级低于mulop，且均为左结合：

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> factor digit | digit
digit -> 0|1|2|3|4|5|6|7|8|9

给定算术表达式 #

200+300+400-50*10/5*2-60+100*10

符合优先级与左结合的运算过程 #

该表达式需通过自上而下解析得到与C编译器一致的结果1640，其优先级与左结合规则对应的运算过程如下（括号标注）：

((200+300)+400)-(((50*10)/5)*2)-60+(100*10)
=> 900-(200)-60+1000
=> 900-260+1000
=> 1640

原文法问题与修改方案 #

使用原文法无法为该表达式构建语法树，触发第二条规则后无法回溯至第一条规则。用户提出如下文法修改方案：

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor | expr
factor -> factor digit | digit
digit -> 0|1|2|3|4|5|6|7|8|9

原文法推导过程验证 #

根据@sepp2k的建议，已使用原文法完成该表达式的推导过程，以下是验证结论：

提交的推导过程 #

200+300+400-50*10/5*2-60+100*10

expr -> expr + term 
=> expr - term + term 
=> expr - term - term + term
=>...=> expr+term+term-term -term+term
=> term + term + term - term - term+term 
=> factor + term +...- term+term 
=>...=> 900-term-term+term 
=> 900-term*factor-term+term
=> 900-term/factor*factor-term +term
=> 900-term*factor/factor* factor-term+term
=>...=> 900 - 50 * 10 / factor * factor - term+term
=> 900-50*10/5*factor-term+term 
=> 900-500/5* factor-term+term
=> 900 - 100*factor-term+term
=>...=> 900-100*2-term+term 
=>...=> 700-term+term 
=>...=> 700-60 +term
=>...=>640 + term *factor
=>...=>640 +1000 
=> 1640

验证结论 #

这个推导过程是正确的：

• 它严格遵循原文法的左递归结构，先通过expr的左递归规则展开所有加减运算符对应的term，符合左结合特性；
• 每个term通过左递归展开乘除运算符对应的factor，保证了乘除优先级高于加减；
• 最终通过factor和digit的规则解析出所有数字，逐步计算得到正确结果1640。

左递归文法解析时无限递归概率的计算提示 #

针对左递归文法，自上而下解析时陷入无限递归的概率计算需基于回溯型自上而下解析器的行为分析（LL(1)解析器会直接拒绝左递归文法，不会产生此类尝试），核心思路如下：

定义明确 #

这里的"概率"指解析该表达式时，陷入无限循环的尝试次数占总解析尝试次数的比例。

关键计算要素 #

1. 分子：无限递归触发次数

   • 每次解析器选择左递归规则（如expr -> expr + term、term -> term * factor、factor -> factor digit），但当前输入符号无法匹配规则后续的终结符（如运算符、数字）时，就会触发无限递归尝试（直到栈溢出或解析器终止回溯）。
   • 例如：解析expr时，若当前输入是数字（而非+/-），却优先尝试expr -> expr + term规则，此时无法匹配+，会陷入无限递归，这属于1次触发。

2. 分母：总解析尝试次数

   • 总尝试次数是解析器为匹配表达式所做的所有规则选择次数之和，包括成功匹配的选择和失败回溯的选择。

具体计算步骤 #

1. 枚举规则选择点
   遍历表达式的每个解析阶段，统计每个非终结符（expr、term、factor）的规则选择次数：
   • expr有3条规则（左递归加减、直接到term）；
   • term有3条规则（左递归乘除、直接到factor）；
   • factor有2条规则（左递归加digit、直接到digit）。
2. 统计触发无限递归的次数
   针对每个非终结符，计算错误选择左递归规则的次数：比如当expr对应输入为数字时，解析器先尝试左递归规则导致的失败次数。
3. 计算比例
   无限递归概率 = （触发无限递归的总次数） / （所有规则选择的总次数）

注意事项 #

• 实际回溯型解析器通常会设置递归深度限制，不会真正无限循环，但计算时可视为每次错误的左递归选择对应一次"无限循环尝试"；
• 文法的规则顺序会直接影响尝试次数：左递归规则放在非左递归规则之前时，触发无限递归的概率会更高。

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