如何修复 shift/reduce 解析时的冲突 do while / while

Question

我在使用 do while 和 while do.

解析语法时遇到问题

commands: commands command | command
;
command: WHILE {std::cout<<"D";} condition {std::cout<<"D";} DO {std::cout<<"D";} commands {std::cout<<"D";} ENDWHILE {std::cout<<"D";}
| DO {std::cout<<"D";} commands {std::cout<<"D";} WHILE condition {std::cout<<"D";} ENDDO {std::cout<<"D";}
;

打印 D 只是为了测试目的，我想在那里有几行代码。

它产生警告：由于冲突规则在解析器中无用[-Wother] | DO {std::cout<<"D";} 命令 {std::cout<<"D";} WHILE 条件 {std::cout<<"D";} ENDDO {std: :cout<<"D";}

而commands后面的代码有下划线，所以才会出现问题。

我明白什么是 shift/reduce 冲突，但我可以用像 if/then/else 这样的简单语句来解决它，在这种情况下，这个问题对我来说更复杂。

Answer 1

中间动作 (MRA) 强制解析器做出早期解析决策。在这种情况下，例如，解析器需要在 do ... while 中的 while 之前执行 MRA，但是当它看到 while 时，要知道是否 [=15] 还为时过早=] 终止 do 命令或启动 while 命令。

没有 MRA 就没有问题（可能取决于你的语法的其余部分），因为它可以不断移动标记，直到它看到 do 或 enddo。

除非绝对必要，否则应避免使用 MRA。 [注 1] 在大多数 MRA 看起来很诱人的情况下，事实证明你试图在解析器内部做太多事情。通常最好将解析器限制为生成抽象语法树 (AST)，或在控制流图结构内部的基本块中生成三地址代码 (TAC) 段，而不是作为单一指令数组。 [注 2] 这些中间数据结构使基本算法（例如填充分支目标）更简单，并且是各种更复杂和极其有用的算法的基础，这些算法可以生成更快、更小的代码。（公共子表达式消除、死代码消除、常量折叠等）

但即使您决定采用一种似乎受益于 MRA 的方法，您也会发现通常最好通过将操作移至它们遵循的非终结符来避免它们，或者使用显式标记非终结符（即，一个空的非终结符，其唯一目的是执行一个动作）。这些策略通常会产生更具可读性的语法，并且在许多情况下——包括这个——重组解决了归约-归约冲突。

Bison 有效地将 MRA 转化为标记——您可以在使用 -v 选项生成的语法报告中看到这一点——但真正的标记具有可以多次使用的优势。相比之下，每个 MRA 都是不同的（在 bison 实现中），即使操作是逐个字符相同的。例如，在您问题的简化语法中，野牛生成九个不同的标记非终结符，所有标记都具有相同的操作：{std::cout<<"D";}。结果，野牛最终抱怨减少减少冲突，因为它无法在两个做同样事情的不同标记之间做出决定。显然，这种情况下没有潜在的冲突，用显式标记替换动作将完全避免问题，而无需大手术。

例如，这是一个非常简化的语法，它（直接）生成三地址代码。注意插入标签的 new-label 标记的使用（并将标签编号作为其语义值）：

%{
#include <stdarg.h>
#include <stdio.h>

void yyerror(const char*);
int yylex(void);

int pc = 0;     /* Program counter */
int label = 0;  /* Current label */
int temp = 0;   /* Current temporary variable */

void emit_label(int n) { printf("%10s_L%d:\n", "", n); }

void emit_stmt(const char* fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  printf("/* %3d */\t", pc++);
  vprintf(fmt, ap);
  putchar('\n');
  va_end(ap);
}

%}

%token T_DO "do" T_ENDDO "enddo" T_ENDWHILE "endwhile" T_WHILE "while"
%token ID NUMBER

%%

program
     : statements

/* Inserts a label. 
 * The semantic value is the number of the label.
 */
new-label
     : %empty            { $$ = label++; emit_label($$); }

/* Parses a series of statements as a block, preceded by a label
 * The semantic value is the label preceding the block.
 */
statements               
     : new-label
     | statements statement

statement
     : while-statement
     | do-statement
     | assign-statement

assign-statement
     : ID '=' expr       { emit_stmt("%c = _t%d", , ); }

while-statement
     : new-label "while" condition-jump-if-false "do" statements "endwhile"
                         { emit_stmt("JUMP _L%d", , 0); emit_label(); }

