如何消除下述含if-then-else分支的上下文无关文法的二义性？

原文法说明 #

你提供的原产生式如下，二义性核心来源于悬空else问题：

S → if E then S
   | if E then S else S
   | other

对于嵌套的if结构，同一个句子可以对应多棵语法树，最典型的歧义场景是if E1 then if E2 then S1 else S2，else分支既可以匹配第一个if，也可以匹配第二个if，没有固定语义。 #

可落地的消歧方案 #

方案1：添加消歧规则（实现成本最低，工业界常用） #

不需要修改原有文法，仅在语法分析阶段添加约束即可：

• 语义规则约定：else永远和**最近的、未配对过else的if**绑定，这是C、Java、Python等绝大多数主流编程语言采用的规则
• 分析逻辑适配：如果用LR分析器，给else设置比if-then更高的移进优先级，遇到移进/规约冲突时优先移进else；如果用递归下降分析，在解析if-then结构后优先判断是否存在else，再进行后续解析。

适配后上面的歧义句子只会被解析为if E1 then (if E2 then S1 else S2)，符合常规语义预期。

方案2：重写为无二义文法（彻底消除二义，适合严谨场景） #

直接改写产生式，从文法规则层面禁止else匹配更远的if，拆分出「匹配语句（所有if都有对应else）」和「不匹配语句（存在if无对应else）」两类，改写后的产生式如下：

// S：所有合法语句
S → M | U
// M：匹配语句，所有if都配对了else
M → if E then M else M
   | other
// U：不匹配语句，存在未配对的if
U → if E then S
   | if E then M else U

这个文法天然不存在二义性，不需要额外加消歧规则，完全从语法规则层面限制了else的绑定逻辑，适合编译器前端、形式化验证等对文法严谨性要求高的场景。

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