本文系 Creating JVM language 翻譯的第三篇。

0. 自頂向下的方式

開發(fā)一門語言不是短期任務(wù)沈自，我將以自頂向下的視角來開發(fā)烘贴。為了避免陷入每個(gè)模塊的實(shí)現(xiàn)細(xì)節(jié)筷畦，我準(zhǔn)備先宏觀的描述每個(gè)模塊，然后在每個(gè)迭代症杏，我將慢慢加入更多的細(xì)節(jié)加以完善。

1. 代碼

作者原來的代碼是 Maven 工程瑞信，譯者這里改成了 Gradle（譯者熟悉 Gradle 并且覺得更為優(yōu)雅）厉颤，目錄結(jié)構(gòu)以及包名也做了些許改動(dòng)，但是邏輯上都是等價(jià)的凡简。
讀者可根據(jù)喜好逼友，自行選擇精肃。

• 譯者的 Gradle 工程地址
• 作者的 Maven 工程地址

約定：每個(gè)章節(jié)，涉及到代碼變更帜乞，譯者都會(huì)打 tag, tag 的名字和章節(jié)名字保持統(tǒng)一司抱，比如，當(dāng)前章節(jié)的代碼版本是 PART-3黎烈，以此類推习柠。

2. 功能

本章節(jié)我將為 Enkel 添加如下功能特性：

• 聲明 int 或者 string 類型的變量
• 打印變量
• 簡單的類型推斷

示例如下:

//first.enk
 var five=5
 print five   
 var dupa="dupa"  
 print dupa  

下面我們將實(shí)現(xiàn)能最簡化版本，讓上述代碼可以運(yùn)行在 JVM 上照棋。

3. 用 ANTLR4 實(shí)現(xiàn)詞法分析&語法分析

從零開始實(shí)現(xiàn)一個(gè)詞法分析器是重復(fù)性很強(qiáng)的勞動(dòng)资溃。這里使用 Antlr （Antlr 4）實(shí)現(xiàn)。你需要做的只是創(chuàng)建一個(gè)語法規(guī)則文件烈炭，Antlr 幫你生成可以遍歷 AST 的基礎(chǔ)代碼溶锭。

本章語法規(guī)則文件為 Enkel.g4:

//header
grammar Enkel;

@header {
package com.bendcap.enkel.antlr;
}

//RULES
compilationUnit : ( variable | print )* EOF; //root rule - our code consist consist only of variables and prints (see definition below)
variable : VARIABLE ID EQUALS value; //requires VAR token followed by ID token followed by EQUALS TOKEN ...
print : PRINT ID ; //print statement must consist of 'print' keyword and ID
value : op=NUMBER
      | op=STRING ; //must be NUMBER or STRING value (defined below)

//TOKENS
VARIABLE : 'var' ; //VARIABLE TOKEN must match exactly 'var'
PRINT : 'print' ;
EQUALS : '=' ; //must be '='
NUMBER : [0-9]+ ; //must consist only of digits
STRING : '"'.*'"' ; //must be anything in qutoes
ID : [a-zA-Z0-9]+ ; //must be any alphanumeric value
WS: [ \t\n\r]+ -> skip ; //special TOKEN for skipping whitespaces

語法規(guī)則很簡單，需要注意的是：

• EOF - 文件結(jié)束
• 語法規(guī)則中的空格和 ; 是必須

Enkel.g4 定義好后符隙，可以運(yùn)行命令來生成后續(xù)需要的 Java 代碼：
antlr Enkel.g4

命令執(zhí)行完后暖途，會(huì)生成四個(gè)類：

• EnkelLexer - 包含 Token 相關(guān)信息
• EnkelParser - 解析器，Token 信息以及一些內(nèi)部類來做規(guī)則解析
• EnkelListener - 當(dāng)訪問語法節(jié)點(diǎn)的時(shí)候膏执，提供回調(diào)函數(shù)
• EnkelBaseListener - 空的 EnkelListener 實(shí)現(xiàn)

譯注: 如果你使用 Gradle 工程的話驻售，可以使用 ./gradlew :antlr:generateGrammarSource 來生成上述代碼。

其中最重要的是 EnkelBaseListener更米，這個(gè)類提供了遍歷 AST 時(shí)的回調(diào)函數(shù)欺栗，我們不用關(guān)心詞法分析和語法分析，Antlr 幫助我們屏蔽了這個(gè)過程征峦。