do-statement
     : "do" statements new-label "while" condition-jump-if-false "enddo"
                         { emit_stmt("JUMP _L%d", , 0); emit_label(); }

/* Semantic value is the label which will be branched to if the condition
 * evaluates to false.
 */
condition-jump-if-false
     : compare           { $$ = label++; emit_stmt("IFZ   _t%d, _L%d", , $$); }

compare
    : expr '<' expr      { $$ = temp++; emit_stmt("_t%d = _t%d < _t%d", $$, , ); }

expr: term
    | expr '+' term      { $$ = temp++; emit_stmt("_t%d = _t%d + _t%d", $$, , ); } 

term: factor
    | term '*' factor    { $$ = temp++; emit_stmt("_t%d = _t%d * _t%d", $$, , ); } 

factor
    : ID                 { $$ = temp++; emit_stmt("_t%d = %c", $$, ); }
    | NUMBER             { $$ = temp++; emit_stmt("_t%d = %d", $$, ); }
    | '(' expr ')'       { $$ = ; }

该代码创建的标签比实际需要的多。直接输出架构强制打印这些标签，但真正重要的是生成代码中的位置被保存为表示基本块头部的非终端（可能）的语义值。始终如一地这样做意味着最终行动可以访问他们需要的信息。

值得注意的是标记 new-label 在 while 的两个实例之前使用。只有一种情况是它创建的标签是实际需要的，但无法知道最终会成功制作哪个。

由于各种原因，上述代码并不完全令人满意。首先，由于它坚持立即写出每一行，因此不可能为跳转语句插入占位符。因此，插入条件跳转的标记总是向前跳转（也就是说，它将跳转编译到一个尚未定义的标签），结果是最终测试 do while construct 以类似的代码结束（来源：.. .do ... while a < 3 enddo)

         _L4:
/* ... Loop body omitted */
/*  23 */       _t16 = a
/*  24 */       _t17 = 3
/*  25 */       _t18 = _t16 < _t17
/*  26 */       IFZ   _t18, _L6
/*  27 */       JUMP _L4
          _L6:

而不是效率稍微高一点的

         _L4:
/* ... Loop body omitted */
/*  23 */       _t16 = a
/*  24 */       _t17 = 3
/*  25 */       _t18 = _t16 < _t17
/*  26 */       IFNZ  _t18, _L4

这可以通过将 TAC 存储在数组中而不是打印出来，然后将标签回溯到分支中来解决。（不过，这种变化并没有真正影响语法，因为它都是在最后的动作中完成的。）但是实现经典的预测试优化会更难：

          _L1:
/*   2 */       _t1 = a
/*   3 */       _t2 = 0
/*   4 */       _t3 = _t1 < _t2
/*   5 */       IFZ   _t3, _L2
/* ...   Loop body omitted */
/*  14 */       JUMP _L1

进入

          _L1:
/*   2 */      JUMP _L2
/* ...   Loop body omitted */
          _L2:
/*  12 */       _t1 = a
/*  13 */       _t2 = 0
/*  14 */       _t3 = _t1 < _t2
/*  15 */       IFNZ  _t3, _L1

（重新排序基本块通常可以节省分支；一般来说，以最佳顺序输出基本块比按文本顺序构建它们然后移动它们更容易。）

备注

MRA 当然不应该用于尝试跟踪解析器，因为（在本例中）它们实质上改变了解析的性质。如果您想跟踪您的解析器，请按照 bison 手册中关于 tracing parses 的部分中的步骤进行操作（并阅读有关调试解析器的章节的其余部分。）
通过 print 语句生成 TAC 的风格可以追溯到计算的早期，当时内存非常昂贵且非常有限，编译必须分多个阶段完成，每个阶段都写出结果到“外部存储”（例如纸带），以便可以在下一次通过时顺序读取。当编译器不再需要这种编写风格时，绝大多数真正的程序员还没有出生，但数量惊人的教学资源仍然有意或无意地从这种基本架构开始。您用来阅读此答案的浏览器会毫不犹豫地使用 2 GB 的（虚拟内存）来显示它。在这种情况下，担心在同一台计算机上编译程序时使用几百 KB 的临时存储来保存 AST 似乎很愚蠢。

如何修复 shift/reduce 解析时的冲突 do while / while

How to fix shift/reduce conflict in parsing do while / while

c++

bison

flex-lexer

备注