github.com/acsoto/BUAA-Compiler @main

24.7.30 前来更新一下这个README。发现有很多学弟学妹有参考到这个仓库，甚至前两年有学弟好几次来很详细地问了代码里面的很多实现和思路，本以为大家不屑于写PCODE，没想到能帮助到大家，还是很感恩得到认可，有问到好多我自己也想不起来的于是又重新看了代码和文档，也是帮我重新完整的复习了一遍。

之前里面的英语一大堆语法错误，所以大致修改了一下。另外那个有点迷惑的Before Coding After Coding是因为课程要求文档要写代码前后的设计思路，保留了这个写法。

---

可切换分支查看每个设计阶段的代码，分为词法分析，语法分析，错误处理，代码生成四个部分。

设计有限自动机进行词法分析，处理非法字符，建立抽象语法树，使用递归下降方法进行语法分析和错误处理，将SysY语言编译为PCode代码，最终设计了对应的虚拟机进行解释执行。

Lexical Analysis 词法分析

Before Coding

Requirement: Read testfile.txt, parse every character into words and print them. At the same time, memorize the type, content, and line number of each word.

File reading

Read by line, scan every character of every string and analyze.

while ((s = bf.readLine()) != null) {
    ...
}

Analyse

After identifying the current token, continue with the next step of analysis.

while ((c = getChar()) != null) {
  if (c == ' ' || c == '\r' || c == '\t') {
    continue;
  } else if (c == '+' || c == '-' || c == '*' || c == '%') {
    words.add(new Word(c));
  } else if (c == '/') {
    analyseSlash();
  } else if (c == '(' || c == ')' || c == '[' || c == ']' || c == '{' || c == '}') {
    words.add(new Word(c));
  } else if (c == '>' || c == '<' || c == '=' || c == '!') {
    analyseRelation(c);
  } else if (c == ',' || c == ';') {
    words.add(new Word(c));
  } else if (c == '"') {
    analyseCitation();
  } else if (c == '&' || c == '|') {
    analyseLogic(c);
  } else if (Character.isDigit(c)) {
    analyseDigit(c);
  } else if (Character.isLetter(c) || c == '_') {
    analyseLetter(c);
  }
}

Common

For example, when encountering +, directly create a new Word and classify it as PLUS.

Function

For example

When encountering <, enter the function analyseRelation to read one more character. If it is =, classify it as LEQ...

if (c == '<') {
  c = getChar();
  if (c == '=') {
    words.add(new Word("<="));
  } else {
    unGetChar();
    words.add(new Word("<"));
  }

analyseLogic works in the same way.

Digit and Letter

Digit: When encountering a digit, scan a sequence of digits and turn it into a Word classified as INTCON.

Letter: When encountering a letter, scan a string of letters or digits. It may become IDENFR or STRCON, depending on whether it exists in the keyword map.

Word

class Word:

public class Word {
    private String identification;
    private String content;
    private String type;
}

Encapsulate the initialization logic so that only new Word(...) is needed in the main processor, which will create the corresponding token.

For example

    public Word(char identification) {
        this.identification = String.valueOf(identification);
        this.type = new KeyWordMap().getType(this.identification);
        this.content = this.identification;
    }

KeyWordMap is a HashMap that maps each token string to its type.

    public KeyWordMap() {
        keyWords = new HashMap<>();
        keyWords.put("main", "MAINTK");
        keyWords.put("const", "CONSTTK");
        keyWords.put("int", "INTTK");
        ...
        }

After Coding

File reading

Reading the file line by line is not convenient for lookahead or undo operations, so the file is first read into a single String.

The method reads the file line by line, appends \n after each line, and then scans every character. When \n is encountered, lineNum++.

    private String transferFileToCode() {
        BufferedReader bf = new BufferedReader(reader);
        StringBuffer buffer = new StringBuffer();
        String s = null;
        while ((s = bf.readLine()) != null) {
            buffer.append(s).append("\n");
        }
        return buffer.toString();
    }

Analyse

Regarding analysis, it is different from what was described before coding.

First, tokens need to be analyzed one by one, so a global variable index is added to track the current pointer position.

Additionally, situations may arise where reading one more character or undoing a read is necessary, so the functions ungetChar and getChar are encapsulated to facilitate the analysis.

    private Character getChar() {
        if (index < code.length()) {
            char c = code.charAt(index);
            if (c == '\n') {
                lineNum++;
            }
            index++;
            return c;
        } else {
            return null;
        }
    }

    private void unGetChar() {
        index--;
        char c = code.charAt(index);
        if (c == '\n') {
            lineNum--;
        }
    }

Slash

1) // : When it comes to \n , stop.

