文章目录

一、手写符号表

语义分析阶段有两个比较关键的任务：

类型检查

对于 statically-typed language，如 java，c++，C#，Go，我们可以在编译期 确定变量类型

对于 Dynamically-typed language，如 python，javascript，php，ruby，类型在运行时确定

相应的，我们也可以根据类型检查强弱 来划分为 强类型 / 弱类型 语言。

比如 以安全性著称的 rust，就非常的严格（简直在防止程序员写代码）

符号检查

符号：变量名，函数名，类型名，标签名……

比如下面这段有问题的代码：

int one = 1;
int three = one + two;	// undefined
int five = len("Hello");	// undefined

int two = one(one);	// 错误地把int 当作函数来用
int one = 1;		// 重复定义

语义分析阶段，我们就要找出上面这些符号上的错误

我们在这个阶段需要建立符号表。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

1.1 符号表

符号表（Symbol Table）是用于保存各种符号相关信息的数据结构。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

“领域特定语言”(DSL)通常只有单作用域(全局作用域)

host = antlr.org;
port = 80;
webmaster = parrt@antlr.org;

对于这种语言我们用一个哈希表记录符号信息即可。

“通用程序设计语言”(GSL)通常需要嵌套作用域

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

这个时候我们就需要多个哈希表，它们之间呈现一种树状结构。

比如下面这段代码对应的符号表：

int x;
int y;

void a(){
    int x;
    x = 1
    y = 2;
    { int y = x; }
}
void b(int z)
{}

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

这张表的建立非常简单，我们还是使用监听器模式，递归的时候在进入和离开的时候进行控制即可。

1.2 手写符号表

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

我们下面基于之前的 Cymbol.g4 中 的文法定义，来实现在dfs时建立如上面这种树形符号表关系。

1.2.1 需要的类

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

类间派生关系如上图

1.2.2 类的定义

Type

package symtable;

public interface Type {
}

Symbol

package symtable;

public interface Symbol {
  String getName();
}

BaseSymbol

package symtable;

import com.google.common.base.MoreObjects;

public class BaseSymbol implements Symbol {
  final String name;
  final Type type;

  public BaseSymbol(String name, Type type) {
    this.name = name;
    this.type = type;
  }

  public String getName() {
    return name;
  }

  public Type getType() {
    return type;
  }

  public String toString() {
    return MoreObjects.toStringHelper(this)
        .add("name", name)
        .add("type", type)
        .toString();
  }
}

FuntionSymbol

package symtable;

public class FunctionSymbol extends BaseScope implements Symbol {
  public FunctionSymbol(String name, Scope enclosingScope) {
    super(name, enclosingScope);
  }
}

Scope

package symtable;

import java.util.Map;

public interface Scope {
  String getName();
  void setName(String name);

  Map<String, Symbol> getSymbols();

  // 父作用域
  Scope getEnclosingScope();
  // 定义符号
  void define(Symbol symbol);
  // 解析
  Symbol resolve(String name);
}

GlobalScope

全局作用域默认添加了几个symbol

package symtable;

public class GlobalScope extends BaseScope {
  public GlobalScope(Scope enclosingScope) {
    super("GlobalScope", enclosingScope);

    define(new BasicTypeSymbol("int"));
    define(new BasicTypeSymbol("double"));
    define(new BasicTypeSymbol("void"));
  }
}

LocalScope

package symtable;

public class LocalScope extends BaseScope {
  private static int localScopeCounter = 0;

  public LocalScope(Scope enclosingScope) {
    super("LocalScope", enclosingScope);

    String localScopeName = getName() + localScopeCounter;
    setName(localScopeName);
    localScopeCounter++;
  }
}
1.2.3 BaseScope

BaseScope 作为 作用域的基类，需要符号表symbols，父作用域enclosingScope，名称name

symbols 就是一个简单的Map

package symtable;

import com.google.common.base.MoreObjects;

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

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

  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) {
    this.symbols.put(symbol.getName(), symbol);
    System.out.println("+" + symbol);
  }

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

    // 往根节点找
    if (this.enclosingScope != null) {
      return this.enclosingScope.resolve(name);
    }

    // error
    System.out.println("?" + name);
    return null;
  }

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

需要注意的就是 define 和 resolve 的实现

define 只需向 符号表中添加 <name，symbol> 键值对

