作业

编译原理大作业提要

jxtxzzw · 10月11日 · 2019年 · 68次已读

这是第一篇提要,也可能是最后一篇,我不知道后面还有没有。因为这次作业比较复杂,可能后面我写着写着就会去改前面的东西,所以没法一边 coding 一边 blogging,但是等到我全部做完,估计也没有时间去重现整个过程。

作业要求其实可以分为这么几个步骤:

  1. 读入 CX 代码,各种词法分析、语法分析,把源代码变成一棵抽象语法树。
  2. 遍历抽象语法树,依次翻译为 p-code。
  3. (如果必要,修改 Pmachine 语法并重新编译后,)将 p-code 运行在 Pmachine 上。

我不可能从零开始讲怎么自上而下、自下而上地构建语法书,这个太花时间了,所以有些地方我默认你已经掌握,我会简单说,但是所有必要的地方我都会提及。

首先假设你已经有了一棵抽象语法树 AST。

那么,如果存在一种遍历方法,能够以此访问各个节点,只需要在访问特定节点的时候输出一些东西即可。

例如对于 100+200 这个表达式,要变成 p-code,只需要先把 100 入栈,即 ldc i 100(压入一个整数 100),再把 200 入栈,即 ldc i 200,然后将栈顶的两个元素(出栈并)做整数的加法,得到的结果存放在栈顶,即 add i

因此,如果在遍历这个部分的时候,程序能够输出 ldc i 100\n ldc i 200\n add i\n 就完成任务了。

为了把问题说清楚,不妨假设我们现在已经存在了一个 Visitor,这个 Visitor 会依次遍历 AST,并且保证一定的访问次序(例如,加法是左结合的访问顺序),然后在遍历到不同的成分的时候,执行不同的函数,例如它在遍历到当前是数字的时候,就会执行 visitNumber(),它在执行到表达式的时候,就会执行 visitCalc()

至于这个 Visitor 怎么来的,后面再说。

如上文说的,在遍历到数字 x 的时候,期望的结果就是输出一个“把当前数字 x 压入栈顶”的 p-code 代码,于是,输出 ldc i ctx.NUM().getText() 即可。

在下面这段代码中,visitNumber() 就是做了这件事情,从上下文中获取当前数字的内容,然后按格式输出。

需要说明的是,这里只是为了说明问题,所以遇到数字就直接 System.out.println() 了,也没有在意返回值的事情,直接 return ""

@Override public String visitNumber(ExpressionTestParser.NumberContext ctx) {
        System.out.println("ldc i " + ctx.NUM().getText());
        return "";
    }

类似的,有:

@Override public String visitCalc(ExpressionTestParser.CalcContext ctx) {
        visit(ctx.expr(0));
        visit(ctx.expr(1));
        switch (ctx.op.getType()) {
            case ExpressionTestParser.ADD:
                System.out.println("add i");
            break;
            case ExpressionTestParser.SUB:
                System.out.println("sub i");
                break;
            case ExpressionTestParser.MUL:
                System.out.println("mul i");
                break;
            case ExpressionTestParser.DIV:
                System.out.println("div i");
                break;
        }
        return "";
    }

这里需要说明的有 2 个部分。

一,由于左右表达式可能分别为嵌套了的子表达式,所以需要依次遍历左右子表达式并输出他们的代码。

二,ctx.op 是运算符,根据运算符的不同,进入一个分支判断,决定输出最后一行的运算代码。

这样一来,我们就可以在 Main 函数简单的写上:

Visitor v = new Visitor();;
v.visit(tree);
System.out.println("hlt");

运行,输入表达式 120+330+50,然后构造抽象语法树,并调用上面的 Main 函数,可以发现输出了

ldc i 120
ldc i 330
add i
ldc i 50
add i

最后我加上了 out ihlt 分别输出结果和停止程序。

将输出的内容保存到 1.p 并用 Pmachine 执行,得到如图所示的结果。

看到输出了正确的结果 500。

现在的关键在于怎么实现这个访问的过程。

所谓的访问过程,包括抽象语法树的建立,以及遍历并输出代码的部分。

问题一个个解决。

我是用 Java 写的,但其实没有用到什么特性,如果你硬要说类的话,C++ 也可以写类,甚至你可以用 C 的结构体来作为一个个类。因此,你用 C 还是 C++ 什么的,也完全是 OK 的。不过有一个坑我已经踩过了,别用 JavaScript。

首先定义一个接口,Statement,这个接口有一个默认的方法 compile(),他接受一个 ParseTree 表示当前的语句,返回一个 String 表示编译后的代码。

