用 ANTLR 制作简单的解释语言 “Print”

Pluveto

Apr 16, 2022 发布

? 次浏览

简介

本文将介绍用 ANTLR（一个 Parser 生成器）制作一个名为 Print 的的编程语言。它的语法有点像 Python 2，不过要简单得多，这样便于学习。

下面是一个 Print 语言的例子：

print   "hello, world!"
print   false
print   100
mystr   = "hi"
print   mystr
mystr2  = mystr
print   mystr2

从上面的例子，可以看到我们这一门语言它有以下特点：

可以打印字符串、整数，还有真假三种类型的值。
支持声明和赋值。所以它有一个全局符号表。
可以打印变量。

本来打算用 C++ 以及 Flex&Bison 来写的，然而作业逼得紧，C++ 的内存管理让我头大，只好暂先选用比较简单容易出工的方式了。

环境的搭建

我的本机环境如下：

Ubuntu 20.04 LTS
VSCode SSH-Remote
ANTLR 4.10.1
Zsh Shell

安装 ANTLR

apt install openjdk-17-jdk # or jre

cd /usr/local/lib
wget https://www.antlr.org/download/antlr-4.10.1-complete.jar
code .zshrc

export CLASSPATH=".:/usr/local/lib/antlr-4.10.1-complete.jar:$CLASSPATH"
alias antlr4='java -jar /usr/local/lib/antlr-4.10.1-complete.jar'
alias grun='java org.antlr.v4.gui.TestRig'

起步

mkdir ~/repo/print-lang
code $_

规范起见。我们创建这样的目录结构：

.
├── Makefile
├── src/
│   ├── com/
│   │   └── less_bug/
│   │       └── print/
│   └── hello.print

可以安装 ANTLR4 grammar syntax support 插件，以便在 VSCode 中获得代码提示。

将最上面的示例代码写入 hello.print 文件。

设计语法

语法设计如下：

src/com/less_bug/print/Print.g4 43:

grammar Print;

@header {
    package com.less_bug.print;
}

/*
 * Tokens
 */

PRINT: 'print';