resolve 只需向 符号表中解析 name 对应的符号，如果自己的符号表有，那么就返回

否则向父作用域找

1.2.4 SymbolTableListener

Cymbol.g4

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

符号表监听器的逻辑分为四部分：

  • 进入时 创建作用域，并切换当前作用域
    • enterProg 进入 Prog
    • enterBlock 进入局部作用域
    • enterFunctionDecl 函数声明
  • 添加符号
    • 离开变量声明时，exitVarDecl，添加符号到当前作用域的符号表
    • 离开参数列表时，exitFormalParameter，添加符号到当前作用域的符号表
  • 使用符号
    • 离开标识符时，exitId，标识符进行解析
  • 离开作用域，返回其父作用域
    • exitProg
    • exitBlock
    • exitFunctionDecl
package symtable;

import cymbol.CymbolBaseListener;
import cymbol.CymbolParser;

public class SymbolTableListener extends CymbolBaseListener {
  private GlobalScope globalScope = null;
  private Scope currentScope = null;

  private final SymbolTableTreeGraph graph = new SymbolTableTreeGraph();

  /**
   * (1) Create and enter a new scope
   */
  // 起始规则 开启全局作用域
  @Override
  public void enterProg(CymbolParser.ProgContext ctx) {
    globalScope = new GlobalScope(null);
    this.currentScope = globalScope;
  }

  // 开启作用域
  @Override
  public void enterBlock(CymbolParser.BlockContext ctx) {
    LocalScope localScope = new LocalScope(currentScope);

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

    currentScope = localScope;
  }

  // 函数声明
  @Override
  public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    String funcName = ctx.ID().getText();
    FunctionSymbol scope = new FunctionSymbol(funcName, currentScope);
    graph.addEdge(scope.getName(), currentScope.getName());

    currentScope.define(scope); // 加入 当前作用域符号表
    this.currentScope = scope;
  }

  /**
   * (2) define symbols
   */
  @Override
  public void exitVarDecl(CymbolParser.VarDeclContext ctx) {
    String typeName = ctx.type().getText();
    Type type = (Type) this.currentScope.resolve(typeName);

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

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

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

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

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

   /**
   * (3) use symbols
   */
  @Override
  public void exitId(CymbolParser.IdContext ctx) {
    String varName = ctx.ID().getText();
    this.currentScope.resolve(varName);
  }

  /**
   * (4) Exit the current scope and return to its enclosing scope
   */

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

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

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

  public SymbolTableTreeGraph getGraph() {
    return graph;
  }
}

二、符号表

2.1 定义

  • 用来存储程序中的变量相关信息
    • 类型
    • 作用域
    • 访问控制信息
  • 必须非常高效
    • 程序中的变量规模会很大

2.2 符号表的接口

#ifndef TABLE_H
#def TABLE_H

typedef ... Table_t;	// 符号表的数据结构

// 新建符号表
Table_t Table_new ();
// 符号表的插入
void Table_enter (Table_t, Key_t, Value_t);
// 符号表的查找
Table_t Table_lookup (Table_t, Key_t);

#endif

2.3 符号表的典型数据结构

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

// 符号表是典型的字典结构
symbolTable: key->value;
// 一种简单的数据结构定义（概念上的）：
typedef char *key;
typedef struct value{
    Type_t type;
    Scope_t scope;
    ... // 必要的其它字段
} value;

2.4 符号表的高效实现

  • 为了高效，可以使用哈希表等数据结构来实现符号表
    • 查找是O(1)时间
  • 为了节约空间，也可以使用红黑树等平衡树
    • 查找是**O(log N)**时间

2.5 作用域

int x;
int f() {
	if (4) {
        int x;
        x = 6;
    } else {
        int x;
        x = 5;
    }
    x = 8;
}

符号表处理作用域的方法

  • 方法1：一张表的方法
    • 进入作用域时，插入元素
    • 退出作用域时，删除元素

如下：

int x;			 σ = (x->int)
int f() {		 σ1 = σ + (f->...) = {x->int, f->...}
	if (4) {
        int x;	 σ2 = σ1 = σ + (x->int) = {x->..., f->..., x->...}
        x = 6;
    }		 	σ1 
    else {	
        int x;	  σ4 = σ1 + {x->int} = {x->..., f->..., x->...}
        x = 5;
    }			σ1
    x = 8;
}				σ1

