yacc shift-reduce 用于不明确的 lambda 语法

Question

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

start:
  stmt_list

expr:
  INT | IDENT | lambda | '(' expr ')' { $$ =  }

lambda:
  '(' params ')' '{' stmt_list '}'

params:
  expr | params ',' expr

stmt:
  /* empty */ | expr

stmt_list:
  stmt | stmt_list ';' stmt

lambda 函数看起来像这样：

map((v) { v * 2 }, collection)

我的解析器发出：

conflicts: 1 shift/reduce

给定输入：

(a)

它根据 '(' expr ')' 规则正确解析了 expr。但是给定输入：

(a) { a }

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

syntax error: unexpected '{'

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

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

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

Answer 1

您的分析确实正确；虽然语法没有歧义，但解析器不可能决定将输入减少到 ( <expr> 并使用前瞻性 ) 是否应该将 expr 减少到 params 在移动 ) 之前，或者 ) 是否应该作为 lambda 的一部分移动。如果下一个标记可见，则可以做出决定，因此语法 LR(2) 超出了 go/yacc.

的权限

如果您使用的是 bison，您可以通过请求 GLR 解析器轻松解决此问题，但我不相信 go/yacc 提供该功能。

该语言有一个 LR(1) 文法（对于 k 的任何值，总是有一个 LR(1) 文法对应于任何 LR(k) 文法）但是它很烦人手写。 LR(k) 到 LR(1) 转换的基本思想是通过将上下文的 k-1 个标记累积到每个生产中来将减少决策 k-1 个标记前移。所以在 k 为 2 的情况下，每个产生式 P: N → α 将被替换为产生式 TNU → Tα U 对于 FIRST(α) 中的每个 T 和 FOLLOW(N) 中的每个 U . [见注释 1] 这会导致在任何非平凡语法中大量使用非终结符。

与其追求那个想法，不如让我提出两个更简单的解决方案，这两个方案您似乎都非常接近。

首先，在您提供的语法中，问题实际上只是当两个标记为 ){。这可以很容易地在词法分析器中检测到，并导致一个解决方案仍然是 hacky 但更简单的 hack：Return ){ 作为单个标记。您需要处理中间的空格等，但不需要在词法分析器中保留任何上下文。这有额外的好处，您不需要将 params 定义为 expr 的列表；它们可以只是 IDENT 的列表（如果相关；评论表明它不是）。

我认为更简洁的替代方案是扩展您似乎已经提出的解决方案：接受太多并拒绝语义操作中的错误。在这种情况下，您可以这样做：

start:
  stmt_list

expr:
    INT
  | IDENT
  | lambda
  | '(' expr_list ')'
        { // If  has more than one expr, report error
          $$ = 
        }

lambda:
  '(' expr_list ')' '{' stmt_list '}'
        { // If anything in expr_list is not a valid param, report error
          $$ = make_lambda(, )
        }

expr_list:
  expr | expr_list ',' expr

stmt:
  /* empty */ | expr

stmt_list:
  stmt | stmt_list ';' stmt

备注

这只是一个大纲；完整的算法包括恢复原始解析树的机制。如果 k 大于 2，则 T 和 U 是 FIRSTk-1 的字符串和 FOLLOWk-1 组。

Answer 2

如果确实是移位-归约冲突，而您只需要移位行为，您的解析器生成器可能会为您提供一种方法，让您更喜欢移位与归约。这就是 "if-then-stmt" 和 "if-then-stmt-else-stmt" 的语法规则冲突的经典解决方式，当时 if 语句也可以是语句。

见http://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html

您可以通过两种方式获得此效果： a) 依靠解析引擎的偶然行为。如果 LALR 解析器首先处理移位，然后在没有移位的情况下处理缩减，那么您将免费获得此 "prefer shift"。无论如何，解析器生成器所要做的就是构建解析表，即使检测到冲突也是如此。 b) 加强意外行为。设计（或获得）解析器生成器以接受 "prefer shift on token T"。然后可以抑制歧义。仍然需要像 a) 中那样实现解析引擎，但这很容易。

我认为这 easier/cleaner 而不是滥用词法分析器来制作奇怪的标记（而且这并不总是有效）。

显然，您可以偏好减少，以相反的方式进行调整。通过一些额外的黑客攻击，您可以使 shift-vs-reduce 特定于发生冲突的状态；您甚至可以使其特定于一对相互冲突的规则，但现在解析引擎需要为非终结符保留偏好数据。那还是不难。最后，您可以为每个非终结符添加一个谓词，当即将发生 shift-reduce 冲突时调用它，并让它提供一个决定。

重点是您不必接受 "pure" LALR 解析；如果您愿意稍微修改解析器 generator/engine，您可以通过多种方式轻松地改变它。这为了解这些工具的工作原理提供了一个很好的理由；然后你可以滥用它们来为你谋利。

yacc shift-reduce 用于不明确的 lambda 语法

yacc shift-reduce for ambiguous lambda syntax

parsing

yacc

go

shift-reduce-conflict

备注