?2016-2026 Matools All rights reserved,
粵ICP備17059708號
項(xiàng)目的完整代碼在 C2j-Compiler <https://github.com/dejavudwh/C2j-Compiler>
前言
這一篇不看也不會影響后面代碼生成部分
現(xiàn)在經(jīng)過詞法分析語法分析語義分析，終于可以進(jìn)入最核心的部分了。前面那部分可以稱作編譯器的前端，代碼生成代碼優(yōu)化都是屬于編譯器后端，如今有關(guān)編譯器的工作崗位主要都是對后端的研究。當(dāng)然現(xiàn)在寫的這個編譯器因?yàn)樗接邢蓿]有優(yōu)化部分。
在進(jìn)行代碼生成部分之前，我們先來根據(jù)AST來直接解釋執(zhí)行，其實(shí)就是對AST的遍歷?，F(xiàn)代解釋器一般都是生成一個比較低級的指令然后跑在虛擬機(jī)上，但是簡單起見我們就直接根據(jù)AST解釋執(zhí)行的解釋器。（原本這部分是不想寫的，是可以直接寫代碼生成的）
這次的文件在interpreter包里，這次涉及到的文件比較多，就不列舉了
一個小問題
在開始說解釋器的部分前我們看一下，認(rèn)真觀察之前在構(gòu)造符號表對賦初值的推導(dǎo)式的處理是有問題的，但是問題不大，只要稍微改動一下
在github源代碼的部分已經(jīng)改了，改動如下：
case SyntaxProductionInit.VarDecl_Equal_Initializer_TO_Decl:
attributeForParentNode = (Symbol) valueStack.get(valueStack.size() - 3);
((Symbol) attributeForParentNode).value = initialValue; break; case
SyntaxProductionInit.Expr_TO_Initializer: initialValue = (Integer)
valueStack.get(valueStack.size() - 1); System.out.println(initialValue); break;
其實(shí)就是一個拿到賦的初值放到Symbol的value里
示例
先看一下這篇完成之后解釋執(zhí)行的效果
void swap(int arr[10], int i, int j) { int temp; temp = arr[i]; arr[i] =
arr[j]; arr[j] = temp; } void quickSort(int a[10], int p, int r) { int x; int
i; i = p - 1; int j; int t; int v; v = r - 1; if (p < r) { x = a[r]; for (j =
p; j <= v; j++) { if (a[j] <= x) { i++; swap(a, i, j); } } v = i + 1; swap(a,
v, r); t = v - 1; quickSort(a, p, t); t = v + 1; quickSort(a, t, r); } } void
main () { int a[10]; int i; int t; printf("Array before quicksort:"); for(i =
0; i < 10; i++) { t = (10 - i); a[i] = t; printf("value of a[%d] is %d", i,
a[i]); } quickSort(a, 0, 9); printf("Array after quicksort:"); for (i = 0; i <
10; i++) { printf("value of a[%d] is %d", i, a[i]); } }
Executor接口
所有能夠執(zhí)行結(jié)點(diǎn)的類都要實(shí)現(xiàn)這個接口，所以以此來達(dá)到遍歷AST來執(zhí)行代碼
解釋器的啟動在Interpreter類里，它也實(shí)現(xiàn)了Executor接口
Interpreter類的execute傳入的參數(shù)就是整棵抽象語法樹的頭節(jié)點(diǎn)了，ExecutorFactory的getExecutor則是根據(jù)當(dāng)前結(jié)點(diǎn)的TokenType返回一個可以解釋當(dāng)前節(jié)點(diǎn)的類，而其它執(zhí)行節(jié)點(diǎn)的類都繼承了BaseExecutor
@Override public Object execute(AstNode root) { if (root == null) { return
null; } ExecutorFactory factory = ExecutorFactory.getInstance(); Executor
executor = factory.getExecutor(root); executor.execute(root); return root; }
BaseExecutor的兩個主要方法就是執(zhí)行它的子節(jié)點(diǎn)，并且可以指定執(zhí)行哪個子節(jié)點(diǎn)?？梢韵群雎訠rocaster，這些是用來實(shí)現(xiàn)執(zhí)行節(jié)點(diǎn)類之前的通訊的，現(xiàn)在還沒有用。reverseChildren是用來對節(jié)點(diǎn)的反轉(zhuǎn)，因?yàn)樵趧?chuàng)建的AST的過程由于堆棧的原因，所以節(jié)點(diǎn)順序的相反的。continueExecute是標(biāo)志位，后面可能會執(zhí)行到設(shè)置它的節(jié)點(diǎn)來結(jié)束運(yùn)行
protected void executeChildren(AstNode root) { ExecutorFactory factory =
ExecutorFactory.getInstance(); root.reverseChildren(); int i = 0; while (i <
root.getChildren().size()) { if (!continueExecute) { break; } AstNode child =
root.getChildren().get(i); executorBrocaster.brocastBeforeExecution(child);
Executor executor = factory.getExecutor(child); if (executor != null) {
executor.execute(child); } else { System.err.println("Not suitable Generate
found, node is: " + child.toString()); }
executorBrocaster.brocastAfterExecution(child); i++; } } protected AstNode
executeChild(AstNode root, int childIdx) { root.reverseChildren(); AstNode
child; ExecutorFactory factory = ExecutorFactory.getInstance(); child =
(AstNode)root.getChildren().get(childIdx); Executor executor =
factory.getExecutor(child); AstNode res = (AstNode)executor.execute(child);
return res; }
解釋執(zhí)行
我們可以知道一個C語言的源文件一般都是一些函數(shù)定義和一個main的函數(shù)來啟動，所以在AstBuilder里返回給Interpreter的節(jié)點(diǎn)就是從main開始的
public AstNode getSyntaxTreeRoot() { AstNode mainNode = funcMap.get("main");
return mainNode; }
執(zhí)行函數(shù)ExtDefExecutor
用來執(zhí)行函數(shù)的Executor是ExtDefExecutor
* 在進(jìn)入execute會先執(zhí)行FunctDecl節(jié)點(diǎn)，再執(zhí)行CompoundStmt節(jié)點(diǎn)
* saveArgs和restoreArgs屬于保護(hù)當(dāng)前的環(huán)境，就是進(jìn)入其它作用域的時(shí)候保證這個符號不變修改，不比如當(dāng)作參數(shù)傳遞的時(shí)候
* returnVal也是屬于由其它節(jié)點(diǎn)設(shè)置的屬性
* root.setAttribute的作用就是對節(jié)點(diǎn)設(shè)置屬性，把值往上傳遞 @Override public Object
execute(AstNode root) { this.root = root; int production = (Integer)
root.getAttribute(NodeKey.PRODUCTION); switch (production) { case
SyntaxProductionInit.OptSpecifiers_FunctDecl_CompoundStmt_TO_ExtDef: AstNode
child = root.getChildren().get(0); funcName = (String)
child.getAttribute(NodeKey.TEXT); root.setAttribute(NodeKey.TEXT, funcName);
saveArgs(); executeChild(root, 0); executeChild(root, 1); Object returnVal =
getReturnObj(); clearReturnObj(); if (returnVal != null) {
root.setAttribute(NodeKey.VALUE, returnVal); } isContinueExecution(true);
restoreArgs(); break; default: break; } return root; }
函數(shù)定義 FunctDeclExecutor
執(zhí)行函數(shù)會先執(zhí)行它的括號的前部分也就是標(biāo)識符和參數(shù)那部分，對參數(shù)進(jìn)行初始化，函數(shù)的傳遞的參數(shù)用單獨(dú)一個類FunctionArgumentList來表示
@Override public Object execute(AstNode root) { int production = (Integer)
root.getAttribute(NodeKey.PRODUCTION); Symbol symbol; currentNode = root;
switch (production) { case SyntaxProductionInit.NewName_LP_RP_TO_FunctDecl:
root.reverseChildren(); copyChild(root, root.getChildren().get(0)); break; case
SyntaxProductionInit.NewName_LP_VarList_RP_TO_FunctDecl: symbol = (Symbol)
root.getAttribute(NodeKey.SYMBOL); Symbol args = symbol.getArgList();
initArgumentList(args); if (args == null || argsList == null ||
argsList.isEmpty()) { System.err.println("generate function with arg list but
arg list is null"); System.exit(1); } break; default: break; } return root; }
執(zhí)行語句部分 CompoundStmtExecutor
執(zhí)行語句的部分就開始對樹的遍歷執(zhí)行，但是我們來看一下這個節(jié)點(diǎn)的推導(dǎo)式
COMPOUND_STMT-> LC LOCAL_DEFS STMT_LIST RC
在構(gòu)建AST的時(shí)候我們并沒有構(gòu)建LOCAL_DEFS，并且在之前符號表也沒有進(jìn)行處理，所以我們直接執(zhí)行第0個節(jié)點(diǎn)就可以了
@Override public Object execute(AstNode root) { return executeChild(root, 0); }
一元操作
下面看UnaryNodeExecutor，UnaryNodeExecutor應(yīng)該是所有Executor最復(fù)雜的之一了，其實(shí)對于節(jié)點(diǎn)執(zhí)行，先執(zhí)行子節(jié)點(diǎn)，并且向上傳遞執(zhí)行結(jié)果的值。
只說其中的幾個
*
指針
這個就是對指針的操作了，本質(zhì)是對內(nèi)存分配的一個模擬，再設(shè)置實(shí)現(xiàn)ValueSetter的DirectMemValueSetter，讓它的父節(jié)點(diǎn)可以通過這個節(jié)點(diǎn)的setter對指針指向進(jìn)行賦值
ValueSetter是一個可以對變量進(jìn)行賦值的接口，數(shù)組、指針、簡單的變量都有各自的valueSetter
case SyntaxProductionInit.Start_Unary_TO_Unary: child =
root.getChildren().get(0); int addr = (Integer)
child.getAttribute(NodeKey.VALUE); symbol = (Symbol)
child.getAttribute(NodeKey.SYMBOL); MemoryHeap memHeap =
MemoryHeap.getInstance(); Map.Entry<Integer, byte[]> entry =
memHeap.getMem(addr); int offset = addr - entry.getKey(); if (entry != null) {
byte[] memByte = entry.getValue(); root.setAttribute(NodeKey.VALUE,
memByte[offset]); } DirectMemValueSetter directMemSetter = new
DirectMemValueSetter(addr); root.setAttribute(NodeKey.SYMBOL, directMemSetter);
break;
*
指針和數(shù)組操作：
這是執(zhí)行數(shù)組或者是指針的操作，對于數(shù)組和指針的操作會在節(jié)點(diǎn)中的Symbol里設(shè)置一個可以進(jìn)行賦值的接口：ArrayValueSetter、PointerValueSetter，邏輯都不是很復(fù)雜。對于指針的操作其實(shí)是對于內(nèi)存地址分配的一個模擬。
case SyntaxProductionInit.Unary_LB_Expr_RB_TO_Unary: child =
root.getChildren().get(0); symbol = (Symbol)
child.getAttribute(NodeKey.SYMBOL); child = root.getChildren().get(1); int
index = (Integer) child.getAttribute(NodeKey.VALUE); try { Declarator
declarator = symbol.getDeclarator(Declarator.ARRAY); if (declarator != null) {
Object val = declarator.getElement(index); root.setAttribute(NodeKey.VALUE,
val); ArrayValueSetter setter = new ArrayValueSetter(symbol, index);
root.setAttribute(NodeKey.SYMBOL, setter); root.setAttribute(NodeKey.TEXT,
symbol.getName()); } Declarator pointer =
symbol.getDeclarator(Declarator.POINTER); if (pointer != null) {
setPointerValue(root, symbol, index); PointerValueSetter pv = new
PointerValueSetter(symbol, index); root.setAttribute(NodeKey.SYMBOL, pv);
root.setAttribute(NodeKey.TEXT, symbol.getName()); } } catch (Exception e) {
System.err.println(e.getMessage()); e.printStackTrace(); System.exit(1); }
break;
*
函數(shù)調(diào)用
函數(shù)調(diào)用也是屬于一元操作，對于函數(shù)調(diào)用有兩種情況：一種是自定義的函數(shù)，還有一種是解釋器提供的函數(shù)
* 如果是自定義函數(shù)，就找到這個函數(shù)的頭節(jié)點(diǎn)，從這個頭節(jié)點(diǎn)開始執(zhí)行
* 如果是解釋器提供的函數(shù)，就交由ClibCall處理，比如printf就是屬于庫函數(shù) case
SyntaxProductionInit.Unary_LP_RP_TO_Unary: case
SyntaxProductionInit.Unary_LP_ARGS_RP_TO_Unary: String funcName = (String)
root.getChildren().get(0).getAttribute(NodeKey.TEXT); if (production ==
SyntaxProductionInit.Unary_LP_ARGS_RP_TO_Unary) { AstNode argsNode =
root.getChildren().get(1); ArrayList<Object> argList = (ArrayList<Object>)
argsNode.getAttribute(NodeKey.VALUE); ArrayList<Object> symList =
(ArrayList<Object>) argsNode.getAttribute(NodeKey.SYMBOL);
FunctionArgumentList.getInstance().setFuncArgList(argList);
FunctionArgumentList.getInstance().setFuncArgSymbolList(symList); } AstNode
func = AstBuilder.getInstance().getFunctionNodeByName(funcName); if (func !=
null) { Executor executor = ExecutorFactory.getInstance().getExecutor(func);
executor.execute(func); Object returnVal = func.getAttribute(NodeKey.VALUE); if
(returnVal != null) { ConsoleDebugColor.outlnPurple("function call with name "
+ funcName + " has return value that is " + returnVal.toString());
root.setAttribute(NodeKey.VALUE, returnVal); } } else { ClibCall libCall =
ClibCall.getInstance(); if (libCall.isApiCall(funcName)) { Object obj =
libCall.invokeApi(funcName); root.setAttribute(NodeKey.VALUE, obj); } } break;
邏輯語句處理
邏輯語句處理無非就是根據(jù)節(jié)點(diǎn)值判斷該執(zhí)行哪些節(jié)點(diǎn)
*
FOR、WHILE語句
代碼邏輯和語句的邏輯是一樣，比如對于
for(i = 0; i < 5; i++){}
就會先執(zhí)行i = 0部分，在執(zhí)行{}和i++部分，然后再判斷條件是否符合
case SyntaxProductionInit.FOR_OptExpr_Test_EndOptExpr_Statement_TO_Statement:
executeChild(root, 0); while (isLoopContinute(root, LoopType.FOR)) { //execute
statement in for body executeChild(root, 3); //execute EndOptExpr
executeChild(root, 2); } break; case
SyntaxProductionInit.While_LP_Test_Rp_TO_Statement: while
(isLoopContinute(root, LoopType.WHILE)) { executeChild(root, 1); } break;
*
IF語句
if語句就是先執(zhí)行判斷部分，再根據(jù)判斷的結(jié)果來決定是否執(zhí)行{}塊
@Override public Object execute(AstNode root) { AstNode res =
executeChild(root, 0); Integer val = (Integer)res.getAttribute(NodeKey.VALUE);
copyChild(root, res); if (val != null && val != 0) { executeChild(root, 1); }
return root; }
小結(jié)
這一篇寫的很亂，一是解釋器部分還是蠻大的，想在一篇之內(nèi)寫完比較難。所以省略了很多東西。但其實(shí)對于解釋器實(shí)現(xiàn)部分對于AST的遍歷才比較涉及編譯原理部分，其它的主要是邏輯實(shí)現(xiàn)
對于解釋器部分，因?yàn)闆]有采用虛擬機(jī)那樣的實(shí)現(xiàn)，而是直接對AST的遍歷。所以對AST的遍歷是關(guān)鍵，主要在于遍歷到該執(zhí)行的子節(jié)點(diǎn)部分，然后處理邏輯，再把信息通過子節(jié)點(diǎn)傳遞到父節(jié)點(diǎn)部分。
熱門工具 換一換