具有相同前缀的语法冲突

Question

这是我对 for 语句的语法：

FOR x>0 {
    //somthing
}

// or

FOR x = 0; x > 0; x++ {
   //somthing
}

它具有相同的前缀 FOR，我想在 InitExpression 之后打印 for_begin 标签，但是 FOR 后面的代码会因为冲突而变得无用。

    ForStmt
            : FOR   {
                                printf("for_begin_%d:\n", n);
                       } Expression {
                                                           printf("ifeq for_exit_%d\n", n);
                                                 } ForBlock
           | FOR ForClause ForBlock
    ;

ForClause
            : InitExpression ';'   {
                                                            printf("for_begin_%d:\n", n);
                                                    }  Expression  ';'  Expression  { printf("ifeq for_exit_%d\n", n); }
    ;

我曾尝试将其更改为：

ForStart
      : FOR
      | FOR InitExpression
;

或使用标志提及打印 for_begin 标签的位置，但也未能解决冲突。

如何让它不冲突？

Answer 1

解析器如何知道它看到了 FOR 语句的哪个备选方案？

虽然 InitExpression 可能具有可识别的形式，例如赋值语句，但不能在条件表达式中使用。这让我觉得对于实际目的来说限制太多——除了直接赋值之外，你可以做很多事情来初始化一个循环——但撇开这一点不谈，这意味着最早可以确定的 InitExpression 是当看到赋值运算符时。如果您的语言中的左值只能是简单的标识符，那将使它成为 FOR 之后的第二个前瞻标记，但在大多数有用的语言中，左值可能比简单的标识符复杂得多，因此很可能 InitExpression 无法通过有限前瞻明确识别。

但更有可能的是，这两种形式之间唯一的显着区别是第一种形式的表达式后面跟着一个块（我想它不能以分号开头），而第二种形式的第一个表达式是后跟一个分号。所以解析器知道它在第一个表达式的末尾解析什么，而不是更早的。

通常情况下，这不会造成问题。如果不是插入标签的 MidRule Action，解析器在到达第一个表达式的末尾之前不必做出缩减决定，此时它需要决定是否将第一个表达式缩减为 InitExpression 或 Expression。但在那一点上，先行标记作为分号或块的第一个标记，因此先行标记可以指导决策。

但是中间规则行动使这成为不可能。在移动紧跟在 FOR 标记之后的标记之前，必须减少或不减少中间规则操作，并且 - 正如您的示例所示 - 前瞻标记可能是相同的（i）两种情况。

从根本上说，问题是您想要构建一个一次性编译器，而不是仅仅将输入解析为 AST，然后遍历 AST 以生成汇编代码（可能在按顺序对 AST 进行一些其他遍历之后执行其他分析并允许代码优化）。 one-pass代码生成器依赖于Mid-Rule Actions，而Mid-Rule Actions又很容易产生无法解决的解析冲突。这个问题臭名昭著，有a chapter in the bison manual dedicated to it，非常值得一读

所以没有很好的解决办法。但在这种情况下，有一个简单的解决方案，因为您要采取的操作只是插入一个标签，而插入一个碰巧从未使用过的标签不会以任何方式影响最终将要执行的代码.所以你不妨在 FOR 语句之后立即插入一个标签，无论你是否需要它，然后在 InitExpression 之后插入另一个标签，如果事实证明有这样的话。在到达条件表达式的末尾之前，您不需要真正知道要使用哪个标签，这要晚得多。

正如我已经链接到的 Bison 手册章节中所解释的那样，这不能使用中间规则操作来完成，因为 Bison 不会尝试相互比较中间规则操作。即使两个动作碰巧相同，Bison 仍然需要决定执行哪个动作，从而产生冲突。因此，不是使用 MRA，而是需要将操作放在标记非终端中——一个右侧为空的非终端，仅用于触发操作。

这将使语法看起来像这样：

ForLabel
      : %empty             { $$ = n; printf("for_begin_%d:\n", n++); }             
ForStmt
      : FOR
          ForLabel[label]
          Expression       { printf("ifeq for_exit_%d\n", label); }
          ForBlock         { printf("jmp for_begin_%d\n", label);
                             printf("for_exit_%d:\n", label); }
      | FOR
          ForLabel
          InitExpress ';'
          ForLabel[label]
          Expression ';'
          Expression       { printf("ifeq for_exit_%d\n", label); }
          ForBlock         { printf("jmp for_begin_%d\n", label);
                             printf("for_exit_%d:\n", label); }
;

([label] 为语义值命名，这避免了必须使用相当神秘且可能不正确的 </code> 或 <code>。请参阅 Named References方便的 Bison 手册。）

具有相同前缀的语法冲突

Grammar conflict with same prefix

grammar

parsing

yacc