public interface Statement {
    String compile();
}

解释一下 tree。

你可以把 tree 当做一个数据结构,对于非叶子节点,tree 表示当前的根,它有一个或多个孩子,孩子可能是叶子节点也可能是非叶子节点,对于叶子节点,可以把它当做终结符。

需要指出的是,可以当做终结符的具体含义是,如果当前根拥有 3 个孩子,分别是 INTEGER、ADD、INTEGER,显然这是一个 x+y 的表达式,但是在语法定义中,ADD 是 “+” 是一个终结符,而 INTEGER 事实上可以继续被展开成 (+|-)?[1-9]\d*,但是由于 INTEGER 的含义过于直白,就把它当做一个终结符也没事。

我保证了 tree 至少有 2 个成员函数,一个是 getChildCount(),返回孩子个数,一个是 getChild(int x) 表示获取第 x 个孩子。事实上它还有其他便于 coding 的方法,不过最主要的还是这两个。

其次,Expression 是一个抽象类,它实现了 Statement 接口,这意味着表达式也可以通过 compile() 方法得到编译后的代码。除此之外,它还有一个 BaseType,表示表达式的类型,是 int 还是 boolean 等,这是为了之后做表达式的运算的时候,要保持类型一致。

BaseType 在这里是一个自己定义的类,由 String nameString code 组成,其中 name 表示类型的名字,是 human-readable 的,例如 int,而 code 表示类型的 p-code 代码,例如 int 对应的就是 i

我没想好到底 BaseType 还要不要一个 size,看需要就加吧。

Expression 类还可以增加一些其他的成员,例如 ParseTree,这个可以看具体是什么表达式,具体做什么拓展。这个下面会说到。

abstract class Expression implements Statement {

    private BaseType baseType;

    Expression(BaseType baseType) {
        this.baseType = baseType;
    }

    public BaseType getBaseType() {
        return baseType;
    }
}
public class BaseType {
    private String name;
    private String code;

    public BaseType(String name, String code) {
        this.name = name;
        this.code = code;
    }

    public String getCode() {
        return code;
    }

    public String getName() {
        return name;
    }
}

我在 Expression 下新定义了一个子类叫做 ArithmeticExpression,这是算数表达式,它继承了 Expression。

显然,构造的时候需要保留一个 BaseType 并记录 ParseTree。由于我这里只是做一个简单的提要,就默认只算 int 吧,那于是 baseType 就是 new BaseType("int", "i");

另外需要 @Override 那个 compile() 方法。

在继续之前,现在需要梳理一下了———我们有了一个接口 Statement,一个抽象类 Expression,一个类 ArithmeticExpression。

那我现在想要处理赋值表达式应该怎么办呢?没错,从 Expression 派生出一个 AssignmentExpression 子类。

那我现在想要处理变量怎么办呢?一种可能的做法是,定义一个抽象类 Variable 实现 Statement 接口。我没想好,可能会搞一个 Declaration 的抽象类。

由于都是实现了 Statement 接口,所以只需要为每一个类分别实现属于自己的 compile() 就可以了。

写到这里的时候我意识到,Statement 和 Declaration 好像是平行的。而且接口的名字应该像 Comparable 这样,那这个接口就应该叫做 Compilerable?

算了,以后再考虑这些 Clean Code。

有了这些类,我们就可以做一些事情了。

定义一个类叫做 Program,这个 Program 就是我们的程序,那么它应该要做两件事情。

第一件事情,读输入,并构造抽象语法树。

public void buildAbstractSyntaxTree(ParseTree tree) {
        for (int i = 0; i < tree.getChildCount(); i++) {
            statements.add(AbstractSyntaxTree.buildStatement(tree.getChild(i)));
        }
    }

第二件事情,遍历抽象语法树,并输出编译后的 code。

private void generateCode() {
    for (Statement statement : statements) {
        code.append(statement.compile());
    }
}

public String outputCode() {
    this.generateCode();
    return code.toString();
}

这两段代码都是自解释的,想必不需要再详细说明了。

需要注意的是,由于 buildStatement 接受的是一个 tree,而返回值是 Statement 接口,因此,直接加到 ArrayList 就可以了。而又由于这个 list 中所有的元素都是可以 compile() 的,所以输出代码也变得非常简单。

如果有了这样一个类,那么主函数就变得非常简单。

假设我们已经得到了一个 ParseTree,那么只需要简单的 3 句就可以完成整个编译过程。

Program p = new Program();
p.buildAbstractSyntaxTree(tree);
System.out.println(p.outputCode());