ID: [a-zA-Z_][a-zA-Z0-9_]*;
STRING: '"' (~["\n] | '""')* '"';
NUMBER: [0-9]+ | [0-9]* '.' [0-9]+;

WS: [ \t\n]+ -> skip;

/*
 * Rules
 */

program: statement*;

statement: printStatement | assignment;

printStatement: PRINT expression | PRINT ID;

assignment: ID '=' expression;

expression:
	ID
	| stringExpression
	| numberExpression
	| booleanExpression;

stringExpression: STRING;

numberExpression: NUMBER;

booleanExpression: 'true' | 'false';

规定了四种主要词符：

PRINT：打印指令。
ID：标识符名。
STRING：字符串字面量。
NUMBER：数字字面量。

而 WS 表示空白字符。直接跳过即可。

编译

进入到 src/com/less_bug/print 目录，执行：

java -jar /usr/local/lib/antlr-4.10.1-complete.jar Print.g4

即可用 ANTLR 生成词法分析器和语法分析器。

然后用下面的指令编译：

javac *.java

构建自动化

每次都手打很长一串命令来进行编译是很麻烦的。尤其是之后我们要调试的时候更加麻烦。所以我们做一个 Makefile 来自动化这个过程。

Makefile 18:

TARGET=Print
JAVA=java
ANTLR4=-jar /usr/local/lib/antlr-4.10.1-complete.jar
GRUN=org.antlr.v4.gui.TestRig
SRC=src/com/less_bug/print
COMP_NAME=com.less_bug.print.Interpreter

default: build

build:
	@cd $(SRC) &amp;&amp; $(JAVA) $(ANTLR4) $(TARGET).g4 -visitor &&\
		javac *.java

run: build
	    @cd ./src && java $(COMP_NAME) hello.print

debug: build
	    @cd ./src && java -Dprint.logLevel=FINEST $(COMP_NAME) hello.print

这样，我们只需要执行 make 即可编译，执行 make run 即可运行，执行 make debug 即可在 FINEST 日志等级下运行。

同时，我们提供了 -visitor 参数，这样生成一个 PrintVisitor 基类，基于它可以派生出我们的 Visitor，用于访问 AST。

设计符号表

符号表设计如下：

src/com/less_bug/print/SymbolTable.java 69:

package com.less_bug.print;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SymbolTable {
    private Map<String, Object> symbols = new HashMap<>();

    public SymbolTable() {
    }

    public void set(String name, Object value) {
        symbols.put(name, value);
    }

    public Object lookup(String name) {
        if (symbols.containsKey(name)) {
            return symbols.get(name);
        } else {
            return null;
        }
    }

    public void print() {
        System.out.println("SymbolTable");
        for (Map.Entry<String, Object> entry : symbols.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

符号表的设计说明

在这里有我们实现了三个函数：

set 用于像符号表里面存入数据。
lookup 用于在符号表中查询数据，如果查询不到就会返回 null。
一个是 print 用于打印符号表中的所有内容，用于调试。

进阶：设计带作用域的符号表

在实际的编程语言中，往往不可能全部存成全局变量。我们需要一些具有作用范围的符号，这样的话，符号表之间就会产生树状关系。

我这里给出一个参考实现：

src/com/less_bug/print/SymbolTable.java 69:

package com.less_bug.print;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SymbolTable {
    private List<SymbolTable> children = new ArrayList<>();
    private Map<String, Object> symbols = new HashMap<>();
    private SymbolTable parent;

    public SymbolTable() {
    }

    public SymbolTable(SymbolTable parent) {
        this.parent = parent;
    }

    public SymbolTable getParent() {
        return parent;
    }

    public void set(String name, Object value) {
        symbols.put(name, value);
    }

    public Object lookup(String name) {
        if (symbols.containsKey(name)) {
            return symbols.get(name);
        } else if (parent != null) {
            return parent.lookup(name);
        } else {
            return null;
        }
    }

    public void addChild(SymbolTable child) {
        children.add(child);
    }

    public List<SymbolTable> getChildren() {
        return children;
    }

    private void _print(int level) {
        for (int i = 0; i < level; i++) {
            System.out.print("  ");
        }
        System.out.println("SymbolTable");
        for (Map.Entry<String, Object> entry : symbols.entrySet()) {
            for (int i = 0; i < level; i++) {
                System.out.print("  ");
            }
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        for (SymbolTable child : children) {
            child._print(level + 1);
        }
    }

    public void print() {
        this._print(0);
    }
}

设计 Visitor

前面说到我们的解释过程是通过访问 AST 来实现的。所以我们实现一个 Visitor，就可以实现解释器。

src/com/less_bug/print/Visitor.java 166:

package com.less_bug.print;

import java.util.logging.Logger;

import com.less_bug.print.PrintParser.AssignmentContext;
import com.less_bug.print.PrintParser.BooleanExpressionContext;
import com.less_bug.print.PrintParser.ExpressionContext;
import com.less_bug.print.PrintParser.NumberExpressionContext;
import com.less_bug.print.PrintParser.PrintStatementContext;
import com.less_bug.print.PrintParser.ProgramContext;
import com.less_bug.print.PrintParser.StatementContext;
import com.less_bug.print.PrintParser.StringExpressionContext;

import org.antlr.v4.runtime.tree.ErrorNode;
import org.antlr.v4.runtime.tree.ParseTree;
import org.antlr.v4.runtime.tree.RuleNode;
import org.antlr.v4.runtime.tree.TerminalNode;

public class Visitor implements PrintVisitor<Object> {

    private SymbolTable rootSymtab = new SymbolTable();
    private SymbolTable currentSymtab = rootSymtab;
    private Logger logger;

    public Visitor(Logger logger) {
        this.logger = logger;
    }

    @Override
    public Object visit(ParseTree arg0) {
        logger.finer("[visit] ");
        return null;
    }

    @Override
    public Object visitChildren(RuleNode arg0) {
        logger.finer("[visit] Children");
        return null;
    }

    @Override
    public Object visitErrorNode(ErrorNode arg0) {
        logger.finer("[visit] ErrorNode");
        return null;
    }

    @Override
    public Object visitTerminal(TerminalNode arg0) {
        logger.finer("[visit] Terminal");
        return null;
    }

    @Override
    public Object visitProgram(ProgramContext ctx) {
        if (ctx.exception != null) {
            logger.finer("[visit] Program: " + ctx.exception.getMessage());
            System.exit(1);
        }
        logger.finer("[visit] Program");
        ctx.children.forEach(child -> {
            if (child instanceof StatementContext) {
                visitStatement((StatementContext) child);
            }
        });
        return null;
    }

    @Override
    public Object visitStatement(StatementContext ctx) {
        logger.finer("[visit] Statement");
        ctx.children.forEach(child -> {
            if (child instanceof PrintStatementContext) {
                visitPrintStatement((PrintStatementContext) child);
            } else if (child instanceof AssignmentContext) {
                visitAssignment((AssignmentContext) child);
            }
        });
        return null;
    }

    @Override
    public Object visitPrintStatement(PrintStatementContext ctx) {
        logger.finer("[visit] PrintStatement");
        var child = ctx.getChild(1);
        Object value = null;
        if (child instanceof ExpressionContext) {
            value = visitExpression((ExpressionContext) child);
        } else {
            value = currentSymtab.lookup(child.getText());
        }
        if (value != null) {
            System.out.println(value);
        } else {
            logger.finer("null");
        }

        return null;
    }

    @Override
    public Object visitAssignment(AssignmentContext ctx) {
        logger.finer("[visit] Assignment");
        var valueNode = ctx.getChild(2);
        Object value = null;
        if (valueNode instanceof ExpressionContext) {
            value = visitExpression((ExpressionContext) valueNode);
        } else {
            logger.finer("[visit] Assignment: valueNode is not supported: " + valueNode.getClass().getName());
        }
        var name = ctx.getChild(0).getText();
        if (currentSymtab.lookup(name) != null) {
            logger.finer("warning: " + name + " is already defined");
        }
        currentSymtab.set(name, value);
        logger.finer("set " + name + " to " + value);
        return null;
    }

    @Override
    public Object visitExpression(ExpressionContext ctx) {
        logger.finer("[visit] Expression");
        Object value = null;
        var child = ctx.getChild(0);
        if (child instanceof StringExpressionContext) {
            value = visitStringExpression((StringExpressionContext) child);
        } else if (child instanceof NumberExpressionContext) {
            value = visitNumberExpression((NumberExpressionContext) child);
        } else if (child instanceof BooleanExpressionContext) {
            value = visitBooleanExpression((BooleanExpressionContext) child);
        } else if (child instanceof TerminalNode) {
            value = currentSymtab.lookup(child.getText());
            if (value == null) {
                logger.finer("[visit] identifer: " + child.getText() + " is not defined or null");
            }
        } else {
            logger.finer("[visit] Expression: child is not supported: " + child.getClass().getName());
        }
        return value;
    }

    @Override
    public Object visitStringExpression(StringExpressionContext ctx) {
        logger.finer("[visit] StringExpression");
        var raw = ctx.getText();
        var value = raw.substring(1, raw.length() - 1);
        return value;
    }

    @Override
    public Object visitNumberExpression(NumberExpressionContext ctx) {
        logger.finer("[visit] NumberExpression");
        var raw = ctx.getText();
        var value = Integer.parseInt(raw);
        return value;
    }

    @Override
    public Object visitBooleanExpression(BooleanExpressionContext ctx) {
        logger.finer("[visit] BooleanExpression");
        var raw = ctx.getText();
        var value = Boolean.parseBoolean(raw);
        return value;
    }

}

Visitor 的设计说明

在 visitor 中，我们自上而下的访问 AST。

比如说，当访问到 program 的时候，我们就会访问他之后的这些 statement。当访问 statement 的时候就会访问之候的打印语句或者赋值语句。

以打印语句为例，我们会先取得表达式的值，然后通过 System.out.println 打印出来。

值得注意的是 ctx.getChild (2); 这种操作。例如，对于一个产生式：

assignment: ID '=' expression;

其 Children 分别为产生式头（assignment）右侧的各个符号，ID 编号为 0， '=' 编号为 1，expression 编号为 2. 这与他们在栈上的位置也是对应的。

assignment    :                     ID      '='    expression;
    |                                |       |        |
    |                                |       |        |
Assignment $$ = new Assignment((ID) $1, (Expression) $2);

符号表的相关操作

我们需要关心符号表的数据来源和去向：

来源：赋值语句
- 因此，在访问 Assignment 的时候，我们需要先取得赋值语句的左侧的字面量，作为符号的名称，取得右侧的值，作为符号的值，然后把这个符号放入符号表中。
- 并且，如果右侧的值是标识符，则需要查询这个标识符的值，将其拿过来作为左侧符号的值。
去向：打印语句、赋值语句。
- 赋值语句前面说过了。
- 打印语句，则访问到 PrintStatement 的时候，需要查询涉及的标识符的值，将其拿过来作为左侧符号的值。

在实际的强类型编程语言里，不可能全部都存成 Object 类型，这样的设计有隐患（尤其是参与运算的时候）。这就需要将值设计为一个 Symbol 类型，然后其下可以存储数据类型等元信息。

Interpreter 主类的设计

Interpreter 类负责 “驱动” 起整个流程。

src/com/less_bug/print/Interpreter.java 77:

package com.less_bug.print;

import org.antlr.v4.runtime.CommonTokenStream;

import java.io.IOException;
import java.util.logging.Logger;

import org.antlr.v4.runtime.CharStream;
import org.antlr.v4.runtime.CharStreams;

public class Interpreter {
    private static Logger logger;

    public static void main(String[] args) {

        initLogger();

        if (args.length == 0) {
            System.out.println("Usage: java Interpret <filename>");
            System.exit(1);
        }

        var filename = args[0];
        CharStream chstream;
        var abspath = new java.io.File(filename).getAbsolutePath();
        try {
            chstream = CharStreams.fromFileName(filename);
        } catch (IOException e) {
            System.out.println("Error: on reading" + abspath + ": " + e.getMessage());
            System.exit(1);
            return;
        }
        var lexer = new PrintLexer(chstream);
        var tokens = new CommonTokenStream(lexer);
        var parser = new PrintParser(tokens);

        parser.removeErrorListeners();
        parser.addErrorListener(PrintErrorHandler.INSTANCE);

        var program = parser.program();

        logger.fine(program.toStringTree());

        var visitor = new Visitor(logger);
        visitor.visitProgram(program);

    }

    private static void initLogger() {
        logger = Logger.getGlobal();

        var level = System.getProperty("print.logLevel");
        var formatter = new ColorFormatter();
        var handler = new java.util.logging.ConsoleHandler();
        if (level == null || level.isEmpty()) {
            logger.setLevel(java.util.logging.Level.OFF);
            return;
        }
        try {
            var loglevel = java.util.logging.Level.parse(level.toUpperCase());

            handler.setLevel(loglevel);
            logger.setLevel(loglevel);
        } catch (IllegalArgumentException e) {
            System.err.println("Error: invalid log level: " + level);
            System.exit(1);
        }

        handler.setFormatter(formatter);
        logger.setUseParentHandlers(false);
        logger.addHandler(handler);

        logger.info("Log level set to " + level);

    }
}

主类主要是进行一些初始化的 Wiring 工作。没什么可讲的。

日志格式化类

为了让日志更好看，我们需要一个日志格式化类。

src/com/less_bug/print/ColorFormatter.java 74:

package com.less_bug.print;

import java.util.logging.Formatter;
import java.util.logging.Level;
import java.util.logging.LogRecord;

public class ColorFormatter extends Formatter {

    // https://stackoverflow.com/questions/5947742/how-to-change-the-output-color-of-echo-in-linux

    public static final String RESET = "\u001B[0m";
    public static final String BLACK = "\u001B[30m";
    public static final String RED = "\u001B[31m";
    public static final String GREEN = "\u001B[32m";
    public static final String YELLOW = "\u001B[33m";
    public static final String BLUE = "\u001B[34m";
    public static final String PURPLE = "\u001B[35m";
    public static final String DARK_GRAY = "\u001B[90m";
    public static final String CYAN = "\u001B[36m";
    public static final String WHITE = "\u001B[37m";

    private String padding(String str, int n) {
        StringBuilder sb = new StringBuilder();
        sb.append(str);
        for (int i = str.length(); i < n; i++) {
            sb.append(" ");
        }
        return sb.toString();
    }

    private String getColor(Level level) {
        if (level.intValue() >= java.util.logging.Level.SEVERE.intValue()) {
            return RED;
        } else if (level.intValue() >= java.util.logging.Level.WARNING.intValue()) {
            return YELLOW;
        } else if (level.intValue() >= java.util.logging.Level.INFO.intValue()) {
            return BLUE;
        } else if (level.intValue() >= java.util.logging.Level.FINE.intValue()) {
            return WHITE;
        } else {
            return DARK_GRAY;
        }
    }

    @Override
    public String format(LogRecord record) {
        StringBuilder builder = new StringBuilder();
        builder.append(getColor(record.getLevel()));

        builder.append("[");
        builder.append(padding(record.getLevel().getName(), 8));
        builder.append("] ");

        builder.append(RESET);
        builder.append(record.getMessage());

        Object[] params = record.getParameters();

        if (params != null) {
            builder.append("\t");
            for (int i = 0; i < params.length; i++) {
                builder.append(params[i]);
                if (i < params.length - 1)
                    builder.append(", ");
            }
        }

        builder.append(RESET);
        builder.append("\n");
        return builder.toString();
    }

}

运行解释器

执行 make run 命令，就可以运行解释器了，输出如下：

hello, world!
false
100
hi
hi

更新于 Apr 16, 2022 18:30 CST

Flex & Bison 实战：一个简单计算器

HBase、ZooKeeper 集群部署及实践

如果有任何问题或者需要反馈文章的错误，欢迎您在此评论。