Compiler lab

实验课地址（包括对应实验包下载）：https://hitsz-cslab.gitee.io/compiler/

实验一词法分析

实验任务：

确定词法规则对应的 DFA
确定自动机状态, 转移方式, 以及在特定转移步骤时要采取的动作
使用 switch 以状态机方式实现词法分析器

也就是把下面的转换成对应的Token形式：

int result;
int a;
int b;
int c;
a = 8;
b = 5;
c = 3 - a;
result = a * b - ( 3 + b ) * ( c - a );
return result;

// 只选取了一部分展示
(int,)
(id,result)
(Semicolon,)
(int,)
(id,a)
(Semicolon,)
(int,)
(id,b)
(Semicolon,)
(int,)
(id,c)
(Semicolon,)
(id,a)
(=,)
(IntConst,8)

对于词法分析，需要的结果就是词法单元token:(种别码，属性值)这样的二元组。正式去做实验之前还要提前看一些已经实现好的代码框架，因为是用Java实现的，所以很自然就把token定义成了类😀，这里简要说明一下，需要去浏览一下Term、TokenKind、Token，SymbolTableEntry这四个类的实现，Term对应的其实就是所有文法符号 (终止符与非终止符) 的基类，TokenKind对应的是词法单元类型，其实就是对应着种别码，Token是语法单元的实现，是词法分析的结果，除了含有种别码之外，还有属性值，对应上面二元组的第二个元素。SymbolTableEntry是符号表条目，类似于TokenKind实例，是SymbolTable所要维护的。

TokenKind实例 -> (String id, int code)

TokenKind类中用来维护关键字的映射集合allowed -> HashMap<String, TokenKind>

Token实例 -> (TokenKind kind, String text)

创建Token实例的两种方法：

normal(String tokenKindId, String text)
normal(TokenKind kind, String text)

第一种就是一般标识符，符号表维护的，对应去生成Token，第二种是关键字，或者数字常量这种在TokenKind中已经有维护的。

先看Main函数，第一问中涉及到的代码如下：

   TokenKind.loadTokenKinds(); // 这个是加载一些关键字，coding-map.csv文件
   final var symbolTable = new SymbolTable(); // 这个是字符表，用来存标识符的

   // 词法分析
   inal var lexer = new LexicalAnalyzer(symbolTable);
   lexer.loadFile(FilePathConfig.SRC_CODE_PATH);
   lexer.run();
   lexer.dumpTokens(FilePathConfig.TOKEN_PATH);
// tokens的格式: [(int,), (id,result), ...]
symbolTable.dumpTable(FilePathConfig.OLD_SYMBOL_TABLE);

这样会得到两个输出，分别存在data/out/token.txt和data/out/old_symbol_table.txt。

主要还是获得LexicalAnalyzer进行处理后得到的tokens，在LexicalAnalyzer需要完成loadFile函数、run函数、getTokens函数，此外还要完成SymbolTable类的设计。

首先来说SymbolTabel类的设计，这个我是参考了TokenKind的实现，因为实际上，TokenKind首先会调用loadTokenKinds这个方法，是用来加载关键字，这个逻辑和SymbolTalbel维护那些不是关键字的标识符很像。可以说，SymbolTalbel所要实现的功能就是TokenKind中维护关键字部分的内容。

其实也就是创建一个映射Map的成员变量Map<String, SymbolTableEntry> allowed，然后对应TokenKind类去完成add和has函数的设计。

对于输入文件，我是读到了这个成员变量里：

1	private List<String> txtList = new ArrayList<String>(); // 这个是读入文件的存储list，每个元素存了一行的字符串

1	private ArrayList<Token> tokens = new ArrayList<Token>(); // 这个是最终存tokens的数据结构

然后词法分析的过程如下：

