從零寫一個編譯器（一）：輸入系統(tǒng)和詞法分析

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

前言

從半抄半改的完成一個把C語言編譯到Java字節(jié)碼到現(xiàn)在也有些時間，一直想寫一個系列來回顧整理一下寫一個編譯器的過程，也算是學(xué)習(xí)筆記吧。就從今天開始動筆吧。

一開始會先寫一個C語言的解釋器，直接遍歷AST直接執(zhí)行，再之后會加入生成代碼部分，也就是編譯成Java字節(jié)碼

支持C語言的大部分使用，具體可以到上面的鏈接去看，當(dāng)然依舊是比玩具級還玩具級的編譯器。

正式開始

完成一個編譯器大抵上主要有這幾部分

* 詞法分析
一般用有限狀態(tài)自動機(jī)或者手工編寫來實現(xiàn)，這一步輸出的是token序列

* 語法分析
主要分為自頂向下和自底向上的語法分析，一般有遞歸下降，LL(1),LR(1),LALR(1)幾種方法實現(xiàn)。這一步輸出的是語法樹

* 語義分析
語義分析主要任務(wù)是生成符號表，并且發(fā)現(xiàn)不符合語義的語句，這一步輸出的還是AST

* 代碼生成
這里一般會生成一個與平臺無關(guān)的較為貼近底層的中間語言（IR），這一步輸入AST，輸出的是IR

* 代碼優(yōu)化
這一步的工作和名字一樣，就是進(jìn)行代碼的優(yōu)化，提升性能等等

* 目標(biāo)代碼生成
這一步的任務(wù)就是生成平臺相關(guān)的匯編語言了

以上差不多就是整個通用意義上來說的編譯器了，但是也可以把包括調(diào)用鏈接器匯編器來生成可執(zhí)行文件


水平時間有限C2j-Compiler里對于后三步是直接遍歷AST生成目標(biāo)Java字節(jié)碼的，沒有任何優(yōu)化。詞法分析使用手工編寫，語法分析使用LALR(1)語法分析表

輸入系統(tǒng)

對于一個有千行計的源文件，構(gòu)建一個輸入系統(tǒng)來提高輸入的效率是很有必要的。

輸入系統(tǒng)主要有三個文件

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

作為一個輸入的接口，DiskFileHandler實現(xiàn)這個接口來實現(xiàn)從文件讀入。主要有三個方法
void open(); int close(); int read(byte[] buf, int begin, int end);
其中read就是把指定數(shù)據(jù)長度復(fù)制到指定的緩沖區(qū)里并且指定了緩沖區(qū)的開始位置

完整的源代碼都在我的倉庫里 dejavudwh <https://github.com/dejavudwh>

Input


Input是整個輸入系統(tǒng)實現(xiàn)的關(guān)鍵點(diǎn)，其中利用了一個緩沖區(qū)來提高輸入的效率，也就是先把一部分的文件內(nèi)容放入緩沖區(qū)，當(dāng)輸入指針即將越過危險區(qū)域時，就重新的對緩沖區(qū)進(jìn)行輸入，這樣就可以整塊整塊的來讀入文件內(nèi)容，來避免多次的IO。

inputAdvance是向前一個位置獲取輸入，在獲取輸入前，會先檢查是不是需要flush緩沖區(qū)
public byte inputAdvance() { char enter = '\n'; if (isReadEnd()) { return 0; }
if (!readEof && flush(false) < 0) { //緩沖區(qū)出錯 return -1; } if (inputBuf[next] ==
enter) { curCharLineno++; } endCurCharPos++; return inputBuf[next++]; }
flush的主要邏輯就是判斷next指針是不是越過了危險位置，或者force為true也就是要求強(qiáng)制flush，就調(diào)用fillbuf來填滿緩沖區(qū)
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) {
//輸入流已經(jīng)到末尾 readEof = true; } return got; }
詞法分析

詞法分析的工作在于把源文件的輸入流分割成一個一個token，Lexer的輸出可能就類似<if, keyword>。識別出標(biāo)識符，數(shù)字，關(guān)鍵字就在這一部分。

Lexer里一共有兩個文件：

* Token.java
* Lexer.java
Token

Token主要就是用來標(biāo)識每個Token，在Lexer里用到主要是像NAME來表示標(biāo)識符，NUMBER來表示數(shù)字，STRUCT來表示struct關(guān)鍵字。
//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的結(jié)束，
（這里如果遇見雙引號也就是字符串里的空格不能當(dāng)作空白符處理），之后就開始進(jìn)行分析。

代碼太長只截出來一部分，邏輯都很簡單，另外一開始寫的時候就沒有處理注釋，后來也就沒有加上去
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(); ... ... }
到這里輸入系統(tǒng)和詞法分析就結(jié)束了。


詞法分析階段的工作就是將輸入的字符流轉(zhuǎn)換為特定的Token。這一步是識別組合字符的過程，主要是標(biāo)識數(shù)字，標(biāo)識符，關(guān)鍵字等過程。這一部分應(yīng)該是整個編譯器中最簡單的部分

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

• ? 上一篇：從零寫一個編譯器（八）：語義分析之構(gòu)造符號表
• ? 下一篇：Linux殺不死的進(jìn)程之CPU使用率700%