基于GUI的交互式编译系统之中间代码生成器的设计与实现毕业论文.docx

基于GUI的交互式编译系统之中间代码生成器的设计与实现毕业论文.docx

《基于GUI的交互式编译系统之中间代码生成器的设计与实现毕业论文.docx》由会员分享，可在线阅读，更多相关《基于GUI的交互式编译系统之中间代码生成器的设计与实现毕业论文.docx（62页珍藏版）》请在冰点文库上搜索。

基于GUI的交互式编译系统之中间代码生成器的设计与实现毕业论文

基于GUI的交互式编译系统之中间代码生成器的设计与实现

摘要

本设计实现了一个编译器前端，它将一个用C语言的子语言编写的源程序翻译成中间代码。

词法分析器、语法分析器、中间代码生成器均是采用C++语言手动书写完成，未采用自动生成器，GUI采用Win32API实现以保证轻快的运行速度及良好的系统性能，编辑控件采用Scintilla。

词法分析器采用确定有限自动机实现，语法分析器是一个递归下降分析器，中间代码生成器输出的中间代码以四元式形式表示。

本设计实现的编译器前端，运行在Windows平台下，Windows系统版本为WindowsXP、Windows7或更高版本。

本设计提供了一个可工作的界面友好的编译器前端，可以用来理解编译原理及解释怎样用一种语言如C++实现编译器前端，以供学习和教学所用。

关键词：

编译器前端；GUI；C++

Design&ImplementationofIntermediateCodeGeneratorofInteractiveCompilationSystemBasedGUI

Abstract

Thisfinalprojectimplementsacompilerfront-end,ittranslatessourceprogramswritteninasubsetoftheClanguageintointermediatecode.Thelexer、parserandintermediatecodegeneratorareallhand-writteninC++,noautolexerorparserareused,GUIisimplementedinWin32APIforfastrunningspeedandhighperformance,andeditcontrolusesScintilla.ThelexerisimplementedinDeterministicfiniteautomata,theparserisarecursive-descentparser,theintermediatecodesarerepresentedinquadruple。

Thecompilerfront-endrunsontheWindowsplatform,WindowssystemversionisWindowsXP,Windows7orlater.Thisprojectprovideaworkinganduserinterfacefriendlycompilerfront-end,whichcanbeusedtodemonstratecompilerprincipleandhowcompilerscanbeimplementedinalanguagesuchasC++,forlearningandteaching.

Keywords:

compilerfront-end;GUI;C++

附件1：

开题报告（文献综述）

附件2：

译文及原文影印件

1绪论

很少有人去自己编写或修改编译器，那么为什么要去实现编译器前端呢？

很重要的一点就是，理解计算机程序怎样被编译以及执行，可以帮助任何程序员理解他们写的代码是怎样驱动计算机的，从而帮助他们写出更快、更高效的程序。

编译原理经过多年发展已日趋成熟，然而现代很多跟编译原理相关的教材，内容陈旧落后，比如以Fortran或Pascal等过时语言为例进行分析讲解，或者全书充满晦涩难懂的定理公式，不能以直观的方式进行阐述，致使学生望而生畏。

本设计用C++语言实现了一个编译器前端，它将一个用C子语言编写的源程序翻译成中间代码，拥有友好直观的交互式图形界面，有助于对编译原理的理解，可用于学习及教学。

在一段程序可以执行之前，首先需要把它翻译成一种其能够被计算机接受的形式，完成这项翻译工作的程序称为编译器（compiler）[1]。

简单而言，编译器是一个程序，它将使用源语言编写的程序转换成另一种目标语言。

在转换阶段很重要的一部分是报告用户当前源程序的错误。

为了将源程序从一种语言翻译成另一种语言，编译器必须首先把程序的各种成分拆开，并搞清其结构和含义，然后再把这些成分组合成有意义的计算机能识别的语言。

编译器的前端进行词法分析、语法分析和语义分析，并且产生中间代码，即进行分析。

编译器的后端对中间代码进行优化并将中间代码翻译成机器语言，即进行组合。

词法分析的任务是：

对源程序进行从左到右逐个字符地扫描，产生一个个独立的单词符号（token）。

词法分析是编译的基础。

语法分析的任务是：

在词法分析识别出一系列单词符号的基础上，分析并判定源程序的结构是否符合语法规则。

语法分析可以粗略地分为两类，一类是自顶向下，一类是自底向上[2]。

对于本设计，采用的是自顶向下进行分析。

语法分析得到语法树，尽管可以直接将语法树转换成目标机器代码，但这样做不利于可移植性和模块化设计。

假设需要这样一个编译器：

它可以编译N种不同的源语言，然后为M台不同的目标机生成代码。

理论上，这是N*M个编译器，如图1.1（a），但实现这么多的编译器是需要花费大量的人力物力。

