從零寫一個(gè)編譯器（十三）：代碼生成之遍歷AST

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

前言


在上一篇完成對(duì)JVM指令的生成，下面就可以真正進(jìn)入代碼生成部分了。通?，F(xiàn)代編譯器都是先把生成IR，再經(jīng)過(guò)代碼優(yōu)化等等，最后才編譯成目標(biāo)平臺(tái)代碼。但是時(shí)間水平有限，我們沒(méi)有IR也沒(méi)有代碼優(yōu)化，就直接利用AST生成Java字節(jié)碼

入口

進(jìn)行代碼生成的入口在CodeGen，和之前解釋器一樣：先獲取main函數(shù)的頭節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)開(kāi)始，先進(jìn)入函數(shù)定義，再進(jìn)入代碼塊

函數(shù)定義節(jié)點(diǎn)

在進(jìn)入函數(shù)定義節(jié)點(diǎn)的時(shí)候，就要生成一個(gè)函數(shù)定義對(duì)應(yīng)的Java字節(jié)碼，即一個(gè)靜態(tài)方法（因?yàn)槲覀儗?duì)整個(gè)C語(yǔ)言文件生成為一個(gè)類，main方法為public
static main，其它的則是對(duì)應(yīng)的靜態(tài)方法，結(jié)構(gòu)體則是另外的類）