我們可以使用 javac *.java 編譯上述代碼迟几，來測(cè)試我們的規(guī)則正確性。

$ export CLASSPATH=".:$ANTLR_JAR_LOCATION:$CLASSPATH"
$ java org.antlr.v4.gui.TestRig Enkel compilationUnit -gui
var x=5
print x
var dupa="dupa"
print dupa
ctrl+D //end of file

上述輸入會(huì)生成如下的圖形化樹形結(jié)構(gòu)（抽象語法書的圖形化展示）：

image

譯者注：可以使用 IDEA 插件 ANTLR 4 grammar plugin 來實(shí)現(xiàn)同樣的效果栏笆，或許更方便一些类腮。

image

4. 遍歷語法樹

EnkelListener 提供了我們遍歷語法樹的辦法。

EnkelTreeWalkListener.java
public class EnkelTreeWalkListener extends EnkelBaseListener {

    Queue<Instruction> instructionsQueue = new ArrayDeque<>();
    Map<String, Variable> variables = new HashMap<>();

    public Queue<Instruction> getInstructionsQueue() {
        return instructionsQueue;
    }

    @Override
    public void exitVariable(@NotNull EnkelParser.VariableContext ctx) {
        final TerminalNode varName = ctx.ID();
        final EnkelParser.ValueContext varValue = ctx.value();
        final int varType = varValue.getStart().getType();
        final int varIndex = variables.size();
        final String varTextValue = varValue.getText();
        Variable var = new Variable(varIndex, varType, varTextValue);
        variables.put(varName.getText(), var);
        instructionsQueue.add(new VariableDeclaration(var));
        logVariableDeclarationStatementFound(varName, varValue);
    }

    @Override
    public void exitPrint(@NotNull EnkelParser.PrintContext ctx) {
        final TerminalNode varName = ctx.ID();
        final boolean printedVarNotDeclared = !variables.containsKey(varName.getText());
        if (printedVarNotDeclared) {
            final String erroFormat = "ERROR: WTF? You are trying to print var '%s' which has not been declared!!!.";
            System.err.printf(erroFormat, varName.getText());
            return;
        }
        final Variable variable = variables.get(varName.getText());
        instructionsQueue.add(new PrintVariable(variable));
        logPrintStatementFound(varName, variable);
    }

    private void logVariableDeclarationStatementFound(TerminalNode varName, EnkelParser.ValueContext varValue) {
        final int line = varName.getSymbol().getLine();
        final String format = "OK: You declared variable named '%s' with value of '%s' at line '%s'.\n";
        System.out.printf(format, varName, varValue.getText(), line);
    }

    private void logPrintStatementFound(TerminalNode varName, Variable variable) {
        final int line = varName.getSymbol().getLine();
        final String format = "OK: You instructed to print variable '%s' which has value of '%s' at line '%s'.'\n";
        System.out.printf(format, variable.getId(), variable.getValue(), line);
    }
}

getInstructionsQueue 按照代碼順序返回指令蛉加。

下面我們可以注冊(cè) Listener:

SyntaxTreeTraverser.java
public class SyntaxTreeTraverser {
    public Queue<Instruction> getInstructions(String fileAbsolutePath) throws IOException {
        CharStream charStream = new ANTLRFileStream(fileAbsolutePath); //fileAbsolutePath - file containing first enk code file

        EnkelLexer lexer = new EnkelLexer(charStream);  //create lexer (pass enk file to it)

        CommonTokenStream tokenStream = new CommonTokenStream(lexer);

        EnkelParser parser = new EnkelParser(tokenStream);

        EnkelTreeWalkListener listener = new EnkelTreeWalkListener(); //EnkelTreeWalkListener extends EnkelBaseLitener - handles parse tree visiting events
        BaseErrorListener errorListener = new EnkelTreeWalkErrorListener(); //EnkelTreeWalkErrorListener - handles parse tree visiting error events

        parser.addErrorListener(errorListener);
        parser.addParseListener(listener);
        parser.compilationUnit(); //compilation unit is root parser rule - start from it!
        return listener.getInstructionsQueue();
    }
}

這里我提供了另一個(gè) Listener 來做異常處理:

