search

Mike-Smith-rem / buaa_compiler

A Record Of Compiler Lesson
1 stars 0 forks source link

readme

2021-秋 编译器实验设计文档

一、文法分析

1、设计

​ 文法分析的目的实际上就是了解Syst这一门课程组所定义的语言的结构，从而更加有利于之后的分析。因此实际上只需要按照文档中的说明进行设计，而不需要考虑太多。下面给出一个示例程序：

const int const_1 = 0;
const int const_2 = 1, const_3 = 2;
int a;
int b, c = 0;
int func_1(int st, int ed){
    const int mod = 2;
    while (st != ed) {
        st = st + 1;
    }
    printf("func_1 complete: int func, int, int\n");
    return 0;
}
void func_2(int a_number, int b_number) {
    printf("func_2 complete: void func, int, int\n");
}
void func_3(){
    return;
}
int func_4() {
    int b_1;
    b_1 = func_1(1, 10);
    const int a_1 = 0;
    func_2(1, a);
    func_3();
    printf("func_3 complete: void func\n");
    return a_1 + b_1;
}
int func_5() {
    printf("func_5 complete: int func\n");
    return 0;
}

int main() {
    func_4();
    printf("func_4 complete: int func\n");
    func_5();
    printf("global const int: const_1 = %d\n", const_1);
    printf("global const int int: const_2 = %d, const_3 = %d\n", const_2, const_3);
    printf("global int: a = %d\n", a);
    printf("global int, int: b = %d, c = %d\n", b, c);
    return 0;
}

二、词法分析

1、设计

​ 词法分析过程需要的写的代码也不多，这一阶段的主要任务还是在于对于Syst语言的理解。因此，此过程只需要考虑以下因素：

​ 相对而言第一和第二次作业较为简单，也是为之后的语法分析做准备。

​ 因此设计如下：

​ 将这两个函数完成之后，词法分析便能够顺利通过了。

2、设计改善

​ 本次词法分析设计改善主要用于之后在错误处理中进行定位。因为符号表的建立是在语法分析阶段之后的，而语法分析的依据是来自于LexMap而不再是OriginFile，因此，为了能够在错误处理中定位到错误所在行数，自建了一个类$MyString$。用于词法分析中保存该word所在行数。

​ MyString的定义位于src/LexAnalyse文件下，和LexAnalyse.java位于同一目录。

public class MyString {
    //和string同定义
    String token;
    int line;

    public MyString(String token, int line) {
        this.token = token;
        this.line = line;
    }

    public String getToken() {
        return token;
    }

    public int getLine() {
        return line;
    }

    public boolean equals(String target) {
        return token.equals(target);
    }

    public void refreshLine() {
        CompilerLoad.current_line = line;
    }
}

​ 因此在结果保存中使用的是HashMap<MyString, String>的结构，当进行错误处理时，只需要通过获取当前Token，然后得到Token中MyString内的Line属性即可定位行数。

三、语法分析

1、设计

（1）结构

​ 当已经有了词法分析的基础时，此时我们已经获得了LexMap，保存并翻译了所有的Token，因此可以新建一个文件夹GrammarAnalyse，其中用于存放对LexMap进行 分析的分析函数，而保证了程序结构的完整性。

​ 另外可以看到需要将每一个非终结符都进行分析，由于java的特性，一个类文件中最好只有一个类，因此需要建立从AddExp直到VarDef等三十多个文件进行逐一分析。另外由于文件用途的相似性，可以建立一个公共类，从而通过继承减少代码的数量。

​ 因此文件结构如下：

​ 另外需要说明的是，LexMap采取的队列结构，也就是java中的Queue。由于输出需要从头到尾输出，而另一方面需要从左到右进行读入，因此采取队列的结构现阶段是合理的（但是另一方面考虑可能在最后代码生成过程中这种结构仍然不太适用）。

​ 本次作业可以不建立符号表，因此只需要如上结构即可。

（2）分析方式

​ 语法分析相对复杂，而且可能出现回溯的问题，因此本次设计中主要采用两种思路：递归下降和预测。

I、父类定义

​ 首先对父类进行定义：

public class GrammarInterface {
    //获得LexMap
    public Queue<HashMap<MyString, String>> LexMap;
    //section用于构造树结构，也就是将递推得到的其他符号添加进当前的非终结符
    public ArrayList<Object> section = new ArrayList<>();
    //output.txt中需要输出的文件
    public Queue<HashMap<MyString, MyString>> OutputMap = new LinkedList<>();

    //需要子类覆写的方法
    public void analyse() {

    }

    //子类共有的构造方法
    public GrammarInterface() {
        LexMap = LexAnalyse.getLexMap();
    }

