仿c语言自制编程语言笔记4

语义分析

语义分析是对生成的抽象语法树的语义进行分析,并且实施变量引用的消解和类型检查.有如下几个处理:

  1. 变量引用的消解 确定具体指向哪个变量.比如有全局变量i,有局部变量i,通过作用域来消除.
  2. 类型名称的消解 TypeRef表示类型的名称,要转化为Type.
  3. 类型定义的检查 检查语义问题,比如void数组不合法,结构体含有自身类型的成员不合法等.
  4. 表达式的有效性检查 检查表达式是否可以执行.
  5. 静态类型检查 检查类型是否正确.
    上述执行的顺序是1->4,2->3->4,4->5.

一颗语法树的结构大致如下:

1
2
3
4
5
6
7
=
     *   *
   *       *
 *          +
i         *   *
        *       *
       1         3

我们作上述的检查需要对整个树进行遍历,而且是需要先遍历左右子树然后再到父节点,是一个后序遍历.我们可以在每个节点的–类中实现一个check方法,方法中调用自己所含的节点check方法.为了将代码能够整合到一起,可以用vsitior模式,编写一个专门用来check的类,然后在每个类中调用这个类中的方法.考虑到每种消解都要进行遍历,因此一个节点如果对每种消解方法都要写一个调用,会导致成倍的增加,因此我们把所有消解方法抽象出一个接口,然后每个类中的accept方法接受这个接口.
比如说,对于节点的visit接口:

1
2
3
4
5
6
7
8
9
10
11
12
public interface ASTVisitor {
	//语句的接口
    public void visit(BlockNode node);
    public void visit(ExprStmtNode node);
    //...
    // 表达式的visit接口
    public void visit(AssignNode node);
    public void visit(OpAssignNode node);
    public void visit(CondExprNode node);
    //...
}