EnkelTreeWalkErrorListener.java
public class EnkelTreeWalkErrorListener extends BaseErrorListener {
    @Override
    public void syntaxError(Recognizer<?, ?> recognizer, Object offendingSymbol, int line, int charPositionInLine, String msg, RecognitionException e) {
        final String errorFormat = "You fucked up at line %d,char %d :(. Details:\n%s";
        final String errorMsg = String.format(errorFormat, line, charPositionInLine, msg);
        System.err.println(errorMsg);
    }
}

遍歷語法樹的 Listener 寫完后蚜枢，我們來測(cè)試一下。創(chuàng)建 Compiler 類作為入口针饥，輸入?yún)?shù)為我們 Enkel 語言的源文件路徑厂抽。

//Compiler.java
public class Compiler {

    public static void main(String[] args) throws Exception {
        new Compiler().compile(args);
    }

    public void compile(String[] args) throws Exception {
        //arguments validation skipped (check out full code on github)
        final File enkelFile = new File(args[0]);
        String fileName = enkelFile.getName();
        String fileAbsolutePath = enkelFile.getAbsolutePath();
        String className = StringUtils.remove(fileName, ".enk");
        final Queue<Instruction> instructionsQueue = new SyntaxTreeTraverser().getInstructions(fileAbsolutePath);
        //TODO: generate bytecode based on instructions
    }
}

下面我們既可以驗(yàn)證我們的 *.enk 文件了。目前的實(shí)現(xiàn)很簡陋丁眼，但是可以做如下事情：

• 允許用 var x=1 或者 var x = "anthing" 來聲明變量
• 允許用 print x 打印變量
• 如果語法不符合規(guī)則筷凤，報(bào)錯(cuò)提示

下面我們創(chuàng)建示例 first.enk:

 var five=5
 print five   
 var dupa="dupa"  
 print dupa  

驗(yàn)證：

$java Compiler first.enk

OK: You declared variable named 'five' with value of '5' at line '1'.
OK: You instructed to print variable '0' which has value of '5' at line '2'.'
OK: You declared variable named 'dupa' with value of '"dupa"' at line '3'.
OK: You instructed to print variable '1' which has value of '"dupa"' at line '4'.'

在 first.enk 最后添加一行 void noFunctionsYet(), 再次驗(yàn)證，ErrorListener 可以檢測(cè)到錯(cuò)誤苞七，并且輸出如下提示信息：

You fucked up at line 1,char 0 :(. Details:
mismatched input 'void' expecting {<EOF>, 'var', 'print'}

5. 根據(jù) instructions queue 生成字節(jié)碼

Java 的 class 文件的包含的指令描述參見 JSE 文檔藐守。每一條指令包含如下結(jié)構(gòu)：

• 操作符（1 byte）- 指令
• 可選的操作數(shù) - 指令的輸入

例： iload 5 (0x15 5)挪丢，從局部變量加載數(shù)據(jù)，5 是局部變量數(shù)組的索引卢厂。
指令也可以實(shí)現(xiàn)操作數(shù)占的出棧入棧操作吃靠。
例如：

iload 3
iload 2
iadd

上述代碼分別從局部變量數(shù)組中加載索引為 3 和 2 的變量，此時(shí)棧中包含兩個(gè)數(shù)值足淆，iadd 指令將棧中兩個(gè)出棧巢块，相加，然后結(jié)果再次入棧巧号。

6. ASM

這里選用 ASM 來操作 Java 字節(jié)碼族奢。這樣可以不用關(guān)心非常底層的十六進(jìn)制數(shù)字，你只需要知道指令的名字丹鸿，ASM 會(huì)自動(dòng)幫你處理剩下的事情越走。

7. Instruction interface

SyntaxTreeTraverser 在遍歷 AST 的時(shí)候會(huì)把指令按照順序存儲(chǔ)到 instructionsQueue 中。我們做一次抽象靠欢，定義接口 Instruction：

public interface Instruction {
    void apply(MethodVisitor methodVisitor);
}

接口的實(shí)現(xiàn)需要使用 MethodVisitor（ASM 提供的類） 來做一些代碼生成的操作廊敌。

//Compiler.java
public void compile(String[] args) throws Exception {
    //some lines deleted -> described in previous sections of this post
    final Queue<Instruction> instructionsQueue = new SyntaxTreeTraverser().getInstructions(fileAbsolutePath);
    final byte[] byteCode = new BytecodeGenerator().generateBytecode(instructionsQueue, className);
    saveBytecodeToClassFile(fileName, byteCode);
}
//ByteCodeGenerator.java
public class BytecodeGenerator implements Opcodes {
    public byte[] generateBytecode(Queue<Instruction> instructionQueue, String name) throws Exception {

        ClassWriter cw = new ClassWriter(0);
        MethodVisitor mv;
               //version ,      acess,       name, signature, base class, interfaes
        cw.visit(52, ACC_PUBLIC + ACC_SUPER, name, null, "java/lang/Object", null);
        {
            //declare static void main
            mv = cw.visitMethod(ACC_PUBLIC + ACC_STATIC, "main", "([Ljava/lang/String;)V", null, null);
            final long localVariablesCount = instructionQueue.stream()
                    .filter(instruction -> instruction instanceof VariableDeclaration)
                    .count();
            final int maxStack = 100; //TODO - do that properly

            //apply instructions generated from traversing parse tree!
            for (Instruction instruction : instructionQueue) {
                instruction.apply(mv);
            }
            mv.visitInsn(RETURN); //add return instruction

            mv.visitMaxs(maxStack, (int) localVariablesCount); //set max stack and max local variables
            mv.visitEnd();
        }
        cw.visitEnd();

        return cw.toByteArray();
    }
}  

由于目前 Enkel 不支持 方法，類以及作用域等概念门怪，因?yàn)榫幾g后的類直接繼承自 Object, 包含一個(gè) main 函數(shù)骡澈。MethodVisitor 需要提供局部變量以及棧的深度。然后我們遍歷 instructionQueue 的每條指令來生成對(duì)應(yīng)的字節(jié)碼掷空。目前我們只有兩種指令（變量聲明以及打印語句）：

