编译原理——变量！

2019-10-22 本文已影响0人 madao756

前言：我们要到编译原理比较难的地方了，我们开始在我们的语言 Lox 中，实现「变量」！

0X00 基本原理

这是我们实现的第三个语句，所以我们要更新程序的「上下文无关文法」

program     → declaration* EOF ;

declaration → varDecl
                            | statement;

statement   → exprStmt
                           | printStmt;

注意这个：declaration 申明的是全局变量

之前的文法在这里：https://www.jianshu.com/p/9e4cff9f4594

然后我们再写出 varDecl 的文法：

varDecl → "var" IDENTIFIER ( "=" expression )? ";" ;

同时我们能够操纵 identifier 了，所以我们要更新 primary 的文法：

primary → "true" | "false" | "nil"
                     | NUMBER | STRING
                     | "(" expression ")"
                     | IDENTIFIER ;

至此，配合上代码，我们就能从 token 流中识别出，声明变量的操作。接下来我们需要学习「变量」及「作用域」的实现原理。

环境（environment）

「标识符」和「标识符值」的「联系」需要保存在某个地方，我们把这个地方叫做「环境（environment）」

这个「环境」我们用 HashMap 实现，完成 String（标识符名字）到 Object 之间的映射

赋值（Assignment）

首先我们写出 Assignment 的语法：

expression → assignment ;
assignment → IDENTIFIER "=" assignment
                            | equality ;

注意这里有一个复杂左值的问题：a.b.c = 2，这样的问题，在后面解决。

这里仅仅处理了连等，

块作用域（Slope）

{
  var a = "first";
  print a; // "first".
}

{
  var a = "second";
  print a; // "second".
}

这里有两个作用域。

当然还有嵌套的作用域：

{
  var a = "first";
    {
        var a = "second";
        print a; // "second".
    }
  print a; // "first".
}

为了识别这样的作用域，我们又得修改相关 {} 的「文法」

statement → exprStmt
                          | printStmt
                          | block ;

block     → "{" declaration* "}" ;

有了块的概念以后，我们来说如何实现，作用域之间变量的隔离：

当我们访问块（block）中的每个语句时，生成新的环境，记录所有在块中声明的变量
生成新的环境的时候，要把当前环境传进去，构成一个作用域链，遍历整个作用域链查找与赋值
当我们离开块（block）的时候，要删除掉新的环境

这仅仅解决了，变量的隔离，还需要跟踪「作用域链」，查找变量。具体实现可以看后面的代码！

0X01 代码实现

全局变量

我们首先写出「环境」的定义：


public class Environment {
    private final Map<String, Object> values = new HashMap<>();

    void define(String name, Object value) {
        values.put(name, value);
    }

    Object get(Token name) {
        if (values.containsKey(name.lexeme)) {
            return values.get(name.lexeme);
        }

        throw new RuntimeError(name, "Undefined variable '" + name.lexeme + "'.");
    }

HashMap 记录 token 名字与值的映射。

然后我们通过文法写出：声明变量「抽象语法树」的格式

// 
static class Var extends Stmt {
    Var(Token name, Expr initializer) {
        this.name = name;
        this.initializer = initializer;
    }

    <R> R accept(Visitor<R> visitor) {
        return visitor.visitVarStmt(this);
    }

    final Token name;
    final Expr initializer;
}

将 token 按照上述格式生成语句：

private Stmt varDeclaration() {
    // varDecl → "var" IDENTIFIER ( "=" expression )? ";" ;
    // 返回变量声明抽象语法树
    Token identifier = consume(IDENTIFIER, "after 'var' must be an Identifier");
    Expr initializer = null;

    if (match(EQUAL)) {
        initializer = expression();
    }
    consume(SEMICOLON, "Expect ';' after value.");
    return new Stmt.Var(identifier, initializer);
}    

private Stmt declaration() {
    // 在这里抓错误
    try {
        if (match(VAR)) {
            return varDeclaration();
        }
        return statement();
    } catch (ParseError e) {
        // 进入 panic mode
        synchronize();
        return null;

    }
}

什么是「恐慌模式」：

当 parser 的过程出错的时候，不着急退出当前程序，而是尽快退出当前语句的 parse 进入下一个语句的 parse。


    private void synchronize() {
        // 从当前语句中退出
        // 去生成其他语句的「抽象语法树」
        advance();

        while (!isAtEnd()) {
            if (previous().type == SEMICOLON)
                return;

            switch (peek().type) {
            case CLASS:
            case FUN:
            case VAR:
            case FOR:
            case IF:
            case WHILE:
            case PRINT:
            case RETURN:
                return;
            }

            advance();
        }
    }

最后执行「抽象语法树」也就是在「环境」中建立映射：

    @Override
    public Void visitVarStmt(Stmt.Var stmt) {
        // 给 environment 中的变量赋值
        String tokenName = stmt.name.lexeme;
        Expr expr = stmt.initializer;
        if(expr == null) {
            environment.define(tokenName, null);
            return null;
        }
        Object value = evaluate(expr);
        environment.define(tokenName, value);
        return null;
    }

给全局变量赋值

第一步：通过文法写出：「抽象语法树」的格式

    static class Assign extends Expr {
        Assign(Token name, Expr value) {
            this.name = name;
            this.value = value;
        }

        <R> R accept(Visitor<R> visitor) {
            return visitor.visitAssignExpr(this);
        }

        final Token name;
        final Expr value;
    }

第二步：生成「抽象语法树」


    private Expr assignment() {
        // assignment → IDENTIFIER "=" assignment
        // | equality;
        // 左值可能需要计算我们先跳过计算左值
        Expr expr = equality();

        if (match(EQUAL)) {
            Token equal = previous();
            Expr value = assignment();
            // expr 通过递归，应该得到是一个 Variable，不应该是其他的别的东西
            // 否则报错
            if (expr instanceof Expr.Variable) {
                Token name = ((Expr.Variable) expr).name;
                return new Expr.Assign(name, value);
            }

            error(equal, "Invalid assignment target.");

        }
        return expr;
    }

第三步：执行「抽象语法树」


    @Override
    public Object visitAssignExpr(Expr.Assign expr) {
        // Assign 的表达式是
        // Assign(Token name, Expr value)
        // 顺着作用域链给 Environment 中的「变量」赋值
        Token token = expr.name;
        Object value = evaluate(expr.value);

        environment.assign(token, value);

        return value;
    }

块作用域

同样第一步是：通过文法写出「抽象语法树」的格式

但是直接看文法有点看不懂，我来解释一下：


declaration → varDecl
                            | statement;
statement → exprStmt
                          | printStmt
                          | block ;

block     → "{" declaration* "}" ;

block 就是多个 declaration 的结合。

    static class Block extends Stmt {
        Block(List<Stmt> statements) {
            this.statements = statements;
        }

        <R> R accept(Visitor<R> visitor) {
            return visitor.visitBlockStmt(this);
        }

        final List<Stmt> statements;
    }