SysY 编译器

1. 项目概述

1.1 这是什么项目？

北京航空航天大学的《编译技术》课程实验要求设计并编写一个编译器，该项目即对该编译器的设计开发。

1.2 需要翻译什么语言？

该编译器可以将 SysY 语言 ( C 语言的子集 ) 编写的代码翻译成中间代码或目标代码。

1.3 源代码将被翻译成什么语言？

源代码需要翻译成中间代码 ( LLVM IR Code 或 P-code ) 或目标代码 ( MIPS ) 。

2. 参考编译器介绍

课程组提供了两个编译器 ( Pascal-Compiler 和 Pl0-Compiler ) 以供参考，我们需要阅读分析其源代码，然后在此基础上完成我们自己的编译器的整体架构设计。

在本节中，我将总结其中一个编译器的设计思想，包括但不限于其总体结构、接口设计和文件组织。具体内容如下。

3. SysY 编译器总体设计

项目仓库：SysY Compileropen in new window

3.1 目录结构

该编译器使用 Java 语言开发，当前源代码目录结构如下 ( 目录结构将随开发过程不断更新 ) 。

src
├── Compiler.java
├── config.json
├── exception
│   ├── CompilationException.java
│   └── ExceptionCategory.java
├── lexer
│   ├── ILexer.java
│   ├── impl
│   │   ├── DefaultLexerImpl.java
│   │   └── StateTransitionLexerImpl.java
│   ├── token
│   │   ├── Assistant.java
│   │   ├── CharConst.java
│   │   ├── Identifier.java
│   │   ├── IntConst.java
│   │   ├── Keyword.java
│   │   ├── Operator.java
│   │   ├── StringConst.java
│   │   ├── Token.java
│   │   └── TokenCategory.java
│   └── utils
│       ├── State.java
│       └── StateConverter.java
├── parser
│   ├── IParser.java
│   ├── impl
│   │   └── DefaultParserImpl.java
│   └── node
│       ├── BlockNode.java
│       ├── ParseTreeLeafNode.java
│       └── ParseTreeNode.java
├── semantic
│   ├── ISemanticAnalyzer.java
│   ├── env
│   │   ├── ArrayItem.java
│   │   ├── Env.java
│   │   ├── EnvItem.java
│   │   ├── FunctionItem.java
│   │   └── ItemCategory.java
│   └── impl
│       └── DefaultSemanticAnalyzerImpl.java
├── symbol
│   ├── BlankCategory.java
│   ├── Category.java
│   └── NonTerminalCategory.java
└── tools
    ├── FirstFollowCalculator.java
    ├── Grammar.java
    ├── PredictiveParsingTableBuilder.java
    └── ToolMain.java

3.2 根目录

根目录下的 Compiler 类是整个编译器的入口，配置文件 config.json 为评测所需的配置文件，与编译器程序本身无关。

3.3 目录 exception

该目录下的两个类分别为异常类和枚举类。

异常类 CompilationException 意为编译错误，当编译器遇到源程序的错误时，可以抛出该异常。

枚举类 ExceptionCategory 作为上述异常类的一个字段，代表不同类型的编译错误，包括词法错误、语法错误、语义错误。

3.4 目录 lexer

该目录包含词法分析子程序的相关文件。

接口 ILexer 为词法分析器接口，对外暴露词法分析器功能，其可以拥有不同的实现。

子目录 impl 包含不同的词法分析器实现，当前拥有两个实现类，实现思路不同。另外，实现类 DefaultLexerImpl 不保证在词法分析阶段之后的阶段正常工作，当前仅使用 StateTransitionLexerImpl 类作为词法分析器实现。

子目录 token 定义词法单元。抽象类 Token 作为所有词法单元的基类，枚举类 TokenCategory 作为该类的一个字段标记该词法单元的类型，其余的类均为 Token 类的子类，用于更好地对词法单元进行分类。