* 對(duì)于函數(shù)定義先從節(jié)點(diǎn)中拿到對(duì)應(yīng)的函數(shù)命和參數(shù)
* emitArgs是用來(lái)處理參數(shù)的，根據(jù)參數(shù)生成相應(yīng)的Java字節(jié)碼
* 如果這個(gè)函數(shù)是main的話已經(jīng)是交由前面處理了，邏輯差不多（具體在start.Start中） case
SyntaxProductionInit.NewName_LP_RP_TO_FunctDecl: root.reverseChildren();
AstNode n = root.getChildren().get(0); String name = (String)
n.getAttribute(NodeKey.TEXT); symbol = (Symbol)
root.getAttribute(NodeKey.SYMBOL); generator.setCurrentFuncName(name); if (name
!= null && !name.equals("main")) { String declaration = name +
emitArgs(symbol); generator.emitDirective(Directive.METHOD_PUBBLIC_STATIC,
declaration); generator.setNameAndDeclaration(name, declaration); }
copyChild(root, root.getChildren().get(0)); break; case
SyntaxProductionInit.NewName_LP_VarList_RP_TO_FunctDecl: n =
root.getChildren().get(0); name = (String) n.getAttribute(NodeKey.TEXT); symbol
= (Symbol) root.getAttribute(NodeKey.SYMBOL);
generator.setCurrentFuncName(name); if (name != null && !name.equals("main")) {
String declaration = name + emitArgs(symbol);
generator.emitDirective(Directive.METHOD_PUBBLIC_STATIC, declaration);
generator.setNameAndDeclaration(name, declaration); } Symbol args =
symbol.getArgList(); if (args == null || argsList == null ||
argsList.isEmpty()) { System.err.println("generate function with arg list but
arg list is null"); System.exit(1); } break;
創(chuàng)建結(jié)構(gòu)體和數(shù)組

數(shù)組


創(chuàng)建結(jié)構(gòu)體和數(shù)組的節(jié)點(diǎn)在DefGenerate里，可以看到在這里只處理了數(shù)組和普通變量，有關(guān)結(jié)構(gòu)體的處理是在對(duì)結(jié)構(gòu)體第一次使用的時(shí)候。順便提一下代碼生成對(duì)于賦初值操作是沒(méi)有進(jìn)行處理的。

* 如果是個(gè)數(shù)組，酒直接調(diào)用ProgramGenerator直接生成創(chuàng)建數(shù)組的指令
*
如果是個(gè)普通變量，就直接找到它并且賦值為0（這里變量在隊(duì)列里的位置是根據(jù)符號(hào)表來(lái)計(jì)算的，具體可以看上一篇的getLocalVariableIndex方法）
public class DefGenerate extends BaseGenerate { @Override public Object
generate(AstNode root) { int production = (int)
root.getAttribute(NodeKey.PRODUCTION); ProgramGenerator generator =
ProgramGenerator.getInstance(); Symbol symbol = (Symbol)
root.getAttribute(NodeKey.SYMBOL); switch (production) { case
SyntaxProductionInit.Specifiers_DeclList_Semi_TO_Def: Declarator declarator =
symbol.getDeclarator(Declarator.ARRAY); if (declarator != null) { if
(symbol.getSpecifierByType(Specifier.STRUCTURE) == null) {
generator.createArray(symbol); } } else { int i =
generator.getLocalVariableIndex(symbol); generator.emit(Instruction.SIPUSH, ""
+ 0); generator.emit(Instruction.ISTORE, "" + i); } break; default: break; }
return root; } }
結(jié)構(gòu)體

處理結(jié)構(gòu)體定義的代碼在UnaryNodeGenerate，也就是只有在使用到結(jié)構(gòu)體定義時(shí)才會(huì)進(jìn)行定義

* 先拿到當(dāng)前UNARY的符號(hào)，如果instanceof
ArrayValueSetter就說(shuō)明是一個(gè)結(jié)構(gòu)體數(shù)組，就進(jìn)入getStructSymbolFromStructArray方法創(chuàng)建一個(gè)結(jié)構(gòu)體數(shù)組，并返回當(dāng)前下標(biāo)的結(jié)構(gòu)體對(duì)象
* 設(shè)置當(dāng)前結(jié)構(gòu)體的作用域范圍
* 對(duì)結(jié)構(gòu)體作為類進(jìn)行定義
* 然后對(duì)讀取結(jié)構(gòu)體的域
* 其實(shí)可以忽略指針部分，因?yàn)榇a生成并沒(méi)有對(duì)指針進(jìn)行模擬 case
SyntaxProductionInit.Unary_StructOP_Name_TO_Unary: child =
root.getChildren().get(0); String fieldName = (String)
root.getAttribute(NodeKey.TEXT); Object object =
child.getAttribute(NodeKey.SYMBOL); boolean isStructArray = false; if (object
instanceof ArrayValueSetter) { symbol = getStructSymbolFromStructArray(object);
symbol.addValueSetter(object); isStructArray = true; } else { symbol = (Symbol)
child.getAttribute(NodeKey.SYMBOL); } if (isStructArray) { ArrayValueSetter vs
= (ArrayValueSetter) object; Symbol structArray = vs.getSymbol();
structArray.addScope(ProgramGenerator.getInstance().getCurrentFuncName()); }
else { symbol.addScope(ProgramGenerator.getInstance().getCurrentFuncName()); }
ProgramGenerator.getInstance().putStructToClassDeclaration(symbol); if
(isSymbolStructPointer(symbol)) { copyBetweenStructAndMem(symbol, false); }
Symbol args = symbol.getArgList(); while (args != null) { if
(args.getName().equals(fieldName)) { args.setStructParent(symbol); break; }
args = args.getNextSymbol(); } if (args == null) { System.err.println("access a
filed not in struct object!"); System.exit(1); } if (args.getValue() != null) {
ProgramGenerator.getInstance().readValueFromStructMember(symbol, args); }
root.setAttribute(NodeKey.SYMBOL, args); root.setAttribute(NodeKey.VALUE,
args.getValue()); if (isSymbolStructPointer(symbol)) {
checkValidPointer(symbol); structObjSymbol = symbol; monitorSymbol = args;
GenerateBrocasterImpl.getInstance().registerReceiverForAfterExe(this); } else {
structObjSymbol = null; } break;
一元操作節(jié)點(diǎn)

這個(gè)節(jié)點(diǎn)和在解釋器的有很多相同，除了有對(duì)結(jié)構(gòu)體的操作，其它的也是有非常重要的作用

* 像數(shù)字、字符串或者是變量和之前的操作都是把信息傳遞到父節(jié)點(diǎn)，交由父節(jié)點(diǎn)處理 case
SyntaxProductionInit.Number_TO_Unary: text = (String)
root.getAttribute(NodeKey.TEXT); boolean isFloat = text.indexOf('.') != -1; if
(isFloat) { value = Float.valueOf(text); root.setAttribute(NodeKey.VALUE,
value); } else { value = Integer.valueOf(text);
root.setAttribute(NodeKey.VALUE, value); } break; case
SyntaxProductionInit.Name_TO_Unary: symbol = (Symbol)
root.getAttribute(NodeKey.SYMBOL); if (symbol != null) {
root.setAttribute(NodeKey.VALUE, symbol.getValue());
root.setAttribute(NodeKey.TEXT, symbol.getName()); } break; case
SyntaxProductionInit.String_TO_Unary: text = (String)
root.getAttribute(NodeKey.TEXT); root.setAttribute(NodeKey.VALUE, text); break;
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 = 0; if (child.getAttribute(NodeKey.VALUE) != null) { index = (Integer)
child.getAttribute(NodeKey.VALUE); } Object idxObj =
child.getAttribute(NodeKey.SYMBOL); try { Declarator declarator =
symbol.getDeclarator(Declarator.ARRAY); if (declarator != null) { Object val =
declarator.getElement((int) index); root.setAttribute(NodeKey.VALUE, val);
ArrayValueSetter setter; if (idxObj == null) { setter = new
ArrayValueSetter(symbol, index); } else { setter = new ArrayValueSetter(symbol,
idxObj); } 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) {
e.printStackTrace(); System.exit(1); } break;
賦值操作

* 如果當(dāng)前是一個(gè)數(shù)組，先拿到它的符號(hào)和下標(biāo)
* 如果不是結(jié)構(gòu)體數(shù)組，那么拿到下標(biāo)直接用readArrayElement生成讀取數(shù)組元素的指令
* 如果是一個(gè)符號(hào)則用getLocalVariableIndex讀取這個(gè)符號(hào)的值
* 如果是一個(gè)常數(shù)，則直接生成IPUSH指令
* 最后進(jìn)行賦值操作，如果不是對(duì)結(jié)構(gòu)體的域進(jìn)行賦值就直接用getLocalVariableIndex拿到隊(duì)列位置然后生成ISTORE
*
如果是對(duì)結(jié)構(gòu)體數(shù)組的元素的域的賦值，就調(diào)用assignValueToStructMemberFromArray生成代碼，如果只是結(jié)構(gòu)體就直接調(diào)用assignValueToStructMember生成代碼
ProgramGenerator generator = ProgramGenerator.getInstance(); if
(BaseGenerate.resultOnStack) { this.value = obj; BaseGenerate.resultOnStack =
false; } else if (obj instanceof ArrayValueSetter) { ArrayValueSetter setter =
(ArrayValueSetter) obj; Symbol symbol = setter.getSymbol(); Object index =
setter.getIndex(); if (symbol.getSpecifierByType(Specifier.STRUCTURE) == null)
{ if (index instanceof Symbol) {
ProgramGenerator.getInstance().readArrayElement(symbol, index); if (((Symbol)
index).getValue() != null) { int i = (int) ((Symbol) index).getValue(); try {
this.value = symbol.getDeclarator(Declarator.ARRAY).getElement(i); } catch
(Exception e) { e.printStackTrace(); } } } else { int i = (int) index; try {
this.value = symbol.getDeclarator(Declarator.ARRAY).getElement(i); } catch
(Exception e) { e.printStackTrace(); }
ProgramGenerator.getInstance().readArrayElement(symbol, index); } } } else if
(obj instanceof Symbol) { Symbol symbol = (Symbol) obj; this.value =
symbol.value; int i = generator.getLocalVariableIndex(symbol);
generator.emit(Instruction.ILOAD, "" + i); } else if (obj instanceof Integer) {
Integer val = (Integer) obj; generator.emit(Instruction.SIPUSH, "" + val);
this.value = obj; } if (!this.isStructMember()) { int idx =
generator.getLocalVariableIndex(this); if (!generator.isPassingArguments()) {
generator.emit(Instruction.ISTORE, "" + idx); } } else { if
(this.getStructSymbol().getValueSetter() != null) {
generator.assignValueToStructMemberFromArray(this.getStructSymbol().getValueSetter(),
this, this.value); } else {
generator.assignValueToStructMember(this.getStructSymbol(), this, this.value);
} }
最后

完成這部分后，對(duì)下面的代碼
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++; t = A[i]; A[i] = A[j]; A[j] = t; } } v = i + 1; t = A[v]; A[v] =
A[r]; A[r] = t; t = v - 1; quicksort(A, p, t); t = v + 1; quicksort(A, t, r); }
} void main () { int a[10]; int i; int t; printf("before quick sort:"); 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("after quick sort:"); for (i = 0; i < 10;
i++) { printf("value of a[%d] is %d", i, a[i]); } }
則會(huì)生成下面的Java字節(jié)碼
.class public C2Bytecode .super java/lang/Object .method public static
main([Ljava/lang/String;)V sipush 10 newarray int astore 0 sipush 0 istore 1
sipush 0 istore 2 getstatic java/lang/System/out Ljava/io/PrintStream; ldc
"before quick sort:" invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V getstatic java/lang/System/out
Ljava/io/PrintStream; ldc " " invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V sipush 0 istore 1 loop0: iload 1
sipush 10 if_icmpge branch0 sipush 10 iload 1 isub istore 2 aload 0 iload 1
iload 2 iastore aload 0 iload 1 iaload istore 3 iload 1 istore 4 getstatic
java/lang/System/out Ljava/io/PrintStream; ldc "value of a[" invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V getstatic java/lang/System/out
Ljava/io/PrintStream; iload 4 invokevirtual java/io/PrintStream/print(I)V
getstatic java/lang/System/out Ljava/io/PrintStream; ldc "] is " invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V getstatic java/lang/System/out
Ljava/io/PrintStream; iload 3 invokevirtual java/io/PrintStream/print(I)V
getstatic java/lang/System/out Ljava/io/PrintStream; ldc " " invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V iload 1 sipush 1 iadd istore 1
goto loop0 branch0: aload 0 sipush 0 sipush 9 invokestatic
C2Bytecode/quicksort([III)V getstatic java/lang/System/out
Ljava/io/PrintStream; ldc "after quick sort:" invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V getstatic java/lang/System/out
Ljava/io/PrintStream; ldc " " invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V sipush 0 istore 1 loop2: iload 1
sipush 10 if_icmpge branch4 aload 0 iload 1 iaload istore 3 iload 1 istore 4
getstatic java/lang/System/out Ljava/io/PrintStream; ldc "value of a["
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V getstatic
java/lang/System/out Ljava/io/PrintStream; iload 4 invokevirtual
java/io/PrintStream/print(I)V getstatic java/lang/System/out
Ljava/io/PrintStream; ldc "] is " invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V getstatic java/lang/System/out
Ljava/io/PrintStream; iload 3 invokevirtual java/io/PrintStream/print(I)V
getstatic java/lang/System/out Ljava/io/PrintStream; ldc " " invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V iload 1 sipush 1 iadd istore 1
goto loop2 branch4: return .end method .method public static quicksort([III)V
sipush 2 newarray int astore 6 sipush 0 istore 5 sipush 1 istore 5 aload 6
iload 5 sipush 1 iastore aload 6 sipush 1 iaload istore 10 getstatic
java/lang/System/out Ljava/io/PrintStream; ldc "before quick sort: "
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V getstatic
java/lang/System/out Ljava/io/PrintStream; iload 10 invokevirtual
java/io/PrintStream/print(I)V getstatic java/lang/System/out
Ljava/io/PrintStream; ldc " " invokevirtual
java/io/PrintStream/print(Ljava/lang/String;)V sipush 0 istore 9 sipush 0
istore 3 iload 1 sipush 1 isub istore 3 sipush 0 istore 4 sipush 0 istore 7
sipush 0 istore 8 iload 2 sipush 1 isub istore 8 iload 1 iload 2 if_icmpge
branch1 aload 0 iload 2 iaload istore 9 iload 1 istore 4 loop1: iload 4 iload 8
if_icmpgt ibranch1 aload 0 iload 4 iaload iload 9 if_icmpgt ibranch2 iload 3
sipush 1 iadd istore 3 aload 0 iload 3 iaload istore 7 aload 0 iload 3 aload 0
iload 4 iaload iastore aload 0 iload 4 iload 7 iastore ibranch2: iload 4 sipush
1 iadd istore 4 goto loop1 ibranch1: iload 3 sipush 1 iadd istore 8 aload 0
iload 8 iaload istore 7 aload 0 iload 8 aload 0 iload 2 iaload iastore aload 0
iload 2 iload 7 iastore iload 8 sipush 1 isub istore 7 aload 0 iload 1 iload 7
invokestatic C2Bytecode/quicksort([III)V iload 8 sipush 1 iadd istore 7 aload 0
iload 7 iload 2 invokestatic C2Bytecode/quicksort([III)V branch1: return .end
method .end class
小結(jié)

這篇的代碼生成和之前解釋器的思路很相似，都是根據(jù)AST和對(duì)應(yīng)的產(chǎn)生式來(lái)執(zhí)行或者生成代碼。

其實(shí)主要的思路是很清晰的，只是其中有太多細(xì)節(jié)容易讓人太過(guò)糾結(jié)。這個(gè)系列算作是我自己的學(xué)習(xí)筆記，到這也有十三篇了，下一篇可能寫寫總結(jié)就正式結(jié)束了。

歡迎Star!

• ? 上一篇：數(shù)組（ArrayPool數(shù)組池、Span<T>結(jié)構(gòu)）
• ? 下一篇：開(kāi)源題材征集 + MVC&EF Core 完整教程小結(jié)