中间代码（intermediatecode,IC）是一种抽象机器语言，它可以表示目标机的操作而不需太多涉及与机器相关的细节，而且，它也独立于源语言的细节[3]。

一个可移植的编译器如图1.1（b）所示，它先将源语言转换成中间代码，然后再将中间代码转化成目标机器语言，这样便只需要实现N个前端和M个后端。

这种实现要更容易合理些。

即使在只需实现一个前端和一个后端的情况下，好的中间代码也利于将系统模块化，使得编译器前端不会因机器相关的细节而复杂化，编译器后端不会因源语言的特殊信息而干扰。

编译器可以使用的中间代码有多种形式，对于本设计，采用简单的四元式。

IC

（a）（b）

图1.1面向5种语言并支持4种目标机的编译器：

（a）没有IC，（b）有IC

编译器的每个阶段都可能遇到错误，如果编译器在遇到第一个错误时就停止运行，对于修正程序肯定起不到多大帮助作用。

词法分析阶段可以检测出来自输入的字符串不能形成语言的任何单词符号（token）。

语法分析阶段可以检测出违反语言语法的单词符号串。

本设计可以报告出错误是什么及错误在源程序的行号和列号。

2基本原理

一个编译器是一个计算机程序，它可以把用某种高级语言写的源代码转换成另一种形式，典型的形式是机器码。

机器码是计算机可以执行的一系列指令[4]。

intmax（inta,intb）

{

if（a>b）

returna;

returnb;

}

一个编译器由有两部分组成，如图2.1所示。

（1）源代码分析器：

它将输入的源代码看作是一个字符串，然后将其翻译成有意义的符号（变量，值，操作符等）。

（2）目标代码生成器：

它将源代码分析器的结果转换成可执行代码。

图2.1编译器结构

源代码分析器不依赖于机器，然而目标代码生成器需要针对不同的机器类型生成不同的代码，因此是依赖于机器的。

源代码分析器经常被称作编译器的前端，目标代码生成器被称作后端。

本设计要实现的正是编译器的前端。

编译器的前端又分为三个阶段，如图2.2所示。

图2.2编译器前端

2.1词法分析

词法分析器以字符流作为输入，删除单词之间的空白符和注释（程序中每一部分都有可能出现空白和注释）并生成一系列的名字、关键字和标点符号。

如果让语法分析器来处理它们就会使得语法分析过于复杂，结构也不清晰，这便是将词法分析成为一个独立阶段，从语法分析中分离出去的主要原因[5]。

在词法分析器中，词法单元（token）通常包含以下几种类型：

•标识符

•保留字（如：

“if”，“while”等）

•数值常量（如：

整数，实数等）

•字符串常量

•简单符号（运算符如：

“+”，“-”等，分隔符如：

“；”，“，”等）

•多重符号（运算符如“+=”，“++”等）

这些词法单元将用于下一阶段语法分析。

2.1.1词法分析结果

对于下面一段程序：

intmatch（char*str）//findazero

{

if（!

strncmp（str,“0”,1））

return0;

}

词法分析器将产生如下tokens：

INTID（match）LPARENCHARSTARID（str）RPAREN

LBRACE

IFLPARENBANGID（strncmp）LPARENID（str）COMMASTRING（0）COMMANUM

（1）RPARENRPARENRETURNREAL（0）SEMI

RBRAC

EOF

2.1.2确定有限自动机

确定有限自动机可用来实现词法分析器。

有限自动机包括一个有限状态集合和一些从一个状态通往另一状态的边，每条边上标有一个符号；其中一个状态是初态，某些状态是终态[6]。

图2.3给出了几个有限自动机的例子。

i

f

IF

a-z

0-9

0-9

0-9

IDNUM

图2.3词法单词的有限自动机

在确定有限自动机中，不会有从同一状态发出的两条边标记有相同的符号，确定有限自动机以如下方式接受或拒绝一个字符串：

从初始状态出发，对于输入串中的每个字符，自动机都将沿着一条确定的边到达另一状态，这条边必须是标有输入字符的边，对n个字符的字符串进行了n次状态转换后，如果自动机到达了一个终态，自动机将接受该字符串，若到达的不是终态，或者找不到与输入字符相匹配的边，那么自动机将拒绝接受该字符串[7]。

2.2语法分析

语法分析是分析如何根据一个文法生成一个终结符号串的过程。

一种语言的识别器是一个程序，它把输入看作一个字符串x，如果x是该语言的一个句子，则回答是，否则回答否。

大多数分析方法都可以归为以下两类：

自顶向下方法和自底向上方法。

在自顶向下语法分析器中，构造过程从根结点开始，逐步向叶子节点方向进行，直至推出句子。

自顶向下方法可以较容易地手工构造出高效的语法分析器。

