编译技术：语义分析

语义分析设计

编码前的设计

需求分析

读取语法分析构建的 AST，分析其语义构建符号表输出至 symbol.txt。如果存在错误则将错误信息输出至 error.txt。

符号类型见下表。

语义分析符号类型

类型	类型名称	类型	类型名称	类型	类型名称
int型常量	ConstInt	int型变量	Int	void型函数	VoidFunc
int型常量数组	ConstIntArray	int型变量数组	IntArray	int型函数	IntFunc
int型静态变量	StaticInt	int型静态变量数组	StaticIntArray

语义分析错误类型

错误类型	类别码	解释
名字重定义	b	函数名或变量名在当前作用域下重定义
未定义的名字	c	使用了未定义的标识符
函数参数个数不匹配	d	函数调用时参数个数与函数定义不同
函数参数类型不匹配	e	函数调用时参数类型与函数定义不同
return语句不匹配	f	无返回值的函数存在不匹配的return
return语句缺失	g	有返回值的函数末尾缺少return
不能改变常量的值	h	常量无法被赋值
printf格式字符与表达式个数不匹配	l	“%d”的个数与表达式不同
非循环快中使用break和continue语句	m	只有for语句块中出现

文件组织

新建目录 src\midend，其中包含一个类：

Midend：该模块为中段“主函数”。

新建目录 src\midend\symbol，该部分定义符号表，其中包含若干类：

SymbolType：枚举类，枚举所有符号类型。
Symbol：符号类，定义符号对象，存储标识符和符号类型。
SymbolTable：符号表类，记录符号表的作用域序号 depth、父节点 parentTable、子结点 childTables、符号容器 symbolList。
SymbolManager：内含静态方法，是该模块的引擎。

总体思路

符号表的逻辑结构：构建一个符号表的树形结构，作用域之间的嵌套和并列关系通过树结构实现，每一个作用域都是一个符号表（及其父节点与递归父节点）。

抽象语法树的遍历：对每个 Node 类定义 public void visit() 方法，该方法实现针对该节点子结点的遍历，并以此更新符号表和发现错误。

符号表的内容填充：在 SymbolManager 中定义静态方法 public static void addSymbol(TokenNode ident, SymbolType type)，传入标识符节点对象及已识别的符号类型，这样所有 Node 在进行 visit 时都能使用，将符号填入当前符号表。

当前符号表的切换：在 SymbolManager 中记录当前符号表 curSymbolTable，并定义切换方法，切换时机在 Node 类 visit 时判断。

public static void sinkDown()：符号表下沉，创建一个新的子符号表，并把当前符号表设为子符号表，depth 加一。
public static void floatUp()：符号表上浮，当前符号表设为父符号表，depth 减一。

编码完成之后的修改

FuncSymbol 类

新建类 src\midend\symbol\FuncSymbol.java，继承于 Symbol 类，表示函数符号，新增参数列表 paramList。

ValueSymbol 类

新建类 src\midend\symbol\ValueSymbol.java，继承于 Symbol 类，表示变量符号，新增常量类型判断 isConst。

符号表切换的时机

当遇到 Block 节点时，几乎必触发符号表的切换，这也统一了作用域序号的计算：诸如 for (;;) a=1; 、if (a==1) b=0; 这样的并不会新增作用域，思考其原因为此类作用块中不会出现定义语句，因此与符号表构建无关。

如果遇到 Block 便切换符号表，存在函数定义的冲突，即函数定义的参数列表应属于该作用域，应该在读取参数列表前就进行切换符号表，而再读到 Block 时不进行切换。针对此问题，在 SymbolManager 中定义新方法：

public static void diveInto()：符号表下潜，该方法取代原 sinkDown 方法的无脑下沉逻辑，而给原方法增加一条判断，如果需要，则不进行下沉。

因此最终统一为：

在 Block 前后使用 sinkDown 与 floatUp。
在 FuncFParams 前使用 diveInto。

