语义分析——符号表

符号表

Definition（符号表- Symbol Table）

符号表是用于保存各种信息的数据结构

作用域

  • 领域特定语言（DSL）通常只有单作用域（全局作用域）
  • 通用程序设计语言（GPL）通常需要嵌套作用域

Example

We take a WRONG assumption here about FunctionSymbol’s scope

在这里我们认为z属于FunctionSynbol中的symbols

如何实现

将上述过程抽象为函数接口的调用

Scope

SymbolTableListener

struct/class

当然无论是在c或者c++，又或者Java中，我们不可避免的会遇到类型作用域

Talk is cheap , show me the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//BaseScope.java
package symtable;

import com.google.common.base.MoreObjects;

import java.util.LinkedHashMap;
import java.util.Map;

public class BaseScope implements Scope {
  private final Scope enclosingScope;
  private final Map<String, Symbol> symbols = new LinkedHashMap<>();
  private String name;

  public BaseScope(String name, Scope enclosingScope) {
    this.name = name;
    this.enclosingScope = enclosingScope;
  }

  @Override
  public String getName() {
    return this.name;
  }

  @Override
  public void setName(String name) {
    this.name = name;
  }

  @Override
  public Scope getEnclosingScope() {
    return this.enclosingScope;
  }

  public Map<String, Symbol> getSymbols() {
    return this.symbols;
  }

  @Override
  public void define(Symbol symbol) {
    symbols.put(symbol.getName(), symbol);
    System.out.println("+" + symbol);
  }

  @Override
  public Symbol resolve(String name) {
    Symbol symbol = symbols.get(name);
    if (symbol != null) {
      System.out.println("*" + symbol);
      return symbol;
    }

    if (enclosingScope != null) {
      return enclosingScope.resolve(name);
    }

    System.err.println("Cannot find " + name);
    return null;
  }

  @Override
  public String toString() {
    return MoreObjects.toStringHelper(this)
        .add("name", name)
        .add("symbols", symbols.values().toString())
        .toString();
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//SymbolTableListener.java
package symtable;

import cymbol.CymbolBaseListener;
import cymbol.CymbolParser;

public class SymbolTableListener extends CymbolBaseListener {
  private final SymbolTableTreeGraph graph = new SymbolTableTreeGraph();
  private GlobalScope globalScope = null;
  private Scope currentScope = null;
  private int localScopeCounter = 0;

  @Override
  public void enterProg(CymbolParser.ProgContext ctx) {
    globalScope = new GlobalScope(null);
    currentScope = globalScope;
  }

  @Override
  public void exitProg(CymbolParser.ProgContext ctx) {
    graph.addNode(SymbolTableTreeGraph.toDot(currentScope));
  }

  @Override
  public void exitVarDecl(CymbolParser.VarDeclContext ctx) {
    String typeName = ctx.type().getText();
    Type type = (Type) globalScope.resolve(typeName);

    String varName = ctx.ID().getText();
    VariableSymbol varSymbol = new VariableSymbol(varName, type);
    currentScope.define(varSymbol);
  }

  @Override
  public void exitId(CymbolParser.IdContext ctx) {
    String varName = ctx.ID().getText();
    currentScope.resolve(varName);
  }

  @Override
  public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    String retType = ctx.type().getText();
    globalScope.resolve(retType);

    String funcName = ctx.ID().getText();

    FunctionSymbol func = new FunctionSymbol(funcName, currentScope);
    graph.addEdge(funcName, currentScope.getName());

    currentScope.define(func);
    currentScope = func;
  }

  @Override
  public void exitFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    graph.addNode(SymbolTableTreeGraph.toDot(currentScope));
    currentScope = currentScope.getEnclosingScope();
  }

  @Override
  public void exitFormalParameter(CymbolParser.FormalParameterContext ctx) {
    String typeName = ctx.type().getText();
    Type type = (Type) globalScope.resolve(typeName);

    String varName = ctx.ID().getText();

    VariableSymbol varSymbol = new VariableSymbol(varName, type);
    currentScope.define(varSymbol);
  }

  @Override
  public void enterBlock(CymbolParser.BlockContext ctx) {
    LocalScope localScope = new LocalScope(currentScope);

    String localScopeName = localScope.getName() + localScopeCounter;
    localScope.setName(localScopeName);
    localScopeCounter++;

    graph.addEdge(localScopeName, currentScope.getName());

    currentScope = localScope;
  }

  @Override
  public void exitBlock(CymbolParser.BlockContext ctx) {
    graph.addNode(SymbolTableTreeGraph.toDot(currentScope));
    currentScope = currentScope.getEnclosingScope();
  }

  public SymbolTableTreeGraph getGraph() {
    return graph;
  }
}