yacc shift-reduce用于模糊的lambda语法

您的分析确实是正确的；虽然语法不是模糊的，这是不可能的解析器来决定与输入减少到

(<expr>

与先行

)

是否

expr

应减少到

params

移位之前

)

或者是否

)

应该被作为偏移的一部分

lambda

。如果可以看到下一个标记，则可以做出决定，因此语法go（yacc）之外的语法LR（2）。

如果您使用的是野牛，则可以通过请求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)

让我提出两个简单得多的解决方案，而不是追求这个想法，您似乎都非常接近。

首先，在您呈现的语法中，问题实际上仅是当两个标记为时需要提前两个标记

)``{

。在词法分析器中可以很容易地检测到这一点，并导致一种解决方案，该解决方案仍然很笨拙，但是更简单：

){

单个令牌返回。您需要处理中间的空格等，但是不需要在词法分析器中保留任何上下文。这具有您无需定义

params

为

expr

s
列表的额外好处；它们可以只是一个列表

IDENT

（如果有的话；有注释表明没有）。

我认为较干净的另一种选择是扩展您似乎已经提出的解决方案：接受太多，拒绝语义动作中的错误。在这种情况下，您可以执行以下操作：

start:  stmt_listexpr:    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 ',' exprstmt:   | exprstmt_list:  stmt | stmt_list ';' stmt

笔记

1. 那只是一个轮廓；完整的算法包括恢复原始解析树的机制。如果

   k

   大于2，则

   T

   and

   U

   为字符串，并设置。

   FIRSTk-1``FOLLOWk-1