在自底向上语法分析器中，逐步对输入串进行归约，直至文法的开始符号，即从叶子节点开始，逐步向上归约，直至语法树的根节点。

LL

（1）文法表示对输入串从左到右扫描，进行最左推导，分析时每步向前查看一个字符。

LL

（1）分析法需要消除左递归和克服回溯。

LR分析法表示对输入串从左到右扫描，构造最右推导的逆过程。

LR分析法若采取手工构造，工作量非常大。

本设计语法分析采用递归下降分析法。

2.2.1递归下降分析法

递归下降分析方法是一种不带回溯的自顶向下语法分析方法，它使用一组递归过程来处理输入。

为文法的每个非终结符都创建一个相应的过程。

递归下降分析法的一种简单形式是预测分析法。

在预测分析法中，各个非终结符号对应的过程中的控制流可以由向前看符号无二义性地确定，在分析输入串时出现的过程调用序列隐式地定义了该输入串的一棵语法树[8]。

假设用预测分析法分析以下文法（黑体字符序列被视为一个单元，也就是单个终结符号）：

stmtexpr;

|if（expr）stmt

|for（optExpr;optExpr;optExpr）stmt

|other

optExprε

|expr

则预测分析器如下所示：

voidstmt（）{

switch（curToken）{

caseexpr:

accept（expr）;accept（‘;’）;

break;

caseif:

accept（if）;accept（‘（’）;accept（expr）;accept（‘）’）;stmt（）;

break;

casefor:

accept（for）;accept（‘（’）;

optExpr（）;accept（‘;’）;optExpr（）;accept（‘;’）optExpr（）;

accept（‘）’）;stmt（）;

break;

caseother:

accept（other）;break;

default:

report（“syntaxerror”）;

}

}

voidoptExpr（）{

if（curToken==expr）

accept（expr）;

}

voidaccept（terminalt）{

if（curToken==t）

curToken=nextTerminal;

else

report（“syntaxerror”）;

}

该预测分析器中包含了两个过程stmt（）和optExpr（），分别对应于文法中非终结符号stmt和optExpr。

该分析器中还包括一个额外的过程accept。

这个额外的过程用来简化stmt和optExpr（）的代码。

过程accept（t）将它的参数t和向前看符号比较，如果匹配就前进到下一个输入终结符号。

因此，accept改变了全局变量curToken的值，该变量存储了当前正被扫描的输入终结符号。

在分析过程的开始，首先调用文法的开始非终结符号stmt对应的过程，根据相应的语法规则，调用相应的处理过程。

例如在处理“for（expr;expr;expr）other”输入时，curToken被初始化为第一个终结符号for。

每个非终结符都产生一个对相应过程的调用：

accept（for）;accept（‘（’）;

optExpr（）;accept（‘;’）;optExpr（）;accept（‘;’）;optExpr（）;

accept（‘）’）;stmt（）;

2.2.2运算符的优先级

考虑表达式5+2*3。

该表达式可有两种不同的翻译，即（5+２）*3或5+（2*3）。

因此当多种运算符出现时，需要给出一些规则来确定运算符之间的相对优先关系。

先考虑“+-*/”这四个常用运算符之间的优先级关系：

左结合：

+-

左结合：

*/

创建两个非终结符expr和term，expr对应于“左结合：

+-”，term对应于“左结合：

*/”，并使用另一个非终结符号factor来表示表达式中的基本单元。

当前，表达式中基本单元是数字位和带括号的表达式。

factordigit|（expr）

现在考虑具有最高优先级的二目运算符*和/。

由于这些运算符是左结合的，因此其产生式和左结合列表的产生式类似：

termterm*factor

|term/factor

|factor

类似的，expr生成由加减运算符分隔的term列表：

exprexpr+term

|expr–term

|term

因此最终得到的文法是：

exprexpr+term|expr–term|term

termterm*factor|term/factor|factor

factordigit|（expr）

2.3中间代码生成

图2.4中间代码

经常会有这种情况，编译器需要为几个目标机器生成机器码或汇编程序。

中间代码是跟目标机器无关的，所以相同的中间代码可以在目标语言之间共享（如图2.4）。

那么为一台新的机器开发编译器时就可以减少工作量。

另外，很容易对中间代码进行优化，优化也是与机器无关的[9]。

中间代码生成阶段将语法树翻译成中间语言表示形式。

中间代码是机器无关的，但是它们接近机器指令。

源程序通过中间代码生成器翻译成等价的中间语言。

中间代码可以是不同的语言，它由编译器的设计者决定。

语法树可以作为中间语言，后缀表达式可以作为中间语言，三地址代码（四元式）也可以作为中间语言。

在后缀表达式中，任何语句表示都可以不使用括号，如：

a*（9+d）=>a9d+*

后缀表达式计算可以通过栈来实现。

