对于没有语句终止符的语言，在解析器中更喜欢 shift 而不是 reduce
Preferring shift over reduce in parser for language without statement terminators
我正在解析一种没有语句终止符的语言，例如 ;。表达式被定义为最长的标记序列，因此 5-5 必须被解析为减法，而不是两个语句（文字 5 后跟一元否定 -5）。
我正在使用 LALRPOP 作为解析器生成器（尽管名称不同，它是 LR(1) 而不是 LALR，afaik）。 LALRPOP 没有优先级属性，并且不像 yacc 那样默认情况下更喜欢 shift 而不是 reduce。我想我了解如何通过构建规则“链”在 LR 文法中对常规运算符优先级进行编码，但我不知道如何将其应用于此问题。
预期的解析将是（括号中的单个语句）：
"5 - 5" → 5-5 instead of 5, -5
"5 (- 5)" → 5, -5
"- 5" → -5
"5 5" → 5, 5
如何更改语法，使其始终优先使用较长的解析？
查看 google 结果的前几页以及堆栈溢出并未针对此特定问题产生任何结果。大多数相关问题需要更多的前瞻性，否则结果是不允许没有终止符的连续语句。
我创建了一个重现 shift/reduce 冲突的最小示例语法（此语法中的语句只是一个表达式，在完整语法中还会有“if”、“while”等，并且更多级别的运算符优先级，但为简洁起见，我省略了它们）。除了一元减号外，原始语法中还有其他冲突，如 print(5)，可以解析为标识符 print 和括号内的数字 (5) 或函数调用。可能会有更多这样的冲突，但它们都有相同的潜在问题，即应该首选较长的序列，但两者目前都有效，但只有第一个应该有效。
为了方便，我创建了一个repo（checkout and cargo run）。语法是：
use std::str::FromStr;
grammar;
match {
"+",
"-",
"(",
")",
r"[0-9]+",
// Skip whitespace
r"\s*" => { },
}
Expr: i32 = {
<l:Expr> "+" <r:Unary> => l + r,
<l:Expr> "-" <r:Unary> => l - r,
Unary,
};
Unary: i32 = {
"-" <r:Unary> => -r,
Term,
}
Term: i32 = {
Num,
"(" <Expr> ")",
};
Num: i32 = {
r"[0-9]+" => i32::from_str(<>).unwrap(),
};
Stmt: i32 = {
Expr
};
pub Stmts: Vec<i32> = {
Stmt*
};
部分错误（full error message）：
/lalrpop-shift-repro/src/test.lalrpop:37:5: 37:8: Local ambiguity detected
The problem arises after having observed the following symbols in the input:
Stmt+ Expr
At that point, if the next token is a `"-"`, then the parser can proceed in two different ways.
First, the parser could execute the production at
/lalrpop-shift-repro/src/test.lalrpop:37:5: 37:8, which would consume
the top 1 token(s) from the stack and produce a `Stmt`. This might then yield a parse tree like
Expr ╷ Stmt
├─Stmt──┤ │
├─Stmt+─┘ │
└─Stmt+──────┘
Alternatively, the parser could shift the `"-"` token and later use it to construct a `Expr`. This might
then yield a parse tree like
Stmt+ Expr "-" Unary
│ ├─Expr───────┤
│ └─Stmt───────┤
└─Stmt+────────────┘
See the LALRPOP manual for advice on making your grammar LR(1).
您将不得不面对的问题是如何处理函数调用。我真的不能根据你的问题给你任何具体的建议，因为你提供的语法没有任何关于函数调用预期语法的指示，但是 print(5) 是一个有效语句的提示清楚地表明有两种截然不同的情况，需要分别处理。
考虑：
5 - 5 One statement 5 ( - 5 ) Two statements
print(-5) One statement print - 5 Two statements (presumably)
a - 5 ???
如果编译器知道 a 是函数还是变量（如果我们假设函数不是 first-class 值，使 print 无效语句）。但是解析器可以知道的方法并不多，而且 none 似乎很有可能：
- 可能没有任何用户定义的函数。然后可以构建词法分析器以识别恰好是内置函数（如
print）的类似标识符的标记，然后 a(-5) 将是非法的，因为 a 不是内置函数功能。
- 函数和标识符的名称可能在词法分析器可以检测到的某些方面有所不同。例如，该语言可能要求函数以大写字母开头。我认为情况并非如此，因为您写的是
print 而不是 Print 但可能还有其他一些简单的区别，例如要求标识符是单个字符。
- 函数必须在函数首次使用前声明，解析器与词法分析器共享符号 table。 （我没有搜索您正在使用的生成器的相当不充分的文档来查看词汇反馈是否实用。）
- 如果有一个 optional 语句分隔符（例如 Lua），那么您可以简单地要求以括号开头的语句（通常是一个漂亮的极少数情况下）被显式分隔，除非它们是块中的第一条语句。或者可能有一个可选的关键字，例如
compute，它可以用作明确的语句起始符，并且对于以括号开头的语句需要使用它。我认为这两种情况都不是这里的情况，因为您可以使用它来强制 5 - 5 被识别为两个语句（5; -5 或 5 compute - 5。）
- 另一个不太可能的可能性，同样基于
print(5) 示例，是函数调用使用与表达式分组不同的括号。在这种情况下，a[5]（例如）将是一个函数调用，而 a(5) 将明确地成为两个语句。
由于我不知道这里的确切要求，我将展示一个语法（在 yacc/bison 语法中，尽管它应该很容易翻译）它试图说明一个有代表性的示例。除了表达式语句外，它还实现了一个语句（return），表达式包括乘法、减法、取反和单参数函数调用。为了强制“贪婪”表达式，它禁止某些语句序列：
- 以一元运算符开头的语句
- 如果前面的语句以标识符结尾，则语句以左括号开头。 （这实际上要求在调用表达式中应用的函数是一个简单的标识符。没有这个限制，几乎不可能将两个连续的括号表达式与单个函数调用表达式区分开来，然后您需要一些其他方法来消除歧义.)
这些规则很容易表述，但实际的实现却重复得令人恼火，因为它需要各种不同类型的表达式，具体取决于表达式中的第一个和最后一个标记是什么，以及可能不同类型的语句，如果你有可能以表达式结尾的语句。 （例如，return x。）ECMAScript 使用的形式主义在这里很有用，但我怀疑您的解析器生成器没有实现它——尽管它的宏工具可能用于实现该效果，如果它带有类似文档的东西。没有它，就会有很多重复。
在生成语法的模糊尝试中，我使用了以下后缀：
_un / _pr / _oth: 以一元/括号/其他标记开头_id / _nid：结束/不以id结束
没有后缀用于不同可能性的并集。可能有比必要更多的单元制作。它没有被彻底调试，但它在一些测试用例上工作（见下文）：
program : block
block_id : stmt_id
| block_id stmt_oth_id
| block_nid stmt_pr_id
| block_nid stmt_oth_id
block_nid : stmt_nid
| block_id stmt_oth_nid
| block_nid stmt_pr_nid
| block_nid stmt_oth_nid
block : %empty
| block_id | block_nid
stmt_un_id : expr_un_id
stmt_un_nid : expr_un_nid
stmt_pr_id : expr_pr_id
stmt_pr_nid : expr_pr_nid
stmt_oth_id : expr_oth_id
| return_id
stmt_oth_nid : expr_oth_nid
| return_nid
stmt_id : stmt_un_id | stmt_pr_id | stmt_oth_id
stmt_nid : stmt_un_nid | stmt_pr_nid | stmt_oth_nid
return_id : "return" expr_id
return_nid : "return" expr_nid
expr_un_id : sum_un_id
expr_un_nid : sum_un_nid
expr_pr_id : sum_pr_id
expr_pr_nid : sum_pr_nid
expr_oth_id : sum_oth_id
expr_oth_nid : sum_oth_nid
expr_id : expr_un_id | expr_pr_id | expr_oth_id
expr_nid : expr_un_nid | expr_pr_nid | expr_oth_nid
expr : expr_id | expr_nid
sum_un_id : mul_un_id
| sum_un '-' mul_id
sum_un_nid : mul_un_nid
| sum_un '-' mul_nid
sum_un : sum_un_id | sum_un_nid
sum_pr_id : mul_pr_id
| sum_pr '-' mul_id
sum_pr_nid : mul_pr_nid
| sum_pr '-' mul_nid
sum_pr : sum_pr_id | sum_pr_nid
sum_oth_id : mul_oth_id
| sum_oth '-' mul_id
sum_oth_nid : mul_oth_nid
| sum_oth '-' mul_nid
sum_oth : sum_oth_id | sum_oth_nid
mul_un_id : unary_un_id
| mul_un '*' unary_id
mul_un_nid : unary_un_nid
| mul_un '*' unary_nid
mul_un : mul_un_id | mul_un_nid
mul_pr_id : mul_pr '*' unary_id
mul_pr_nid : unary_pr_nid
| mul_pr '*' unary_nid
mul_pr : mul_pr_id | mul_pr_nid
mul_oth_id : unary_oth_id
| mul_oth '*' unary_id
mul_oth_nid : unary_oth_nid
| mul_oth '*' unary_nid
mul_oth : mul_oth_id | mul_oth_nid
mul_id : mul_un_id | mul_pr_id | mul_oth_id
mul_nid : mul_un_nid | mul_pr_nid | mul_oth_nid
unary_un_id : '-' unary_id
unary_un_nid : '-' unary_nid
unary_pr_nid : term_pr_nid
unary_oth_id : term_oth_id
unary_oth_nid: term_oth_nid
unary_id : unary_un_id | unary_oth_id
unary_nid : unary_un_nid | unary_pr_nid | unary_oth_nid
term_oth_id : IDENT
term_oth_nid : NUMBER
| IDENT '(' expr ')'
term_pr_nid : '(' expr ')'
这里有一个小测试：
> 5-5
{ [- 5 5] }
> 5(-5)
{ 5; [~ -- 5] }
> a-5
{ [- a 5] }
> a(5)
{ [CALL a 5] }
> -7*a
{ [* [~ -- 7] a] }
> a*-7
{ [* a [~ -- 7]] }
> a-b*c
{ [- a [* b c]] }
> a*b-c
{ [- [* a b] c] }
> a*b(3)-c
{ [- [* a [CALL b 3]] c] }
> a*b-c(3)
{ [- [* a b] [CALL c 3]] }
> a*b-7(3)
{ [- [* a b] 7]; 3 }
我正在解析一种没有语句终止符的语言，例如 ;。表达式被定义为最长的标记序列，因此 5-5 必须被解析为减法，而不是两个语句（文字 5 后跟一元否定 -5）。
我正在使用 LALRPOP 作为解析器生成器（尽管名称不同，它是 LR(1) 而不是 LALR，afaik）。 LALRPOP 没有优先级属性，并且不像 yacc 那样默认情况下更喜欢 shift 而不是 reduce。我想我了解如何通过构建规则“链”在 LR 文法中对常规运算符优先级进行编码，但我不知道如何将其应用于此问题。
预期的解析将是（括号中的单个语句）：
"5 - 5" → 5-5 instead of 5, -5
"5 (- 5)" → 5, -5
"- 5" → -5
"5 5" → 5, 5
如何更改语法，使其始终优先使用较长的解析？
查看 google 结果的前几页以及堆栈溢出并未针对此特定问题产生任何结果。大多数相关问题需要更多的前瞻性，否则结果是不允许没有终止符的连续语句。
我创建了一个重现 shift/reduce 冲突的最小示例语法（此语法中的语句只是一个表达式，在完整语法中还会有“if”、“while”等，并且更多级别的运算符优先级，但为简洁起见，我省略了它们）。除了一元减号外，原始语法中还有其他冲突，如 print(5)，可以解析为标识符 print 和括号内的数字 (5) 或函数调用。可能会有更多这样的冲突，但它们都有相同的潜在问题，即应该首选较长的序列，但两者目前都有效，但只有第一个应该有效。
为了方便，我创建了一个repo（checkout and cargo run）。语法是：
use std::str::FromStr;
grammar;
match {
"+",
"-",
"(",
")",
r"[0-9]+",
// Skip whitespace
r"\s*" => { },
}
Expr: i32 = {
<l:Expr> "+" <r:Unary> => l + r,
<l:Expr> "-" <r:Unary> => l - r,
Unary,
};
Unary: i32 = {
"-" <r:Unary> => -r,
Term,
}
Term: i32 = {
Num,
"(" <Expr> ")",
};
Num: i32 = {
r"[0-9]+" => i32::from_str(<>).unwrap(),
};
Stmt: i32 = {
Expr
};
pub Stmts: Vec<i32> = {
Stmt*
};
部分错误（full error message）：
/lalrpop-shift-repro/src/test.lalrpop:37:5: 37:8: Local ambiguity detected
The problem arises after having observed the following symbols in the input:
Stmt+ Expr
At that point, if the next token is a `"-"`, then the parser can proceed in two different ways.
First, the parser could execute the production at
/lalrpop-shift-repro/src/test.lalrpop:37:5: 37:8, which would consume
the top 1 token(s) from the stack and produce a `Stmt`. This might then yield a parse tree like
Expr ╷ Stmt
├─Stmt──┤ │
├─Stmt+─┘ │
└─Stmt+──────┘
Alternatively, the parser could shift the `"-"` token and later use it to construct a `Expr`. This might
then yield a parse tree like
Stmt+ Expr "-" Unary
│ ├─Expr───────┤
│ └─Stmt───────┤
└─Stmt+────────────┘
See the LALRPOP manual for advice on making your grammar LR(1).
您将不得不面对的问题是如何处理函数调用。我真的不能根据你的问题给你任何具体的建议，因为你提供的语法没有任何关于函数调用预期语法的指示，但是 print(5) 是一个有效语句的提示清楚地表明有两种截然不同的情况，需要分别处理。
考虑：
5 - 5 One statement 5 ( - 5 ) Two statements
print(-5) One statement print - 5 Two statements (presumably)
a - 5 ???
如果编译器知道 a 是函数还是变量（如果我们假设函数不是 first-class 值，使 print 无效语句）。但是解析器可以知道的方法并不多，而且 none 似乎很有可能：
- 可能没有任何用户定义的函数。然后可以构建词法分析器以识别恰好是内置函数（如
print）的类似标识符的标记，然后a(-5)将是非法的，因为a不是内置函数功能。 - 函数和标识符的名称可能在词法分析器可以检测到的某些方面有所不同。例如，该语言可能要求函数以大写字母开头。我认为情况并非如此，因为您写的是
print而不是Print但可能还有其他一些简单的区别，例如要求标识符是单个字符。 - 函数必须在函数首次使用前声明，解析器与词法分析器共享符号 table。 （我没有搜索您正在使用的生成器的相当不充分的文档来查看词汇反馈是否实用。）
- 如果有一个 optional 语句分隔符（例如 Lua），那么您可以简单地要求以括号开头的语句（通常是一个漂亮的极少数情况下）被显式分隔，除非它们是块中的第一条语句。或者可能有一个可选的关键字，例如
compute，它可以用作明确的语句起始符，并且对于以括号开头的语句需要使用它。我认为这两种情况都不是这里的情况，因为您可以使用它来强制5 - 5被识别为两个语句（5; -5或5 compute - 5。） - 另一个不太可能的可能性，同样基于
print(5)示例，是函数调用使用与表达式分组不同的括号。在这种情况下，a[5]（例如）将是一个函数调用，而a(5)将明确地成为两个语句。
由于我不知道这里的确切要求，我将展示一个语法（在 yacc/bison 语法中，尽管它应该很容易翻译）它试图说明一个有代表性的示例。除了表达式语句外，它还实现了一个语句（return），表达式包括乘法、减法、取反和单参数函数调用。为了强制“贪婪”表达式，它禁止某些语句序列：
- 以一元运算符开头的语句
- 如果前面的语句以标识符结尾，则语句以左括号开头。 （这实际上要求在调用表达式中应用的函数是一个简单的标识符。没有这个限制，几乎不可能将两个连续的括号表达式与单个函数调用表达式区分开来，然后您需要一些其他方法来消除歧义.)
这些规则很容易表述，但实际的实现却重复得令人恼火，因为它需要各种不同类型的表达式，具体取决于表达式中的第一个和最后一个标记是什么，以及可能不同类型的语句，如果你有可能以表达式结尾的语句。 （例如，return x。）ECMAScript 使用的形式主义在这里很有用，但我怀疑您的解析器生成器没有实现它——尽管它的宏工具可能用于实现该效果，如果它带有类似文档的东西。没有它，就会有很多重复。
在生成语法的模糊尝试中，我使用了以下后缀：
_un/_pr/_oth: 以一元/括号/其他标记开头_id/_nid：结束/不以id结束
没有后缀用于不同可能性的并集。可能有比必要更多的单元制作。它没有被彻底调试，但它在一些测试用例上工作（见下文）：
program : block
block_id : stmt_id
| block_id stmt_oth_id
| block_nid stmt_pr_id
| block_nid stmt_oth_id
block_nid : stmt_nid
| block_id stmt_oth_nid
| block_nid stmt_pr_nid
| block_nid stmt_oth_nid
block : %empty
| block_id | block_nid
stmt_un_id : expr_un_id
stmt_un_nid : expr_un_nid
stmt_pr_id : expr_pr_id
stmt_pr_nid : expr_pr_nid
stmt_oth_id : expr_oth_id
| return_id
stmt_oth_nid : expr_oth_nid
| return_nid
stmt_id : stmt_un_id | stmt_pr_id | stmt_oth_id
stmt_nid : stmt_un_nid | stmt_pr_nid | stmt_oth_nid
return_id : "return" expr_id
return_nid : "return" expr_nid
expr_un_id : sum_un_id
expr_un_nid : sum_un_nid
expr_pr_id : sum_pr_id
expr_pr_nid : sum_pr_nid
expr_oth_id : sum_oth_id
expr_oth_nid : sum_oth_nid
expr_id : expr_un_id | expr_pr_id | expr_oth_id
expr_nid : expr_un_nid | expr_pr_nid | expr_oth_nid
expr : expr_id | expr_nid
sum_un_id : mul_un_id
| sum_un '-' mul_id
sum_un_nid : mul_un_nid
| sum_un '-' mul_nid
sum_un : sum_un_id | sum_un_nid
sum_pr_id : mul_pr_id
| sum_pr '-' mul_id
sum_pr_nid : mul_pr_nid
| sum_pr '-' mul_nid
sum_pr : sum_pr_id | sum_pr_nid
sum_oth_id : mul_oth_id
| sum_oth '-' mul_id
sum_oth_nid : mul_oth_nid
| sum_oth '-' mul_nid
sum_oth : sum_oth_id | sum_oth_nid
mul_un_id : unary_un_id
| mul_un '*' unary_id
mul_un_nid : unary_un_nid
| mul_un '*' unary_nid
mul_un : mul_un_id | mul_un_nid
mul_pr_id : mul_pr '*' unary_id
mul_pr_nid : unary_pr_nid
| mul_pr '*' unary_nid
mul_pr : mul_pr_id | mul_pr_nid
mul_oth_id : unary_oth_id
| mul_oth '*' unary_id
mul_oth_nid : unary_oth_nid
| mul_oth '*' unary_nid
mul_oth : mul_oth_id | mul_oth_nid
mul_id : mul_un_id | mul_pr_id | mul_oth_id
mul_nid : mul_un_nid | mul_pr_nid | mul_oth_nid
unary_un_id : '-' unary_id
unary_un_nid : '-' unary_nid
unary_pr_nid : term_pr_nid
unary_oth_id : term_oth_id
unary_oth_nid: term_oth_nid
unary_id : unary_un_id | unary_oth_id
unary_nid : unary_un_nid | unary_pr_nid | unary_oth_nid
term_oth_id : IDENT
term_oth_nid : NUMBER
| IDENT '(' expr ')'
term_pr_nid : '(' expr ')'
这里有一个小测试：
> 5-5
{ [- 5 5] }
> 5(-5)
{ 5; [~ -- 5] }
> a-5
{ [- a 5] }
> a(5)
{ [CALL a 5] }
> -7*a
{ [* [~ -- 7] a] }
> a*-7
{ [* a [~ -- 7]] }
> a-b*c
{ [- a [* b c]] }
> a*b-c
{ [- [* a b] c] }
> a*b(3)-c
{ [- [* a [CALL b 3]] c] }
> a*b-c(3)
{ [- [* a b] [CALL c 3]] }
> a*b-7(3)
{ [- [* a b] 7]; 3 }