解决Mini-C语法悬空else问题：Sly解析器移进归约冲突与递归消除

问题背景 #

在用Sly实现Mini-C解析器时，原selection_statement规则因悬空else问题引发移进归约冲突：

selection_statement 
    ::= IF '(' expression ')' statement
    | IF '(' expression ')' statement ELSE statement

尝试通过matched/unmatched重构规则时，因matched的递归定义导致无限循环，添加其他语句又产生新冲突，需要不依赖优先级的解决方案。

正确的语法重构方案 #

核心思路是明确区分带匹配else的选择语句（matched）和无匹配else的选择语句（unmatched），同时让matched包含所有不会引发悬空else的语句，彻底避免递归问题。

具体Sly实现代码 #

@_("matched", "unmatched")
def selection_statement(self, p):
    return p[0]

# matched：完整的if-else，或其他不会产生悬空else的语句
@_("IF '(' expression ')' matched ELSE matched",
   "compound_statement",
   "expression_statement",
   "iteration_statement",
   "jump_statement")
def matched(self, p):
    if len(p) == 7:
        # 返回完整if-else的AST节点
        return IfElse(p.expression, p.matched0, p.matched1)
    else:
        # 直接返回其他类型语句的节点
        return p[0]

# unmatched：无else的if，或else后跟unmatched的if（强制else绑定最近的if）
@_("IF '(' expression ')' statement",
   "IF '(' expression ')' matched ELSE unmatched")
def unmatched(self, p):
    if len(p) == 5:
        # 返回无else的if节点
        return If(p.expression, p.statement)
    else:
        # 返回else绑定unmatched的if-else节点
        return IfElse(p.expression, p.matched, p.unmatched)

方案解释 #

1. 避免无限递归：matched除了完整的if-else，还包含复合语句、表达式语句、循环语句、跳转语句——这些语句本身不会触发悬空else，因此不会形成递归依赖；
2. 解决移进归约冲突：unmatched严格限定两种场景：要么是无else的if，要么是else后跟一个unmatched的选择语句，强制实现else与最近if绑定的语义，消除了解析时的歧义；
3. LR解析器兼容：重构后的语法属于LL(1)兼容结构，Sly的LR解析器可以直接处理，无需依赖优先级或结合性设置。

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