从零写一个编译器（一）：输入系统和词法分析 - 好文

项目的完整代码在 C2j-Compiler <https://github.com/dejavudwh/C2j-Compiler>

前言

从半抄半改的完成一个把C语言编译到Java字节码到现在也有些时间，一直想写一个系列来回顾整理一下写一个编译器的过程，也算是学习笔记吧。就从今天开始动笔吧。

一开始会先写一个C语言的解释器，直接遍历AST直接执行，再之后会加入生成代码部分，也就是编译成Java字节码

支持C语言的大部分使用，具体可以到上面的链接去看，当然依旧是比玩具级还玩具级的编译器。

正式开始

完成一个编译器大抵上主要有这几部分

* 词法分析
一般用有限状态自动机或者手工编写来实现，这一步输出的是token序列

* 语法分析
主要分为自顶向下和自底向上的语法分析，一般有递归下降，LL(1),LR(1),LALR(1)几种方法实现。这一步输出的是语法树

* 语义分析
语义分析主要任务是生成符号表，并且发现不符合语义的语句，这一步输出的还是AST

* 代码生成
这里一般会生成一个与平台无关的较为贴近底层的中间语言（IR），这一步输入AST，输出的是IR

* 代码优化
这一步的工作和名字一样，就是进行代码的优化，提升性能等等

* 目标代码生成
这一步的任务就是生成平台相关的汇编语言了

以上差不多就是整个通用意义上来说的编译器了，但是也可以把包括调用链接器汇编器来生成可执行文件

水平时间有限C2j-Compiler里对于后三步是直接遍历AST生成目标Java字节码的，没有任何优化。词法分析使用手工编写，语法分析使用LALR(1)语法分析表

输入系统

对于一个有千行计的源文件，构建一个输入系统来提高输入的效率是很有必要的。

输入系统主要有三个文件

* FileHandler.java
* DiskFileHandler.java
* Input.java
FileHadnler

作为一个输入的接口，DiskFileHandler实现这个接口来实现从文件读入。主要有三个方法
void open(); int close(); int read(byte[] buf, int begin, int end);
其中read就是把指定数据长度复制到指定的缓冲区里并且指定了缓冲区的开始位置

完整的源代码都在我的仓库里 dejavudwh <https://github.com/dejavudwh>

Input

Input是整个输入系统实现的关键点，其中利用了一个缓冲区来提高输入的效率，也就是先把一部分的文件内容放入缓冲区，当输入指针即将越过危险区域时，就重新的对缓冲区进行输入，这样就可以整块整块的来读入文件内容，来避免多次的IO。

inputAdvance是向前一个位置获取输入，在获取输入前，会先检查是不是需要flush缓冲区
public byte inputAdvance() { char enter = '\n'; if (isReadEnd()) { return 0; }
if (!readEof && flush(false) < 0) { //缓冲区出错 return -1; } if (inputBuf[next] ==
enter) { curCharLineno++; } endCurCharPos++; return inputBuf[next++]; }
flush的主要逻辑就是判断next指针是不是越过了危险位置，或者force为true也就是要求强制flush，就调用fillbuf来填满缓冲区
private int flush(boolean force) { int noMoreCharToRead = 0; int flushOk = 1;
int shiftPart, copyPart, leftEdge; if (isReadEnd()) { return noMoreCharToRead;
} if (readEof) { return flushOk; } if (next > DANGER || force) { leftEdge =
next; copyPart = bufferEndFlag - leftEdge; System.arraycopy(inputBuf, leftEdge,
inputBuf, 0, copyPart); if (fillBuf(copyPart) == 0) {
System.err.println("Internal Error, flush: Buffer full, can't read"); }
startCurCharPos -= leftEdge; endCurCharPos -= leftEdge; next -= leftEdge; }
return flushOk; } private int fillBuf(int startPos) { int need; int got; need =
END - startPos; if (need < 0) { System.err.println("Internal Error (fill buf):
Bad read-request starting addr."); } if (need == 0) { return 0; } if ((got =
fileHandler.read(inputBuf, startPos, need)) == -1) { System.err.println("Can't
read input file"); } bufferEndFlag = startPos + got; if (got < need) {
//输入流已经到末尾 readEof = true; } return got; }
词法分析

词法分析的工作在于把源文件的输入流分割成一个一个token，Lexer的输出可能就类似<if, keyword>。识别出标识符，数字，关键字就在这一部分。

Lexer里一共有两个文件：

* Token.java
* Lexer.java
Token

Token主要就是用来标识每个Token，在Lexer里用到主要是像NAME来表示标识符，NUMBER来表示数字，STRUCT来表示struct关键字。
//terminals NAME, TYPE, STRUCT, CLASS, LP, RP, LB, RB, PLUS, LC, RC, NUMBER,
STRING, QUEST, COLON, RELOP, ANDAND, OR, AND, EQUOP, SHIFTOP, DIVOP, XOR,
MINUS, INCOP, DECOP, STRUCTOP, RETURN, IF, ELSE, SWITCH, CASE, DEFAULT, BREAK,
WHILE, FOR, DO, CONTINUE, GOTO,
Lexer

而Lexer就是利用之前的Input读入输入流，来输出Token流
public void advance() { lookAhead = lex(); }
Lexer的主要逻辑就是在lex()，每次利用inputAdvance从输入流读出，直到遇见空白符或者换行符就代表了至少一个Token的结束，
（这里如果遇见双引号也就是字符串里的空格不能当作空白符处理），之后就开始进行分析。

代码太长只截出来一部分，逻辑都很简单，另外一开始写的时候就没有处理注释，后来也就没有加上去
for (int i = 0; i < current.length(); i++) { length = 0; text =
current.substring(i, i + 1); switch (current.charAt(i)) { case ';': current =
current.substring(1); return Token.SEMI.ordinal(); case '+': if (i + 1 <
current.length() && current.charAt(i + 1) == '+') { current =
current.substring(2); return Token.INCOP.ordinal(); } current =
current.substring(1); return Token.PLUS.ordinal(); case '-': if (i + 1 <
current.length() && current.charAt(i + 1) == '>') { current =
current.substring(2); return Token.STRUCTOP.ordinal(); } else if (i + 1 <
current.length() && current.charAt(i + 1) == '-') { current =
current.substring(2); return Token.DECOP.ordinal(); } current =
current.substring(1); return Token.MINUS.ordinal(); ... ... }
到这里输入系统和词法分析就结束了。

词法分析阶段的工作就是将输入的字符流转换为特定的Token。这一步是识别组合字符的过程，主要是标识数字，标识符，关键字等过程。这一部分应该是整个编译器中最简单的部分

另外我的github博客：https://dejavudwh.cn/ <https://dejavudwh.cn/>

热门工具换一换