Lemon语法解析冲突求助：LaTeX转MathML解析器开发

问题描述 #

你编写的Lemon语法规则用于实现LaTeX数学公式到MathML的转换，但解析器报出shift-reduce冲突：

原始语法规则 #

%token BEGIN_GROUP END_GROUP MATH_SHIFT ALIGNMENT_TAB.
%token END_OF_LINE PARAMETER SUPERSCRIPT SUBSCRIPT.
%token SPACE LETTER DIGIT SYMBOL.
%token COMMAND COMMAND_LEFT COMMAND_RIGHT.
%token COMMAND_LIMITS COMMAND_NOLIMITS.
%token BEGIN_ENV END_ENV.
%token NBSP.

/* Some API */

document ::= list.

list ::= list element.
list ::= .

element ::= identifier(Id).
element ::= symbol(O).
element ::= number(Num).

identifier ::= LETTER.

symbol ::= SYMBOL.

number(N) ::= number DIGIT(D). /* Append digit */
number(N) ::= DIGIT(D). /* Init digits */

/* Lexer code */

解析冲突信息 #

State 2:
      (2) element ::= number *
          number ::= number * DIGIT

                         DIGIT shift-reduce 3      number ::= number DIGIT
                         DIGIT reduce       2       ** Parsing conflict **
                     {default} reduce       2      element ::= number

冲突原因 #

当解析器识别出一个number后遇到DIGIT时，存在两种合法推导路径：

1. 移进：将DIGIT加入当前number，执行number ::= number DIGIT以构建更长的数字；
2. 归约：将当前number归约为element，执行element ::= number，再将后续DIGIT作为新element的起始。

解析器无法自行判断优先级，因此产生shift-reduce冲突。

解决方法 #

通过指定优先级让解析器优先选择移进，确保完整数字被解析后再归约为element，有两种实现方式：

方式一：全局声明DIGIT的优先级 #

在语法开头添加%left DIGIT;声明，让DIGIT触发的移进操作优先级高于归约操作：

%token BEGIN_GROUP END_GROUP MATH_SHIFT ALIGNMENT_TAB.
%token END_OF_LINE PARAMETER SUPERSCRIPT SUBSCRIPT.
%token SPACE LETTER DIGIT SYMBOL.
%token COMMAND COMMAND_LEFT COMMAND_RIGHT.
%token COMMAND_LIMITS COMMAND_NOLIMITS.
%token BEGIN_ENV END_ENV.
%token NBSP.

/* 声明DIGIT的左优先级，优先移进 */
%left DIGIT;

/* Some API */

document ::= list.

list ::= list element.
list ::= .

element ::= identifier(Id).
element ::= symbol(O).
element ::= number(Num).

identifier ::= LETTER.

symbol ::= SYMBOL.

number(N) ::= number DIGIT(D). /* Append digit */
number(N) ::= DIGIT(D). /* Init digits */

/* Lexer code */

方式二：为数字扩展产生式指定优先级 #

给number ::= number DIGIT产生式添加%prec DIGIT，明确该产生式的优先级与DIGIT相同，优先移进：

%token BEGIN_GROUP END_GROUP MATH_SHIFT ALIGNMENT_TAB.
%token END_OF_LINE PARAMETER SUPERSCRIPT SUBSCRIPT.
%token SPACE LETTER DIGIT SYMBOL.
%token COMMAND COMMAND_LEFT COMMAND_RIGHT.
%token COMMAND_LIMITS COMMAND_NOLIMITS.
%token BEGIN_ENV END_ENV.
%token NBSP.

/* Some API */

document ::= list.

list ::= list element.
list ::= .

element ::= identifier(Id).
element ::= symbol(O).
element ::= number(Num).

identifier ::= LETTER.

symbol ::= SYMBOL.

number(N) ::= number DIGIT(D) %prec DIGIT; /* 指定该产生式优先级与DIGIT一致 */
number(N) ::= DIGIT(D). /* Init digits */

/* Lexer code */

两种方式都能让解析器遇到DIGIT时优先选择移进，先构建完整的数字，再归约为element，彻底解决冲突。

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