用Java实现一门编程语言（一）

这几天着实业务需求少了很多，更多是放量配置啥的，所以闲着就想写点什么，就尝试写一下，语言名我就叫Azul，当然性能肯定差的一批，不过作为第一版主要先跑起来再说

先看结果吧

test.zul

var five=5
print five
var five2="five"
print five2

上面就是我的语言的语法，很简单，执行结果就是就是直接输出5 和 five 两个参数

那就开始吧，这个是一个工程量偏长的项目，不会很快就能够完结，毕竟不是每天都会空闲，工作还是挺忙的...

本次实现功能

• 声明int或者string类型的基本变量
• 简单的类型推断
• 打印变量值

使用 Antlr4 进行词法分析和解析

本来想自己实现一个词法分析器的，但感觉自己实现性能和功能上又不行，且还是一个庞大且复杂的任务，于是就准备用antlr4来解析了，这个工具非常方便，你只需向它“提供”一个描述语言规则的类似模式的文件，它就会为你生成遍历抽象语法树的方法代码antlr4用法

Azul.g4 规则文件以.g4结尾

//header
grammar Enkel;

//parser rules
// 根规则——全局代码只包含变量和打印
compilationUnit : ( variable | print )* EOF; 
// 
variable : VARIABLE ID EQUALS value; 

print : PRINT ID ; 
// value 必须是 数字或者字符串
value : NUMBER
      | STRING ; 

//lexer rules (词法分析器规则)
// 变量必须匹配 var
VARIABLE : 'var' ; 
PRINT : 'print' ;
EQUALS : '=' ; 
NUMBER : [0-9]+ ; 
STRING : '"'.*'"' ; 
ID : [a-zA-Z0-9]+ ; 
WS: [ \t\n\r]+ -> skip ; 

规则百度一下就知道，有一些比较注意的条件就是

• EOF-文件结尾
• 规则和; 之间的空格是必须要有的

定义了规则后，就可以用工具antlr来生成java类了

直接执行antlr4 Azul.g4

没有安装antlr4的自行百度安装，不是很难

执行后会生成四个类：

• AzulLexer-包含标记信息

• AzulParser-包含解析器、标记信息和每个解析器规则的内部类。

• AzulListener - 当访问节点时提供解析树事件的回调

• AzulBaseListener - 只是 AzulListener 的一个空实现

然后通过 grun Azul -r -tree等命令就可以看到语法树的ui图

遍历解析树

Antlr4提供了一种通过子类化生成的来遍历（访问）解析树元素的方法 AzulListener

public class AzulTreeWalkListener extends AzulBaseListener {

    private static final Logger logger = LoggerFactory.getLogger(AzulTreeWalkListener.class);

    private Queue<Instruction> instructionQueue = new ArrayDeque<>();

    private Map<String, Variable> variableMap = new HashMap<>();


    public Queue<Instruction> getInstructionQueue() {
        return instructionQueue;
    }

    @Override
    public void exitVariable(VariableContext ctx) {
        final TerminalNode varName = ctx.ID();
        final ValueContext varValue = ctx.value();
        final int varType = varValue.getStart().getType();
        final int varIndex = variableMap.size();
        final String varTextValue = varValue.getText();
        logger.info("id: {}, tpye: {}, value: {}", varIndex, varType, varTextValue);
        Variable var = new Variable(varIndex, varType, varTextValue);
        variableMap.put(varName.getText(), var);
        instructionQueue.add(new VariableDeclaration(var));
        logVariableDeclaration(varName, varValue);
    }

    @Override
    public void exitPrint(PrintContext ctx) {
        final TerminalNode varName = ctx.ID();
        final boolean printedVarNotDeclared = !variableMap.containsKey(varName.getText());
        if (printedVarNotDeclared) {
            logger.error("ERROR: WTF? You are trying to print var '{}' which has not been declared!!!111. ",
                    varName.getText());
            return;
        }
        final Variable variable = variableMap.get(varName.getText());
        instructionQueue.add(new PrintVariable(variable));
        logPrintStatement(varName, variable);
    }

    private void logVariableDeclaration(TerminalNode varName, ValueContext varValue) {
        logger.info("【SUCCESS】声明了变量：{}， 值为：{}，行数：{}", varName, varValue.getText(), varName.getSymbol().getLine());
    }

    private void logPrintStatement(TerminalNode varName, Variable variable) {
        logger.info("【SUCCESS】打印变量：{}，值：{},行数：{}", variable.getId(), variable.getValue(), varName.getSymbol().getLine());
    }
}

getInstructionQueue会按照顺序返回正确的指令，这些指令稍后被转化为JVM字节码 实现上面的listener后，就该注册它了