子目录 utils 中的文件用于词法分析器的状态转换。枚举类 State 定义不同的状态，接口 StateConverter 为函数式接口，用于在词法分析器中实现不同状态之间的转换。

3.5 目录 parser

该目录包含语法分析子程序的相关文件。

接口 IParser 为语法分析器接口，对外暴露语法分析器功能，其可以拥有不同的实现。

子目录 impl 包含不同类型的语法分析器实现，当前仅有一个实现类。

子目录 node 定义语法分析树节点。类 ParseTreeNode 为语法分析树节点类，包含中间节点和叶子节点共有的属性和方法；类 ParseTreeLeafNode 继承自 ParseTreeNode 类，包含叶子节点特有的属性和方法。

3.6 目录 semantic

该目录包含语义分析子程序的相关文件。

接口 ISemanticAnalyzer 为语义分析器接口，对外暴露语义分析器功能，其可以拥有不同的实现。

子目录 impl 包含不同类型的语义分析器实现，当前仅有一个实现类。

子目录 env 包含符号表相关类。类 Env 为符号表树节点类，类 EnvItem 为符号表项，其拥有两个子类，分别是 ArrayItem 类和 FunctionItem 类，代表数组和函数，其中包含一些数组和函数特有的属性和方法。枚举类 ItemCategory 可作为 EnvItem 类的一个字段，标记符号表项的类型。

3.7 目录 symbol

该目录中的文件定义语法分析过程中需要用到的类型信息。

接口 Category 拥有三个实现类，这三个类均为枚举类，分别是上文提到的 TokenCategory 以及该目录下的 BlankCategory 和 NonterminalCategory 。

枚举类 BlankCategory 定义文法中的空产生式。

枚举类 NonterminalCategory 定义文法中的非终结符类型。

上文中的 TokenCategory 定义文法中的终结符类型，特别的，其中还包含终止符，用于语法分析器识别词法单元流的结尾。

3.8 目录 tools

该目录下的文件用于处理文法并产生语法分析所需的预测分析表。

枚举类 Grammar 定义所有的文法。

类 FirstFollowCalculator 根据文法计算每个非终结符的 FIRST 集和 FOLLOW 集，并将集合内容输出到输出流中。

类 PredictiveParsingTableBuilder 根据文法及刚才计算出的 FIRST 集和 FOLLOW 集生成预测分析表，并可以将预测分析表信息输出到输出文件中。

类 ToolMain 启动整个预测分析表生成流程，将上述两个类的计算结果输出到文件中，并将预测分析表的数据结构返回给调用者。

4. 词法分析设计

词法分析器包含两个实现类，实现类 DefaultLexerImpl 由于结构混乱现已被标记为弃用。

实现类 StateTransitionLexerImpl 使用状态转换图实现词法分析，对外暴露的方法 nextToken 从给定输入流中读取下一个词法单元并返回给调用者。

根据给定的词法，我们可以绘制出如下的状态转换图：

在构造词法分析器类时，会将状态初始化为 Start 。

每次调用 nextToken 方法，都会根据当前状态找到对应的状态转换处理器，然后根据读入的字符执行对应的状态转换逻辑；这个转换过程将不断进行，直到可以返回下一个词法单元或者抛出异常为止。

除了普通的状态转换处理器外，词法分析器还包含一个特殊的错误状态处理器，当发现词法错误或到达文件尾时便会进入错误状态。如果是由于发现词法错误进入错误状态，该处理器会抛出词法错误异常；如果是由于到达文件尾进入错误状态，处理器会将词法分析器状态永久置为 FileEnd 用以标记文件读入结束。

如果词法分析器状态为 FileEnd 即文件读入结束之后再次调用 nextToken 方法，该方法只会返回 null 。

5. 语法分析设计

语法分析器设计的基本思想：预测分析表驱动，非递归，自顶向下分析。

5.1 改造文法

为了满足设计需求，我们首先要对原文法进行改造，使之基本符合 LL(1) 文法的规定。改造过程如下，其中 \epsilon 代表空串：