于是,你发现了,所有的重头戏,其实只剩下了如何定义那些类,以及,每一个类的 compile() 具体应该怎么写。

我下面就以 ArithmeticExpression 为例,简单说说。

定义一个简单的语法 ExpressionTest。

        grammar ExpressionTest;
        r: expr;
        expr: expr op expr # arithmetic
            | NUM # number
            ;
        op: ADD | SUB | MUL | DIV;
        NUM: INT;
        INT: [0-9]+;
        ADD: '+';
        SUB: '-';
        MUL: '*';
        DIV: '/';
        WS: [ \t\r\n]+ -> skip;

这段语法应该也写的非常简单了,规则是 expr,expr -> expr op expr | NUM。

其中 op 是加减乘除,分别对应四个符号。NUM 在这里只表示 INT,INT 是 [0-9]+。

跳过所有的 WhiteSpace。

注意这段是不完备的,应该还要加很多东西。

语法清晰了以后,可以去定义 ArithmeticExpression 这个类了,构造函数与上文说的一样。

ArithmeticExpression(BaseType baseType, ParseTree tree) {
        super(baseType);
        this.tree = tree; // TODO: do we really need the whole tree? or can just use built expression
    }

注意这里的一个 TODO:是不是需要保留整个 ParseTree?这个问题我留到下面再讨论,不过我觉得到目前为止,我想表达的意思已经传达的够清楚了。

另外还有一个 compile()

@Override
    public String compile() {
        String code = "";
        // TODO: use recursively build here, 'cause we can just compile 1+2 but not 1+2+3 now
        code += "ldc i " + tree.getChild(0).getText() + "\n";
        code += "ldc i " + tree.getChild(2).getText() + "\n";
        // TODO: better change the String compare to token == in lexer
        ParseTree token = (ParseTree) tree.getChild(1).getPayload();
        switch (token.getText()) {
            case "+":
                code += "add i \n";
                break;
            case "-":
                code += "sub i \n";
                break;
            case "*":
                code += "mul i \n";
                break;
            case "/":
                code += "div i \n";
                break;
            // TODO: default branch
        }
        return code;
    }

首先这里也是非常简陋的,初始化 code = "" 后,先后输出 idc i 开头的左右表达式的值。

需要指出的是,这里应该是要递归地访问左右子表达式,即,build,而不是直接输出,否则就会把 100+200+300 输出成 ldc i 100+200\n ldc i 300\n add i\n 这个样子。

在输出了左右子表达式的代码以后,就要对此进行运算了,于是,通过判断 token 的类型,决定输出 add 还是 sub 或者其他。

需要指出的是,这里为了说明问题,直接判断了 getText() 是不是 +-*/。其实最好的做法,应该是这里获取 token.getType(),并判断其值是不是等于 ExpressionTestLexer.ADD 或者 ExpressionTestLexer.DIV 之类的。这样的话在修改语法以后,不需要修改这里的代码,实现了松耦合。

另外,这里完全没有做出错处理,常见的出错处理有,左右子表达式类型不一致的时候,抛出异常,运算符进入 default branch 的时候,抛出异常……

问题涉及到变量的时候会更加复杂——变量未定义?未初始化?那就会有更多的异常。

所以简单小结一下,这段 demo 的问题还有:

  1. 左右子表达式需要递归地访问。
  2. 需要使用 token 的 type 来确定运算符。
  3. 出错处理。

如果你看到这里都能完全理解,那么,我们可以继续往下了,否则,建议你重新读一遍上面的内容。

先来解决上面这三个问题。简单说一下思路。

第一个,派生一个 ConstantExpression 子类。可以判断 childCount 是不是等于 3,如果是,则对左右子表达式分别 buildArithematicExpression,否则判断是不是等于 1,如果是等于 1,直接 buildConstantExpression,buildConstantExpression 的时候的 compile() 就是返回 getText()

第二个,直接把 op 当做终结符 OP,并直接把 ADD|SUB 写在语法规则中。

第三个,勤判断,勤抛异常。

最后,在 Test.java 里面,我们只需要简单的把输入 input,依次经过词法分析、语法分析,然后,直接用 Program 来 build 和 compile 即可。

ParseTree tree = parser.r();
Program p = new Program();
p.buildAbstractSyntaxTree(tree);
System.out.println(p.outputCode());

具体来说,在我拿到一个 tree 的时候,我判断它孩子的个数,如果是 3 个孩子,说明他是一个算数表达式,否则,他是一个常数表达式。