然而使用后缀表达式有很多不利的地方，如后缀表达式生成的汇编代码包含冗余的操作；这些操作只能在汇编代码中进行优化，而不是在中间代码中；优化需要针对特定的目标机器。

因此需要一种接近汇编语言的中间代码，它支持机器无关级的优化。

所以本设计采用四元式。

2.3.1四元式

在四元式中，所有的操作都可以归约为一元或二元操作。

这种中间代码可以看成是一系列的执行步骤，每步的执行结果存储在临时变量中[10]。

四元式由如下成分组成：

•操作符

•操作数，即两个操作数

•结果，存储运算结果

（operator,arg1,arg2,result）

一个简单的表达式可以用一个四元式表示：

b+c=>（+,b,c,tmp1）

稍微复杂的表达式可以由一个四元式集合表示，临时变量存储中间结果。

a*（5+d）

=>（+,5,d,tmp1）

（*,a,tmp1,tmp2）

2.3.2四元式的常见结构

•算术运算和布尔表达式

a+b=>（+,a,b,tmp1）

a*（b+c）=>（+,b,c,tmp1）,（*,a,tmp1,tmp2）

按照运算顺序，先计算括号中的表达式“b+c”，运算结果保存在临时变量tmp1中，然后计算a*tmp1。

a（<,a,b,tmp）

•一元运算

-a=>（-,a,_,tmp）

下划线表示空。

•赋值

a=a+b=>（+,a,b,tmp）,（=,tmp,_,a）

本设计的赋值运算只支持简单赋值，不支持连续赋值，如a=b=0。

•声明

inta,b=>无

inta=5=>（=,5,_,a）

声明时可以进行初始化。

•数组引用

a=x[i]=>（=,x[i],_,a）

x[i]=a=>（=,a,_,x[i]）

•无条件跳转

（jmp,jump_address,_,_）

jump_address表示跳转目标地址，在本设计中是一个目标标号。

•条件跳转

（<,i,5,tmp1）//条件

（jtrue,jump_address,tmp1,_）//表示如果tmp1为真则跳转。

注：

是条件调转还是无条件调转，由arg2决定。

•for循环

for（i=0;i<3;i++）

body

=>

（=,0,_,i）//初始化

（label_0:

_,_,_）

（<,i,3,temp_0）//条件

（jtrue,label_1,temp_0,_）

（jmp,label_3,_,_）

（label_1:

_,_,_）

bodyofloop...

（label_2:

_,_,_）

（+,i,1,i）//迭代

（jmp,label_0,_,_）

（label_3:

_,_,_）

每个for语句会产生四个标号，一个表示类似“i=0”的初始化，一个表示类似“i<３”的条件判断，一个表示body,一个表示类似“i++”的表达式。

•if-else语句

if（a

c=a;

else

c=b;

=>

（<,a,b,temp_0）

（jtrue,label_1,temp_0,_）

（jmp,label_0,_,_）

（label_1:

_,_,_）

（=,a,_,c）

（jmp,label_2,_,_）

（label_0:

_,_,_）

（=,b,_,c）

（label_2:

_,_,_）

一个if-else语句会产生3个标号，一个表示条件为真时的执行语句，一个表示条件为假的执行语句，一个表示跳出if-else语句。

•while语句

while（a

a=a+1;

=>

（label_0:

_,_,_）

（<,a,b,temp_0）

（jtrue,label_1,temp_0,_）

（jmp,label_2,_,_）

（label_1:

_,_,_）

（+,a,1,temp_1）

（=,temp_1,_,a）

（jmp,label_0,_,_）

（label_2:

_,_,_）

每个while语句产生3个标号，一个表示类似“a=0”的初始化，一个表示类似“a

•switch语句

switch（i）{

case1:

a=a+1;break;

default:

a=a+2;

}

=>

（jmp,label_0,_,_）

（label_3:

_,_,_）

（+,a,1,temp_0）

（=,temp_0,_,a）

（jmp,label_2,_,_）

（label_1:

_,_,_）

（+,a,2,temp_1）

（=,temp_1,_,a）

（jmp,label_2,_,_）

（label_0:

_,_,_）

（==,i,1,temp_2）

（jtrue,label_3,temp_2,_）

（jmp,label_1,_,_）

（label_2:

_,_,_）

每个switch语句会针对相应的case和default产生标号，同时，还会产生跳出switch的标号。

•函数调用

intadd（inta,intb）

{

returna+b;

}

voidmain（）

{

inta=1,b=1,c;

c=add（a,b）;

}

=>

（add:

_,_,_）

（enter,16,_,_）

（+,a,b,temp_0）

（return,temp_0,_,_）

（return,_,_,_）

（main:

_,_,_）

（enter,16,_,_）

（=,1,_,a）

（=,1,_,b）

（param,b,_,_）

（param,a,_,_）

（call,add,_,temp_1）

（incStackPtr,8,_,_）

（=,te