当规则涵盖另一个规则的子集时消除语法歧义
Eliminating grammar ambiguity when a rule covers a subset of another
我正在尝试构建一个小的 bison 语法，但我对部分定义有疑问。可以使用右侧任何合法的表达式（语法中的expression_list）作为参数调用函数。
出现问题是因为在左侧，函数可以通过分配给它们来定义（标识符后跟标识符列表 - assignment_expression 和 identifier_list 在语法中）
我的问题是如何消除语法中的歧义，因为左侧合法的语句是右侧合法语句的子集。
语法是用 bison (v. 2.4.1) 写的
命令的输出是：
2 shift/reduce, 2 reduce/reduce
warning: rule useless in parser due to conflicts: assignment_expression: IDENTIFIER LPAREN RPAREN
完整语法如下：
expression:
assignment_expression
| expression DECORATOR IDENTIFIER
value:
IDENTIFIER
| HEX
| BIN
| OCT
| SCI
| FLOAT
| INT
;
constant_expression:
value
| LPAREN constant_expression RPAREN
| constant_expression OR constant_expression
| constant_expression XOR constant_expression
| constant_expression AND constant_expression
| constant_expression LSHIFT constant_expression
| constant_expression RSHIFT constant_expression
| constant_expression PLUS constant_expression
| constant_expression MINUS constant_expression
| constant_expression MUL constant_expression
| constant_expression DIV constant_expression
| constant_expression MOD constant_expression
| constant_expression POW constant_expression
| constant_expression FACTORIAL
| NOT constant_expression
| IDENTIFIER LPAREN RPAREN
| IDENTIFIER LPAREN constant_expression RPAREN
| IDENTIFIER LPAREN expression_list RPAREN
;
expression_list:
constant_expression COMMA constant_expression
| expression_list COMMA constant_expression
;
assignment_expression:
constant_expression
| IDENTIFIER EQUAL assignment_expression
| IDENTIFIER LPAREN RPAREN
| IDENTIFIER LPAREN IDENTIFIER RPAREN
| IDENTIFIER LPAREN identifier_list RPAREN
;
identifier_list:
IDENTIFIER COMMA IDENTIFIER
| identifier_list COMMA IDENTIFIER
;
以下是详细模式 (-v) 的 bison 输出的相关部分：
State 34 conflicts: 2 shift/reduce
State 35 conflicts: 2 reduce/reduce
state 34
3 value: IDENTIFIER .
25 constant_expression: IDENTIFIER . LPAREN RPAREN
26 | IDENTIFIER . LPAREN constant_expression RPAREN
27 | IDENTIFIER . LPAREN expression_list RPAREN
33 assignment_expression: IDENTIFIER LPAREN IDENTIFIER . RPAREN
35 identifier_list: IDENTIFIER . COMMA IDENTIFIER
COMMA shift, and go to state 53
LPAREN shift, and go to state 39
RPAREN shift, and go to state 54
COMMA [reduce using rule 3 (value)]
RPAREN [reduce using rule 3 (value)]
$default reduce using rule 3 (value)
state 35
25 constant_expression: IDENTIFIER LPAREN RPAREN .
32 assignment_expression: IDENTIFIER LPAREN RPAREN .
$end reduce using rule 25 (constant_expression)
$end [reduce using rule 32 (assignment_expression)]
DECORATOR reduce using rule 25 (constant_expression)
DECORATOR [reduce using rule 32 (assignment_expression)]
$default reduce using rule 25 (constant_expression)
根据要求，这里有一个最小语法问题：
assignment_expression:
constant_expression
| IDENTIFIER LPAREN identifier_list RPAREN
;
value:
IDENTIFIER
| INT
;
constant_expression:
value
| IDENTIFIER LPAREN expression_list RPAREN
;
expression_list:
constant_expression COMMA constant_expression
| expression_list COMMA constant_expression
;
identifier_list:
IDENTIFIER COMMA IDENTIFIER
| identifier_list COMMA IDENTIFIER
;
您的文字和语法不太一致。或者，也许我没有正确理解您的文字。你说：
on the left side, functions can be defined by assigning to them (an identifier followed by a list of identifiers - assignment_expression and identifier_list in the grammar)
在我的脑海中，我想象这样一个例子：
comb(n, r) = n! / (r! * (n-r)!)
但是你的语法是：
assignment_expression:
constant_expression
| IDENTIFIER EQUAL assignment_expression
| IDENTIFIER LPAREN RPAREN
| IDENTIFIER LPAREN IDENTIFIER RPAREN
| IDENTIFIER LPAREN identifier_list RPAREN
不会解析上面的定义，因为EQUAL左边唯一能出现的是IDENTIFIER。右递归允许在 assignment_expression 之前重复任意次数的 IDENTIFIER =，但最后一件事必须是 constant_expression 或三个原型产品之一。所以这将被匹配：
c = r = f(a,b)
但是这也是：
c = r = f(2, 7)
我会说这会使您的语法本质上有歧义，但这可能是一个错误。你的意思可能是：
assignment_expression: rvalue
| lvalue '=' assignment_expression
rvalue: constant_expression
lvalue: IDENTIFIER
| IDENTIFIER '(' ')'
| IDENTIFIER '(' identifier_list ')'
顺便提一下，您对 identifier_list 的定义要求至少两个标识符过于复杂，因此我在上面假设 identifier_list 的实际定义是：
identifier_list: IDENTIFIER | identifier_list ',' IDENTIFIER
但这还不足以解决问题。它仍然让解析器不知道是否：
comb(n | lookahead ','
是
的开始
comb(n, r) = ...
或者只是一个函数调用
comb(n, 4)
所以要解决这个问题，我们需要拿出一些重型火炮。
我们可以从简单的解决方案开始。这个语法没有歧义，因为 lvalue 后面必须跟着 =。当我们最终到达 = 时，我们可以判断我们目前拥有的是 rvalue 还是 lvalue，即使它们恰好看起来相同。 （例如，comb(n, r)。）唯一的问题是 = 可能与我们碰巧所在的位置之间的距离是无限的。
对于 bison，如果我们有一个明确的语法并且我们懒得解决先行问题，我们可以要求一个 GLR 解析器。 GLR 解析器的效率略低，因为它需要并行维护所有可能的解析，但对于大多数无歧义语法来说，它仍然是线性复杂度。 （GLR 解析器甚至可以在 O(N3) 中解析歧义语法，但 bison 实现不容忍歧义。毕竟，它旨在解析编程语言。）
因此，您只需添加
%glr-parser
并阅读 bison 手册中关于语义动作如何受到影响的部分。 （总结：它们一直存储到解析被消除歧义之前，因此它们可能不会像在 LALR(1) 解析器中那样在解析过程中发生得那么早。）
第二种在实践中相当常见的简单解决方案是让解析器接受所需语言的超集，然后在语义操作中添加可以说是句法检查的内容。因此，您可以只编写语法以允许任何看起来像 call_expression 的内容位于赋值的左侧，但是当您实际为 assignment/definition 构建 AST 节点时，请验证调用的参数列表实际上是一个简单的标识符列表。
这不仅可以简化您的语法而无需太多的实现成本，还可以生成准确的错误消息来描述语法错误，这对于标准的 LALR(1) 解析器来说并不容易。
不过， 有一个 LALR(1) 文法适用于您的语言（或者更确切地说，适用于我想象中的您的语言）。为了生成它，我们需要避免强制减少 lvalue 和 rvalue，直到我们知道它是哪个。
所以问题是 IDENTIFIER 可能是 expression_list 的一部分，也可能是 identifier_list 的一部分。我们不知道是哪一个，即使我们看到 )。因此，我们需要特殊情况 IDENTIFIER '(' identifier_list ')'，以允许它成为 lvalue 和 rvalue 的一部分。换句话说，我们需要这样的东西：
lvalue: IDENTIFIER | prototype
rvalue: expression_other_than_lvalue | lvalue
剩下的问题是我们如何定义 expression_other_than_lvalue。
很多时候，解决方案很简单：常量、运算符表达式、括号表达式； none 其中可以是左值。带有包含 expression_other_than_identifier 的括号列表的调用也是 expression_other_than_identifier。唯一不算的就是 IDENTIFIER(IDENTIFIER,IDENTIFIER,...)
所以让我们尽可能重写语法。 （我已经将 constant_expression 更改为 lvalue 因为它更短，并且用许多标记名称代替了实际符号，我发现它更具可读性。但以下大部分与您的原始符号相同.)
value_not_identifier: HEX | BIN | OCT | SCI | FLOAT | INT
expr_not_lvalue:
value_not_identifier
| '(' rvalue ')'
| rvalue OR rvalue
| ...
| IDENTIFIER '(' list_not_id_list ')'
lvalue:
IDENTIFIER
| IDENTIFIER '(' ')'
| IDENTIFIER '(' identifier_list ')'
identifier_list:
IDENTIFIER | identifier_list ',' IDENTIFIER
现在，除了我们尚未定义的细节 list_not_id_list，一切都将水到渠成。 lvalue 和 expr_not_lvalue 是不相交的，所以我们可以得到：
rvalue:
lvalue
| expr_not_lvalue
assignment_expression:
rvalue
| lvalue '=' assignment_expression
而且我们只需要处理不是标识符列表的表达式列表。如上所述，这类似于：
expr_not_identifier:
expr_not_lvalue
lvalue_not_identifier
list_not_id_list:
expr_not_identifier
| list_not_id_list ',' rvalue
| identifier_list ',' expr_not_identifier
因此，在解析列表时，我们第一次发现不是标识符的内容时，我们会从 identifier_list 产生式中删除该列表。如果我们遍历整个列表，那么当需要 rvalue 时，我们可能仍然会发现自己有 lvalue，但是当我们看到 = 或时，可以（最终）做出决定语句终止符。
所以正确的（我希望）完整的语法是：
expression:
assignment_expression
| expression DECORATOR IDENTIFIER
assignment_expression:
rvalue
| lvalue '=' assignment_expression
value_not_identifier: HEX | BIN | OCT | SCI | FLOAT | INT
expr_not_lvalue:
value_not_identifier
| '(' rvalue ')'
| rvalue OR rvalue
| rvalue XOR rvalue
| rvalue AND rvalue
| rvalue LSHIFT rvalue
| rvalue RSHIFT rvalue
| rvalue '+' rvalue
| rvalue '-' rvalue
| rvalue '*' rvalue
| rvalue '/' rvalue
| rvalue '%' rvalue
| rvalue POW rvalue
| rvalue '!'
| NOT rvalue
| IDENTIFIER '(' list_not_id_list')'
lvalue_not_identifier:
IDENTIFIER '(' ')'
| IDENTIFIER '(' identifier_list ')'
lvalue:
lvalue_not_identifier
| IDENTIFIER
rvalue:
lvalue
| expr_not_lvalue
identifier_list:
IDENTIFIER | identifier_list ',' IDENTIFIER
list_not_id_list:
expr_not_identifier
| list_not_id_list ',' rvalue
| identifier_list ',' expr_not_identifier
expr_not_identifier:
expr_not_lvalue
lvalue_not_identifier
考虑到简单解决方案的可用性，以及实现精确语法所需的转换不够优雅，难怪您很少看到这种构造。但是，您会发现它广泛用于 ECMA-262 标准（它定义了 ECMAScript 又名 Javascript）。该报告中使用的语法形式包括一种简化上述转换的宏功能，但它并没有使语法更易于阅读（恕我直言），而且我不知道实现该功能的解析器生成器。
我正在尝试构建一个小的 bison 语法，但我对部分定义有疑问。可以使用右侧任何合法的表达式（语法中的expression_list）作为参数调用函数。
出现问题是因为在左侧，函数可以通过分配给它们来定义（标识符后跟标识符列表 - assignment_expression 和 identifier_list 在语法中）
我的问题是如何消除语法中的歧义，因为左侧合法的语句是右侧合法语句的子集。
语法是用 bison (v. 2.4.1) 写的
命令的输出是：
2 shift/reduce, 2 reduce/reduce
warning: rule useless in parser due to conflicts: assignment_expression: IDENTIFIER LPAREN RPAREN
完整语法如下：
expression:
assignment_expression
| expression DECORATOR IDENTIFIER
value:
IDENTIFIER
| HEX
| BIN
| OCT
| SCI
| FLOAT
| INT
;
constant_expression:
value
| LPAREN constant_expression RPAREN
| constant_expression OR constant_expression
| constant_expression XOR constant_expression
| constant_expression AND constant_expression
| constant_expression LSHIFT constant_expression
| constant_expression RSHIFT constant_expression
| constant_expression PLUS constant_expression
| constant_expression MINUS constant_expression
| constant_expression MUL constant_expression
| constant_expression DIV constant_expression
| constant_expression MOD constant_expression
| constant_expression POW constant_expression
| constant_expression FACTORIAL
| NOT constant_expression
| IDENTIFIER LPAREN RPAREN
| IDENTIFIER LPAREN constant_expression RPAREN
| IDENTIFIER LPAREN expression_list RPAREN
;
expression_list:
constant_expression COMMA constant_expression
| expression_list COMMA constant_expression
;
assignment_expression:
constant_expression
| IDENTIFIER EQUAL assignment_expression
| IDENTIFIER LPAREN RPAREN
| IDENTIFIER LPAREN IDENTIFIER RPAREN
| IDENTIFIER LPAREN identifier_list RPAREN
;
identifier_list:
IDENTIFIER COMMA IDENTIFIER
| identifier_list COMMA IDENTIFIER
;
以下是详细模式 (-v) 的 bison 输出的相关部分：
State 34 conflicts: 2 shift/reduce
State 35 conflicts: 2 reduce/reduce
state 34
3 value: IDENTIFIER .
25 constant_expression: IDENTIFIER . LPAREN RPAREN
26 | IDENTIFIER . LPAREN constant_expression RPAREN
27 | IDENTIFIER . LPAREN expression_list RPAREN
33 assignment_expression: IDENTIFIER LPAREN IDENTIFIER . RPAREN
35 identifier_list: IDENTIFIER . COMMA IDENTIFIER
COMMA shift, and go to state 53
LPAREN shift, and go to state 39
RPAREN shift, and go to state 54
COMMA [reduce using rule 3 (value)]
RPAREN [reduce using rule 3 (value)]
$default reduce using rule 3 (value)
state 35
25 constant_expression: IDENTIFIER LPAREN RPAREN .
32 assignment_expression: IDENTIFIER LPAREN RPAREN .
$end reduce using rule 25 (constant_expression)
$end [reduce using rule 32 (assignment_expression)]
DECORATOR reduce using rule 25 (constant_expression)
DECORATOR [reduce using rule 32 (assignment_expression)]
$default reduce using rule 25 (constant_expression)
根据要求，这里有一个最小语法问题：
assignment_expression:
constant_expression
| IDENTIFIER LPAREN identifier_list RPAREN
;
value:
IDENTIFIER
| INT
;
constant_expression:
value
| IDENTIFIER LPAREN expression_list RPAREN
;
expression_list:
constant_expression COMMA constant_expression
| expression_list COMMA constant_expression
;
identifier_list:
IDENTIFIER COMMA IDENTIFIER
| identifier_list COMMA IDENTIFIER
;
您的文字和语法不太一致。或者，也许我没有正确理解您的文字。你说：
on the left side, functions can be defined by assigning to them (an identifier followed by a list of identifiers - assignment_expression and identifier_list in the grammar)
在我的脑海中，我想象这样一个例子：
comb(n, r) = n! / (r! * (n-r)!)
但是你的语法是：
assignment_expression:
constant_expression
| IDENTIFIER EQUAL assignment_expression
| IDENTIFIER LPAREN RPAREN
| IDENTIFIER LPAREN IDENTIFIER RPAREN
| IDENTIFIER LPAREN identifier_list RPAREN
不会解析上面的定义，因为EQUAL左边唯一能出现的是IDENTIFIER。右递归允许在 assignment_expression 之前重复任意次数的 IDENTIFIER =，但最后一件事必须是 constant_expression 或三个原型产品之一。所以这将被匹配：
c = r = f(a,b)
但是这也是：
c = r = f(2, 7)
我会说这会使您的语法本质上有歧义，但这可能是一个错误。你的意思可能是：
assignment_expression: rvalue
| lvalue '=' assignment_expression
rvalue: constant_expression
lvalue: IDENTIFIER
| IDENTIFIER '(' ')'
| IDENTIFIER '(' identifier_list ')'
顺便提一下，您对 identifier_list 的定义要求至少两个标识符过于复杂，因此我在上面假设 identifier_list 的实际定义是：
identifier_list: IDENTIFIER | identifier_list ',' IDENTIFIER
但这还不足以解决问题。它仍然让解析器不知道是否：
comb(n | lookahead ','
是
的开始comb(n, r) = ...
或者只是一个函数调用
comb(n, 4)
所以要解决这个问题，我们需要拿出一些重型火炮。
我们可以从简单的解决方案开始。这个语法没有歧义，因为 lvalue 后面必须跟着 =。当我们最终到达 = 时，我们可以判断我们目前拥有的是 rvalue 还是 lvalue，即使它们恰好看起来相同。 （例如，comb(n, r)。）唯一的问题是 = 可能与我们碰巧所在的位置之间的距离是无限的。
对于 bison，如果我们有一个明确的语法并且我们懒得解决先行问题，我们可以要求一个 GLR 解析器。 GLR 解析器的效率略低，因为它需要并行维护所有可能的解析，但对于大多数无歧义语法来说，它仍然是线性复杂度。 （GLR 解析器甚至可以在 O(N3) 中解析歧义语法，但 bison 实现不容忍歧义。毕竟，它旨在解析编程语言。）
因此，您只需添加
%glr-parser
并阅读 bison 手册中关于语义动作如何受到影响的部分。 （总结：它们一直存储到解析被消除歧义之前，因此它们可能不会像在 LALR(1) 解析器中那样在解析过程中发生得那么早。）
第二种在实践中相当常见的简单解决方案是让解析器接受所需语言的超集，然后在语义操作中添加可以说是句法检查的内容。因此，您可以只编写语法以允许任何看起来像 call_expression 的内容位于赋值的左侧，但是当您实际为 assignment/definition 构建 AST 节点时，请验证调用的参数列表实际上是一个简单的标识符列表。
这不仅可以简化您的语法而无需太多的实现成本，还可以生成准确的错误消息来描述语法错误，这对于标准的 LALR(1) 解析器来说并不容易。
不过， 有一个 LALR(1) 文法适用于您的语言（或者更确切地说，适用于我想象中的您的语言）。为了生成它，我们需要避免强制减少 lvalue 和 rvalue，直到我们知道它是哪个。
所以问题是 IDENTIFIER 可能是 expression_list 的一部分，也可能是 identifier_list 的一部分。我们不知道是哪一个，即使我们看到 )。因此，我们需要特殊情况 IDENTIFIER '(' identifier_list ')'，以允许它成为 lvalue 和 rvalue 的一部分。换句话说，我们需要这样的东西：
lvalue: IDENTIFIER | prototype
rvalue: expression_other_than_lvalue | lvalue
剩下的问题是我们如何定义 expression_other_than_lvalue。
很多时候，解决方案很简单：常量、运算符表达式、括号表达式； none 其中可以是左值。带有包含 expression_other_than_identifier 的括号列表的调用也是 expression_other_than_identifier。唯一不算的就是 IDENTIFIER(IDENTIFIER,IDENTIFIER,...)
所以让我们尽可能重写语法。 （我已经将 constant_expression 更改为 lvalue 因为它更短，并且用许多标记名称代替了实际符号，我发现它更具可读性。但以下大部分与您的原始符号相同.)
value_not_identifier: HEX | BIN | OCT | SCI | FLOAT | INT
expr_not_lvalue:
value_not_identifier
| '(' rvalue ')'
| rvalue OR rvalue
| ...
| IDENTIFIER '(' list_not_id_list ')'
lvalue:
IDENTIFIER
| IDENTIFIER '(' ')'
| IDENTIFIER '(' identifier_list ')'
identifier_list:
IDENTIFIER | identifier_list ',' IDENTIFIER
现在，除了我们尚未定义的细节 list_not_id_list，一切都将水到渠成。 lvalue 和 expr_not_lvalue 是不相交的，所以我们可以得到：
rvalue:
lvalue
| expr_not_lvalue
assignment_expression:
rvalue
| lvalue '=' assignment_expression
而且我们只需要处理不是标识符列表的表达式列表。如上所述，这类似于：
expr_not_identifier:
expr_not_lvalue
lvalue_not_identifier
list_not_id_list:
expr_not_identifier
| list_not_id_list ',' rvalue
| identifier_list ',' expr_not_identifier
因此，在解析列表时，我们第一次发现不是标识符的内容时，我们会从 identifier_list 产生式中删除该列表。如果我们遍历整个列表，那么当需要 rvalue 时，我们可能仍然会发现自己有 lvalue，但是当我们看到 = 或时，可以（最终）做出决定语句终止符。
所以正确的（我希望）完整的语法是：
expression:
assignment_expression
| expression DECORATOR IDENTIFIER
assignment_expression:
rvalue
| lvalue '=' assignment_expression
value_not_identifier: HEX | BIN | OCT | SCI | FLOAT | INT
expr_not_lvalue:
value_not_identifier
| '(' rvalue ')'
| rvalue OR rvalue
| rvalue XOR rvalue
| rvalue AND rvalue
| rvalue LSHIFT rvalue
| rvalue RSHIFT rvalue
| rvalue '+' rvalue
| rvalue '-' rvalue
| rvalue '*' rvalue
| rvalue '/' rvalue
| rvalue '%' rvalue
| rvalue POW rvalue
| rvalue '!'
| NOT rvalue
| IDENTIFIER '(' list_not_id_list')'
lvalue_not_identifier:
IDENTIFIER '(' ')'
| IDENTIFIER '(' identifier_list ')'
lvalue:
lvalue_not_identifier
| IDENTIFIER
rvalue:
lvalue
| expr_not_lvalue
identifier_list:
IDENTIFIER | identifier_list ',' IDENTIFIER
list_not_id_list:
expr_not_identifier
| list_not_id_list ',' rvalue
| identifier_list ',' expr_not_identifier
expr_not_identifier:
expr_not_lvalue
lvalue_not_identifier
考虑到简单解决方案的可用性，以及实现精确语法所需的转换不够优雅，难怪您很少看到这种构造。但是，您会发现它广泛用于 ECMA-262 标准（它定义了 ECMAScript 又名 Javascript）。该报告中使用的语法形式包括一种简化上述转换的宏功能，但它并没有使语法更易于阅读（恕我直言），而且我不知道实现该功能的解析器生成器。