节点间的信息传递

由于错误处理需要大量信息传递，而 visit 方法本身没有参数也没有返回值（为了强迫症好看，并不是所有节点都需要信息传递的），因此节点间的信息传递费了一点心思，最终还是比较像屎山。

主要有两种思路：

SymbolManager 中的“全局变量”：在其中定义所有 Node 可以读写的全局变量，优点是存取简单，缺点是递归限制。例如：
1. private static FuncSymbol curFuncSymbol：当前函数符号，目的是记录当前函数定义的函数类型，以判断是否有正确的 return。因为函数定义不会出现嵌套覆盖，此方法是可行的。
2. private static TokenNode curFuncIdent：当前函数标识符，目的是记录当前函数调用的函数标识符，以寻找对应的函数定义，定位参数个数不匹配错误，因为同一行只有一个错误，因此嵌套函数调用并不会对其造成影响。
Node 中的属性传递：在 Node 中定义个性化信息，然后通过父子的链接进行传递，优点是可以处理嵌套递归的信息覆盖问题，缺点是传递繁琐。例如：
1. private SymbolType symbolType;：对 Exp 求类型时在一系列 Node 中传递，自底向上确定。
2. private boolean isReturnStmt;：在 Stmt 中记录是否是 return 语句，便于在其父节点中判断 return 的合法性。
3. private boolean isForStmt;：在 Stmt 中记录是否是 for 语句块，便于在父节点中判断 break 和 continue 的合法性。
4. private ArrayList<SymbolType> paramTypeList：在 FuncRParams 中记录实参列表，便于与函数定义的形参列表进行校对。

其余示例不再详细说明，将在下文错误处理部分复盘。

语法分析错误的纠正

语法分析中处理了 ijk 类错误，主要是符号缺失，但之前没有对其进行补全，导制语义分析阶段无法正常解析错误。

在 Node 类中定义新方法：

1
2
3

protected void padTokenNode(TokenType tokenType) {  
    this.addNode(new TokenNode(new Token(tokenType, tokenType.toString(), getPrevToken().getLineNumber())));  
}

在 parse 时每次 catchError 后调用一次该方法，补全语法树节点。

错误处理总结

b 名字重定义：

只在当前作用域下判断，内层作用域新定义会覆盖外层作用域。因此以 SymbolTable 为域，定义两个方法：

public Symbol getSymbol(String name) {  
    return this.symbolTable.get(name);  
}  
  
public boolean isRedefine(String name) {  
    return getSymbol(name) != null;  
}

并在 SymbolManager 给出全局调用方法。每次识别到变量定义和函数定义时调用。

c 未定义的名字：

在当前作用域及其外层作用域递归查找，与 b 类错误有所不同。因此直接在 SymbolManager 中定义递归查找方法：

public static Symbol getSymbol(String name) {  
    SymbolTable table = curSymbolTable;  
    while (table != null) {  
        Symbol symbol = table.getSymbol(name);  
        if (symbol != null) {  
            return symbol;  
        }  
        table = table.getParentTable();  
    }  
    return null;  
}  
  
public static boolean isUndefine(String ident) {  
    return getSymbol(ident) == null;  
}

每次在识别到 LVal（变量或数组）和 UnaryExp（函数调用）时调用。

d 函数参数个数不匹配：

识别到 FuncRParams 即函数实参列表时考虑，获取 private FuncSymbol funcSymbol 信息，该信息由父节点识别到 Ident 时填充，表示该函数对应的函数符号，从中可以获取到函数定义的参数信息。

if (paramNum != funcSymbol.getParamList().size()) {  
    ErrorCatcher.catchError(  
            new Error(ErrorType.UNMATCHING_FUNC_PARAM_NUM, SymbolManager.getCurFuncIdent().getLineNumber()));  
}

e 函数参数类型不匹配：

