对于没有语句终止符的语言，更倾向于移位而不是减少语法分析器
我正在解析一种没有像;这样的语句终结符的语言。表达式被定义为最长的标记序列，因此必须将5-5解析为减法，而不是两个语句(文字5，后面是一元否定的-5)。
我使用拉罗波普作为解析器生成器(尽管名称是LR(1)，而不是LALR、afaik)。LALRPOP没有优先级属性，也不像yacc那样，默认情况下更喜欢shift。我想我理解规则操作符优先级是如何通过构建“规则链”在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)或函数调用。可能会有更多这样的冲突，但所有这些冲突都有相同的潜在问题，应该优先考虑较长的序列，但两者目前都是有效的，尽管只有第一个冲突应该是有效的。
为了方便起见，我创建了一个存储库 (结帐和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*
};错误的一部分(全错误信息)：
/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).回答 1
Stack Overflow用户
发布于 2022-01-04 05:55:17
您必须面对的问题是如何处理函数调用。我实际上不能根据您的问题给出任何具体的建议，因为您提供的语法缺乏对函数调用的预期语法的任何指示，但是print(5)是一个有效语句的暗示清楚地表明，有两种不同的情况需要单独处理。
考虑：
5 - 5 One statement 5 ( - 5 ) Two statements
print(-5) One statement print - 5 Two statements (presumably)
a - 5 ???如果编译器知道a是函数还是变量(如果我们假设函数不是第一类值，使print成为无效语句)，则可以解决第三个表达式的歧义。但是解析器不可能知道这一点，而且这些方法似乎都不太可能：
- 可能没有任何用户定义的函数。然后，可以构建lexer来识别标识符之类的标记，这些标识符恰好是内置函数(如
print)，而a(-5)则是非法的，因为a不是内置函数。 - 函数和标识符的名称可能会以lexer可以检测到的某种方式不同。例如，语言可能需要以大写字母开头的函数。我认为情况并非如此，因为您编写的是
print而不是Print，但可能还有其他一些简单的区别，例如要求标识符为单个字符。 - 函数必须在第一次使用该函数之前声明为该函数，解析器与lexer共享符号表。(我没有搜索您正在使用的生成器的相当不足的文档，以查看词汇反馈是否实用。)
- 如果有一个可选的语句分隔符(例如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：ends /不以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 }https://stackoverflow.com/questions/70571344
复制相似问题
腾讯云开发者
