具有相同前缀的语法冲突

Question

这是for语句的语法：

FOR x>0 {
    //somthing
}

// or

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

它具有相同的前缀FOR，我想在for_begin之后打印InitExpression标签，但是，由于冲突，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进行了其他遍历之后，才能执行其他分析并允许代码优化）。单遍代码生成器取决于中规矩操作，而中规矩操作又可以轻松生成无法解决的解析冲突。这个问题臭名昭著，以至于a chapter in the bison manual dedicated to it非常值得一读。

因此，没有好的解决方案。但是在这种情况下，有一个简单的解决方案，因为您要执行的操作只是插入标签，而插入一个永远不会使用的标签不会以任何方式影响最终将执行的代码。因此，无论是否需要，您都可以在FOR语句后立即插入一个标签，然后在发现InitExpression语句后插入另一个标签（如果有的话）。您无需真正知道要使用哪个标签，直到到达条件表达式的末尾为止。]

正如我已经链接到的Bison手册章节中所解释的，这无法使用Mid-Rule Actions来完成，因为Bison不会尝试将Mid-Rule Actions相互比较。即使两个动作恰好相同，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]为语义值命名，这避免了必须使用相当神秘且可能不正确的$2或$6。请参阅方便的Bison手册中的Named References。]