    //以下是通用可以继承的方法

    //用于比较
    public boolean equals(HashMap<MyString, String> word, String target) {
        ...
    }

    //获得map中前一部分
    public String getToken(HashMap<MyString, String> word) {
        ...
    }

    //获得map中后一部分
    public String getContent(HashMap<MyString, String> word) {
        ...
    }
}

​ 通过对于父类的定义，子类在描述中可以省去很多麻烦，基本只需要覆写analyse方法即可。

II、递归下降

​ 根据对于文法的定义，从CompUnit依次进行递归下降分析。下面以LVal的递归下降分析为例：

public class LVal extends GrammarInterface {
    //LVal -> Ident {'[' Exp ']'}

    @Override
    public void analyse() {
        //Ident
        Ident identF = new Ident();
        identF.analyse();
        section.add(identF);

        //[exp]
        while (equals(LexMap.element(), "LBRACK")) {
            //[
            section.add(LexMap.poll());
            //Exp
            Exp exp = new Exp();
            exp.analyse();
            section.add(exp);
            //]
            section.add(LexMap.poll());
        }

        //最后加入output.txt
        //可以任意用一个标志符来区分原来的LexMap单元和添加的`<>`单元
        ....
    }
}

​ 需要完成的过程基本就是新建非终结符分析单元、进行分析、添加新建单元到当前section中，最后加入output.txt对应的list中。通过这样一个方式，从而可以直接进行递归下降分析，而且通过section也搭建好了子元素。

III、多用预测，避免回溯

​ 显然递归下降中是需要提前了解需要下降到哪一个非终结符。而有些文法可能其FIRST集合存在相同单元，因此无法通过LL（1）分析而直接确定从哪一个区域进行递归下降，而同时为了避免回溯（回溯基本没有考虑，感觉实现过程很麻烦），因此可以多偷看一些单元，从而能够确定应该从哪个非终结符进行递归下降。

​ 这里就以CompUnit为例：

public class CompUnit extends GrammarInterface {

    @Override
    public void analyse() {
        declAnalyse();
        funcAnalyse();
        mainAnalyse();
    }

    public void declAnalyse() {
        while (true) {
            //通过循环查看三个量
            //这里实际上也体现出Queue结构的劣势
            HashMap<MyString, String> firstToken = null;
            HashMap<MyString, String> secondToken = null;
            HashMap<MyString, String> thirdToken = null;
            int time = 0;
            for (HashMap<MyString, String> key : LexMap) {
                firstToken = time == 0 ? key : firstToken;
                secondToken = time == 1 ? key : secondToken;
                thirdToken = time == 2 ? key : thirdToken;
                time += 1;
                if (time == 3) {
                    break;
                }
            }

            assert firstToken != null && secondToken != null && thirdToken != null;

            //之后通过if来分析需要往哪个方向进行递推下降
            if (equals(firstToken, "CONSTTK")) {
                Decl decl = new Decl();
                section.add(decl);
                decl.analyse();
            }
            else if (equals(firstToken, "INTTK")
                    && equals(secondToken, "IDENFR")
                    && !equals(thirdToken, "LPARENT")) {
                Decl decl = new Decl();
                section.add(decl);
                decl.analyse();
            }
            else {
                return;
            }
        }
    }

    public void funcAnalyse() {...}
    public void mainAnalyse() {...}
}

​ 可以看到CompUnit无论是Decl还是funcDef都会使得前两个Token一个为Type一个为Ident，因此通过提前查看三个Token，从而能够分析出需要从哪个方向进行递归下降。

​ 总而言之，实现以上几点，语法分析能够较为轻松的完成。

2、设计改善

​ 这里的设计改善主要针对于某些非终结符。在每一个非终结符中虽然已经利用了section这一个保存Object的数组存入其递推单元，但是之后在值类型、错误分析中仅仅通过section是不够的。比如对于LVal，由于其递推式：

LVal -> Ident {'[' Exp ']'}

​ 实际上可以直接新建一些本地变量保存其值类型等，从而能够为错误处理提供方便。具体的说明还是放在错误处理中。（因为在写错误处理的时候重构了一次，才有了现在的结构）

四、错误处理（debug）

1、重构（以上版本是重构后的内容）

​ 之前的语法分析版本我并没有分出文件结构，所有的文件都在src目录下（当时学习OO的时候没有专注解决的问题），因而加上所有的非终结符类然后加上所有的错误处理A~M有50多个文件看过来确实过于困难，而且在debug过程中基本无解。另外之前并没有构建树（也就是没有加上section单元），无法从一个非终结符了解到其子结构，这样也很难进行错误处理。因此在错误处理延期后，放弃了已有的程序，而重新规划结构，故而进行了重构。