编译单元

// <CompUnit> -> {<Decl>} {<FuncDef>} <MainFuncDef>
<CompUnit> -> <DeclList> <FuncDefList> <MainFuncDef>
<DeclList> -> <Decl> <DeclList> | \epsilon
<FuncDefList> -> <FuncDef> <FuncDefList> | \epsilon

声明

// <Decl> -> <ConstDecl> | <VarDecl>
<Decl> -> <ConstDecl> | <VarDecl>

常量声明

// <ConstDecl> -> CONSTTK <BType> <ConstDef> { COMMA <ConstDef> } SEMICN
<ConstDecl> -> CONSTTK <BType> <ConstDef> <ConstDefList> SEMICN
<ConstDefList> -> COMMA <ConstDef> <ConstDefList> | \epsilon

基本类型

// <BType> -> INTTK | CHARTK
<BType> -> INTTK | CHARTK

常量定义

// <ConstDef> -> IDENFR [ LBRACK <ConstExp> RBRACK ] ASSIGN <ConstInitVal>
<ConstDef> -> IDENFR <ArrSym> ASSIGN <ConstInitVal>
<ConstArrSym> -> LBRACK <ConstExp> RBRACK | \epsilon

常量初值

// <ConstInitVal> -> <ConstExp> | LBRACE [ <ConstExp> { COMMA <ConstExp> } ] RBRACE | STRCON
<ConstInitVal> -> <ConstExp> | LBRACE <ConstExpListOpt> RBRACE | STRCON
<ConstExpListOpt> -> <ConstExp> <ConstExpTail> | \epsilon
<ConstExpTail> -> COMMA <ConstExp> <ConstExpTail> | \epsilon

变量声明

// <VarDecl> -> <BType> <VarDef> { COMMA <VarDef> } SEMICN
<VarDecl> -> <BType> <VarDef> <VarDefList> SEMICN
<VarDefList> -> COMMA <VarDef> <VarDefList> | \epsilon

变量定义

// <VarDef> -> IDENFR [ LBRACK <ConstExp> RBRACK ] | IDENFR [ LBRACK <ConstExp> RBRACK ] ASSIGN <InitVal>
<VarDef> -> IDENFR <ConstArrSym> | IDENFR <ArrSym> ASSIGN <InitVal>

提取左公因子：

<VarDef> -> IDENFR <ArrSym> <_VarDef>
<_VarDef> -> ASSIGN <InitVal> | \epsilon

变量初值

// <InitVal> -> <Exp> | LBRACE [ <Exp> { COMMA <Exp> } ] RBRACE | STRCON
<InitVal> -> <Exp> | LBRACE <ExpListOpt> RBRACE | STRCON
<ExpListOpt> -> <Exp> <ExpTail> | \epsilon
<ExpTail> -> COMMA <Exp> <ExpTail> | \epsilon

函数定义

// <FuncDef> -> <FuncType> IDENFR LPARENT [ <FuncFParams> ] RPARENT <Block>
<FuncDef> -> <FuncType> IDENFR LPARENT <FuncFParamsList> RPARENT <Block>
<FuncFParamsList> -> <FuncFParams> | \epsilon

主函数定义

// <MainFuncDef> -> INTTK MAINTK LPARENT RPARENT <Block>
<MainFuncDef> -> INTTK MAINTK LPARENT RPARENT <Block>

函数类型

// <FuncType> -> VOIDTK | INTTK | CHARTK
<FuncType> -> VOIDTK | INTTK | CHARTK

函数形参表

// <FuncFParams> -> <FuncFParam> { COMMA <FuncFParam> }
<FuncFParams> -> <FuncFParam> <FuncFParamList>
<FuncFParamList> -> COMMA <FuncFParam> <FuncFParamList> | \epsilon

函数形参