识别到 UnaryExp 即函数调用时考虑，首先将紧跟着的 FuncRParams 遍历透彻，此过程顺序：FuncRParams->Exp->AddExp->MulExp->UnaryExp->(PrimaryExp/函数调用)，且 PrimaryExp->LVal/Number，且LVal->Ident/数组。

自顶向下中遇到终结符即确定该 Exp 的类型：

函数调用：类型由对应函数定义的返回值确定，Int 或 Void。
Number：类型为 Int。
Ident：类型为除了函数的所有情况。
数组：类型为除了函数和数组的所有情况。

自底向上中不断将属性 private SymbolType symbolType 传递和记录，最终 Exp 会获取到实际的类型。

在 FuncRParams 中记录 private ArrayList<SymbolType> paramTypeList，该信息传递给父节点 UnaryExp，至此实参类型列表已获取。

由 FuncSymbol funcSymbol = (FuncSymbol) SymbolManager.getSymbol(ident.getStringValue()); 获取到对应的函数定义，由 funcSymbol.getParamList() 获取到形参列表，至此形参类型列表已获取。

if (node1 instanceof TokenNode &&  
        ((TokenNode) node1).getTokenType().equals(TokenType.RPARENT)) {  
} else if (node1 instanceof FuncRParams) {  
    FuncRParams funcRParams = (FuncRParams) node1;  
    funcRParams.setFuncSymbol(funcSymbol);  
    funcRParams.visit();  
    ArrayList<SymbolType> paramTypeList = funcRParams.getParamTypeList();  
    int i = 0;  
    for (Symbol symbol : funcSymbol.getParamList()) {  
        SymbolType fParamType = symbol.getType();  
        if (i < paramTypeList.size() &&  
                !paramTypeList.get(i).paramEquals(fParamType)) {  
            ErrorCatcher.catchError(new Error(ErrorType.UNMATCHING_FUNC_PARAM_TYPE, ident.getLineNumber()));  
            break;  
        }  
        i++;  
    }  
}

同时需要注意类型的兼容性，ConstInt、StaticInt、Int 和 IntFunc 的实参应该同属于 Int 的形参，ConstIntArray、StaticIntArray 和 IntArray 的实参应该同属于 IntArray 的形参。

f 无返回值的函数存在不匹配的 return 语句：

只考虑 VoidFunc，当 return 中出现实际的 Exp 时报错，有多少行就报多少个错。

在 Stmt 中的 return 分支中判断，由 SymbolManager.getCurSymbolTableFuncSymbol() 获取当前所处函数定义类型。

