减少野牛的订单 [英] Reduce order in Bison

问题描述

我正在使用Bison编写编译器，并且试图在while和重复循环中使用相同的功能.我需要解析器在"statements_off"之前减少"condition". ¿我可以指定减少顺序吗?

I am writing a compiler using Bison and I am trying to use the same function with while and repeat loops. I need the parser to reduce "condition" before "statements_off". ¿Can I specify the reduction order?

以下是循环的代码:

loop_stmt:
        WHILE line condition DO ENDL line statements_off DONE
            { $$ = process_while($<elem>3, $<elem>7, $<ival>2, $<ival>6); }
    |   REPEAT ENDL line statements_off UNTIL line condition    
            { $$ = process_not($<elem>7);
              $$ = process_while($$, $<elem>4, $<ival>6, $<ival>3);  }
    |   FOR for_condition DO ENDL statements_off DONE
            { $$ = process_for($<elem>5, $<ival>2); }
    ;

condition: '(' expr_bool_or ')' { validate_bool_condition($<elem>2); $$ = $<elem>2; }
    ;

推荐答案

从下而上和从左至右评估野牛的减少量.这是该算法的重要组成部分.

Bison reductions are evaluated bottom-up and left-to-right. That is an essential part of the algorithm.

这给了您一点自由度-有时您可以编写一种语法，以便自下而上的归纳会产生从右到左的效果-但您实际上不应该这样做.解析为AST(理想情况下与动作评估的顺序无关)，然后在必要且方便的情况下遍历AST时，语义分析最有效.

That gives you a tiny bit of latitude -- occassionally you can write a grammar so that bottom-up reductions will have a right-to-left effect -- but you really shouldn't. Semantic analysis works best when you parse into an AST (ideally independent of the order of action evaluation) and then walk the AST as necessary and convenient.

通过将语言直接线性化为三个地址的代码来编写单程编译器似乎是一种简化或优化.但是由于将设计成树的过程扭曲成线性控制流的困难，最终感觉更像是一件直筒外套.

Writing a one-pass compiler by directly linearizing the language into three-address code may seem like a simplification, or an optimisation. But it will end up feeling more like a straight-jacket because of the difficulty of warping a process designed to produce a tree into a linear control flow.

一遍遍的编译器-Lua编译器浮现在脑海-经常由于这种问题的构造以及为了实现非猫眼优化而不得不重新排序生成的代码块.

One-pass compilers -- the Lua compiler springs to mind -- often end up having to reorder chunks of generated code, both because of constructs such as this question and in order to implement non-peephole optimizations.

(在循环末尾将while和for语句中的预测试改组实际上是很普遍的，这似乎与此处所设想的相反.)

(It's actually pretty common to shuffle the pre-test in while and for statements to the end of the loop, which seems to be the opposite of what is being contemplated here.)

要弄清楚可能性，请考虑以下两者之间的区别:

To be clear about the possibilities, consider the difference between:

expressions: 
           | expressions expression     { printf("%d\n", $2); }

和

expressions:
           | expression expressions     { printf("%d\n", $1); }

这两个值都从左到右缩小expression，但是expressions的自下而上的缩小导致第二节摘录以相反的顺序打印表达式的值.如果expression不是递归的(几乎可以肯定是递归的)，则可以将其分解为expressions产生式，从而使表达式本身的约简与自下而上的逻辑相对应.但是这种转换是非常有限的，因为它只在您递归产生之前就起作用，并且几乎所有有趣的产生都是递归的. (statement和expression只是两个示例.)

Both of these reduce expression left-to-right, but the bottom-up reduction of expressions causes the second excerpt to print the values of the expressions in reverse order. If expression were not recursive (which it almost certainly is), you could unfactor it into the expressions production, causing the reductions of the expressions themselves to correspond to the bottom-up logic. But this transformation is extremely limited, because it will only work until you hit a recursive production, and almost all interesting productions are recursive. (statement and expression being just two examples.)

这篇关于减少野牛的订单的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！