// <FuncFParam> -> <BType> IDENFR [ LBRACK RBRACK ]
<FuncFParam> -> <BType> IDENFR <BracketPair>
<BracketPair> -> LBRACK RBRACK | \epsilon

语句块

// <Block> -> LBRACE { <BlockItem> } RBRACE
<Block> -> LRACE <BlockItemList> RBRACE
<BlockItemList> -> <BlockItem> <BlockItemList> | \epsilon

语句块项

// <BlockItem> -> <Decl> | <Stmt>
<BlockItem> -> <Decl> | <Stmt>

语句

原文法：

<Stmt> -> <Lval> ASSIGN <Exp> SEMICN
| [ <Exp> ] SEMICN
| <Block>
| IFTK LPARENT <Cond> RPARENT <Stmt> [ ELSETK <Stmt> ]
| FORTK LPARENT [ <ForStmt> ] SEMICN [ <Cond> ] SEMICN [ <ForStmt> ] RPARENT <Stmt>
| BREAKTK SEMICN
| CONTINUETK SEMICN
| RETURNTK [ <Exp> ] SEMICN
| <Lval> ASSIGN GETINTTK LPARENT RPARENT SEMICN
| <Lval> ASSIGN GETCHARTK LPARENT RPARENT SEMICN
| PRINTFTK LPARENT STRCON { COMMA <Exp> } RPARENT SEMICN

改写后文法：

<Stmt> -> <Lval> ASSIGN <Exp> SEMICN
       | <ExpOpt> SEMICN
       | <Block>
       | IFTK LPARENT <Cond> RPARENT <Stmt> <ElseOpt>
       | FORTK LPARENT <ForStmtOpt> SEMICN <CondOpt> SEMICN <ForStmtOpt> RPARENT <Stmt>
       | BREAKTK SEMICN
       | CONTINUETK SEMICN
       | RETURNTK <ExpOpt> SEMICN
       | <Lval> ASSIGN GETINTTK LPARENT RPARENT SEMICN
       | <Lval> ASSIGN GETCHARTK LPARENT RPARENT SEMICN
       | PRINTFTK LPARENT STRCON <ExpListTailOpt> RPARENT SEMICN

<ExpOpt> -> <Exp> | \epsilon
<ElseOpt> -> ELSETK <Stmt> | \epsilon
<ForStmtOpt> -> <ForStmt> | \epsilon
<CondOpt> -> <Cond> | \epsilon
<ExpListTailOpt> -> COMMA <Exp> <ExpListTailOpt> | \epsilon

提取左公因子：

<Stmt> -> <LVal> ASSIGN <ReadOrOther>
       | <ExpOpt> SEMICN
       | <Block>
       | IFTK LPARENT <Cond> RPARENT <Stmt> <ElseOpt>
       | FORTK LPARENT <ForStmtOpt> SEMICN <CondOpt> SEMICN <ForStmtOpt> RPARENT <Stmt>
       | BREAKTK SEMICN
       | CONTINUETK SEMICN
       | RETURNTK <ExpOpt> SEMICN
       | PRINTFTK LPARENT STRCON <ExpListTailOpt> RPARENT SEMICN
<ReadOrOther> = <Exp> SEMICN | <GetFunc> LPARENT RPARENT SEMICN
<GetFunc> -> GETINTTK | GETCHARTK

For循环语句

// <ForStmt> -> <Lval> ASSIGN <Exp>
<ForStmt> -> <Lval> ASSIGN <Exp>

表达式

// <Exp> -> <AddExp>
<Exp> -> <AddExp>

条件表达式

// <Cond> -> <LOrExp>
<Cond> -> <LOrExp>

左值表达式

// <LVal> -> IDENFR [ LBRACK <Exp> RBRACK ]
<LVal> -> IDENFR <ArrSym>
<ArrSym> -> LBRACK <Exp> RBRACK | \epsilon

基本表达式