else if (tokenNode.equals(TokenType.RETURNTK)) {  
    // Stmt → 'return' [Exp] ';'  
    this.setReturnStmt();  
    if (getNode(1) instanceof Exp) {  
        Exp exp1 = (Exp) getNode(1);  
        exp1.visit();  
        if (SymbolManager.getCurSymbolTableFuncSymbol().getType().equals(SymbolType.VOID_FUNC)) {  
            ErrorCatcher.catchError(new Error(ErrorType.UNMATCHING_RETURN, tokenNode.getLineNumber()));  
        }  
    } else if (getNode(1) instanceof TokenNode &&  
            ((TokenNode) getNode(1)).equals(TokenType.SEMICN)) {  
    }

g 有返回值的函数缺少 return 语句：

只考虑 IntFunc，当结束大括号的上一个语句不是正确的 return 时报错。

在 Block 中判断，使用到属性 private boolean isIntFuncBlock，由父节点的 Ident 判断并提供信息。使用到 Stmt 中的属性 private boolean isReturnStmt 以及 BlockItem 中的属性 private boolean isReturnBlockItem，这些信息从 Stmt 的 return 分支中自底向上传递。

if (this.isIntFuncBlock &&  
        (i == 1 || !((BlockItem) getNode(i - 1)).isReturnStmt())) {  
    ErrorCatcher.catchError(  
            new Error(ErrorType.MISSING_RETURN, ((TokenNode) getNode(i)).getLineNumber()));  
}

需要注意 Block 中没有 BlockItem 的情况。

h 不能改变常量的值：

在 Stmt 与 ForStmt 中出现，核心思路是判断 LVal 是不是常量。

lVal.visit();  
if (lVal.isConst()) {  
    ErrorCatcher.catchError(new Error(ErrorType.CHANGING_CONST, lVal.getLineNumber()));  
}

LVal 中包含信息 private boolean isConst，该信息由 Ident 获取。

1
2
3

if (((ValueSymbol) SymbolManager.getSymbol(ident.getStringValue())).isConst()) {  
    this.setConst();  
}

l printf 语句中格式字符与表达式个数不匹配：

在 Stmt 的 printf 分支中判断，由正则表达式解析 StringConst 中的 %d 出现次数，然后对 Exp 计数并判等。

else if (tokenNode.equals(TokenType.PRINTFTK)) {  
    // Stmt → 'printf''('StringConst {','Exp}')'';'  
    TokenNode stringConst = (TokenNode) getNode(2);  
    int formatCharNum = 0;  
    String string = stringConst.getStringValue();  
    java.util.regex.Pattern pattern = java.util.regex.Pattern.compile("(?<!%)%d");  
    java.util.regex.Matcher matcher = pattern.matcher(string);  
    while (matcher.find()) {  
        formatCharNum++;  
    }  
    int expNum = 0;  
    for (Node node1 : nodeList) {  
        if (node1 instanceof Exp) {  
            Exp exp = (Exp) node1;  
            exp.visit();  
            expNum++;  
        }  
    }  
    if (formatCharNum != expNum) {  
        ErrorCatcher.catchError(new Error(ErrorType.UNMATCHING_PRINTF, tokenNode.getLineNumber()));  
    }  
}

m 在非循环块中使用 break 和 continue 语句：

在 Stmt 的 break 和 continue 分支中判断，判断当前符号表在不在 for 符号表中。

else if (tokenNode.equals(TokenType.BREAKTK)) {  
    // Stmt → 'break' ';'  
    if (!this.isForStmt && !SymbolManager.getCurSymbolTable().inForSymbolTable()) {  
        ErrorCatcher.catchError(new Error(ErrorType.INVALID_BREAK_OR_CONTINUE, tokenNode.getLineNumber()));  
    }  
} else if (tokenNode.equals(TokenType.CONTINUETK)) {  
    // Stmt → 'continue' ';'  
    if (!this.isForStmt && !SymbolManager.getCurSymbolTable().inForSymbolTable()) {  
        ErrorCatcher.catchError(new Error(ErrorType.INVALID_BREAK_OR_CONTINUE, tokenNode.getLineNumber()));  
    }  
}

由于存在嵌套，虽然可能处于 if 块，但若 if 块被 for 块包围也算正确，所以需要向上递归查找 for 符号表。SymbolTable 中：

public boolean inForSymbolTable() {  
    SymbolTable symbolTable = this;  
    while (symbolTable != null) {  
        if (symbolTable.isForSymbolTable()) {  
            return true;  
        }  
        symbolTable = symbolTable.getParentTable();  
    }  
    return false;  
}

而是否是 for 符号表的信息在 Block 中设置完成：

1
2
3

if (this.isForBlock) {  
    SymbolManager.getCurSymbolTable().setForSymbolTable();  
}

注意考虑这种情况：

int main() {  
    for(;;) break;  
    return 0;  
}

错误输出：

2 m

第一次 AC 的提交未考虑这种 Stmt 直接解析为 break 而不是 Block 的，后来写文档的时候发现漏洞，修改后提交仍然是 AC。

原思路是以符号表 SymbolTable 为单位进行考察是不是 for 的符号表，但实际上没有 Block 的 for 不会进行建表（因为不计算作用域所以我的实现也没有建表），因此会漏掉这种情况。

BaconToast's Shop