我正在用Yacc（与Go一起打包的一种语言）为一种玩具语言编写语法，由于以下伪问题，我预期会有移位-减少冲突。我必须将问题语法简化为以下内容。
start: stmt_list expr: INT | IDENT | lambda | '(' expr ')' { $$ = $2 } lambda: '(' params ')' '{' stmt_list '}' params: expr | params ',' expr stmt: /* empty */ | expr stmt_list: stmt | stmt_list ';' stmt
Lambda函数如下所示：
map((v) { v * 2 }, collection)
我的解析器发出：
冲突：1班/减少
给定输入：
(a)
它会expr按'(' expr ')'规则正确解析一个。但是考虑到以下输入：
expr
'(' expr ')'
(a) { a }
（这将是身份函数的lambda，返回其输入）。我得到：
语法错误：意外的’{‘
这是因为(a)读取时，解析器选择将其简化为'(' expr ')'，而不是将其视为'(' params ')'。鉴于此冲突是转移减少而不是减少减少，因此我认为这是可以解决的。我只是不知道如何构造语法来支持这种语法。
'(' params ')'
编辑| 这很丑陋，但我正在考虑定义一个令牌，以便词法分析器可以识别’）’‘{‘序列并将其作为单个令牌发送以解决此问题。
编辑2 | 实际上，更好的是，我会让lambda要求像语法中那样->(a, b) { a * b}的语法，但是让词法分析器发出->而不是在实际的源代码中。
->(a, b) { a * b}
->
您的分析确实是正确的；虽然语法不是模糊的，这是不可能的解析器来决定与输入减少到( <expr>与先行)是否expr应减少到params移位之前)或者是否)应该被作为偏移的一部分lambda。如果可以看到下一个标记，则可以做出决定，因此语法go（yacc）之外的语法LR（2）。
( <expr>
)
params
lambda
如果您使用的是野牛，则可以通过请求GLR解析器轻松解决此问题，但是我不认为go / yacc提供了该功能。
该语言有一个LR（1）语法（对于的任何值，总是存在一个与任何LR（k）语法相对应的LR（1）语法k），但是手工编写会很烦人。LR（k）到LR（1）转换的基本思想是通过将上下文的k-1个令牌累积到每个产品中来将减少决策k-1个令牌向前移动。因此，在这种情况下k为2，各生产，P：N → α将与生产被替换为每个在每个中。[请参阅注1]在任何非平凡的语法中，这都会导致大量非末尾的爆炸。TNU → Tα U``T``FIRST(α)``U``FOLLOW(N)
k
N → α
TNU → Tα U``T``FIRST(α)``U``FOLLOW(N)
让我提出两个简单得多的解决方案，而不是追求这个想法，您似乎都非常接近。
首先，在您呈现的语法中，问题实际上仅是当两个标记为时需要提前两个标记)``{。在词法分析器中可以很容易地检测到这一点，并导致一种解决方案，该解决方案仍然很笨拙，但是更简单：){单个令牌返回。您需要处理中间的空格等，但是不需要在词法分析器中保留任何上下文。这具有您无需定义params为exprs 列表的额外好处；它们可以只是一个列表IDENT（如果有的话；有注释表明没有）。
)``{
){
IDENT
我认为较干净的另一种选择是扩展您似乎已经提出的解决方案：接受太多，拒绝语义动作中的错误。在这种情况下，您可以执行以下操作：
start: stmt_list expr: INT | IDENT | lambda | '(' expr_list ')' { // If $2 has more than one expr, report error $$ = $2 } lambda: '(' expr_list ')' '{' stmt_list '}' { // If anything in expr_list is not a valid param, report error $$ = make_lambda($2, $4) } expr_list: expr | expr_list ',' expr stmt: /* empty */ | expr stmt_list: stmt | stmt_list ';' stmt
T
U
FIRSTk-1``FOLLOWk-1