// <PrimaryExp> -> LPARENT <Exp> RPARENT | <LVal> | <Number> | <Character>
<PrimaryExp> -> LPARENT <Exp> RPARENT | <LVal> | <Number> | <Character>

数值

// <Number> -> INTCON
<Number> -> INTCON

字符

// <Character> -> CHRCON
<Character> -> CHRCON

一元表达式

// <UnaryExp> -> <PrimaryExp> | IDENFR LPARENT [ <FuncRParams> ] RPARENT | <UnaryOp> <UnaryExp>
<UnaryExp> -> <PrimaryExp> | IDENFR LPARENT <FuncRParamsList> RPARENT | <UnaryOp> <UnaryExp>
<FuncRParamsList> -> <FuncRParams> | \epsilon

单目运算符

// <UnaryOp> -> PLUS | MINU | NOT
<UnaryOp> -> PLUS | MINU | NOT

函数实参表

// <FuncRParams> -> <Exp> { COMMA <Exp> }
<FuncRParams> -> <Exp> <ExpListTail>
<ExpListTail> -> COMMA <Exp> <ExpListTail> | \epsilon

乘除模表达式

// <MulExp> -> <UnaryExp> | <MulExp> ( MULT | DIV | MOD ) <UnaryExp>
<MulExp> -> <UnaryExp> | <MulExp> <MultDivModOp> <UnaryExp>
<MultDivModOp> -> MULT | DIV | MOD

消除左递归：

<MulExp> -> <UnaryExp> <_MulExp>
<_MulExp> -> <MultDivModOp> <MulExp> | \epsilon
<MultDivModOp> -> MULT | DIV | MOD

加减表达式

// <AddExp> -> <MulExp> | <AddExp> ( PLUS | MINU ) <MulExp>
<AddExp> -> <MulExp> | <AddExp> <PlusMinuOp> <MulExp>
<PlusMinuOp> -> PLUS | MINU

消除左递归：

<AddExp> -> <MulExp> <_AddExp>
<_AddExp> -> <PlusMinuOp> <AddExp> | \epsilon
<PlusMinuOp> -> PLUS | MINU

关系表达式

// <RelExp> -> <AddExp> | <RelExp> ( GRE | LSS | GEQ | LEQ ) <AddExp>
<RelExp> -> <AddExp> | <RelExp> <GreLssGeqLeqOp> <AddExp>
<GreLssGeqLeqOp> -> GRE | LSS | GEQ | LEQ

消除左递归：

<RelExp> -> <AddExp> <_RelExp>
<_RelExp> -> <GreLssGeqLeqOp> <RelExp> | \epsilon
<GreLssGeqLeqOp> -> GRE | LSS | GEQ | LEQ

相等性表达式

// <EqExp> -> <RelExp> | <EqExp> ( EQL | NEQ ) <RelExp>
<EqExp> -> <RelExp> | <EqExp> <EqlNeqOp> <RelExp>
<EqlNeqOp> -> EQL | NEQ

消除左递归：

<EqExp> -> <RelExp> <_EqExp>
<_EqExp> -> <EqlNeqOp> <EqExp> | \epsilon
<EqlNeqOp> -> EQL | NEQ

逻辑与表达式

// <LAndExp> -> <EqExp> | <LAndExp> AND <EqExp>
<LAndExp> -> <EqExp> | <LAndExp> AND <EqExp>

消除左递归：

<LAndExp> -> <EqExp> <_LAndExp>
<_LAndExp> -> AND <LAndExp> | \epsilon
<LAndExp> -> <EqExp> | <LAndExp> AND <EqExp>

逻辑或表达式

// <LOrExp> -> <LAndExp> | <LOrExp> OR <LAndExp>
<LOrExp> -> <LAndExp> | <LOrExp> OR <LAndExp>

消除左递归：

<LOrExp> -> <LAndExp> <_LOrExp>
<_LOrExp> -> OR <LOrExp> | \epsilon

常量表达式

// <ConstExp> -> <AddExp>
<ConstExp> -> <AddExp>