if (tree.getChildCount() == 3) {
    return buildArithmeticExpression(tree);
} else if (tree.getChildCount() == 1) {
    return buildConstantExpression(tree);
}

ArithmeticExpression 的定义如上文。ConstantExpression 的定义是类似的,构造的时候接受一个 tree,而 compile() 则输出 ldc i X 的形式。

public class ConstantExpression extends Expression {
    private ParseTree tree;

    ConstantExpression(BaseType baseType, ParseTree tree) {
        super(baseType);
        this.tree = tree;
    }

    @Override
    public String compile() {
        return "ldc " + getBaseType().getCode() + " " + tree.getChild(0).getText() + "\n";
    }
}

在上面的代码中,我们的 buildArithmeticExpression 是直接做了这样一件事情,那就是 new ArithmeticExpression(baseType, tree)。

并且我留下了一个疑问:是不是需要保留整个 ParseTree?

现在我们把这件事情想的透彻一点,保留整棵树是不是必要的?有没有可能只保留左右子表达式就够了,而且会更容易操作?

尝试修改定义:

public class ArithmeticExpression extends Expression {

    private Expression leftExpression;
    private Expression rightExpression;
    private Token token;

    ArithmeticExpression(BaseType baseType, Expression leftExpression, Expression rightExpression, Token token) {
        super(baseType);
        this.leftExpression = leftExpression;
        this.rightExpression = rightExpression;
        this.token = token;
    }
}

如此一来,就能够把 Arithmetic 和 Constant 区分开了。

在 AST 中,只提供一个公共的方法:

public class AbstractSyntaxTree {
    public static Statement buildStatement(ParseTree tree) {
        // TODO: token validation + decide the switch
        return buildExpression(tree);
    }
}

其余的都是私有的方法。

private static Expression buildExpression(ParseTree tree) {
        // TODO: token validation + decide the switch
        if (tree.getChildCount() == 3) {
            return buildArithmeticExpression(tree);
        } else if (tree.getChildCount() == 1) {
            return buildConstantExpression(tree);
        }
        return null;
    }

    private static ArithmeticExpression buildArithmeticExpression(ParseTree tree) {
        Expression leftExpression = buildExpression(tree.getChild(0));
        Expression rightExpression = buildExpression(tree.getChild(2));
        if (!(tree.getChild(1).getPayload() instanceof Token)); // TODO exception here
        Token token = (Token) tree.getChild(1).getPayload();
        return new ArithmeticExpression(new BaseType("int", "i"), leftExpression, rightExpression, token);
    }

    private static ConstantExpression buildConstantExpression(ParseTree tree) {
        return new ConstantExpression(new BaseType("int", "i"), tree);
    }

首先,buildStatement 在我目前所涉及的语法中,只会进入 buildExpression

而进入了表达式的构造,就需要判断孩子的个数。

如果是只有一个孩子,那么进入 buildConstantExpression,如上文,直接 new 一个对象即可。

如果有 3 个孩子,首先要递归 build 第 0 和第 2 个孩子,用的是 buildExpression 这个方法,之后判断第 1 个孩子是不是加减乘除,如果是,就把 token 和刚才 build 出来的 Expression 一起 new 一个 ArithmeticExpression 出来,如果不是,那么就进入出错处理,例如,三个孩子是 10、20、30,而不是 10、+、20。

之后如果想要再加别的表达式,例如赋值表达式怎么办?

赋值表达式也是有 3 个孩子:左边的是被赋值的变量,中间的是赋值号,右边的是一个(不知道是什么也许是 Arithmetic 也许是 Constant 也许是其他的 Expression 的子类的)表达式。

但是这并不妨碍我们修改 buildExpression 的代码,通过这样的方式依然可以唯一确定具体的类型,并且出错处理是完备的:

if (tree.getChildCount() == 3) {
    if (!(tree.getChild(1).getPayload() instanceof Token)); // TODO exception here
    Token token = (Token) tree.getChild(1).getPayload();
    if (token.getType() == ExpressionTestLexer.ASSIGN)
        return buildAssignmentExpression(tree);
    else
        return buildArithmeticExpression(tree);
} else if (tree.getChildCount() == 1) {
    return buildConstantExpression(tree);
}

为了文章的完整性,这里给出 AssignmentExpression 类的定义和 buildAssignment 的实现。

private static AssignmentExpression buildAssignmentExpression(ParseTree tree) {
        Expression expression = buildExpression(tree.getChild(2));
        System.out.println(expression);
        return new AssignmentExpression(new BaseType("int", "i"), expression);
    }