这样对于语义分析中的类型检查,我们就可以让它实现这个接口,这样在每个节点类里只要有一个参数是这个接口的visitor方法就可以:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TypeChecker implements ASTVisitor{
	void visit(BlockNode node){
		for(StmtNode sn:node.stmts()){
			sn.accept(this);
		}
		for(Entity en:node.entity()){
			en.accept(this);
		}
//每个节点类中
Class Node{
public abstract void accept(ASTVisitor visitor);
}
Class AST extends Node{
	public void accept(ASTVisitor visitor){
		visitor.visit(this);
	}
}

有三个接口,分别是:

  • ASTVisitor 语句和表达式的节点遍历
  • EntityVisitor 给实体类型遍历
  • DeclarationVisitor 给声明的类型节点遍历

变量引用的消解

当变量名有冲突时,我们要考虑变量i是全局变量i还是局部变量i,对生成的抽象语法树中的VariableNode节点添加该变量的定义的信息,也就是Variable对象.
将整个作用域分成两块:

  • Scope 表示作用域的抽象类
  • ToplevelScope 表示程序顶层的作用域.保存有函数和全局变量.
  • LocalScope 表示一个临时变量的作用域,保存形参和临时变量.

我们作用域可形成一颗树,根节点是全局作用域,其中包含着若干局部作用域,每个局部又包含局部,这样把整个域划分好:

1
2
3
4
5
6
ToplevelScope
*           *
      *              *
  LocalScope       LocalScope
   *  *    *
  *   *      *

我们查找一个变量的定义,只要从引用了该变量的作用域往上查找到第一个变量定义即为其定义.
用来做变量引用消解的类为LocalResolver,也是实现了ASTVisitor接口,该类利用栈来一边生成Scope对象的树一遍进行变量引用的消解.每次将当前作用域的符号表也就是LocalScope对象,push到栈内,对一个变量查找其定义时,从栈顶开始查找,这样能一边给变量添加定义,也能生成Scope树.

Scope类

1
2
3
public abstract class Scope {
	protected List<LocalScope> children;
}

主要就是包含若干子作用域.

ToplevelScope类

1
2
3
public class ToplevelScope extends Scope{
	Map<String, Entity>entities;
}

LocalScope类

1
2
3
4
public class LocalScope extends Scope{
	private Scope parent;
	private Map<String, DefinedVariable>variables;
}

包含了一个保存当前作用域内定义的变量或者函数,称之为符号表.局部作用域还保存了父作用域.

LocalResolver

通过之前编写的visitor模式,对于我们想要实现的操作,我们只要在类中实现具体的visit方法即可,不用管如何在节点中遍历的.
先看含有的成员:

1
2
3
4
5
6
public class LocalResolver extends Visitor{
	private LinkedList<Scope>scopeStack;//用来处理的栈
	private ConstantTable constantTable//用来管理字符串常量的表
	private ErrorHandler errorHandler;
	...
}

其中栈通过pushScope操作来完成,对于变量节点VariableNode的处理,都是在当前栈顶的作用域或向上查找定义.
下面是总的调用,我们先导入所有全局变量的定义,因此不需要像c语言一样考虑全局变量或函数定义和使用的先后顺序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void resolve(AST ast){
		ToplevelScope scope=new ToplevelScope();
		scopeStack.push(scope);
		//首先添加全局声明
		for(Entity entity:ast.declarations() ){
			scope.declareEntity(entity);
		}
		//添加全局定义
		for(Entity entity :ast.definitions()){
			scope.defineEntity(entity);
		}
		resolveConstantValues(ast.constants());
		resolveFunctions(ast.definedFunctions());
		resolveDefinedGvars(ast.definedVariables());
		scope.checkReference(errorHandler);
		//保存信息
		ast.setScope(scope);
		ast.setConstantTable(constantTable);
	}

最后实现具体的三个visit:

1
2
3
4
5
6
7
8
9
10
11
public Void visit(VariableNode node){
		String varName=node.name();
		Entity ent=currentScope().get(varName);//得到定义
		ent.refered();
		node.setEntity(ent);//建立联系
	}
	public Void visit(StringLiteralNode node){
		String name=node.value();
		node.setEntry(constantTable.insert(name));
		return null;
	}

下面是作用域入栈和出栈的方法,由于形参的元素parameter是继承自DefinedVariable,因此需要向下兼容.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void pushScope(List<? extends DefinedVariable> vars){
		LocalScope scope = new LocalScope(currentScope());
        for (DefinedVariable var : vars) {
            if (scope.hasDefinedVariable(var.name())) {
                error(var.location(),
                    "duplicated variable in scope: " + var.name());
            }
            else {
                scope.defineVariable(var);
            }
        }
        scopeStack.addLast(scope);
	}
	public Scope popScope(){
		return scopeStack.pop();
	}

类型名称的消解

目的在于将TypeRef转换Type,我们用TypeResolver类来处理,功能仅仅是遍历抽象语法树,遇到TypeRef类就从叶子节点开始转换为Type类型.没有作用域的限制.
TypeRef和Type的对应关系保存在TypeTable中.
TypeResolver需要一张类型表和一个错误处理的类,类型表在我们遍历语法树的同时向其中添加类型定义.
变量的类型有两种一种定义的一种是声明的,定义的变量又分是否有初始化的.

TypeResolver

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class TypeResolver extends Visitor
		implements DeclarationVisitor<Void>,EntityVisitor<Void>{
	TypeTable typeTable;
	ErrorHandler errorHandler;
	public void resolve(AST  ast){
		defineTypes(ast.types());
		for(TypeDefinition t:ast.types()){
			t.accept(this);
		}
		for(Entity ent:ast.entities()){
			ent.accept(this);
		}
	}
	...
}
用来消解的方法首先对全局定义的结构体,联合体,还有类型别名这些类型添加到表中,这样接下来遇到typeRef类型就从表中查找其对应的Type,然后绑定到节点的TypeNode上.(这也是为什么TypeNode有两个成员Type和TypeRef)

TypeTable

关键代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class TypeTable {
    private int intSize;
    private int longSize;
    private int pointerSize;//规定的指针所占字节
    Map<TypeRef,Type>table;
	{...}//一段静态代码用来添加表中基本类型
	public TypeTable(int intSize,int longSize,int pointerSize){
		this.intSize = intSize;
	    this.longSize = longSize;
	    this.pointerSize = pointerSize;
		table=new HashMap<TypeRef,Type>();
	}
	...
}

我们的table其实就是一个类型名称和其对应类型的map,在遇到定义的类型时,我们向表中添加自己定义的类型元素.

类型定义检查

主要检查三个问题:

  • 包含void数组,结构体,联合体不合法.
  • 成员重复的结构体联合体.
  • 循环定义的结构体,联合体.
    第三个问题的解决可以转成图的有环问题:
    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
    /*
    	 * 检查是否有循环定义:
    	 * 			结构体a中含有结构体b,b中含c,c中含a
    	 * 转换成一个有向图中检查是否有环的问题.
    	 * 可以用DFS,也可以用拓扑排序,后者需要得到图的所有节点,前者可以查看以某一个节点为起点来检查
    	 */
    	//**************DFS实现***************
    	public void checkRecursiveDefinition(Type t,ErrorHandler errorHandler){
    		HashSet<Type>visited=new HashSet<Type>();
    		_checkRecursiveDefinition( t, errorHandler,visited);
    	}
    	public void _checkRecursiveDefinition(Type t,ErrorHandler errorHandler,HashSet<Type> visited){
    		if(visited.contains(t)){
    			errorHandler.error(((NamedType)t).location(),"recursive Type Definition: "+t);
    		}else{
    			visited.add(t);
    			//复合类型检查所有成员
    			if(t instanceof CompositeType){
    				CompositeType tmp=(CompositeType)t;
    				for(Type memberType:tmp.memberTypes()){
    					_checkRecursiveDefinition( memberType, errorHandler,visited);
    				}
    			}
    			//类型别名指向的类型
    			if(t instanceof UserType){
    				_checkRecursiveDefinition( ((UserType)t).realType(), errorHandler,visited);
    			}
    			//数组的基本类型也在图中
    			if(t instanceof ArrayType){
    				ArrayType tmp=(ArrayType)t;
    				_checkRecursiveDefinition( tmp.baseType(), errorHandler,visited);
    			}
    			visited.remove(t);
    		}
    	}

表达式有效性

主要解决表达式不正确的情况,有如下几种:

  • 无法赋值的表达式被赋值 1=2
  • 非法的数组引用 “ab”[1]
  • 非法的函数调用 “string”(a)
  • 非法的成员调用 1.member
  • 操作数非法的指针间接引用(1->memb)
  • 非指针对象取值 *1
  • 非左值表达式取地址 &func(a)

检查的方法主要分成两类,第一,检查表达式是否可以被赋值,第二,检查操作数的类型是否符合.
CorrectExprChecker类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class CorrectExprChecker extends Visitor{
	private TypeTable table;//用来生成指针类型(指定指针大小)
	private ErrorHandler errorHandler;//错误处理
	public CorrectExprChecker(TypeTable table,ErrorHandler errorHandler){
		this.table=table;
		this.errorHandler=errorHandler;
	}
	public void check(AST ast)throws SemanticException{
		checkGlobalVariables(ast.definedVariables());
		checkfunctions(ast.definedFunctions());
		if (errorHandler.errorOccured()) {
            throw new SemanticException("compile failed.");
        }
}

关键调用为check,首先处理全局变量中的初始化的表达式,然后处理定义的函数内部的表达式的正确性.

静态类型检查

负责检查操作数的类型限制.比如乘法和加法左右必须都是整数,参数为int类型的函数不能传入其他类型的实参.
个人不喜欢编译器自动隐式转换,如果需要隐式转换则对于需要转换的节点改成CastNode节点,并附上要转换的类型即可,不实现此功能.
首先是启动方法,检查变量:

1
2
3
4
5
6
7
public void check(AST ast){
		 checkVariables(ast.definedVariables());
		 checkFunctions(ast.definedFunctions());
		 if(errorHandler.errorOccured()) {
	            throw new SemanticException("compile failed.");
		 }
	 }

对于运算符两侧含有short和char类型,需要向上转换到signed int,这属于整型提升.

1
2
3
4
5
6
7
8
9
10
11
12
private Type integralPromotion(Type t) {
        if (!t.isInteger()) {
            throw new Error("integralPromotion for " + t);
        }
        Type intType = typeTable.signedInt();
        if (t.size() < intType.size()) {
            return intType;
        }
        else {
            return t;
        }
    }

在函数类型中,规定禁止结构体或者联合体称为函数参数类型并且不能赋值.
在这一步加了一个boolean类型,对于条件表达式的返回类型,暂且归到整型中,添加了boolean关键字,转换为一个0或者1的字符字面量.占一个字节

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    2、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: true
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

目前在东南大学读研<br>擅长c/c++,linux,shellscript<br>做一些3D人脸识别的研究<br>有兴趣一起交流学习!