//VariableDeclaration.java
public class VariableDeclaration implements Instruction,Opcodes {
    Variable variable;

    public VariableDeclaration(Variable variable) {
        this.variable = variable;
    }

    @Override
    public void apply(MethodVisitor mv) {
        final int type = variable.getType();
        if(type == EnkelLexer.NUMBER) {
            int val = Integer.valueOf(variable.getValue());
            mv.visitIntInsn(BIPUSH,val);
            mv.visitVarInsn(ISTORE,variable.getId());
        } else if(type == EnkelLexer.STRING) {
            mv.visitLdcInsn(variable.getValue());
            mv.visitVarInsn(ASTORE,variable.getId());
        }
    }
}

這里值得注意的是肋殴，我們已經(jīng)添加了簡單的類型推斷。我們會(huì)根據(jù)變量的實(shí)際類型進(jìn)行類型推斷坦弟。針對(duì)不同類型我們需要調(diào)用 ASM 不同的方法：

• visitInsn - 第一個(gè)參數(shù)是操作符护锤，第二個(gè)是操作數(shù)
• BIPUSH - 把一個(gè) byte(integer) 入棧
• ISTORE - int 類型的值出棧，并存儲(chǔ)到局部變量中,需要指定局部變量的索引
• ASTORE - 和 ISTORE 功能類似酿傍，但是數(shù)據(jù)類型是索引

打印語句的代碼生成如下：

//PrintVariable.java
public class PrintVariable implements Instruction, Opcodes {
    public PrintVariable(Variable variable) {
        this.variable = variable;
    }

    @Override
    public void apply(MethodVisitor mv) {
        final int type = variable.getType();
        final int id = variable.getId();
        mv.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
        if (type == EnkelLexer.NUMBER) {
            mv.visitVarInsn(ILOAD, id);
            mv.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(I)V", false);
        } else if (type == EnkelLexer.STRING) {
            mv.visitVarInsn(ALOAD, id);
            mv.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/String;)V", false);
        }
    }
}

• GETSTATIC - 從java.lang.System.out獲得靜態(tài)屬性烙懦，類型是 java.io.PrintStream
• ILOAD - 把局部變量入棧，id 是局部變量的索引
• visitMethodInsn - 訪問方法指令
• INVOKEVIRTUAL - 觸發(fā)實(shí)例方法 （調(diào)用 out 的 print 方法赤炒，該方法接受一個(gè)參數(shù)為整數(shù)類型氯析，返回為空）
• ALOAD - 和 ILOAD 類型，但是數(shù)據(jù)類型是引用

8. 生成字節(jié)碼

cw.toByteArray(); 執(zhí)行后可霎，ASM 創(chuàng)建一個(gè) ByteVector 實(shí)例并把所有的指令加入進(jìn)去魄鸦。Java class 文件的結(jié)構(gòu)為：

