10

我正在编写一个解析器来解析类似 C 的语法。

首先，它现在可以解析如下代码：

a = 1;
b = 2;

现在我想将行尾的分号设为可选。

最初的 YACC 规则是：

stmt: expr ';' { ... }

新行由我自己编写的词法分析器处理（代码被简化）：

rule(/\r\n|\r|\n/)          { increase_lineno(); return :PASS }

这里的 :PASS 指令相当于在 LEX 中不返回任何内容，它会删除当前匹配的文本并跳到下一条规则，就像通常对空格所做的那样。

因此，我不能简单地将我的 YACC 规则更改为：

stmt: expr end_of_stmt { ... }
;
end_of_stmt: ';'
    | '\n'
;

所以我选择相应地由解析器动态改变词法分析器的状态。

像这样：

stmt: expr { state = :STATEMENT_END } ';' { ... }

并添加一个可以将新行与新状态匹配的词法分析器规则：

rule(/\r\n|\r|\n/, :STATEMENT_END) { increase_lineno(); state = nil; return ';' }

这意味着当词法分析器处于 :STATEMENT_END 状态时。它会像往常一样首先增加行号，然后将状态设置为初始状态，然后假装自己是一个分号。

奇怪的是它实际上不适用于以下代码：

a = 1
b = 2

我调试它并得到它实际上并没有得到';' 正如预期的那样，当扫描数字 1 之后的换行符时，状态指定的规则并没有真正执行。

并且设置新状态的代码在它已经扫描新行并且没有返回任何内容之后执行，这意味着这些工作按以下顺序完成：

  1. 扫描a，=和1
  2. 扫描换行符并跳过，所以得到下一个值b
  3. 插入的代码（{ state = :STATEMENT_END }）被执行
  4. b引发错误——这里出乎意料

这是我所期望的：

  1. 扫描a，=和1
  2. 发现它符合规则expr，所以归约为stmt
  3. 执行插入的代码以设置新的词法分析器状态
  4. 扫描换行符并;根据新的状态匹配规则返回a
  5. 继续扫描并解析以下行

经过反省，我发现这可能是由于 YACC 使用 LALR(1) 导致的，该解析器将首先向前读取一个令牌。当它扫描到那里时，状态尚未设置，因此无法获得正确的令牌。

我的问题是：如何让它按预期工作？我对此一无所知。

谢谢。

4

2 回答 2

6

首先要认识到的是，使用像这样的可选行终止符会在您的语言中引入歧义，因此您首先需要确定要解决歧义的方式。在这种情况下，主要的歧义来自可能是中缀或前缀的运算符。例如：

a = b
-c;

您想将以上内容视为单个 expr 语句，还是视为省略第一个分号的两个单独语句？类似 C 语言中的函数调用语法也会出现类似的潜在歧义：

a = b
(c);

如果您希望这些解决为两个语句，您可以使用您尝试过的方法；您只需要提前设置状态一个令牌。这会变得很棘手，因为如果您有未闭合的括号，您不想设置状态，因此您最终需要一个额外的状态变量来记录括号嵌套深度，并且只设置 insert-semi-before-newline 状态是0。

如果您想将上述情况作为一个语句来解决，事情就会变得棘手，因为您实际上需要更多的前瞻性来决定换行符何时应该结束语句——至少您需要在换行符之后查看标记（以及任何评论或其他被忽略的东西）。在这种情况下，您可以让词法分析器进行额外的前瞻。如果您使用的是 flex （您显然不是？），我建议您使用/运算符（直接向前看），或者推迟返回分号，直到与下一个标记匹配的词法分析器规则。

一般来说，在进行这种标记状态记录时，我发现在可能的情况下完全在词法分析器中完成它是最容易的，因此您不必担心有时（但并非总是）由解析器完成的额外前瞻标记. 在这种特定情况下，一种简单的方法是让词法分析器记录看到的括号（+1 表示(，-1 表示)），并返回最后一个标记。然后，在换行规则中，如果括号级别为 0，并且最后一个标记是可以结束表达式的东西（ID 或常量或)或仅后缀运算符），则返回额外的;

另一种方法是让词法分析器NEWLINE作为自己的标记返回。然后，您将更改解析器以接受stmt: expr NEWLINE语法中大多数其他标记之间的可选换行符。这会将歧义直接暴露给解析器（它现在不是 LALR(1)），因此您需要通过使用 yacc 的运算符优先级规则（棘手且容易出错）或使用诸如 bison 的%glr-parser选项或 btyacc 的回溯能力来解决它直接带有歧义。

于 2012-06-10T19:16:56.277 回答
3

您正在尝试的当然是可能的。

事实上，Ruby 正是这样做的，它有一个 yacc 解析器。换行软终止语句，分号是可选的，并且语句“如果需要”会自动在多行上继续。

解析器和词法分析器之间的通信可能是必要的，是的，遗留 yacc 是 LALR(1)。

我不知道Ruby是如何做到的。我的猜测一直是它实际上并没有（太多）通信，而是词法分析器识别显然没有完成的结构，并且默默地将换行符视为空格，直到括号和括号平衡。它还必须注意行何时以二元运算符或逗号结尾并吃掉这些换行符。

只是一个猜测，但我相信这种技术会奏效。Ruby 是开源的……如果你想看看Matz是如何做到的。

于 2012-06-10T17:37:40.860 回答