编译器设计文档

参考编译器介绍

总体结构

接口设计

编译器总体设计

总体结构

接口设计

文件组织

|   Compiler.java
|   config.json
|   error.txt
|   lexer.txt
|   llvm_ir.txt
|   parser.txt
|   symbol.txt
|   testfile.txt
|
|
+---CompileErrors
|       CompileError.java
|       CompileErrorHandler.java
|
+---Datas
|       AstNode.java
|       MiddleData.java
|       SymbolTable.java
|       Token.java
|
+---Lexical
|       CheckTools.java
|       Lexer.java
|
+---LLVMGenerate
|       Instruction.java
|       LLVMer.java
|
|
+---Semantic
|       Semanticer.java
|
\---Syntax
        CheckTools.java
        Parser.java

词法分析

编码前

• 信息数组（token, name, lineNumber, columnNumber)

• enum TokenType记录token类别

• token分析函数analyze（包括过滤空白符和调用自动机）

• next方法用自动机解析token

有穷自动机解析

一段顺序代码段实现有穷自动机的某一状态

分支：转移至其他状态

循环：同一状态转移

采用贪婪匹配，故在识别到终止状态后需要吐出最后一次识别的字符

状态机：

编码后

无修改

语法分析

编码前

• 在每个分析函数的末尾输出语法树节点信息

• 分析每个产生式的First集来决定用哪条推导规则

• 主要是exp簇文法，将文法改写成右递归

• 此时语法树被修改，需要在每次解析下列文法的非最后一项时多输出一个左式的Exp

• 同时注意语法树结构已经被更改，一个xxExp的子节点并非迭代的，而是在同一层

MulExp → UnaryExp | MulExp ('*' | '/' | '%') UnaryExp
AddExp → MulExp | AddExp ('+' | '−') MulExp
RelExp → AddExp | RelExp ('<' | '>' | '<=' | '>=') AddExp
EqExp → RelExp | EqExp ('==' | '!=') RelExp
LAndExp → EqExp | LAndExp '&&' EqExp
LOrExp → LAndExp | LOrExp '||' LAndExp

• 预读几个字符后即可决定采用哪个式子进行推导

• 仅在分析到终结符之后才moveToNextSym()（将分析指针移到下一个token）

编码后

Stmt → LVal '=' Exp ';'
| [Exp] ';'

public class AstNode extends MiddleData {
    // root of AstNode, <CompUnit>
    public static AstNode root;
    public String token;
    public ArrayList<AstNode> children = new ArrayList<AstNode>();
    public int lineno;

    public AstNode(String token) {
        this.token = token;
    }

    public void addChild(AstNode child) {
        children.add(child);
    }

    /**
     * @Description 删除最后一个节点并返回，用于左递归文法改造
     * 后需要在cur和最后节点中间插入一个AstNode的情况
    **/

    public void insertLast(AstNode nodeToInsert) {
        AstNode last = children.get(children.size() - 1);
        children.remove(children.size() - 1);
        children.add(nodeToInsert);
        nodeToInsert.addChild(last);
    }

    public void output(FileWriter writer) {
        try {
            for (AstNode child : children) {
                child.output(writer);
            }
            writer.write(this.token + "\n");
        } catch(IOException e) {
            System.out.println(e.getMessage());
        }
    }
}

    private void MulExp(AstNode parent) {
        AstNode cur = new AstNode("<MulExp>");
        UnaryExp(cur);
        while (curSym.tokenType == MULT || curSym.tokenType == DIV 
	        || curSym.tokenType == MOD) {
            // Because I shift Left Iteration to right one,
            // So I need to output one more <MulExp> after
            //  each <UnaryExp> except the last one
            AstNode tmp = new AstNode("<MulExp>");
            cur.insertLast(tmp);
//            output("<MulExp>");
            TerminalSym(cur);
            UnaryExp(cur);
        }
        parent.addChild(cur);
//        output("<MulExp>");
    }

语义分析

编码前

public class Symbol {
	public int id;
	public int tableId;
	public String token;
	
	public SymbolType symType;
	public ConstType conType; 
	public BType bType;
	
	public int value;  // for var
	
	// for func
	public ReturnType rtType;
	public int paraCount;
	public ArrayList<FuncParameter> paras;
}

class FuncParameter {
	public Btype bType;
	public SymbolType symType;
	public String token;
}