//https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.1
ClassFile {
    u4             magic; //CAFEBABE
    u2             minor_version;
    u2             major_version;
    u2             constant_pool_count;
    cp_info        constant_pool[constant_pool_count-1]; //string constants etc...
    u2             access_flags;
    u2             this_class;
    u2             super_class;
    u2             interfaces_count;
    u2             interfaces[interfaces_count];
    u2             fields_count;
    field_info     fields[fields_count];
    u2             methods_count;
    method_info    methods[methods_count];
    u2             attributes_count;
    attribute_info attributes[attributes_count];
}

魔數(shù)（Magic Number）是 0xCAFEBABE。由于 Enkel 目前不支持字段癣朗，屬性，父類或者接口旺罢，因此我們這里主要描述了 method_info旷余。

9. 寫入字節(jié)碼到文件

JVM 規(guī)范要求我們 .class 文件的名字必須和類型相同绢记。所以我們這里保持文件名字和類名一直，僅替換后綴 (*enk -> *.class)正卧。

//Compiler.java
private static void saveBytecodeToClassFile(String fileName, byte[] byteCode) throws IOException {
        final String classFile = StringUtils.replace(fileName, ".enk", ".class");
        OutputStream os = new FileOutputStream(classFile);
        os.write(byteCode);
        os.close();
    }

10. 驗(yàn)證字節(jié)碼

我們可以使用 JDK 自帶的 javap 工具來驗(yàn)證生成的字節(jié)碼的正確性蠢熄。

$ $JAVA_HOME/bin/javap -v file

Classfile /home/kuba/repos/Enkel-JVM-language/file.class
  Last modified 2016-03-16; size 335 bytes
  MD5 checksum bcbdaa7e7389167342e0c04b52951bc9
public class file
  minor version: 0
  major version: 52
  flags: ACC_PUBLIC, ACC_SUPER
Constant pool:
   #1 = Utf8               file
   #2 = Class              #1             // file
   #3 = Utf8               java/lang/Object
   #4 = Class              #3             // java/lang/Object
   #5 = Utf8               Test.java
   #6 = Utf8               main
   #7 = Utf8               ([Ljava/lang/String;)V
   #8 = Utf8               java/lang/System
   #9 = Class              #8             // java/lang/System
  #10 = Utf8               out
  #11 = Utf8               Ljava/io/PrintStream;
  #12 = NameAndType        #10:#11        // out:Ljava/io/PrintStream;
  #13 = Fieldref           #9.#12         // java/lang/System.out:Ljava/io/PrintStream;
  #14 = Utf8               java/io/PrintStream
  #15 = Class              #14            // java/io/PrintStream
  #16 = Utf8               println
  #17 = Utf8               (I)V
  #18 = NameAndType        #16:#17        // println:(I)V
  #19 = Methodref          #15.#18        // java/io/PrintStream.println:(I)V
  #20 = Utf8               \"dupa\"
  #21 = String             #20            // \"dupa\"
  #22 = Utf8               (Ljava/lang/String;)V
  #23 = NameAndType        #16:#22        // println:(Ljava/lang/String;)V
  #24 = Methodref          #15.#23        // java/io/PrintStream.println:(Ljava/lang/String;)V
  #25 = Utf8               Code
  #26 = Utf8               SourceFile
{
  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=3, args_size=1
         0: bipush        5
         2: istore_0
         3: getstatic     #13                 // Field java/lang/System.out:Ljava/io/PrintStream;
         6: iload_0
         7: invokevirtual #19                 // Method java/io/PrintStream.println:(I)V
        10: ldc           #21                 // String \"dupa\"
        12: astore_1
        13: getstatic     #13                 // Field java/lang/System.out:Ljava/io/PrintStream;
        16: aload_1
        17: invokevirtual #24                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
        20: return
}

11. 運(yùn)行 Enkel

下面我們來運(yùn)行第一個(gè) Enkel 代碼：

 var five=5
 print five   
 var dupa="dupa"  
 print dupa  

如果一切順利的話，會(huì)有如下輸出：

$java Compiler first.enk
$java first
5
"dupa"

譯者注：上述成品代碼托管在 Github

預(yù)告：下一節(jié)給 Enkel 增加一大坨特性炉旷，并定義好規(guī)范签孔，方便后續(xù)迭代實(shí)現(xiàn)。