​ 重构后的文件结构如下：

1636440051467

​ 另外新加了很多单元，从而使得代码结构和层次更加清晰。

2、设计思路

​ 预测手段在错误处理中出现了难题。因此错误的存在使得预测可能预测到意想不到的单元。考虑到错误的出现形式多样，因此实际上课程组给出了一定限制，这也使得我的预测手段仍然具有一线生机。

​ 首先在未改动原本程序的情况下需要新建错误处理单元，同语法分析过程，设定了父类WrongFormatAnalyse和子类文件夹WrongAnalyse。子类文件夹包括从A到M的所有错误处理单元。

​ 另外本次需要构建符号表。按照课堂上的说明，选择栈式结构是可行的，而本人设计时也将函数和变量放在了一起，并设置了一个索引单元。

​ 因此本次设计分为以下部分：

3、设计

（1）符号表构建

​ 在Table文件下存在两个文件Table和TableIndex。其中Table表示表的每一个元组，而TableIndex表示表的容器。因此在Table中只需要定义属性，而TableIndex需要完成和外界的交互。

public class Table {
    //const, var, func
    public String specie = "";

    //if const and var
    //ident
    public String name = "";
    //dimen
    public int lev = 0;

    //if func (name inherent)
    //void int
    public String funcType = "";
    //
    public ArrayList<Table> FParams = new ArrayList<>();
    //if return (use in errorAnalyse)
    public boolean returned = false;
}
public class TableIndex {
    //table变量表
    public static Stack<Table> tables = new Stack<>();

    //索引表
    public static Stack<HashMap<Integer, Integer>> index = new Stack<>();

    //当前所在的block级别
    public static int cur_index = 1;

    //当前的循环深度
    public static int while_depth = 0;

    static {
        HashMap<Integer, Integer> head = new HashMap<>();
        head.put(cur_index, 0);
        index.push(head);
    }

    //新建函数时，block级别增加，并添加索引
    public static void loadIndex() {
        TableIndex.cur_index += 1;
        HashMap<Integer, Integer> index = new HashMap<>();
        index.put(TableIndex.cur_index, TableIndex.tables.size());
        TableIndex.index.push(index);
    }

    //函数结束时，block级别降低，并移除索引以及所有临时变量
    public static void pushIndex() {
        int TableSize = TableIndex.index.peek().get(TableIndex.cur_index);
        while (TableIndex.tables.size() != TableSize) {
            TableIndex.tables.pop();
        }
        TableIndex.index.pop();
        TableIndex.cur_index -= 1;
    }

    //用于外界查找
    public static Table searchTable(String name) {
        for (int i = tables.size() - 1; i >= 0; i--) {
            if (tables.get(i).name.equals(name)) {
                return tables.get(i);
            }
        }
        return null;
    }
}

​ 这样下来一个相对完整的符号表体系就构建完成了，并且符号表能够监控分析过程中的循环深度以及block级别，实现了栈式结构，为错误处理的作用域分析提供了有力保障。

（2）行定位

​ 考虑处理这一问题时，我也考虑直接用全局变量来进行监测。但是问题在于这个全局变量如何能够获得当前行数，或者通过哪种方式得到当前行数。因此在上文中我定义了MyString类就是为行定位服务的。因为自身的程序只有在词法分析扫描时会直接扫描源程序，而后续扫描都将基于前一次扫描得到的结果，此时可能会丢失行信息。

​ 因此在每次错误处理分析之前通过MyString更新所在行，将其赋给全局变量current_line，从而能够实现行定位。

​ 在CompilerLoad中加入了新的方法：

public static int getCurrent_line() {
    //获取顶端元素
    HashMap<MyString, String> item = LexAnalyse.getLexMap().element();
    for (MyString string : item.keySet()) {
        string.refreshLine();
    }
    return current_line;
}

​ 其中refreshLine在MyString中实现：

public void refreshLine() {
    CompilerLoad.current_line = line;
}

​ 通过词法分析将行信息提前保存在MyString中，继而为错误处理的行定位提供了方便。

（3）错误处理单元和调用

I、声明

​ 首先说一下父类WrongFormatAnalyse，父类仅仅帮助子类定义了变量：

public class WrongFormatAnalyse {
    public static ArrayList<String> errorReport;
    public static Stack<Table> tables;
    public static int cur_index;
    public static Stack<HashMap<Integer, Integer>> index;
    public static int while_depth;

