乐者为王

Do one thing, and do it well.

ANTLR 4权威参考读书笔记(28)

  • scope 作用域

为了阐明Cymbol语法是可复用的,本节中我们将在不做修改的基础上再次使用它,用于构建一个完全不同的应用。不仅如此,我们还会在同样的树上使用两个不同的监听器做两次遍历。

验证程序符号的使用情况

为Cymbol这样的编程语言构建解释器、编译器或者转换器,我们需要验证Cymbol程序是否正确地使用符号(标志符)。接下来,我们将构建一个Cymbol验证器用于检查以下的条件:

  • 可见的变量引用有相应的定义(在作用域内)。
  • 函数引用有相应的定义(函数可以以任何顺序出现)。
  • 变量不作为函数使用。
  • 函数不作为变量使用。

让我们看一下有许多不同引用的Cymbol示例代码,其中有些是无效的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int f(int x, float y) {
    g();      // forward reference is ok
    i = 3;    // no declaration for i (error)
    g = 4;    // g is not variable (error)
    return x + y;    // x, y are defined, so no problem
}
void g() {
    int x = 0;
    float y;
    y = 9;    // y is defined
    f();      // backward reference is ok
    z();      // no such function (error)
    y();      // y is not function (error)
    x = f;    // f is not a variable (error)
}

为验证程序中的一切都没问题,根据前面的条件,我们应该打印出函数列表和本地变量以及全局符号列表(函数和全局变量)。更进一步,当我们发现问题时应该给出一个错误。例如,使用上述输入,让我们构建一个称为CheckSymbols的应用。

1
java CheckSymbols vars.cymbol

在执行以上命令后会生成如下输出:

1
2
3
4
5
6
7
8
9
10
locals:[]
function<f:tINT>:[<x:tINT>, <y:tFLOAT>]
locals:[x, y]
function<g:tVOID>:[]
globals:[f, g]
line 3:4 no such variable: i
line 4:4 g is not a variable
line 13:4 no such function: z
line 14:4 y is not a function
line 15:8 f is not a variable

实现这类问题的关键是一个被称为符号表的相应的数据结构。我们的应用会把符号存在符号表中,然后通过在符号表中查找符号引用检查它们的正确性。在接下来的部分,我们将大概看一看数据结构看起来像什么,并且使用它去解决手头的验证问题。

符号表中的速成课

语言实现者通常称持有符号的数据结构为符号表。语言的实现决定符号表的结构和复杂性,如果一门语言允许相同的标志符在不同的上下文中指向不同的东西,符号表会将那些符号分组到不同的作用域中。作用域只是一组符号,例如函数的参数列表或变量列表以及在全局作用域内的函数。

符号表自身只是一个符号定义的存储库——它不作任何检查。为了验证代码,我们需要检查表达式中违反我们之前设置的规则的变量和函数引用。符号验证有两个基本操作:定义符号和解决符号。定义一个符号意味着把它添加到一个作用域中。解决一个符号意味着计算出符号指向哪个定义。在某种程度上,解决一个符号意味着找到最近的匹配定义。最近的作用域是最近的封闭作用域。例如,让我们看看另一个Cymbol例子,它在不同的作用域有符号定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
int x;
int y;
void a()
{
    int x;
    x = 1;
    // x resolves to current scope, not x in global scope
    y = 2;
    // y is not found in current scope, but resolves in global
    { int y = x; }
}
void b(int z)
{ }

全局作用域包含变量x和y以及函数a()和b()。函数处于全局作用域,但它们也构成新的作用域用于持有函数的参数,如果有的话。同样嵌套在函数作用域内的是函数本地代码块,它们构成另一个新的作用域。本地变量被约束在嵌套在函数作用域内的本地作用域内。

因为符号x被定义了两次,所以做不到仅把所有标识符都填充进单个集合而没有冲突。这也是作用域出现的原因。我们保留一组作用域,并且一个作用域中的每个标志符只允许有单个定义。我们还保留一个指向父作用域的指针,以便在外层作用域中找到符号定义。这些作用域形成了一棵树。

沿着从任何作用域到根(全局作用域)的路径的所有节点形成一堆作用域。为了找到一个符号的定义,我们从围绕着引用的作用域开始,并沿着作用域树向上遍历,直到找到它的定义。

验证器架构

开始构建验证器前,先让我们思考下大方向和总体策略。我们可以根据关键操作——定义和解决——把问题分解。对于定义,我们需要侦听变量和函数定义事件,然后把符号对象插入围绕着定义的作用域。在函数定义的开始处,我们需要压栈一个新的作用域,然后在函数定义的结尾处把它出栈。

为解决和检查符号引用,我们需要侦听在表达式中的变量和函数名字引用。针对每个引用,我们将验证是否有匹配的定义,以及引用是否正确使用符号。

这似乎很直截了当,但有个并发症:在源码文件中,Cymbol程序可以调用在它之后定义的一个函数。我们称它为前向引用。为支持这个特性,我们需要在语法分析树上执行两次遍历。第一遍,或者阶段,定义包含函数的符号,然后第二遍进行解决。用这种方法,第二遍可以看到文件中的所有函数。以下是用于触发在语法分析树上两次遍历的代码:

1
2
3
4
5
6
ParseTreeWalker walker = new ParseTreeWalker();
DefPhase def = new DefPhase();
walker.walk(def, tree);
// create next phase and feed symbol table info from def to ref phase
RefPhase ref = new RefPhase(def.globals, def.scopes);
walker.walk(ref, tree);