public SymbolTable{
	public int id;
	public int parentId;
	public ArrayList<int> childrenId;
	public HashMap<String, Symbol> content;
}

• <Block>（FuncDef下遇到的第一个Block除外，此时在FuncFParams处迭代层数）
• 新建SymbolTable(maxLayer + 1, curLayer)，更新当前层数信息

• <VarDecl>
• 检查当前层中是否有同名变量
• 判断数组or变量，然后在当前符号表中添加一条变量记录（new Symbol()）

• <ConstDecl>
• 同上，增加常量纪录

• <FuncDef>
• 检查重定义
• 判断returnType，添加函数记录

• <FuncFParams>
• 层数迭代一次，然后准备记录参数
• 子<FuncFParam>：添加变量记录

• 由于除开全局变量和函数定义以外，仅<Block>会推导出<Decl>，故在进入<MainFuncDef>的<Block>之后推导<Stmt>时，只分析含有<Stmt>和<Block>的分支，否则直接跳出去
• Block
• ‘if’
• ‘for’

编码后

错误处理

语义分析

• b: 名字重定义√
• 每次解析符号时，解析到Ident时判断当前层有无同名符号

• c: 未定义的名字√
• Stmt, ConstDef, InitVal, ConstInitVal, FuncRParam, PrimaryExp → Exp / ConstExp
• 对Exp和LVal → Ident进行迭代解析
• Exp: 迭代至UnaryExp时，若First是Ident则 在最外层 寻找该符号对应的函数是否存在，不在则报错Ident所在行号；其他情况继续迭代
• LVal: 若Fisrt是Ident，则 从当前层到最外层依次 找该符号存在与否，不在则报错

• d: 函数调用参数个数不匹配√
• UnaryExp → Ident时，若Ident存在，但它是个变量 或 此处调用所使用的形参个数不等于实参个数则报错

• e: 函数调用参数类型不匹配
• 编码前
• UnaryExp → Ident时，若Ident存在，则依次与Ident的Symbol中的参数的类型进行比较，但是不急着加入错误列表。若参数个数相同，则报错e，否则报错d
• 编码后
• 函数实参全是以Exp的形式存在的，需要特别判断其类型
• 定义全局的RParamVarType和RParamBType
• 通过向下迭代遍历实参来确定其VarType和BType
• 只需要判断实参对应的Exp的第一个变量即可，因为本实验规定不会出现Exp中变量类型不匹配的问题（如数组 + 变量）

• f: 无返回值函数存在不匹配的return语句√
• 定义funcSymbol和isInFunction记录当前遍历位置是否在函数内部
• 解析到Stmt时，若First是return且isInFunction == true 且 funcSymbol.rtType == VOID，则判断second（可能不存在）是否为Exp，是则报错f，报在return所在行号

• g: 有返回值函数缺少return√
• 定义bool hasReturn来记录当前函数是否有返回值
• 解析到Stmt时，若First是return且isInFunction == true 且 funcSymbol.rtType != VOID，则令hasReturn = true
• 在FuncDef中解析Block的时候，若遍历到”RBRACE }” 且 hasReturn == false则报错

• h: 不能改变常量的值√
• Stmt, FosStmt → LVal = …
• Stmt → ‘for’ …: 解析for时，迭代解析ForStmt
• 判断First是否为LVal，先判断错误c，若存在当前常量则判断是不是常量，是的话直接报错h（文法保证First是LVal的都是赋值语句）

• l: printf格式字符与表达式个数不匹配√
• Stmt → printf时，遍历子节点
• StringConst: 解析里面有多少个”%d”和”%c”，记录个数
• 统计遇到过多少个Exp
• 二者比较即可

• m: 非循环块中使用break和continue
• 定义loopDepth记录当前所在的循环层数
• loopDepth在进入for循环的Stmt时+1，离开（For语句遍历结束）时-1
• 若在loopDepth == 0时解析到break / continue，则报错m

中间代码生成

LLVM IR 简单实例

LLVM IR结构

接口设计

属性传递 & 寄存器设计

// psudo
generate(a.child);
a.setPropertyX(a.child.propertyX);

常量表达式