public void run() {
        // TODO: 自动机实现的词法分析过程
        // while + switch 实现
        // 各种if else进行逻辑的判断
        /*
        简单说一下思路：关键字符号标识符
        对于读入的每行数据，需要进行如下的判断：
        1. 是不是空字符，是的话就直接跳过
        2. 是不是数字常量，是的话就截取整个数字，然后加上token
        3. 是不是标识符or关键字
        4. 是不是运算符
        * */


        int count = 1; // 计数行的变量

        while (count <= txtList.size()) {
            var line = txtList.get(count - 1);
            int index = 0; // 这里是用index结合CharAt进行搭配，对每行的每个元素进行遍历
            while (index < line.length()) {
                var ch = line.charAt(index);
                if (Character.isWhitespace(ch)) {
                    index++;
                }

                // 识别常量数字
                else if (Character.isDigit(ch)) {
                    var startIndex = index++;
                    ch = line.charAt(index);
                    while (Character.isDigit(ch)) {
                        index++;
                        ch = line.charAt(index);
                    }
                    String s = line.substring(startIndex, index);
                    var tokenKind = TokenKind.fromString("IntConst");
                    tokens.add(Token.normal(tokenKind, s));
                }


                else if (Character.isAlphabetic(ch)) {
                    // 先把串读进来，再去看是标识符还是关键字
                    var startIndex = index++;
                    ch = line.charAt(index);
                    while (Character.isAlphabetic(ch) | Character.isDigit(ch)) {
                        index++;
                        ch = line.charAt(index);
                    }
                    String s = line.substring(startIndex, index);

                    // 如果是关键字
                    if (TokenKind.isAllowed(s)) {
                        var tokenKind = TokenKind.fromString(s);
                        tokens.add(Token.simple(tokenKind));
                        // 在标识符表中
                    } else {
                        var tokenKind = TokenKind.fromString("id");
                        tokens.add(Token.normal(tokenKind, s));

                        // 将id类型的变量存入到符号表中
                        if (!symbolTable.has(s)){
                            symbolTable.add(s);
                        }


                    }
                }

                // 运算符
                else {
                    ch = line.charAt(index);
                    TokenKind tokenKind;
                    switch (ch) {
                        // 这里只写了需要用到的，其他的就展示不考虑
                        case '=' : tokenKind = TokenKind.fromString("=");break;
                        case '+' : tokenKind = TokenKind.fromString("+");break;
                        case '-' : tokenKind = TokenKind.fromString("-");break;
                        case '*' : tokenKind = TokenKind.fromString("*");break;
                        case '/' : tokenKind = TokenKind.fromString("/");break;
                        case '(' : tokenKind = TokenKind.fromString("(");break;
                        case ')' : tokenKind = TokenKind.fromString(")");break;
                        case ',' : tokenKind = TokenKind.fromString(",");break;
                        case ';' : tokenKind = TokenKind.fromString("Semicolon");break;
                        default : throw new RuntimeException("Undefined");
                    }
                    tokens.add(Token.simple(tokenKind));
                    index++;
                }
            }

            count ++;

        }

        // 为文件末尾加上EOF
        tokens.add(Token.eof());
        tokens.forEach(System.out::println);
        System.out.println(tokens.size());
    }

实验二语法分析

对于状态栈和符号栈，用java自带的数据结构

1	Stack<Integer> st = new Stack<Integer>();

.push 和 .pop 分别对应入栈出栈

s是栈顶的状态，a是当前读到的token，t是下一个状态

LR语法分析流程伪代码：

非终结符 Shift：
获取当前步的ACTION[s,a]，这个调用status的status.getAction(a)
ACTION[s,a] = status.getAction(a)
t是ACTION[s,a].getStatus
终结符 Goto：
Produciton是ACTION[s,a].getProduction
我们需要的B长度其实就是这个Production的body长度，body是个List
GOTO[t, A]这个状态是ACTION[s,a].getStatus

while(1):
	if(ACTION[s,a] = ActionKind.Shift t):
		push t-> status stack
		push a -> symbol stack
		a <- next input token
		callWhenInShift // output the grammar?
	elif(ACTION[s,a] = reduce(A->B)):
		status stack and symbol stack pop Production.body.size() 个元素
		push GOTO[t, A] -> status stack
		a <- next input token
		callWhenInReduce
	elif(ACTION[s,a] = accept):
		callWhenInAccept
		break

完整代码：

public void run() {
    // TODO: 实现驱动程序
    // 你需要根据上面的输入来实现 LR 语法分析的驱动程序
    // 请分别在遇到 Shift, Reduce, Accept 的时候调用上面的 callWhenInShift, callWhenInReduce, callWhenInAccept
    // 否则用于为实验二打分的产生式输出可能不会正常工作
    Stack<Status> statusStack = new Stack<Status>();
    Stack<Term> symbolStack = new Stack<Term>();

    //初始化
    Status s = lrtable.getInit();
    Action ACTION = null;
    TokenKind a = null;
    NonTerminal A = null;
    List<Term> B = null;
    int count = 0;
    statusStack.push(s);

    while(true){
        if(count <= input_tokens.size()-1){
            a = input_tokens.get(count);
        }else {
            a = input_tokens.get(input_tokens.size()-1);
        }
        s = statusStack.peek(); // 获取当前步骤的状态
        ACTION = s.getAction(a);

        if (ACTION.equals(Action.error())){
            System.out.println("error!");
            break;
        }

        if(ACTION.getKind() == Action.ActionKind.Shift){
            statusStack.push(ACTION.getStatus());
            symbolStack.push(a);
            callWhenInShift(s,Tokens.get(count));
        }

        else if (ACTION.getKind() == Action.ActionKind.Reduce){
            B = ACTION.getProduction().body();
            A = ACTION.getProduction().head();
            for(int i = 0; i < B.size(); i++){
                statusStack.pop();
                symbolStack.pop();
            }
            s = statusStack.peek(); // 要重新获取一下栈顶
            if (s.getGoto(A) == Status.error()){
                System.out.println("Reduce error!");
                break;
            }
            statusStack.push(s.getGoto(A));
            symbolStack.push(A);
            callWhenInReduce(s,ACTION.getProduction());
            count--; // 规约的话是不读的

        }
        else if (ACTION.getKind() == Action.ActionKind.Accept){
            callWhenInAccept(s);
            break;
        }
        count++;
    }