private Expression expression;
    AssignmentExpression(BaseType baseType, Expression expression) {
        super(baseType);
        this.expression = expression;
    }

    @Override
    public String compile() {
        String code = expression.compile();
        code += "str " + getBaseType().getCode() + " 0 " + "get_var_address_placeholder" + "\n";
        return code;
    }

但是请注意,类似 get_var_address_placeholder 这样的内容还需要你们自己去发挥了哦。

现在,请回过头再看一眼这段代码,是不是觉得足够简单了呢?

最后我来说一下符号表。

函数的部分我还没想好怎么写。

Symbol 类比较简单,需要有一个标识符,需要有一个类型,可能还需要一个 size,为今后数组做打算,至于 address 要不要,没想好。

package com.jxtxzzw.compiler.st;

import com.jxtxzzw.compiler.type.BaseType;

public class Symbol {
    private String identifier;
    private BaseType beseType;
    private int address;

    public Symbol(String identifier, BaseType beseType, int address) {
        this.identifier = identifier;
        this.beseType = beseType;
        this.address = address;
    }

    public String getIdentifier() {
        return identifier;
    }

    public BaseType getBeseType() {
        return beseType;
    }

    public int getAddress() {
        return address;
    }

}

接下来看一眼作用域 Scope。

    private Scope parent;
    private int allocated;
    private HashMap<String, Symbol> symbols = new HashMap<>();
    private ArrayList<Scope> scopes = new ArrayList<>();

目前我给了 4 个成员。

不论何时,new 一个新的作用域的时候,一定会有一个唯一的,永远不会变的 parent,所以构造函数只接受一个 parent,newScope() 方法是在当前作用域下开一个子作用域。

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

public Scope openScope() {
    Scope scope = new Scope(this);
    scopes.add(scope);
    return scope;
}

对于 Global 的 Scope,我定义 parent 为 null,于是有:

private int level() {
        int level = 0;
        while (parent != null) {
            level++;
            parent = parent.parent;
        }
        return level;
    }

之后就是一些很显然的方法了,例如计算一共分配了多少内存?即返回 allocated。如果有新的符号被加入,则更新 allocated。

插入和查询符号我用了 HashMap,所以直接 get 和 containsKey 就可以了。如果手动实现的话,大不了一个遍历数组,然后不在就返回 null 嘛。

    public void addSymbol(Symbol symbol) {
        symbols.put(symbol.getIdentifier(), symbol);
    }

    public Symbol getSymbol(String identifier) {
        return symbols.get(identifier);
    }

    public boolean containsSymbol(String identifier) {
        return symbols.containsKey(identifier);
    }

在 SymbolTable 里面,定义一个全局的 Scope,然后开始做事。

梳理一下 CX 的语法规则。

语言最开始就是一对大括号,语句写在大括号里面,所有的 Declaration 都在 Statement 之前。

变量的作用域只在当前的大括号,出了大括号则失效。

大括号中嵌套的大括号可以继续定义变量,定义的变量作用域只在那个大括号中。

如果内层大括号出现外层大括号同名的变量,则在内层大括号使用内层的定义,在内层大括号以外的外层大括号区域使用外层的定义。

于是,一个简单的思路就诞生了:遇到大括号,则开始往 SymbolTable 加符号。

遇到一个符号,看是不是已经存在 containsSymbol,决定是给错误,还是 addSymbol。

重复上面的过程,直到遇到 Statement。

在处理过程中如果遇到嵌套的大括号,则在当前层开启新的 Scope,并重复上面的过程。

由于 containsSymbol 这样的操作是 Scope 的成员函数,所以自然的被限定在了作用域中,不需手动处理同名变量的问题了。

遇到大括号结束的时候,关闭 Scope。关闭的操作指的是 scope = scope.parent

在查询变量的时候,在当前 scope 查找,如果有,get,否则,向上一层,直到最近原则找到。如果 parent 为 null 还找不到,说明使用了未定义的变量,直接报错。

说完了所有的思路,给一个福利。

我给你们看一下我目前的项目结构。

因为还没做完,而且有些地方没有想明白,所以可能以后会改也说不定。

但是如果你只想继续往下做,那么,你只需要继续增加新的子类,并且扩充 buildStatement() 就可以了。

test 是我用了 Junit 来跑测试的,免得每次手动测试了。

最后提醒一下:如果你打算用 LEX 和 YACC,建议你先去了解清楚。因为一旦 LEX 和 YACC 帮你做的事情有点多了以后,可能你只能按照它的思路继续往下写,你可能用不了我的思路了。

0 条回应