3

我正在为 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}中的语法，但是让词法分析器发出->而不是在实际的源代码中。

4

2 回答 2

3

你的分析确实是正确的；尽管语法没有歧义，但解析器不可能在输入缩减为( <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:
  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

笔记

  1. 这只是一个大纲；完整的算法包括恢复原始解析树的机制。如果k大于 2 则TandU是字符串 the and集合。FIRSTk-1FOLLOWk-1
于 2016-09-04T17:32:47.587 回答
0

如果确实是 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 解析；如果您愿意稍微修改解析器生成器/引擎，您可以通过多种方式轻松弯曲它。这为了解这些工具的工作原理提供了一个很好的理由；那么你就可以滥用它们来谋取利益。

于 2016-09-04T23:03:54.660 回答