do {
  c = getChar();
  if (c == null || c == '\n') {
    return;
    // 判断为//注释，结束分析
  }
} while (true);

2) /* */: Get char until */ appears.

do {
  c = getChar();
  if (c == null) {
    return;
  }
  if (c == '*') {
    c = getChar();
    if (c == '/') {
      return;
      // 判断为/* */注释，直接结束分析
    } else {
      unGetChar();
    }
  }
} while (true);

Grammar Analysis 语法分析

Requirement: Based on the words identified by the lexical analysis program, identify various grammatical elements according to the grammatical rules. The recursive descent method is used to analyze the grammatical components defined in the grammar.

Before Coding

Data Reading

Similar to the lexical analysis, functions like getWord and getNextWord are prepared. Additionally, there is a global variable (Word) curWord to indicate the current word when reading ArrayList<Word> words from the lexical analysis one by one.

The analysis strategy is as follows:

• For normal rules: Keep getting words and analyze them.
• For expression rules: First, scan the entire expression using the function getExp. Then, divide the expression and use the recursive descent method to analyze it.

getExp like

    private ArrayList<Word> getExp() {
        ArrayList<Word> exp = new ArrayList<>();
        while (true) {
            if (word is symbol of end) {
                break;
            }
            ...
            getWordWithoutAddToGrammar();
            exp.add(curWord);
            word = getNextWord();
        }
        return exp;
    }

recursive descent

According to grammatical rules, code functions for each term of the rule.

Main idea: Read a word, check what it symbolizes, and enter the next analyzing function.

For example:

to

CompUnit → {Decl} {FuncDef} MainFuncDef // 1.是否存在Decl 2.是否存在 FuncDef

I analyze like this:

private void analyseCompUnit() {
  Word word = getNextWord();
  while (word.typeEquals("CONSTTK") || (
    word.typeEquals("INTTK") && getNext2Word().typeEquals("IDENFR") && !getNext3Word().typeEquals("LPARENT"))) {
    analyseDecl();
    word = getNextWord();
  }
  while (word.typeEquals("VOIDTK") || (
    (word.typeEquals("INTTK") && !getNext2Word().typeEquals("MAINTK")))) {
    analyseFuncDef();
    word = getNextWord();
  }
  if (word.typeEquals("INTTK") && getNext2Word().typeEquals("MAINTK")) {
    analyseMainFuncDef();
  } else {
    error();
  }
  grammar.add("<CompUnit>");
}

grammar is used to memorize the output of both the lexical analysis and the grammar analysis lists.

left recursion

加减表达式 AddExp → MulExp | AddExp ('+' | '−') MulExp // 1.MulExp 2.+ 需覆盖 3.- 需覆盖

Check if the expression contains '+' or '-'. If it does, separate the expression into AddExp and MulExp. Then analyze them separately.

After Code

left recursion

The previous method is not perfect for recursive descent. Therefore, the approach has been revised and rewritten.

to

加减表达式 AddExp → MulExp | AddExp ('+' | '−') MulExp // 1.MulExp 2.+ 需覆盖 3.- 需覆盖

Rewrite it like

AddExp → MulExp ('+' | '−') MulExp  ('+' | '−') MulExp ...

Code like

private void analyseMulExp(ArrayList<Word> exp) {
  Exps exps = divideExp(exp, new ArrayList<>(Arrays.asList("MULT", "DIV", "MOD")));
  int j = 0;
  for (ArrayList<Word> exp1 : exps.getWords()) {
    analyseUnaryExp(exp1);
    grammar.add("<MulExp>");
    if (j < exps.getSymbols().size()) {
      grammar.add(exps.getSymbols().get(j++).toString());
    }
  }
}

Function divideExp is used to divide the entire expression passed by getExp or a preceding function.

divideExp:

Input: - Original expression: exp - Stop symbol: symbol

Output: - List of divided expressions and symbols.