在定义阶段,我们将创建许多作用域。除非我们保持对它们的引用,否则垃圾收集器会回收它们。为了符号表能够度过从定义到解决阶段的转变,我们需要追踪这些作用域。储存它们最合乎逻辑的地方是在语法分析树本身(或者,从技术上讲,使用关联值与树节点的注解映射)。然后引用阶段就可以在它下行语法分析树时很简单地获得当前作用域的指针。与函数和本地块关联的树节点将可以获得它们的作用域的指针。

定义和解决符号

考虑到我们的基本策略,让我们从DefPhase开始构建我们的验证器。这个阶段类需要3个字段:一个全局作用域的引用、一个用于追踪我们创建的作用域的语法分析树注解器,以及一个当前作用域的指针。enterFile()的监听器代码在活动开始时创建全局变量。当活动结束时,exitFile()负责打印结果。

1
2
3
4
5
6
7
8
9
10
11
public class DefPhase extends CymbolBaseListener {
    ParseTreeProperty<Scope> scopes = new ParseTreeProperty<Scope>();
    GlobalScope globals;
    Scope currentScope;    // define symbols in this scope
    public void enterFile(CymbolParser.FileContext ctx) {
        globals = new GlobalScope(null);
        currentScope = globals;
    }
    public void exitFile(CymbolParser.FileContext ctx) {
        System.out.println(globals);
    }

当语法分析器找到函数声明时,应用需要创建一个FunctionSymbol对象。作为一个符号和作为一个包含参数的作用域,FunctionSymbol对象负有双重责任。为把函数作用域嵌套在全局作用域内,我们需要把函数作用域压栈。我们通过设置函数的封闭作用域为当前作用域并重置当前作用域来做到这点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    String name = ctx.ID().getText();
    int typeTokenType = ctx.type().start.getType();
    Symbol.Type type = CheckSymbols.getType(typeTokenType);

    // push new scope by making new one that points to enclosing scope
    FunctionSymbol function = new FunctionSymbol(name, type, currentScope);
    currentScope.define(function);    // Define function in current scope
    saveScope(ctx, function);         // Push: set function's parent to current
    currentScope = function;          // Current scope is now function scope
}

void saveScope(ParserRuleContext ctx, Scope s) {
    scopes.put(ctx, s);
}

方法saveScope()使用函数作用域注解functionDecl规则节点,以便在随后的引用阶段可以获得它。当我们离开函数时就出栈函数作用域,因此当前作用域仍然是全局作用域。

1
2
3
4
public void exitFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    System.out.println(currentScope);
    currentScope = currentScope.getEnclosingScope();    // pop scope
}

本地作用域以类似的方式工作。我们在监听器方法enterBlock()中压栈一个作用域,然后在exitBlock()中出栈它。

在处理好作用域和函数定义后,我们就可以开始定义参数和变量。

1
2
3
4
5
6
7
8
9
10
11
12
public void exitFormalParameter(CymbolParser.FormalParameterContext ctx) {
    defineVar(ctx.type(), ctx.ID().getSymbol());
}
public void exitVarDecl(CymbolParser.VarDeclContext ctx) {
    defineVar(ctx.type(), ctx.ID().getSymbol());
}
void defineVar(CymbolParser.TypeContext typeCtx, Token nameToken) {
    int typeTokenType = typeCtx.start.getType();
    Symbol.Type type = CheckSymbols.getType(typeTokenType);
    VariableSymbol var = new VariableSymbol(nameToken.getText(), type);
    currentScope.define(var); // Define symbol in current scope
}

到此,定义阶段已经完成。

为构建引用阶段,让我们将当前作用域设置为从定义阶段传递过来的全局作用域。

1
2
3
4
5
6
7
public RefPhase(GlobalScope globals, ParseTreeProperty<Scope> scopes) {
    this.scopes = scopes;
    this.globals = globals;
}
public void enterFile(CymbolParser.FileContext ctx) {
    currentScope = globals;
}

然后,就像树遍历器触发Cymbol函数和块的进入与退出事件那样,监听器方法通过访问在定义阶段期间存储在树中的值来及时更新currentScope。

1
2
3
4
5
6
7
8
9
10
11
12
public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentScope = scopes.get(ctx);
}
public void exitFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentScope = currentScope.getEnclosingScope();
}
public void enterBlock(CymbolParser.BlockContext ctx) {
    currentScope = scopes.get(ctx);
}
public void exitBlock(CymbolParser.BlockContext ctx) {
    currentScope = currentScope.getEnclosingScope();
}

随着遍历器的行进恰当地设置作用域,我们可以通过实现变量引用和函数调用的监听器方法解决符号。当遍历器遇到一个变量引用时,它调用exitVar(),该方法使用resolve()试图在当前作用域的符号表中查找变量名。如果resolve()在当前作用域中没有找到符号,它会查找封闭作用域链。如果必要,resolve()将寻找所有方式直到全局作用域。如果找不到一个合适的定义,它会返回null值。如果resolve()找到的符号是一个函数而不是变量,就需要生成一个错误消息。

1
2
3
4
5
6
7
8
9
10
public void exitVar(CymbolParser.VarContext ctx) {
    String name = ctx.ID().getSymbol().getText();
    Symbol var = currentScope.resolve(name);
    if ( var==null ) {
        CheckSymbols.error(ctx.ID().getSymbol(), "no such variable: "+name);
    }
    if ( var instanceof FunctionSymbol ) {
        CheckSymbols.error(ctx.ID().getSymbol(), name+" is not a variable");
    }
}

处理函数调用基本上是相同的,如果不能找到一个定义或找到了一个变量,都需要发出一个错误。

最后,是用来显示早先需要的输出的构建和测试序列:

1
2
3
antlr Cymbol.g
compile *.java
run CheckSymbols vars.cymbol

输出结果如下所示:

1
2
3
locals:[]
function<f:tINT>:[<x:tINT>, <y:tFLOAT>]
...

Comments