小编典典

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

go

我正在用Yacc(与Go一起打包的一种语言)为一种玩具语言编写语法,由于以下伪问题,我预期会有移位-减少冲突。我必须将问题语法简化为以下内容。

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 | 实际上,更好的是,我会让lambda要求像语法中那样->(a, b) { a * b}的语法,但是让词法分析器发出->而不是在实际的源代码中。


阅读 394

收藏
2020-07-02

共1个答案

小编典典

您的分析确实是正确的;虽然语法不是模糊的,这是不可能的解析器来决定与输入减少到( <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)

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

首先,在您呈现的语法中,问题实际上仅是当两个标记为时需要提前两个标记)``{。在词法分析器中可以很容易地检测到这一点,并导致一种解决方案,该解决方案仍然很笨拙,但是更简单:){单个令牌返回。您需要处理中间的空格等,但是不需要在词法分析器中保留任何上下文。这具有您无需定义paramsexprs
列表的额外好处;它们可以只是一个列表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,则Tand U为字符串,并设置。FIRSTk-1``FOLLOWk-1
2020-07-02