private Exps divideExp(ArrayList<Word> exp, ArrayList<String> symbol) {
  ArrayList<ArrayList<Word>> exps = new ArrayList<>();
  ArrayList<Word> exp1 = new ArrayList<>();
  ArrayList<Word> symbols = new ArrayList<>();
  boolean unaryFlag = false;
  int flag1 = 0;
  int flag2 = 0;
  for (int i = 0; i < exp.size(); i++) {
    Word word = exp.get(i);
    if (word.typeEquals("LPARENT")) {
      flag1++;
    }
    if (word.typeEquals("RPARENT")) {
      flag1--;
    }
    if (word.typeEquals("LBRACK")) {
      flag2++;
    }
    if (word.typeEquals("RBRACK")) {
      flag2--;
    }
    if (symbol.contains(word.getType()) && flag1 == 0 && flag2 == 0) {
      //UnaryOp
      if (word.typeOfUnary()) {
        if (!unaryFlag) {
          exp1.add(word);
          continue;
        }
      }
      exps.add(exp1);
      symbols.add(word);
      exp1 = new ArrayList<>();
    } else {
      exp1.add(word);
    }
    unaryFlag = word.typeEquals("IDENFR") || word.typeEquals("RPARENT") || word.typeEquals("INTCON") || word.typeEquals("RBRACK");
  }
  exps.add(exp1);
  return new Exps(exps, symbols);
}

Exps

public class Exps {
    private ArrayList<ArrayList<Word>> words;
    private ArrayList<Word> symbols;
}

other bugs

Most bugs are produced by the functions getExp and divideExp due to some overlooked situations, often resulting in errors like index out of range. Therefore, adjustments were made to some symbols for stopping the expression parsing and modifications were made to the rules for dividing or not dividing the expression, among other changes.

Error Handling 错误处理

Before Coding

Create the symbol table

Symbol class

public class Symbol {
    private String type;
    private int intType;
    private String content;
    private int area = 0;
}

Type represents the type of the symbol.

• IntType is an integer. If it's 0, the symbol is an int. If it's 1, the symbol is an int[]. If it's 2, the symbol is an int[][], and so on.

Content is its content.

Area indicates where it is.

A HashMap of Symbols is created to memorize symbols created in each area.

When entering a new area, area++. When leaving an area, area--, with the corresponding symbols being destroyed.

    private HashMap<Integer, Symbols> symbols = new HashMap<>();
    private HashMap<String, Function> functions = new HashMap<>();
    private ArrayList<Error> errors = new ArrayList<>();
    private int area = -1;
    private boolean needReturn = false;
    private int whileFlag = 0;

needReturn indicates whether the current function needs to return.

whileFlag indicates whether the current code block is within a while loop.

Errors

a

Just check format.

public boolean isFormatIllegal() {
  for (int i = 1; i < content.length() - 1; i++) {
    char c = content.charAt(i);
    if (!isLegal(c)) {
      if (c == '%' && content.charAt(i + 1) == 'd') {
        continue;
      }
      return true;
    } else {
      if (c == '\\' && content.charAt(i + 1) != 'n') {
        return true;
      }
    }
  }
  return false;
}

b c

B: Every time an identifier is encountered, check if the same symbol has already been defined in the current area.

    private boolean hasSymbolInThisArea(Word word) {
        return symbols.get(area).hasSymbol(word);
    } 

C: Check all areas. If the symbol has been defined, handle functions in the same manner.

    private boolean hasSymbol(Word word) {
        for (Symbols s : symbols.values()) {
            if (s.hasSymbol(word)) {
                return true;
            }
        }
        return false;
    }

d e

To check if the function parameters are matched, the parameters of every function are memorized. When a function call is encountered, the function call parameters are scanned and matched. A function is prepared to handle this. It was found that recursive descent is needed again, so the check procedure is added to the recursive descent of the grammatical analyzer. Please check the After Code/Error d and e.

f g

There is a global variable needReturn used to indicate if the current function needs to return. If it does, but there is no return at the end of the code block, or if it doesn't, but there is a return, the error will be recorded.

h

Simply check if it is a constant.

if (isConst(word)) {
  error("h", word.getLineNum());
}

i j k

Encapsulate the function for checking the missing symbol.

For example:

    private void checkParent() {
        if (getNextWord().typeEquals("RPARENT")) {
            getWord();// )
        } else {
            error("j");
        }
    }

l

Count the number of parameters for string and printf separately and check if they are equal.

m

There is a global variable whileFlag indicating if the code block is within a while loop. If it isn't, any continue or break statements will produce an error.

After Coding

Area

I increment area++ when entering a block or a function, but this leads to a situation where the parameters of the function can't be memorized in a different area from the block of the function. Therefore, I changed the rules for marking area++.

    private boolean analyseBlock(boolean fromFunc) {
        ...
        if (!fromFunc) {
            addArea();
        }
        ...
    }

Only when t