    public WrongFormatAnalyse() {
        //在CompilerLoad中增加errorReport的list单元，用于output输出和错误处理输出
        errorReport = CompilerLoad.errorReport;
        tables = TableIndex.tables;
        cur_index = TableIndex.cur_index;
        index = TableIndex.index;
        while_depth = TableIndex.while_depth;
    }
}

​ 实际上必要性不大。

​ 而对于子类的实现实际上需要和原本语法分析的程序建立好连接，确定好错误处理单元所传入的参数，比如d类错误传入三个参数（函数名称、函数需要变量的数量和实际传入的数量），而e类错误传入两个参数（函数名称、传入的参数构成的表），不具有统一性，从而能够实现错误处理。这里的细节就不做过多说明了。

II、调用

​ 调用的方式是在语法分析程序中进行调用的，而修改的地方是根据文档中说明的地方进行修正的。

1636443098485

​ 一般来说可以直接找到对应的语法分析单元进行修正，比如对于a类错误直接在formatString中修改：

public class FormatString extends GrammarInterface {
    public int numberOfD = 0;
    public String content = "";

    @Override
    public void analyse() {
        content = getContent(LexMap.element());

        //以下两行直接调用错误处理
        A_FormatString formatString = new A_FormatString();
        formatString.check(content, CompilerLoad.getCurrent_line())；

        for (int i = 0; i < content.length(); i ++) {
            if (content.charAt(i) == '%'
                    && i + 1 < content.length()
                    && content.charAt(i + 1) == 'd') {
                numberOfD += 1;
                i += 1;
            }
        }
        section.add(LexMap.poll());
    }
}

​ 但是有的需要寻找合适的位置以及添加相应的变量才能实现。

​ 比如在处理break和continue的时候需要新建变量while_depth（在符号表索引中建立），从而才能直接在break和continue中调用，实现方式如下：

public class M_UnNeededToken extends WrongFormatAnalyse {
    public void check(int current_line) {
        //如果当前没有while循环
        if (while_depth == 0) {
            errorReport.add(current_line + " m\n");
        }
    }
}

​ 而对于g类错误则必须在整个函数结束之后才能调用。

​ 因而g类错误的调用我放在了CompUnit下面：

//以main方法为例
public void mainAnalyse() {
    MainFuncDef mainFuncDef = new MainFuncDef();
    section.add(mainFuncDef);
    mainFuncDef.analyse();

    //函数分析完成后调用
    G_LackReturn g_lackReturn = new G_LackReturn();
    g_lackReturn.check(CompilerLoad.current_line);
}

​ 而g类错误本身的定义也需要进行对应更改：

{
    public void check(int current_line) {
        //通过查找刚刚结束的函数,而不是在}之前
        Table func = getLatestFunc();
        boolean wrong = false;
        if (func != null && func.specie.equals("func")
                && !func.funcType.equals("void")
                && !func.returned) {
            wrong = true;
        }
        if (wrong) {
            errorReport.add(current_line + " g\n");
        }
    }

    public Table getLatestFunc() {
        for (int i = tables.size() - 1; i >= 0; i--) {
            if (tables.get(i).specie.equals("func")) {
                return tables.get(i);
            }
        }
        return null;
    }
}

​ 这样的细节需要根据自身的程序进行决定，不具有统一性，因而只提出几个代表进行说明。

（4）操作和实现的一些细节（冲突解决）

​ 这里所谓的细节，就是我在进行预测和错误处理可能产生的冲突。因为存在错误使得预测可能得到意想不到的结果。

​ 这里的我主要以return为例：

​ 可能出现的return错误形式：

return 
return [exp]
return ;

​ 如果按照我的预测方式我会通过是否下一个元素为;从而判断进行Exp分析。如果是那么直接将;加入section， 否则进行Exp分析。但是加入错误处理后，可能不存在分号而产生歧义，此时再次进行Exp分析势必会产生RunTimeError。从而出错。

​ 另一方面Exp本身是很难分析其起始变量的，从而使得解决这样的冲突变得十分困难。

​ 这里最后考虑到不会出现恶意换行，因此我才解决了难题：

//RETURN
case "RETURNTK":
    //更新行数
    CompilerLoad.getCurrent_line();
    //用于g类错误分析
    Table func = getLatestFunc();
    if (func != null && func.funcType.equals("void")) {
        func.returned = true;
    }
    section.add(LexMap.poll());

    //分析过程
    //getline获取return后面Token行数
    //如果行数相同，证明后面是exp，可以进行exp分析
    if (!equals(LexMap.element(), "SEMICN")
        && getLine(LexMap.element()) ==         
        CompilerLoad.current_line) {

        //这里借用funcRParam进行分析，（funcRParam中定义了值类型，用于f类错误）
        //之后会进一步改进，将值类型分析其转移到exp
        FuncRParams funcRParams = new FuncRParams();
        funcRParams.analyse();
        ...
    }
    //;