虽然这个文法不完全符合 LL(1) 文法的规定，但已经足够使用了。

5.2 计算 FIRST 集和 FOLLOW 集

我们将改造完的文法以程序源码的形式在编译器中表示，这样做是为了当文法发生变化时，这两个集合可以随之更新。

接下来我们使用伪代码描述这两个集合计算过程，符号定义如下：

• G ：文法
• N ：非终结符集合
• T ：终结符集合
• P ：产生式集合

按照如下算法计算每个非终结符的 FIRST 集：

function ComputeFIRST(G):
    initialize FIRST(A) = {} for each non-terminal A in N

    repeat
        for each production A -> α in P:
            for each symbol X in α:
                if X in T:
                    add X to FIRST(A)
                    break
                else if x not in T:
                    add all elements of (FIRST(X) - {ε}) to FIRST(A)
                    
                    if ε in FIRST(X):
                        continue
                    else break
            if all Xi (1 <= i <= n) contain ε in their FIRST sets:
                add ε to FIRST(A)

    until no changes to any FIRST set

    return FIRST

或者我们也可以利用 FIRST 集的传递性，递归地进行 FIRST 集计算：

function ComputeFIRST(G):
    initialize FIRST(A) = {} for each non-terminal A in N
    initialize visited(A) = false for each non-terminal A in N

    for each non-terminal A in N:
        if not visited(A):
            FIRST(A) = ComputeFIRSTRecursive(A)

    return FIRST

function ComputeFIRSTRecursive(A):
    if visited(A):
        return FIRST(A)

    visited(A) = true

    for each production A -> α in P:
        for each symbol X in α:
            if X in T:
                add X to FIRST(A)
                break
            else if X not in T:
                add all elements of (ComputeFIRSTRecursive(X) - {ε}) to FIRST(A)

                if ε not in FIRST(X):
                    break

        if all symbols in α can derive ε:
            add ε to FIRST(A)

    return FIRST(A)

按照如下算法计算每个非终结符的 FOLLOW 集：

function ComputeFOLLOW(G):
    initialize FOLLOW(A) = {} for each non-terminal A in N
    initialize FOLLOW(S) = { $ }

    repeat
        for each production A -> α in P:
            for each symbol B in α:
                if B in T:
                    add all elements of (FIRST(β) - {ε}) to FOLLOW(B)

                    if ε in FIRST(β) or B is the last symbol in α:
                        add all elements of FOLLOW(A) to FOLLOW(B)

    until no changes to any FOLLOW set

    return FOLLOW

我们可以将计算结果输出到本地文件用以监测程序运行情况。

5.3 生成预测分析表

计算完 FIRST 集和 FOLLOW 集后，我们可以利用这两个集合生成预测分析表。

对于文法 G 中的每个产生式 A->α 进行如下处理：

1. 对于 FIRST(α) 中的每个终结符号 a 将 A->α 加入到 M[A,a] 中。
2. 如果 ε 在 FIRST(α) 中，那么对于 FOLLOW(A) 中的每个终结符号 b 将 A->α 加入到 M[A,b] 中。如果 ε 在 FIRST(α) 中，且 $ 在 FOLLOW(A) 中，将 A->α 加入到 M[A,$] 中。

完成上面的操作后，如果 M[A,a] 中没有产生式，那么将 M[A,a] 设置为错误，我们通常在表中用一个空条目表示。

同样的，我们可以将预测分析表打印到本地的 .csv 文件监控运行结果。

5.4 语法分析主程序

语法分析主程序采用预测分析表驱动的预测分析算法，算法伪代码如下：