else if (first.token.startsWith("<Character>")) {
            // char
            String charStr = first.children.get(0).token.split("'")[1]; 
            // CHRCON 'c'
            if (charStr.length() > 1 && charStr.charAt(0) == '\\') {
                int asciiCode = 0;
                switch (charStr.charAt(1)) {
                    case 'a' -> asciiCode = 7;
                    case 'b' -> asciiCode = 8;
                    case 't' -> asciiCode = 9;
                    case 'n' -> asciiCode = 10;
                    case 'v' -> asciiCode = 11;
                    case 'f' -> asciiCode = 12;
                    case '"' -> asciiCode = 34;
                    case '\'' -> asciiCode = 39;
                    case '\\' -> asciiCode = 92;
                }
                node.setValueReg(Integer.toString(asciiCode));
            } else {
                node.setValueReg(Integer.toString(charStr.charAt(0)));
            }

局部变量（无数组）初始化

局部变量（无数组）赋值

块与符号表 & 符号引用

全局变量初始化

// Assign
if (layer == 1) {
    output("@" + ident.token + " = dso_local global i32 " + 
	    initExp.valueReg + "\n");
}

// Load (LVal)
if (ident.layer == 1) {
		output("%v" + this.addressReg + " = load i32, i32* @" +
			 ident.token + "\n");
}

函数声明

public void MainFuncDef (AstNode ast) {
    output("\ndefine dso_local i32 @main() {\n");
    generate(ast.getChild().get(4)); //Block
    output("}\n");
}

函数调用

int与char

Array

• 全局

• 局部

• const数组
• 将ConstInitVal的变量各自计算出真值后直接存到Symbol的valueArray里
• 仍然需要显式在中间代码中定义

• 记得在symbol中记录数组size

• const数组元素（ConstExp不存在这种情况）

• 全局数组：类比FuncRParams，ConstInit的valueReg存一个初始化字符串序列（[i32 1, i32 2, i32 0]），通过计算Exp的真值生成 √

• 局部数组：不懂…感觉只能拿一个指针寄存器一个个取数组元素的地址然后store √

• InitVal: 在VarDef / ConstDef里遍历到的时候，先给InitVal节点设置addressReg为当前数组的AddressReg，在InitVal的时候逐个遍历 直接在Def节点这里跨一个initVal遍历就好 √

define dso_local i32 @f(i32* %f0) {
	%v0 = alloca i32*
	store i32* %f0, i32** %v0
	%v2 = load i32*, i32** %v0  ; v2 是 %f0对应的参数的addressReg
	%v3 = getelementptr inbounds i32, i32* %v2, i32 1
	store i32 2, i32* %v3
}

define dso_local i32 @main() { {
  %v1 = alloca [5 x i32]

  ; 使用 GEP 获取指向数组第一个元素的指针
  %v1_first_element = getelementptr inbounds [5 x i32], [5 x i32]* %v1,
   i32 0, i32 0

  ; 将指向第一个元素的指针传递给函数 @f
  call void @f(i32* %v1_first_element)
}

分支语句与Cond处理

• Cond → LOrExp

• LOrExp → LAndExp | LOrExp '||' LAndExp

• LAndExp → EqExp | LAndExp '&&' EqExp

• EqExp → RelExp | EqExp ('==' | '!=') RelExp

• RelExp → AddExp | RelExp ('<' | '>' | '<=' | '>=') AddExp

    private void LOrExp(AstNode node) {
        ArrayList<AstNode> children = node.children;

        for (int i = 0; i < children.size() - 2; i += 2) {
            String nextExpLabel = "label" + this.labelId++;
            AstNode curExp = children.get(i);
            curExp.setTrueLabel(node.trueLabel);
            curExp.setFalseLabel("%" + nextExpLabel);
            generate(curExp);
            output("\n" + Instruction.tabs() + nextExpLabel + ":\n");
        }
        AstNode lastExp = children.get(children.size() - 1);
        lastExp.setTrueLabel(node.trueLabel);
        lastExp.setFalseLabel(node.falseLabel);
        generate(lastExp);
    }

// Last EqExp of a LAndExp which should generate the instruction of 
// condition check and jump
if (node.token.equals("<EqExp>") && node.trueLabel != null 
	&& node.falseLabel != null) {
		String notZeroReg = "%v" + this.varRegId++;
		Instruction.notZeroInstruction(notZeroReg, node.valueReg);
		Instruction.beZeroJumpInstruction(notZeroReg, node.trueLabel, 
			node.falseLabel);
}

for循环