​ 这样的问题不止一处，但是也不是很多。通过条件的限制，从而能够完成对错误处理的分析和判断。

五、代码生成

​ 代码生成考核中我选择的是PCode，而在提交的代码中该部分所对应的文件夹为src/CodeLoad。该文件夹下包括MidCodeGenerate（中间代码生成）、PCodeGenerator（最终代码生成）、PCodeAnalyser（解释器）以及解释器执行中需要的符号表PCodeTable。通过这样一层设计，从而代码结构十分清晰；同时，设计了最终代码和中间代码也使得在Debug的过程中容易许多。

​ 因而根据文件结构，对于代码生成分成四个部分进行分析。

1639622537843

1、中间代码

（一）文件结构

​ 中间代码对应的文件夹为MidCodeGenerate，该文件夹的目录如下：

1639622639205

​ 由于通过语法分析和错误处理后，得到的是一个类似语法树的结构，此时的根节点是整个编译起始非终结符CompUnit，在语法分析设置的section结构中存储了子节点，因此仍需要进行一遍类似于语法分析过程的每一个非终结符的分析，以便分析一遍生成中间代码，从而需要如上的结构。

​ 从上文可知，个人在定义section的时候存储的数据类型是Object，因此此时java中的instanceOf关键词会非常重要。

​ 另外生成中间代码的过程中需要进行部分的计算和生成中间变量等，因此也必须需要一个临时的符号表来进行插入和查询。

（二）实现原理和过程

​ 该过程的目标很明确，就是要生成中间代码，而中间代码的格式参照课程组给出的推荐格式。

（三）临时符号表的构建

​ 这里同语法分析类似，同样构建了临时的符号表；这里构建的临时符号表有两个用处：

  1. 计算常量。

    很多编译器都是提前将常量计算好之后再转入运行栈，因此同样的本次设计也添加了提前计算出常量的代码，而常量的存储需要符号表。

  2. 存储中间变量

    因为中间代码生成需要中间变量加持，所以个人觉得还是需要一个符号表来临时放置一下中间变量。但是最后似乎作用不是很明显。

​ 虽然说中间代码生成也使用了临时符号表，但是在完成整个作业之后感觉其实际意义可能主要在于计算常量中。

（四）生成结果

​ 这里简单给出程序示例，从而展现出中间代码的生成。

​ 源程序是输出指定数字的阶乘。

2、目标代码

（一）文件结构

​ 在src/CodeLoad/PCodeGenerator/PCodeGenerate.java中实现了从中间代码转变为目标代码。

（二）实现过程

3、解释器

（一）文件结构

​ 解释器位于src/PCodeAnalyse/PCodeAnalyser.java中。

（二）实现过程

4、符号表的建立

​ 符号表的文件位置如下：可以看到总共有7个文件；其中主要由PCodeFuncBlock和PCodeBlock实现作用域，PCodeTableIndex是整个表中最重要的索引。

1639815321103

（一）设计

（二）作用域问题

六、代码生成编码后改进

针对条件语句先后执行的改进

​ 之前一直忽略了所谓编译文档中“短路求值”的规则含义；而当我将整个编译过程设计完成，包括作用域的一系列问题都解决了之后突然de出了这一个致命的问题。如何在已有的整体架构上实现这一突然出现的问题确实让我不知所措。吸取了第一次错误处理时的重构教训，因此极力考虑如何能够满足短路求值的判断。

​ 最后从中间代码入手，因为我发现自己在设计中间代码的过程中，条件语句的最终中间变量的名称是确定的——一定是@LOrExp + 次数，因此考虑到新增一个指令定义Case，从而解决了这一问题，避免了可能重新设计的风险。

​ 可以看到中间代码对于条件语句的生成如下：

//在Load_LAndExp的addSentence方法中

midInterface = new MidTable();
midInterface.name = "@LAndExp" + varNum;
varNum += 1;
MidInterface a;
MidInterface b;
...
midCode.add(midInterface.name + " #REPLACE " + a.name + " && " + b.name);

​ 因此实际上最终表示条件比较语句结果的中间代码是预先知道的：类名+次数。

​ 由于这个信息存在，因此在上述语句比较之前可以增加一条语句：

midCode.add("#Case0 " + exp.midInterface.name + " @LAndExp" + varNum);

​ 从而解释器执行过程中会优先遇到Case语句，从而实现短路求值截断，及时作出判断了。