function PredictiveParser(input, parseTable, startSymbol):
    initialize stack = [ $, startSymbol ]
    initialize pointer = 0
    input = input + $

    while stack is not empty:
        top = stack.pop()

        currentInput = input[pointer]

        if top is a terminal or top == $:
            if top == currentInput:
                pointer = pointer + 1
            else:
                return "Error: Unexpected input symbol"

        else if top is a non-terminal:
            production = parseTable[top, currentInput]
            if production is empty:
                return "Error: No matching production"

            else:
                for symbol in reverse(production):
                    if symbol != ε:
                        stack.push(symbol)

        else:
            return "Error: Invalid symbol on stack"

    if pointer == len(input):
        return "Success: Input is parsed successfully"
    else:
        return "Error: Input is not fully parsed"

但是，由于我们的文法不是完全的 LL(1) 文法，所以预测分析表的某些条目会存在两个产生式，我们需要对这些情况单独处理。

存在问题的条目有下面几个：

我们接下来对这些条目逐一进行分析。

<UnaryExp>,IDENFR

<UnaryExp> -> <PrimaryExp>
    | IDENFR LPARENT <FuncRParamsList> RPARENT

相关产生式如下：

<PrimaryExp> -> LPARENT <Exp> RPARENT | <LVal> | <Number> | <Character>
<LVal> -> IDENFR <ArrSym>
<ArrSym> -> LBRACK <Exp> RBRACK | \epsilon

这个问题很好解决。向前读取一个终结符，如果下一个终结符为 LPARENT 则说明为第二个产生式，否则为第一个产生式。

<Stmt>,IDENFR

<Stmt> -> <ExpOpt> SEMICN
    | <LVal> ASSIGN <ReadOrOther>

相关产生式如下：

<ExpOpt> -> <Exp> | \epsilon
<Exp> -> <AddExp>
<AddExp> -> <MulExp> <_AddExp>
<MulExp> -> <UnaryExp> <_MulExp>
<UnaryExp> -> <PrimaryExp> | IDENFR LPARENT <FuncRParamsList> RPARENT | <UnaryOp> <UnaryExp>
<PrimaryExp> -> LPARENT <Exp> RPARENT | <LVal> | <Number> | <Character>

这个问题比较复杂，我们可以这样做：

1. 向前读取一个终结符，如果为 LPARENT 则说明为第一个产生式。
2. 如果不符合第一步的条件，则先分析出 <LVal> 的语法成分，然后判断 <LVal> 之后的下一个终结符，如果为 ASSIGN 说明为第二个产生式，否则为第一个产生式。

<ElseOpt>,ELSETK

<ElseOpt> -> ELSETK <Stmt>
    | \epsilon

这是很经典的悬空 else 问题，我们按照惯例让每个 else 和最近的尚未匹配的 if 匹配即可。

<DeclList>,INTTK 和 <FuncDefList>,INTTK

<DeclList> -> <Decl> <DeclList>
    | \epsilon;
<FuncDefList> -> <FuncDef> <FuncDefList>
    | \epsilon

相关产生式较多，所以这里不再罗列。

解决方法很简单，对于 <DeclList> 的情况，我们向前读取两个终结符，如果第二个终结符为 LPARENT 说明为第二个产生式，否则为第一个产生式；对于 <FuncDefList> 的情况，我们向前读取一个终结符，如果为 MAINTK 说明为第二个产生式，否则为第一个产生式。

<DeclList>,CHARTK

<DeclList> -> <Decl> <DeclList>
    | \epsilon

这种情况的处理方式和上一种情况的处理方式相同，向前读取两个终结符，如果第二个终结符为 LPARENT 说明为第二个产生式，否则为第一个产生式。

5.5 错误处理

按照评测要求，源程序中会出现缺少 SEMICN RPARENT RBRACK 的情况，我们只需要在缺少该种终结符时，创建一个终结符添加到语法分析树中即可，新创建的终结符行号与上一个终结符的行号相同，完成处理后将报错信息打印到错误输出流。

5.6 评测说明

语法分析器的输出为语法分析树，编译器主程序将后序遍历该语法分析树，输出需要输出的终结符和非终结符。

