龙书-一个完整编译器前端
将龙书1，2章阅读后。 照着书上的附录A 实现了一个java语言编写的完整编译器前端。代码基本都是照着书上敲的。 记录一些理解。 编译器是将源语言翻译成一个等价的目标语言的程序。 首先是源语言： 语法定义： 源语言的语法使用“上下文无关的文法” 描述： 我们这个编译器所翻译的语言的文法如下： 先来看程序总体部分： program 是文法的开始符号， 一个程序program由块block组成, 一个块由{ }包围，其中有decls 声明序列，和stmts 语句序列. decls由零个或多个decl 组成. decl 的格式是type id. type是基础数据类型int,float,double或者他们对应的数组类型。 id是终结符，与c语言的标识符定义类似。 stmts 则是由零个或多个stmt语句构成。 —反正就是递归定义。 后面的都是这么个意思。 (注意其中分号 ; 的位置放置得比较巧妙。
program --> block
block --> {decls stmts}
decls --> decls decl '|' null
decl --> type id;
type --> type\[num\] '|' basic
stmts --> stmts stmt '|' null
接下来是语句的定义，语句包括if,if__else , while, do__while , break; (bool 表示各种表达式 ，定义在后面 ) 注意这里把赋值语句也归结到了语句类，而不是将作为一个表达式。 （据说可以简化翻译工作，不用在bool定义里面加东西，就可以翻译出赋值语句
stmt --> loc = bool；
'|' if (bool) stmt
'|' if (bool) stmt else stmt
'|' while(bool) stmt
'|' do stmt while(bool);
'|' break ;
'|' block
loc --> loc\[bool\] '|' id
| 表达式的定义： 这里涉及了运算符的优先级。在优先级低的表达式运算中使用非终结符表示优先级高的表达式运算。 由于递归定义的原因，会先算优先级高的。 如： expr -> expr + term ‘ | ’ term , term -> term * factor ‘ | ’ factor , factor -> digit. 加法运算中使用非终结符term ， term表示乘法运算。产生抽象语法树的时候乘法更深，中间代码生成时候是深度优先。故满足了优先级顺序 需要使用的非终结符的数目应该比优先级层数多一，此文法中用到的优先级如下： |
=
| ’ | ’’ | ’ |
&&
== ！=
< <= => >
+ -
* /
! -
不算赋值符号共7个优先级，需要8个非终结符 ，以此表示如下： （unary表示-号单目运算符 取反.
bool --> bool '|''|' join '|' join
join --> join && equality '|' equality
equality --> equality == rel '|' equality != rel '|' rel
rel --> expr < expr '|' expr <= expr '|' expr >= expr '|' expr > expr '|' expr
expr --> expr + term '|' expr - term '|' term
term --> term * unary'|' term / unary '|' unary
unary --> !unary '|' -unary '|' factor
factor --> (bool) '|' loc '|' num '|' real '|' true '|' false
定义了一堆。。。其实这个语言像这样 (来自书上的列子：
{
int i; int j; float v; float x; float\[100\] a;
while(true) {
do i = i+1; while(a\[i\] < v);
do j = j-1; while(a\[j\] > v);
if(i >= j) break;
x = a\[i\]; a\[i\] = a\[j\];
a\[j\] = x;
}
}
一个完整的编译器包括： 词法分析器–语法分析–语义分析–中间代码生成–代码优化–目标代码生成 六个大阶段。 其中前四个阶段称为编译器的前端。 我们实现的就是编译器的前端。生成中间代码是三地址码。 细节阅读代码。 我大概写一下框架结构 词法分析： 词法分析读入字符流，处理输出词法单元。 在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用于抛出错误异常。
void move()throws IOException{
look = lex.scan();
}
void error(String s) {
throw new Error("near line "+ lex.line + ": " + s);
}
void match(int t) throws IOException{
if(look.tag == t) {
move();
}else
error("syntax error");
}
语法树构建根据文法定义递归执行并判断产生结点即可， 看一小段代码意思意思： (完整代码在后面
// program -> block 一个程序有块组成
public void program() throws IOException{
Stmt s = block();
//这一块是中间代码生成部分。。。。先不管
//int begin = s.newlabel();
//int after = s.newlabel();
//s.emitlabel(begin);
//s.gen(begin, after);
//s.emitlabel(after);
}
// block -> {decls stmts} 一个块有{ 开始，中间包含 decls声明序列和 stmts语句序列 由 } 结束.
Stmt block() throws IOException{
match('{');
Env saveEnv = top;
top = new Env(top);
decls();
Stmt s = stmts();
match('}');
top = saveEnv;
return s;
}
// decls -> decls decl '|' null; 声明序列包含许多decl声明
void decls()throws IOException{
while(look.tag == Tag.BASIC){ //只要当前读入字符是BASIC数据类型代表这是一个声明
Type p = type(); //判断类型
Token tok = look;
match(Tag.ID); //下一个词法单元是否是ID属性
match(';'); //下个此法单元是;
Id id = new Id((Word)tok,p,used); //验证正比这是一个声明，将
top.put(tok, id);
used = used + p.width;
}
}
// decl -> type id
Type type()throws IOException{
Type p = (Type)look;
match(Tag.BASIC); //基本数据类型
if(look.tag != '\[')//下一个不是 \[
return p;
else
return dims(p); //否则判断是否数组类型。。。
}
| 举个简单的 bool表达式的翻译成语法树的例子: a > b ‘ | ’’ | ’ a > 0 . 递归到最后匹配到标识符a，回溯到 > 符号匹配，再递归匹配b .. 回溯到> 的上层匹配 ‘ | ’’ | ‘ ….继续操作。。就建出了下面的树 :-( ，中间有什么与文法定义不符，都会抛出异常. ……..’ | ’’ | ’ ……./ \ ….> > …/ \ / \ .a b a 0 中间代码生成： 中间代码是三地址码。上面的示例源语言生成的三地址中间代码： |
L1:L3: i = i + 1
L5: t1 = i * 8
t2 = a \[ t1 \]
if t2 < v goto L3
L4: j = j - 1
L7: t3 = j * 8
t4 = a \[ t3 \]
if t4 > v goto L4
L6: iffalse i >= j got L8
L9: goto L2
L8: t5 = i * 8
x = a \[ t5 \]
L10: t6 = i * 8
t7 = j * 8
t8 = a \[ t7 \]
a \[ t6 \] = t8
L11: t9 = j * 8
a \[ t9 \] = x
goto L1
L2:
(我觉得复杂的就在这个中间代码生成部分….好好读代码吧。。。) 抽象语法 树中所有类型的结点都有一个基类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类的定义
public class If extends Stmt{
Expr expr;
Stmt stmt;
// if 语句的格式是 if( expr ) stmt 因此定义了这两个成员变量
public If(Expr x, Stmt s) {
expr = x;
stmt = s;
//如果表达式的类型不是bool抛出异常
if(expr.type != Type.Bool)
expr.error("boolean required in if");
}
public void gen(int b, int a) { //参数b，a 分别代表这个语句的开始位置与结束位置 的标号
int label = newlabel(); // 生成一个label
expr.jumping(0, a); //调用expr的jumping if false 产生 goto a 到if语句的结尾
emitlabel(label); //打印标号label
stmt.gen(label,a); //stmt语句代码生成，开始标号为label 结束标号为a
}
}
好好看看gen的代码和jumping吧。。。 我知道 我说不清楚了。。。。。。。坑就开到这里。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。再见 代码： https://github.com/ctguggbond/CompilerFront