一个完整的编译器前端

将龙书1,2章阅读后。 照着书上的附录A 实现了一个java语言编写的完整编译器前端。代码基本都是照着书上敲的。  记录一些理解。

 

 编译器是将源语言翻译成一个等价的目标语言的程序。

首先是源语言:

语法定义:

源语言的语法使用“上下文无关的文法” 描述:  我们这个编译器所翻译的语言的文法如下:

 

先来看程序总体部分: program 是文法的开始符号,    一个程序program由块block组成, 一个块由{ }包围,其中有decls 声明序列,和stmts 语句序列.      decls由零个或多个decl 组成. decl 的格式是type id.   type是基础数据类型int,float,double或者他们对应的数组类型。  id是终结符,与c语言的标识符定义类似。  stmts 则是由零个或多个stmt语句构成。    —反正就是递归定义。  后面的都是这么个意思。   (注意其中分号 ;  的位置放置得比较巧妙。

 

接下来是语句的定义,语句包括if,if__else , while, do__while , break;   (bool 表示各种表达式 ,定义在后面 )  注意这里把赋值语句也归结到了语句类,而不是将作为一个表达式。 (据说可以简化翻译工作,不用在bool定义里面加东西,就可以翻译出赋值语句

 

表达式的定义:  这里涉及了运算符的优先级。在优先级低的表达式运算中使用非终结符表示优先级高的表达式运算。  由于递归定义的原因,会先算优先级高的。
如: expr -> expr + term  | term  ,    term -> term * factor | factor  ,     factor -> digit.   加法运算中使用非终结符term , term表示乘法运算。产生抽象语法树的时候乘法更深,中间代码生成时候是深度优先。故满足了优先级顺序

需要使用的非终结符的数目应该比优先级层数多一,此文法中用到的优先级如下:

 =
 ||
 &&
 ==     !=
 <    <=    =>   >
 +    –
 *    /
 !     –

不算赋值符号共7个优先级,需要8个非终结符 ,以此表示如下: (unary表示-号单目运算符 取反.

 

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。分割线

 

定义了一堆。。。其实这个语言像这样           (来自书上的列子:

 


 

 

 

一个完整的编译器包括: 词法分析器–语法分析–语义分析–中间代码生成–代码优化–目标代码生成   六个大阶段。 其中前四个阶段称为编译器的前端。  我们实现的就是编译器的前端。生成中间代码是三地址码。    细节阅读代码。 我大概写一下框架结构

 

 

词法分析:

词法分析读入字符流,处理输出词法单元。

lexer包下。  包含  Token ,Word  , Tag , Real , Num , Lexer  几个类.

Token 是所有词法单元类的基类。 Num 为整数,Real为浮点数, Word为标识符(包含关键字) 。  Tag定义了所有词法单元的常量表示。   所有词法单元类包含两个成员变量。tag表示类型,value表示值。
lexer依次读入单个的字符 去掉空白字符,将数字 ,符号分割成一个个的词法单元。   如:  int a;  a = 1;   词法分析后为:   <Tag.Basic,int>  <Tag.ID,a>   <=>   <Tag.NUM,1>

       symbol 包 包含:Array,Env,Type  三个类。
Type是Word的子类,其本质也是词法单元, 里面定义了四种基本数据类型int, float ,char ,bool .   用标志Tag.Basic表示。   Array类表示数组类型。
Env类是一个符号链表节点的定义。   符号表存储了所有变量的声明。一个符号表用一个hashtable表示, 键为变量名,值为这个变量对应的词法单元
符号表:      int i; int j; float v;

i <Tag.INT,.i>
j <Tag.INT,j>
v <Tag.FLOAT,v>

符号链表就是这样的表组成的一个链。由于变量的声明有作用域,在我们的这个语言中变量作用域 就是其所在的块内。为每一个快创建一个符号表。形成一个符号链表。 top指针指向当前的块符号表。需要查找变量是否声明时。从top 往下查。

 

语法语义分析器

这里就一个类:Parser
调用Lexer 词法分析器得到一个词法单元。  按照文法定义递归构建抽象语法树,同时调用symbol中的Type类中的方法进行类型检查及自动类型转换。
三个成员变量lex,look,top 分别代表词法分析器,当前读入的词法单元,符号链表的顶结点。  三个辅助方法。 match 用于判断当前词法单元与期望类型是否匹配, move用于读入下一个词法单元,error用于抛出错误异常。

 

语法树构建根据文法定义递归执行并判断产生结点即可, 看一小段代码意思意思:         (完整代码在后面

举个简单的 bool表达式的翻译成语法树的例子:             a  > b || a > 0 .  递归到最后匹配到标识符a,回溯到 > 符号匹配,再递归匹配b  .. 回溯到> 的上层匹配  ||  ….继续操作。。就建出了下面的树 🙁 ,中间有什么与文法定义不符,都会抛出异常.
……..||
……./  \
….>         >
…/  \       / \
.a     b  a    0
中间代码生成:

中间代码是三地址码。上面的示例源语言生成的三地址中间代码:

(我觉得复杂的就在这个中间代码生成部分….好好读代码吧。。。)

抽象语法 树中所有类型的结点都有一个基类Node. 其中newlabel方法产生一个新的标号(如上面的L1  标号用于goto语句跳转)    emitlabel方法用于输出标号。  emit方法输出代码.

 


1.表达式的中间代码生成

Expr 类为表达式代码生成基类,其中有一个Token类型的成员变量表示这个结点的此法单元,Type类型成员变量表示结点的类型  。
jumping方法用于需要判断的语句 if else  while 等的跳转( goto 语句的生成)
gen方法 生成一个三地址指令的右部  如: E = E1 + E2 , gen方法返回 E1+E2 的中间表示 x1+x2  , x1 ,x2是化简后的 ,分别指向E1,E2的结点。
reduce 方法计算表达式, 返回打表表达式的常量、标识符或者临时变量。
所有的子类需要用到这些方法的功能不一样需重写。


2.语句的中间代码

语句包括if , if else , while , do while , 赋值语句, 数组元素赋值, break语句。。。都是继承自Stmt类      Stmt类也有一个gen方法用于语句的中间代码生成。
表达式的判断关键用到上面的Exp类的 jumping 方法设置标号与判断出口标号。
也是用到 gen方法递归产生中间代码。
拿if语句举个例子吧:  这是if类的定义

好好看看gen的代码和jumping吧。。。

 

 

我知道 我说不清楚了。。。。。。。坑就开到这里。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。再见

 

代码:      https://github.com/ctguggbond/CompilerFront