考虑到我们改写了文法，语法分析树的结构会与原文法的语法分析树结构不同，从而导致输出结果不同，我们可以如下处理：

1. 对于新添加的非终结符以及不要求输出的已有非终结符，在遍历过程中不输出其分析信息。
2. 对于改写的左递归文法，将输出根节点的操作放在输出左子树和输出右子树的操作中间。

伪代码描述如下：

function ParseAndPrint(node):
    if node is <MulExp> or <AddExp> or <RelExp> or <EqExp> or <LAndExp> or <LOrExp>:
        ParseAndPrint(node.left)
        print(node)
        ParseAndPrint(node.right)
        return
    else:
        for child in node.children:
            ParseAndPrint(child)
        print(node)

为了方便监测输出结果以进行调试，可以使用如下算法将语法分析树输出到文件中：

function PrintTree(tree, prefix, isLast):
    print(prefix + (isLast ? "└── " : "├── ") + tree)
    for child in tree.children:
        set newPrefix = prefix + (isLast ? "    " : "│   ")
        PrintTree(child, newPrifix, whether child is the last)

PrintTree(SyntaxTree, "", true)

6. 语义分析设计

6.1 主要设计思想

语义分析的主要任务就是生成符号表，并检查源代码中的语义错误。

虽然语义分析可以合并到语法分析过程中，但是为了避免对原有语法分析代码的大范围修改，也为了方便语义分析的编写工作，此次任务中，语义分析将被放置在语法分析之后。语义分析器将利用语法分析输出的语法树，遍历语法树生成符号表并检查其中的语义错误。

6.2 符号表管理

本次编译器设计中使用的符号表将体现为一棵符号表树，树的根节点代表全局作用域，其余节点代表不同嵌套深度的局部作用域。

在语义分析过程中，我们还会使用一个指针指向当前作用域对应的符号表树节点，该指针指向的节点即为顶层作用域节点，该指针也可被称为顶层作用域指针。初始状态下顶层作用域指针指向符号表树的根节点，代表当前作用域为全局作用域。

每当进入一个新的作用域，我们会创建一个新的符号表树节点，同时更新顶层作用域指针指向这个新创建的节点；每当离开一个作用域，我们需要更新顶层作用域指针，使其指向原作用域的外层作用域对应的符号表树节点。为了达成这个目的，每个符号表树节点除存储其对应作用域的符号表项外，还需要存储指向其上层节点的指针，以及指向其下层节点的指针列表。自然，根节点的上层节点指针为空。

最终形成的符号表将如下图所示：

在语义分析过程中，如果需要处理的是变量声明或者函数声明语句，我们将查找当前顶层作用域符号表树节点，检查是否已存在同名表项，如果已存在应当报错处理；否则，应当填入新的符号表项。如果需要处理的是对符号的调用，我们将从当前顶层作用域符号表树节点出发，一路查找到符号表树的根节点，直到查找到对应的符号表项为止；如果一直查找到根节点都没有找到对应的符号表项，应当报错处理。

6.3 评测说明

在已经拥有完整的语法树的情况下，语义分析工作就非常容易了。所以需要注意的其实就是评测要求了。

对于正确的源程序，需要按作用域顺序输出符号表信息，我们只需要对符号表树进行前序深度优先搜索即可，遍历过程中输出每个节点的表项信息。为了便于查找，节点中的表项使用哈希表存储，但是评测要求按照插入顺序输出符号名称。如果使用Java语言编写编译器，可以利用Java集合框架提供的 LinkedHashMap 类，它是可以记录元素插入顺序的哈希表结构，恰好可以满足我们的需求。

对于错误的源程序，由于我们的语义分析工作是在语法分析完成之后进行，所以之前的词法错误和语法错误，以及新的语义错误，不能在分析过程中输出了。所以说，我们需要使用一定的数据结构存储分析过程中检查到的错误，分析结束之后，将所有的错误合并到一起后排序输出。

附录

A. 词法单元定义

B. 错误类型