public class SyntaxTreeTraverser {

    public Queue<Instruction> getInstructions(String fileAbsolutePath) throws IOException {
        CharStream charStream = new ANTLRFileStream(fileAbsolutePath);
        AzulLexer lexer = new AzulLexer(charStream);
        CommonTokenStream tokenStream = new CommonTokenStream(lexer);
        AzulParser parser = new AzulParser(tokenStream);
        AzulTreeWalkListener listener = new AzulTreeWalkListener();
        AzulTreeWalkErrorListener walkErrorListener = new AzulTreeWalkErrorListener();

        parser.addErrorListener(walkErrorListener);
        parser.addParseListener(listener);
        parser.compilationUnit();
        return listener.getInstructionQueue();
    }
}

综上，解析树监听器已经实现了，现在只要运行SyntaxTreeTraverser就行，创建一个MyCompiler类，它接受一个参数（要解析的文件完整路径）。

MyCompiler

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

    public void compile(String[] args) throws Exception {
        if (args.length == 0) {
            throw new IllegalStateException("参数异常, args: " + Arrays.toString(args));
        }
        final File enkelFile = new File(args[0]);
        String fileName = enkelFile.getName();
        String fileAbsolutePath = enkelFile.getAbsolutePath();
        String className = StringUtils.remove(fileName, ".zul");
        logger.info("fileName: {}, className: {}", fileName, className);
        final Queue<Instruction> instructionsQueue = new SyntaxTreeTraverser().getInstructions(fileAbsolutePath);
        logger.info("instructionsQueue: {}", instructionsQueue.size());
        final byte[] byteCode = new BytecodeGenerator().generateBytecode(instructionsQueue, className);
    }

目前就可以验证我们的程序 Azul.zul是否正确，当然现在还没发进行编译运行，但是可以对规则进行验证：

• 可以使用 var a = 1 或者 var a = "a" 等语法来声明变量
• 允许使用print "aa" 等语法打印变量
• 如果代码语法不符合上述规则就会打印错误

直接执行示例test.zul

var five=5
print five
var five2="five"
print five2

运行MyCompiler后可以看到日志

【SUCCESS】声明了变量：five， 值为：5，行数：1

【SUCCESS】打印变量：0，值：5,行数：2

【SUCCESS】声明了变量：five2， 值为："five"，行数：3

【SUCCESS】打印变量：1，值："five",行数：4

可以看到我们的规则没问题，被解析树解析出来了

根据指令队列生成字节码

java.class文件由一组指令组成指令,每条指令由以下部分组成：

• 操作码（一个字节） 指定要执行的操作
• 可选操作数 指令的输入

例如：iload 5（0x15 5）：从局部变量表加载int值，其中5是局部变量表数组中的索引。

当然，指令也可以从操作数栈中弹出值并将其推送到其中。例如：

iload 3

iload 2

iadd

它会从从局部变量表索引3位置加载一个int变量，并在索引2位置加载另外一个变量。此时堆栈会包含两个int变量，调用iadd后，会将两个数值的结果推送到堆栈上面去。

ASM操作字节码

通过asm来操作字节码，可以让我们不用关心指令的实际值（iload是0x15还是0x16），并将他们写入文件。而我们只需要记住指令的名称就行，然后将其通过asm映射到值并保存到文件中。

之前SyntaxTreeTraverser访问树节点时，会存储到instructionQueue中去，该队列的类型就是指令类型，因此我们申明Instruction

public interface Instruction {

    void apply(MethodVisitor methodVisitor);
}

它要求每个实现都使用 methodVisitor（ASM 库）对象执行一些字节码指令。

BytecodeGenerator

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);
        {
            //声明静态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

            //遍历解析树生成对应指令
            for (Instruction instruction : instructionQueue) {
                instruction.apply(mv);
            }
            mv.visitInsn(RETURN); // 添加返回指令

            // 设置最大堆栈和局部变量
            mv.visitMaxs(maxStack, (int) localVariablesCount); 
            mv.visitEnd();
        }
        cw.visitEnd();

        return cw.toByteArray();
    }
}

当前Azul还不支持方法、类和作用域等，所以编译后就作为Object的字类，它只有一个main方法。当指定具体指令后，我们需要提供局部变量表和堆栈的大小，然后每条指令都会在循环中向字节码添加一些内容。目前有两种类型的指令：

VariableDeclaration

public class VariableDeclaration implements Instruction, Opcodes {

