2

我有这样的语法：

“匹配一个或多个规则 1，其中规则 1 是一个或多个规则 2，其中规则 2 是一个或多个规则 3，等等。每个规则由换行符分隔”。看下面的例子。

start:   rule1_list
      ;

rule1_list:   rule1
           |  rule1_list NEWLINE rule1
            ;

rule1:   rule2
     |   rule2 NEWLINE rule3_list
      ;

rule2:   TERMINAL2
      ;

rule3_list:   rule3
          |   rule3_list NEWLINE rule3
          ;

rule3 :  TERMINAL3
      ;

这样做我会遇到 shift/reduce 冲突，如何更改语法以停止？本质上，它需要在新行之后分支并查看下一个是 TERMINAL2 还是 TERMINAL3。

4

3 回答 3

5

模棱两可的语法，不是 LALR(1)，默认无法解析 yacc 模式

长话短说，您可以通过%glr-parser如下声明“修复”此问题：

%glr-parser
%%
start: rule1_list
. . .
. . .

把长篇故事做成中等长度的……

Shift-reduce 冲突通常不是错误。通过总是做通常是你想要的转变来解决冲突。大多数或所有现实世界的语法都有移位减少冲突。如果您想要减少，您可以通过优先声明来安排。

然而，在一个真正模棱两可的文法中，进行移位将使解析器沿着两条路径之一发送，其中只有一条最终会在文法中找到一个字符串。在这种情况下，S/R 冲突是一个致命错误。

分析第一个，当解析器在| rule2 NEWLINE rule3_listcase 中看到换行符时，它可以转换到一个新状态，预计它是一个 rule3_list，或者它可以减少一个 rule1 使用rule1: rule2. 由于默认选择 shift，它将始终查找 rule3_list。

第二个冲突发生在它在 中看到换行符时 rule3_list: rule3_list . NEWLINE rule3。现在它可以转移并开始寻找 rule3 或使用| rule2 NEWLINE rule3_list.

结果是，如所写，假设终端为“2”和“3”，您只能解析 2 行后跟 3 行。如果您摆弄优先级，则只能解析“2”行，而不能解析“3”行。

最后，我应该补充一点，使用 yacc 生成的 GLR 解析器有点杂乱无章。我想它会工作得很好，但它是纯 BFI，解析器分裂，保留两个堆栈，继续沿着两条路径，直到在语法中找到一个字符串。可悲的是，其他修复也很麻烦：1.将语法重新表述为 LALR(1)，2.在扫描仪中添加额外的前瞻并返回复合标记，3.尝试使用您拥有的语法规则，也许 yacc 可以处理一种变体。

这就是为什么我实际上并不喜欢 yacc 而是更喜欢手写递归下降或像 PEG 这样更现代的东西。（见树梢。）

我尝试了一些（首选）左递归规则，这些规则只是忽略了换行符（这会使你的语法复杂化，制作空白标记......）..这个“有效”，虽然我不确定它是否是你想要的。 ..

%%
start:   stmtList
      ;

stmtList: /* nothing */ 
      | stmtList '2' threeList;
      ;

threeList: /* nothing */
      | threeList '3'
      ;
%%
int yylex() { int c; do {  c = getchar (); } while (c == '\n'); return c; }
于 2009-11-19T01:17:35.183 回答
1

不是模棱两可，只是不是 LALR(1)

问题是语法中的几个地方需要 2-token 前瞻，以查看哪个 TERMINAL 出现在 NEWLINE 之后，以便决定要做什么。你可以做很多事情来解决这个问题。

  1. 跳过扫描器中的换行符——然后它们将不再是标记，也不会妨碍前瞻

  2. 使用 %glr-解析器。如果您确实在语法中引入歧义，这可能会很危险，因为它们需要合并函数才能使事情正常进行。没有好的方法可以确定任何给定的冲突是由于模棱两可还是只是需要更多的前瞻——您需要仔细分析每个冲突野牛报告来判断。

  3. 重构语法以推迟决策，因此不需要太多的前瞻。一个简单的选择是将换行符作为终止符而不是分隔符吸收到规则中：

    start:   rule1_list ;

rule1_list:   rule1
          |  rule1_list rule1
          ;

rule1:   rule2
     |   rule2 rule3_list
     ;

rule2:   TERMINAL2 NEWLINE ;

rule3_list:   rule3
          |   rule3_list rule3
          ;

rule3 :  TERMINAL3 NEWLINE ;

当然，这会改变语法，因为现在在 EOF 之前的最后一条规则之后需要换行符

于 2009-11-22T20:29:06.990 回答
0

我认为您必须将左递归转换为右递归。一个例子rule3_list：

rule3_list: TERMINAL3 | TERMINAL3 NEWLINE rule3_list;
于 2009-11-19T01:45:32.957 回答