Yacc shift-reduce用于歧义的lambda语法

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 shift/reduce

给定输入:

(a)

根据'(' expr ')'规则正确解析expr。然而，给定输入:

(a) { a }

(这将是恒等函数的lambda，返回其输入)。我:

语法错误:unexpected '{'

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

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

EDIT 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的情况下，FIRST(α)中的每个T和FOLLOW(N)中的每个U的每个生产P: N → α将被TNU → Tα U取代。[参见注释1]这会导致在任何重要语法中出现大量的非终结符。

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

首先，在您提供的语法中，真正的问题仅仅是当两个标记为){时需要两个标记提前查看。这可以很容易地在词法分析器中检测到，并导致一个解决方案，这个解决方案仍然是黑客的，但更简单:将){作为单个令牌返回。您需要处理中间的空白等，但它不需要在词法分析器中保留任何上下文。这有一个额外的好处，你不需要将params定义为expr s的列表;它们可以只是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，则T和U是FIRSTk-1和FOLLOWk-1集合的字符串。

Answer 2

如果确实是shift-reduce冲突，并且您只想要shift行为，那么解析器生成器可能会给您一种选择shift和reduce的方法。当if语句也可以是语句时，这就是解决"if-then-stmt"one_answers"if-then-stmt-else-stmt"语法规则冲突的典型方法。

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

你可以通过两种方式得到这个效果:a)依赖解析引擎的意外行为。如果LALR解析器首先处理移位，然后在没有移位的情况下进行缩减，那么您将免费获得这种"首选移位"。解析器生成器所要做的就是构建解析表，即使检测到冲突也是如此。b)强制执行意外行为。设计(或get a)解析器生成器以接受"对令牌T进行偏好移位"。这样就可以抑制歧义。仍然需要实现解析引擎，如a)所示，但这非常简单。

我认为这比滥用词法分析器来制作奇怪的令牌更容易/更干净(而且这并不总是有效)。

很明显，你可以设置一个减少的偏好，把它变成另一个方向。通过一些额外的黑客攻击，你可以使shift-vs-reduce特定于冲突发生的状态;您甚至可以将其指定为冲突的规则对，但是现在解析引擎需要为非终结符保留首选项数据。这并不难。最后，您可以为即将发生shift-reduce冲突时调用的每个非终结符添加一个谓词，并让它提供一个决策。

关键是你不必接受"纯"LALR解析;如果您愿意稍微修改一下解析器生成器/引擎，您可以通过多种方式轻松地对其进行修改。这给了我们一个很好的理由去理解这些工具是如何工作的;然后你可以滥用它们来为自己谋利。