用于模棱两可的 lambda 语法的 yacc shift-reduce

Question

我正在为 Yacc 中的一种玩具语言（与 Go 打包的语言）编写语法，并且由于以下伪问题，我有一个预期的 shift-reduce 冲突。我必须将问题语法提炼成以下内容。

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 ')'规则正确解析。但是，如果输入：

(a) { a }

（这将是标识函数的 lambda，返回其输入）。我得到：

语法错误：意外的“{”

这是因为当(a)被读取时，解析器选择将其归约为'(' expr ')'，而不是将其视为'(' params ')'。鉴于这种冲突是一个减少而不是减少的冲突，我假设这是可以解决的。我只是不知道如何构建语法来支持这种语法。

编辑 | 这很难看，但我正在考虑定义一个标记，以便词法分析器可以识别 ')' '{' 序列并将其作为单个标记发送以解决此问题。

编辑 2 | 实际上，更好的是，我会让 lambdas 需要语法->(a, b) { a * b}中的语法，但是让词法分析器发出->而不是在实际的源代码中。

Answer 1

你的分析确实是正确的；尽管语法没有歧义，但解析器不可能在输入缩减为( <expr>和前瞻的情况下)决定是否应在移动 the 之前将其expr缩减为，或者是否应将其作为 a 的一部分进行移动。如果下一个标记可见，则可以做出决定，因此语法 LR(2) 超出了 go/yacc 的权限。params))lambda如果您使用的是 bison，您可以通过请求 GLR 解析器轻松解决此问题，但我不相信 go/yacc 提供该功能。该语言有一个 LR(1) 语法（对于 的任何值，总是有一个 LR(1) 语法对应于任何 LR(k) 语法k），但是手写相当烦人。LR(k) 到 LR(1) 转换的基本思想是通过将 k-1 个上下文标记累积到每个产生式中来将减少决策 k-1 个标记向前移动。因此，在k2 的情况下，每个产生式 P:N → α将被替换为 each in和 each in 的产生式。[见注 1] 这会导致任何非平凡语法中的非终结符出现相当大的爆炸。TNU → Tα UTFIRST(α)UFOLLOW(N)与其追求这个想法，让我提出两个更简单的解决方案，您似乎都非常接近这两个解决方案。首先，在您提出的语法中，问题实际上只是当两个标记为){. 这可以很容易地在词法分析器中检测到，并导致一个仍然是 hacky 但更简单的 hack 的解决方案：){作为单个令牌返回。您需要处理中间的空格等，但它不需要在词法分析器中保留任何上下文。这有额外的好处，您不需要将其定义params为exprs 列表；它们可以只是一个列表IDENT（如果相关的话；评论表明它不是）。我认为更简洁的替代方法是扩展您似乎已经提出的解决方案：接受太多并拒绝语义操作中的错误。在这种情况下，您可能会执行以下操作：start:&nbsp; stmt_listexpr:&nbsp; &nbsp; INT&nbsp; | IDENT&nbsp; | lambda&nbsp; | '(' expr_list ')'&nbsp; &nbsp; &nbsp; &nbsp; { // If $2 has more than one expr, report error&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $$ = $2&nbsp; &nbsp; &nbsp; &nbsp; }lambda:&nbsp; '(' expr_list ')' '{' stmt_list '}'&nbsp; &nbsp; &nbsp; &nbsp; { // If anything in expr_list is not a valid param, report error&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $$ = make_lambda($2, $4)&nbsp; &nbsp; &nbsp; &nbsp; }expr_list:&nbsp; expr | expr_list ',' exprstmt:&nbsp; /* empty */ | exprstmt_list:&nbsp; stmt | stmt_list ';' stmt笔记这只是一个大纲；完整的算法包括恢复原始解析树的机制。如果k大于 2 则TandU是字符串 the and集合。FIRSTk-1FOLLOWk-1

Answer 2

如果确实是 shift-reduce 冲突，并且您只需要 shift 行为，那么您的解析器生成器可能会为您提供一种更喜欢 shift 与 reduce 的方法。当 if 语句也可以是语句时，这是经典地解决“if-then-stmt”和“if-then-stmt-else-stmt”的语法规则冲突的方法。见http://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html您可以通过两种方式获得这种效果： a) 依靠解析引擎的意外行为。如果 LALR 解析器首先处理移位，然后在没有移位的情况下进行归约，那么您将免费获得这个“首选移位”。解析器生成器所要做的就是构建解析表，即使检测到冲突也是如此。b) 强制执行意外行为。设计（或获取）解析器生成器以接受“更喜欢在令牌 T 上移位”。然后可以抑制歧义。仍然必须像 a) 那样实现解析引擎，但这很容易。我认为这比滥用词法分析器制作奇怪的标记更容易/更干净（而且这并不总是有效）。显然，您可以偏爱减少以将其转向其他方式。通过一些额外的黑客攻击，您可以使 shift-vs-reduce 特定于发生冲突的状态；您甚至可以使其特定于一对冲突的规则，但现在解析引擎需要保留非终结符的偏好数据。那仍然不难。最后，您可以为每个非终结符添加一个谓词，当即将发生移位减少冲突时调用该谓词，并让它提供一个决定。关键是您不必接受“纯” LALR 解析；如果您愿意稍微修改解析器生成器/引擎，您可以通过多种方式轻松弯曲它。这为了解这些工具的工作原理提供了一个很好的理由；那么你就可以滥用它们来谋取利益。