能否轻松消除脚本语言解析器中if语句的reduce/reduce冲突？

我正在为自研脚本语言开发解析器，目前实现了支持else、elsif分支的if语句解析代码，代码简洁性尚可：

@_( 'IF LPAREN expr_comp RPAREN THEN NEWLINE statement_set { elsif_statement } ENDIF',
    'IF LPAREN expr_comp RPAREN THEN NEWLINE statement_set { elsif_statement } ELSE NEWLINE statement_set ENDIF',
    )
def if_statement(self, p):
    expressions = []
    expressions.append((p.expr_comp, p[6]))
    else_statement = None
    if (p[8] == 'else'):
        else_statement = p[10]

    expressions.extend(p.elsif_statement)

    return ('IF', expressions, else_statement)

@_('ELSIF LPAREN expr_comp RPAREN THEN NEWLINE statement_set')
def elsif_statement(self, p):
    return (p.expr_comp, p.statement_set)

该代码生成了如下语法规则：

Rule 64 if_statement -> IF LPAREN expr_comp RPAREN THEN NEWLINE statement_set _3_elsif_statement_repeat ELSE NEWLINE statement_set ENDIF
Rule 65 _3_elsif_statement_repeat -> _3_elsif_statement_items
Rule 66 _3_elsif_statement_repeat ->
Rule 67 _3_elsif_statement_items -> _3_elsif_statement_items _3_elsif_statement_item
Rule 68 _3_elsif_statement_items -> _3_elsif_statement_item
Rule 69 _3_elsif_statement_item -> elsif_statement
Rule 70 if_statement -> IF LPAREN expr_comp RPAREN THEN NEWLINE statement_set _4_elsif_statement_repeat ENDIF
Rule 71 _4_elsif_statement_repeat -> _4_elsif_statement_items
Rule 72 _4_elsif_statement_repeat ->
Rule 73 _4_elsif_statement_items -> _4_elsif_statement_items _4_elsif_statement_item
Rule 74 _4_elsif_statement_items -> _4_elsif_statement_item
Rule 75 _4_elsif_statement_item -> elsif_statement
Rule 76 elsif_statement -> ELSIF LPAREN expr_comp RPAREN THEN NEWLINE statement_set

但同时产生了如下冲突：

Conflicts:    

reduce/reduce conflict for ELSIF in state 111 resolved using rule _3_elsif_statement_item -> elsif_statement
rejected rule (_4_elsif_statement_item -> elsif_statement) in state 111
   reduce using _3_elsif_statement_item -> elsif_statement with lookahead ELSIF
   ╭╴
   │ elsif_statement ♦          ELSIF LPAREN expr_comp RPAREN THEN NEWLINE statement_set
   │ ╰_3_elsif_statement_item╯  ╰elsif_statement───────────────────────────────────────╯
   │ ╰_3_elsif_statement_items╯ ╰_3_elsif_statement_item───────────────────────────────╯
   │ ╰_3_elsif_statement_items─────────────────────────────────────────────────────────╯
   ╰╴

   reduce using _4_elsif_statement_item -> elsif_statement with lookahead ELSIF
   ╭╴
   │ elsif_statement ♦          ELSIF LPAREN expr_comp RPAREN THEN NEWLINE statement_set
   │ ╰_4_elsif_statement_item╯  ╰elsif_statement───────────────────────────────────────╯
   │ ╰_4_elsif_statement_items╯ ╰_4_elsif_statement_item───────────────────────────────╯
   │ ╰_4_elsif_statement_items─────────────────────────────────────────────────────────╯
   ╰╴

目前代码可正常运行，但我希望尽可能减少冲突，避免掩盖实际问题。我怀疑冲突源于可选列表的自动化处理，但不清楚具体原因。请问能否轻松消除该归约/归约冲突？

解决方案 #

冲突原因很明确：你定义了两个独立的if_statement规则，解析器为每个规则生成了一套完全独立的elsif重复列表规则（_3_elsif_statement_repeat和_4_elsif_statement_repeat）。这两套规则功能完全相同，但解析器会将它们视为不同规则，当遇到ELSIF时，无法判断该用哪套规则进行归约，从而触发归约/归约冲突。

轻松消除冲突的方法是合并两个if_statement规则，用[ ... ]将else分支标记为可选部分，这样只会生成一套重复列表规则。修改后的代码如下：

@_( 'IF LPAREN expr_comp RPAREN THEN NEWLINE statement_set { elsif_statement } [ ELSE NEWLINE statement_set ] ENDIF',
    )
def if_statement(self, p):
    expressions = [(p.expr_comp, p[6])]
    # 处理elsif_statement可能为空的情况
    expressions.extend(p.elsif_statement or [])
    # 通过hasattr判断是否存在else分支
    else_statement = p.statement_set if hasattr(p, 'statement_set') else None
    return ('IF', expressions, else_statement)

@_('ELSIF LPAREN expr_comp RPAREN THEN NEWLINE statement_set')
def elsif_statement(self, p):
    return (p.expr_comp, p.statement_set)

修改说明 #

• 用[ ELSE NEWLINE statement_set ]替代原来的两个独立规则，将else分支设为可选，避免解析器生成重复的列表规则
• 调整else_statement的获取逻辑，改用hasattr判断是否存在可选分支的内容，比依赖位置索引的判断更可靠，也更符合解析器的属性访问方式
• 简化了expressions的初始化代码，保持简洁性

修改后，生成的语法规则中只会有一套elsif重复规则，归约/归约冲突会彻底消失，同时代码的简洁性也得到了保留。

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