我们在 局部作用域 又定义了x，这要求我们在 符号表中实现变量的屏蔽

而 我们如果用哈希表来实现，开散列的结构，我们要将新的 x 在对应的链进行头插，这样保证我们对应桶的指针默认指向当前作用域中的对应变量

  • 方法2：采用符号表构成的栈
    • 进入作用域时，插入新的符号表
    • 退出作用于时，删除栈顶符号表

这样很好的支持我们作用域的嵌套，栈顶始终是当前作用域的符号表

有点类似我们开始在anltr-v4 中的实现方式

2.6 名字空间

下面用到一个链表和 goto 语句

struct list{		// ①
    int x;
    struct list *list;		// ③
} *list;		// ②
				// ①  ②
void walk(struct list *list) {
    list: // ④
    	printf("%d\n", list->x);	// ②
    	if (list = list->list)		// ② ② ③
            goto list;			// ④
}

上面的代码中出现了很多次list，我们怎样去划分这些 list 呢？

2.7 用符号表处理名字空间

  • 每个名字空间用一个表来处理
  • 以C语言为例
    • 有不同的名字空间:
      • 变量 t1
      • 标签 t2
      • 标号 t3
      • …
  • 可以每一种定义一张符号表

2.8 基于符号表的类型检查算法

有如下文法：

E -> n
   | true
   | false
   | E + E
   | E && E

类型检查算法

enum type {INT, BOOL};
Table_t table;	// 符号表

enum type check_exp (Exp_ t e) {
	switch(e->kind) 
		case EXP_INT: return INT;
		case EXP_TRUE: return BOOL;
		case EXP_FALSE: return BOOL;
		case EXP_ADD: t1 = check_exp(e->left);
					 t2 = check_exp(e->right);
					 if (t1 != INT || t2 != INT) {
					 	error("type mismatch");
					 else return INT;
}

enum type check_prog (Dec_t d, Exp_t e) { 
	table = check_dec(d);
	return check_exp(e);
}

Table_t check_dec(Dec_t d) {
	foreach(T id ∈ d) 
		table_enter(table, id, T);
}

enum type check_exp (Exp_ t e) {
	switch(e->kind) 
		case EXP_ID: 
			t = Table_lookup(table, id);
			if (id not exist)
				error("id not found");
			else return t;
}

void check_stm(Table_t table, Stm_t s) {
	switch(s->kind) 
		case STM_ASSIGN: 
			t1 = Table_lookup(s->id);
			t2 = check_exp(table, s->exp);
			if (t1 != t2)
				error("type mismatch");
			else return INT;
		case STM_PRINTI:
			t = check_exp(s->exp);
			if (t != INT)
				error("type mismatch");
			else return;
		case STM_PRINTB: ... // 类似
}

三、其它问题

语义分析中要考虑的其它问题：

  • 类型相容性?
  • 错误诊断?
  • 代码翻译?

3.1 类型相等

  • 类型检查问题往往归结为判断两个类型是否相等t1==t2？

    • 在实际的语言中，这往往是个需要谨慎处理的复杂问题

  • 示例1：名字相等vs结构相等

    • struct A {
    int i;
} x;

struct B {
    int i;
} y;

x = y;

    • 对采用名字相等的语言，可直接比较

      • 上面 x 和 y 的类型 名称不同，所以赋值非法

    • 对采用结构相等的语言，需要递归比较各个域

      • 上面 A 和 B 的各个域的结构相等，无法 对 x = y 的错误做出检测

  • 示例2：面向对象的继承

    • class A
{
    int i;
}

class B extends A{
    int i;
}

A x;
B y;
x = y;

    • 需要维护类型间的继承关系

3.2 错误诊断

  • 要给出尽可能准确的错误信息
  • 要给出尽可能多的错误信息
    • 从错误中进行恢复
  • 要给出尽可能准确的出错位置
    • 程序代码的位置信息要从前端保留并传递过来

3.3 代码翻译

  • 现代的编译器中的语义分析模块，除了做语义分析外，还要负责生成中间代码或目标代码
    • 代码生成的过程也同样是对树的某种遍历
    • 代码翻译将在后续讨论
  • 因此，语义分析模块往往是编译器中最庞大也最复杂的模块
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

avatar 魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

avatar 魔乐社区
cover

魔乐社区月度精选（26年2月）

avatar 魔乐社区