我用弯曲和野牛为了使一个词法分析器和解析器为EBNF语法.这项工作完成了!我的意思是,当我把一个文件放入我写的程序时,我可以看到程序是否有错误.如果没有,我可以根据我使用的语法在屏幕上看到整个程序.我没有问题.
现在,我想使用循环处理和循环展开.我应该改变哪一部分？词法分析器？解析器？还是解析器之后的主要？如何？
由于我们没有看到您的代码片段以查看您如何处理解析器中的循环并输出代码,以及您可能希望展开的特定循环的示例,因此很难提供任何更详细的建议.那已经给了.在全球任何地方都不可能有比那些已经阅读过您问题的编译器或教师更多的经验!因此,我们需要探索其他方法来解释如何解决这样的问题.
人们通常不会发布他们的代码示例,因为他们从作为课程练习的一部分提供的重要代码库开始,或者从开源存储库开始,他们并不完全理解它是如何工作的,以便能够找到合适的代码.要发布的代码片段.让我们假设您拥有一个真正语言的工作编译器的完整源代码,并希望为现有的,正在运行的编译器添加一些循环优化,您可能会说,正如您所做的那样,"什么来源,我如何显示某些来源？ " (因为实际上它是成千上万行代码).
在没有一些代码可供参考的情况下,替代方案是创建一个作为示例来解释问题和解决方案.这通常是在编译器教科书或编译器类中完成的.我将使用一个类似的简单示例来演示如何使用flex和bison工具实现这种优化.
首先,我们需要定义示例的语言.为了保持在SO答案的合理大小限制范围内,语言必须非常简单.我将使用简单的表达式赋值作为我语言中唯一的语句形式.这种语言中的变量将是单个字母,常量将是正整数.唯一的表达式运算符是plus(+).我的语言示例程序可能是:
i = j + k; j = 1 + 2
由编译器生成的输出代码将是一个单个累加器机器简单汇编与四个指令,LDA,STO,ADD和STP.为上述语句生成的代码将是:
LDA j
ADD k
STO i
LDA #1
ADD #2
STO j
STP
在LDA将值或变量加载到累加器中的情况下,向累加器ADD添加变量或值,将累加器STO存储回变量.STP是"停止"的程序结束.
上面显示的语言需要ID和NUMBER的标记,并且还应该跳过空格.以下就足够了:
%{
#define yyterminate() return (END);
%}
digit [0-9]
id [a-z]
ws [\t\n\r ]
%%
{ws}+ /* Skip whitespace */
{digit}+ {yylval = (int)(0l - atol(yytext)); return(NUMBER); }
{id} {yylval = yytext[0]; return(ID); }
"+" {return('+'); }
"=" {return('='); }
血腥细节
只是关于它是如何工作的一些注释.我习惯于atol转换整数以允许处理读取MAXINT时可能发生的潜在整数溢出.我正在否定常量,因此可以很容易地将它们与一个字节中为正的标识符区分开来.我正在存储单个字符标识符,以避免说明符号表代码的负担,从而允许一个非常小的词法分析器,解析器和代码生成器.
要解析语言并从野牛行动中生成一些代码,我们可以通过以下野牛计划实现这一目标:
%{
#include <stdio.h>
%}
%token NUMBER ID END
%%
program : statements END { printf("STP\n"); return(0) ; }
;
statements : statement
| statements ';' statement
;
statement : ID '=' expression { printf("STO %c\n",$1); }
|
;
expression : operand {
/* Load operand into accumulator */
if ($1 <= 0)
printf("LDA #%d\n",(int)0l-$1);
else printf("LDA %c\n",$1);
}
| expression '+' operand {
/* Add operand to accumulator */
if ($3 <= 0)
printf("ADD #%d\n",(int)0l-$3);
else printf("ADD %c\n",$3);
}
;
operand : NUMBER
| ID
;
%%
#include "lex.yy.c"
方法说明
本段适用于那些知道如何执行此操作并可能查询我的示例中使用的方法的人.我故意避免建造一棵树并进行树木漫步,尽管这将是代码生成和优化的正统技术.我想避免在示例中添加所有必要的代码开销来管理树并遍历它.这样我的示例编译器可能非常小.但是,仅限于使用bison动作来执行代码生成限制了我对bison规则匹配的排序.这意味着只能生成伪机器代码.使用这种方法,源到源的例子不太容易处理.我选择了理想化的机器,它是MU0和无寄存器PDP/11之间的交叉,再次使用最少的功能来演示代码的一些优化.
现在我们有几行代码中的语言编译器,我们可以开始演示添加代码优化的过程如何工作.正如受人尊敬的@Chris Dodd所说:
如果要在解析后进行程序转换,则应在解析后执行它们.您可以逐步执行它们(在解析部分输入后从您的野牛代码中调用转换例程),或者在解析完成后,但无论哪种方式,它们都会在解析您正在转换的程序部分之后发生.
此编译器通过在解析部分输入后以递增方式发出代码来工作.在识别每个语句时,将{...}调用bison操作(在子句中)以生成代码.如果要将其转换为更优化的代码,则必须更改此代码以生成所需的优化.为了能够实现有效的优化,我们需要清楚地了解要优化的语言特征以及最佳转换应该是什么.
可以在编译器中完成的常见优化(或代码转换)是常量折叠.在常量折叠中,编译器将结果替换完全由数字组成的表达式.例如,请考虑以下事项:
i = 1 + 2
优化是将其视为:
i = 3
因此,添加1 + 2是由编译器完成的,而不是放在生成的代码中以便在运行时发生.我们希望得到以下输出结果:
LDA #3
STO i
我们可以通过查找我们NUMBER在两侧都有的显式情况来实现改进的代码expression '+' operand.要做到这一点,我们必须延迟采取任何行动,expression : operand以允许值向前传播.由于expression可能尚未评估a 的值,我们必须在赋值和添加时执行此操作,这会导致if语句略有爆炸.我们只需要更改规则的操作statement,expression但是,如下所示:
statement : ID '=' expression {
/* Check for constant expression */
if ($3 <= 0) printf("LDA #%d\n",(int)0l-$3);
else
/* Check if expression in accumulator */
if ($3 != 'A') printf("LDA %c\n",$3);
/* Now store accumulator */
printf("STO %c\n",$1);
}
| /* empty statement */
;
expression : operand { $$ = $1 ; }
| expression '+' operand {
/* First check for constant expression */
if ( ($1 <= 0) && ($3 <= 0)) $$ = $1 + $3 ;
else { /* No constant folding */
/* See if $1 already in accumulator */
if ($1 != 'A')
/* Load operand $1 into accumulator */
if ($1 <= 0)
printf("LDA #%d\n",(int)0l-$1);
else printf("LDA %c\n",$1);
/* Add operand $3 to accumulator */
if ($3 <= 0)
printf("ADD #%d\n",(int)0l-$3);
else printf("ADD %c\n",$3);
$$ = 'A'; /* Note accumulator result */
}
}
;
如果构建生成的编译器,您将看到它确实生成了更好的代码并执行常量折叠转换.
您在问题中特别询问的转换是循环展开.在循环展开中,编译器将在循环开始和结束条件中查找某些特定的整数表达式值,以确定是否应该执行展开的代码转换.然后,编译器可以为循环生成两个可能的代码替换序列,即展开的和标准的循环代码.我们可以通过使用整数增量在此示例迷你编译器中演示此概念.
如果我们想象机器代码有一个INC指令将累加器递增1并且执行ADD #1指令的速度更快,我们可以通过查找特定情况来进一步改进编译器.这涉及评估整数常量表达式并与特定值进行比较以确定是否应使用替代代码序列 - 就像在循环展开中一样.例如:
i = j + 1
应该导致:
LDA j
INC
STO i
要改变为n + 1我们生成的代码,我们只需要重新编写部分expression语义,并测试当不折叠常量时,要使用的常量将是1(在本例中否定).结果代码变为:
expression : operand { $$ = $1 ; }
| expression '+' operand {
/* First check for constant expression */
if ( ($1 <= 0) && ($3 <= 0)) $$ = $1 + $3 ;
else { /* No constant folding */
/* Check for special case of constant 1 on LHS */
if ($1 == -1) {
/* Swap LHS/RHS to permit INC usage */
$1 = $3;
$3 = -1;
}
/* See if $1 already in accumulator */
if ($1 != 'A')
/* Load operand $1 into accumulator */
if ($1 <= 0)
printf("LDA #%d\n",(int)0l-$1);
else printf("LDA %c\n",$1);
/* Add operand $3 to accumulator */
if ($3 <= 0)
/* test if ADD or INC */
if ($3 == -1) printf("INC\n");
else printf("ADD #%d\n",(int)0l-$3);
else printf("ADD %c\n",$3);
$$ = 'A'; /* Note accumulator result */
}
}
;
在这个迷你教程中,我们定义了一个完整的语言,一个完整的机器代码,一个词法分析器,一个编译器,一个代码生成器和一个优化器.它简要地演示了代码生成过程,并指出(尽管通常)如何执行代码转换和优化.它应该能够在其他(尚未看到的)编译器中进行类似的改进,并且已经解决了识别循环展开条件并为该情况产生特定改进的问题.
它也应该清楚地表明,如果没有一些程序代码的具体例子来回答问题是多么困难.