    Variable variable;

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

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

类型推断，由于我们在文件解析期间就已经根据词法分析的标记动态知道了当前的指令属性类型，因此就直接根据其来执行不同的指令

• visitInsn 访问指令，第一个操作是操作码，第二个操作是操作数
• BIPUSH 将一个字节整数推送到堆栈
• ISTORE 将int存储在局部变量表中，将局部变量表的索引作为操作数，然后从堆栈中弹出int值
• ASTORE 和ISTORE相同，但是它表示的是引用，因为String实例是一个对象

PrintVariable 第二种指令类型

public class PrintVariable implements Instruction, Opcodes {
    private Variable variable;

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

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

• GETSTATIC 从类中获取静态字段（java/lang/System 字段是一种输出类型java.io.PrintStream）
• ILOAD 将局部变量推送到堆栈（id是变量堆栈中变量的索引）
• visitMethodInsn 访问方法说明
• INVOKEVIRTUAL 调用实例方法（调用println方法，接受一个int但是没有返回值）
• ALOAD 类似ILOAD，但是ALOAD代表引用（字符串引用对象）

生成字节码

上面BytecodeGenerator中调用cw.toByteArray()后，ASM会创建一个新的实例ByteVector并将所有指令放入其中。每个class文件的前四个字节都是magic：CAFEBABE，参考：JVM

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];
}

由于当前Azul还没有设计字段、属性、超类、接口等，因此主要描述了方法部分的实现。

将字节码写入文件

其实我们就是将.zul文件编译成.class文件，然后由于JVM代替执行，而本次实现的逻辑ZVM更类似于一个中间工具，将.zul文件转化成.class文件的中间工具

private static void saveBytecodeToClassFile(String fileName, byte[] byteCode) throws IOException {
        final String classFile = StringUtils.replace(fileName, ".zul", ".class");
        String filePath = "/Users/zhaozhenhang/project/java-project/Azul-AVM/src/main/java/compiler/" + classFile;
        OutputStream os = new FileOutputStream(filePath);
        os.write(byteCode);
        os.close();
    }

可以验证一下我们编译后的.class文件, 直接使用javap工具，它是捆绑在jdk中的

执行命令：

$JAVA_HOME/bin/javap -v /Users/zhaozhenhang/project/java-project/Azul-AVM/src/main/java/compiler/first.class

Classfile /Users/zhaozhenhang/project/java-project/Azul-AVM/src/main/java/compiler/first.class
  Last modified 2024年7月31日; size 303 bytes
  MD5 checksum f1727559bdc5f11f2e6d9a138565b08c
public class first
  minor version: 0
  major version: 52
  flags: (0x0021) ACC_PUBLIC, ACC_SUPER
  this_class: #2                          // first
  super_class: #4                         // java/lang/Object
  interfaces: 0, fields: 0, methods: 1, attributes: 0
Constant pool:
   #1 = Utf8               first
   #2 = Class              #1             // first
   #3 = Utf8               java/lang/Object
   #4 = Class              #3             // java/lang/Object
   #5 = Utf8               main
   #6 = Utf8               ([Ljava/lang/String;)V
   #7 = Utf8               java/lang/System
   #8 = Class              #7             // java/lang/System
   #9 = Utf8               out
  #10 = Utf8               Ljava/io/PrintStream;
  #11 = NameAndType        #9:#10         // out:Ljava/io/PrintStream;
  #12 = Fieldref           #8.#11         // java/lang/System.out:Ljava/io/PrintStream;
  #13 = Utf8               java/io/PrintStream
  #14 = Class              #13            // java/io/PrintStream
  #15 = Utf8               println
  #16 = Utf8               (I)V
  #17 = NameAndType        #15:#16        // println:(I)V
  #18 = Methodref          #14.#17        // java/io/PrintStream.println:(I)V
  #19 = Utf8               \"five\"
  #20 = String             #19            // \"five\"
  #21 = Utf8               (Ljava/lang/String;)V
  #22 = NameAndType        #15:#21        // println:(Ljava/lang/String;)V
  #23 = Methodref          #14.#22        // java/io/PrintStream.println:(Ljava/lang/String;)V
  #24 = Utf8               Code
{
  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=100, locals=2, args_size=1
         0: bipush        5
         2: istore_0
         3: getstatic     #12                 // Field java/lang/System.out:Ljava/io/PrintStream;
         6: iload_0
         7: invokevirtual #18                 // Method java/io/PrintStream.println:(I)V
        10: ldc           #20                 // String \"five\"
        12: astore_1
        13: getstatic     #12                 // Field java/lang/System.out:Ljava/io/PrintStream;
        16: aload_1
        17: invokevirtual #23                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
        20: return
}

最后直接运行代码(已经将test.zul编译成test.class了)：

java test

可以看到如下输出：

    5
	"five"

以上就完成我们的第一步了，已经简单实现了一个可执行的.zul文件，下一步会实现一些语法特性～

#Java##项目##面试##校招#