重庆大学编译原理2022教改项目

AI悦创原创2023年5月27日大约 8 分钟...约 2489 字

1. 实验方案

本次实验将实现一个由 SysY (精简版 C 语言，来自 https://compiler.educg.net/) 翻译至 RISC-V 汇编的编译器，生成的汇编通过 GCC 的汇编器翻译至二进制，最终运行在模拟器 qemu-riscv 上

实验至少包含四个部分: 词法和语法分析、语义分析和中间代码生成、以及目标代码生成，每个部分都依赖前一个部分的结果，逐步构建一个完整编译器

实验一：词法分析和语法分析，将读取源文件中代码并进行分析，输出一颗语法树

实验二：接受一颗语法树，进行语义分析、中间代码生成，输出中间表示 IR (Intermediate Representation)

实验三：根据 IR 翻译成为汇编

实验四(可选)：IR 和汇编层面的优化

2. 实验开始之前

本次实验将从零开始，写一个完整的编译器，编译 SysY 语言至 risc-v 汇编，并在 qemu-riscv 上跑起来

在开始之前，请不要抱有畏惧心理，我们准备好的了详细的文档、代码框架和构建方案、自动化测试程序

还有几个小建议：

在编写代码时，注意代码规范，避免出现低级但难以排查的错误甚至是奇奇怪怪的链接错误，请阅读 C++ coding style 和助教为你准备的如果不遵守可能会出现各种奇奇怪怪问题的编码小技巧
在遇到 bug 时，请相信计算机一定不会出错，一定是代码的问题
在需要查找资料来解决问题时，请至少使用 Bing 而不是百度，尽量查阅 Google, wikipedia, stackoverflow 等网站的资料，因为与编译原理相关的中文资料可能会非常少，英文资料相对丰富（以助教的经验来说 CSDN 不太能解决问题
上网查资料并不能解决所有的问题，他们的回答甚至有可能时错的！正确的做法应当是阅读官方文档，官方手册包含了查找对象的所有信息，关于查找对象的一切问题都可以在官方手册中找到答案。如果你需要了解如何使用 GDB，你应该阅读Debugging with GDB，或者是你需要了解 riscv 的指令集定义、汇编规则，你应该到 riscv 官网中的技术手册中寻找答案
在向助教和同学提问之前，请学习提问的智慧，以更高效的解决问题

3. 实验一

3.1 实验目标

实验一将实现编译器前端的词法分析和语法分析部分，目标是分析输入的 源文件 得到一颗 抽象语法树

3.2 实验步骤

3.2.1 实验一标准输出

这是一段最简单的 SysY 程序

int main() {
    return 3;
}

实验一将把他解析为一颗语法分析树，我们用 json 来输出语法树，标准如下：

{
   "name" : "CompUnit",
   "subtree" : [
      {
         "name" : "FuncDef",
         "subtree" : [
            {
               "name" : "FuncType",
               "subtree" : [
                  {
                     "name" : "Terminal",
                     "type" : "INTTK",
                     "value" : "int"
                  }
               ]
            },
            {
               "name" : "Terminal",
               "type" : "IDENFR",
               "value" : "main"
            },
            {
               "name" : "Terminal",
               "type" : "LPARENT",
               "value" : "("
            },
            {
               "name" : "Terminal",
               "type" : "RPARENT",
               "value" : ")"
            },
            {
               "name" : "Block",
               "subtree" : [
                  {
                     "name" : "Terminal",
                     "type" : "LBRACE",
                     "value" : "{"
                  },
                  {
                     "name" : "BlockItem",
                     "subtree" : [
                        {
                           "name" : "Stmt",
                           "subtree" : [
                              {
                                 "name" : "Terminal",
                                 "type" : "RETURNTK",
                                 "value" : "return"
                              },
                              {
                                 "name" : "Exp",
                                 "subtree" : [
                                    {
                                       "name" : "AddExp",
                                       "subtree" : [
                                          {
                                             "name" : "MulExp",
                                             "subtree" : [
                                                {
                                                   "name" : "UnaryExp",
                                                   "subtree" : [
                                                      {
                                                         "name" : "PrimaryExp",
                                                         "subtree" : [
                                                            {
                                                               "name" : "Number",
                                                               "subtree" : [
                                                                  {
                                                                     "name" : "Terminal",
                                                                     "type" : "INTLTR",
                                                                     "value" : "3"
                                                                  }
                                                               ]
                                                            }
                                                         ]
                                                      }
                                                   ]
                                                }
                                             ]
                                          }
                                       ]
                                    }
                                 ]
                              },
                              {
                                 "name" : "Terminal",
                                 "type" : "SEMICN",
                                 "value" : ";"
                              }
                           ]
                        }
                     ]
                  },
                  {
                     "name" : "Terminal",
                     "type" : "RBRACE",
                     "value" : "}"
                  }
               ]
            }
         ]
      }
   ]
}

3.3 词法分析

词法分析的目的是读入外部的字符流（源程序）对其进行扫描，把它们组成有意义的词素序列，对于每个词素，词法分析器都会产生词法单元(Token) 作为输出

1. Token

Token 的定义在 token.h 中，同时 Token 类型的枚举类 TokenType 也定义在其中

struct Token {
    TokenType type;
    string value;
};

enum class TokenType{
    IDENFR,         // identifier    
    INTLTR,            // int literal
    FLOATLTR,        // float literal
    CONSTTK,        // const
    VOIDTK,            // void
    ... 
}

其中 string value 是 Token 所代表的字符串， TokenType type 是指 Token 的类型

2. DFA

在词法分析中，我们使用确定有限状态自动机 (deterministic finite automaton, DFA) 来进行分词，对于一个给定的属于该自动机的状态和一个属于该自动机字母表 Σ 的字符，它都能根据事先给定的 转移函数 转移到下一个状态，某些转移函数会进行输出

我们需要为词法分析设计这样一个 DFA：它可以接收输入字符，进行状态改变，并在某些转移过程中输出累计接受到的字符所组成的字符串

该 DFA 中应存在五种状态，我们用枚举类 State 来表示

enum class State {
    Empty,              // space, \n, \r ...
    Ident,              // a keyword or identifier, like 'int' 'a0' 'else' ...
    IntLiteral,         // int literal, like '1' '1900', only in decimal
    FloatLiteral,       // float literal, like '0.1'
    op                  // operators and '{', '[', '(', ',' ...
};

我们将 DFA 及其行为的抽象为类和类方法，定义在 lexical.h 中

struct DFA {
    /**
     * @brief take a char as input, change state to next state, and output a Token if necessary
     * @param[in] input: the input character
     * @param[out] buf: the output Token buffer
     * @return  return true if a Token is produced, the buf is valid then
     */
    bool next(char input, Token& buf);

    /**
     * @brief reset the DFA state to begin
     */
    void reset();

private:
    State cur_state;    // record current state of the DFA
    string cur_str;    // record input characters
};

其中 State cur_state 记录 DFA 当前的状态，string cur_str 记录 DFA 已经接受的字符串

每次字符输入都应调用 bool next(char input, Token& buf); 该函数是实现 DFA 的核心，即 转移函数 ，其根据自身当前状态和输入来决定转移后的状态，如果产生 Token 则返回 true

TODO: *实现 DFA 中的 bool next(char input, Token& buf) 函数和 void reset(); 函数*

3. Scanner

Scanner 是扫描器，其职责是将字符串输入转化为 Token 串，词法分析实际上就是实现一个 Scanner

Scanner 的定义在 lexical.h 中

struct Scanner {
    /**
     * @brief constructor
     * @param[in] filename: the input file  
     */
    Scanner(std::string filename); 

    /**
     * @brief run the scanner, analysis the input file and result a token stream
     * @return std::vector<Token>: the result token stream
     */
    std::vector<Token> run();

private:
    std::ifstream fin;  // the input file
};

其中 std::ifstream fin 是源文件打开得到的文件流

std::vector<Token> run(); 将执行分析过程，从文件流中读取字符，实例化一个 DFA 对象来获取 Token，但是我们的 DFA 只能识别代码部分，源文件中的注释输入 DFA 后并不能被正确的处理，我们需要在使用 DFA 接受字符串前对字符串进行预处理，所以 run() 的伪代码如下：

vector<Token> ret;
Token tk;
DFA dfa;
string s = preproccess(fin);    // delete comments
for(auto c: s) {
        if(dfa.next(c, tk)){
            ret.push_back(tk);
        }
}

TODO: 实现 Scanner 的 std::vector run() 函数

我们用一段最简单的 SysY 程序来展示词法分析的结果

int main() {
    return 3;
}

结果如下:

TokenType	Value
INTTK	int
IDENFR	main
LPARENT	(
RPARENT	)
LBRACE	{
RETURNTK	return
INTLTR	3
SEMICN	;
RBRACE	}

词法分析部分到此结束

3.4 语法分析

1. SysY 文法

我们对 SysY 文法进行了一定的限制以减少难度，主要改变是同学们不需要支持二维以上的数组解析、不需要支持各种形式的浮点数字面量解析(不需要支持即我们在测试中不会出现这样的用例)，并对左递归文法做了处理。新的文法请参考文法定义。请注意，实现必须以该文法为准

2. 抽象语法树

抽象语法树(abstract syntax tree, AST) 是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构

我们知道文法中的一个 产生式 可以化为树的形式，如 FuncDef -> FuncType Ident '(' [FuncFParams] ')' Block 可以展开为以 FuncDef 为父节点，FuncType Ident '(' [FuncFParams] ')' Block 为从左至右子节点的一颗多叉树

为了之后语义分析的实现方便，我们为每一个非终结符定义一个类，以便不同的树节点可以拥有他们自己的成员变量，他们拥有共同的基类 AstNode，定义在 abstract_syntax_tree.h 中

struct AstNode{
    NodeType type;  // the node type
    AstNode* parent;    // the parent node
    vector<AstNode*> children;     // children of node

    /**
     * @brief Get the json output object
     * @param root: a Json::Value buffer, should be initialized before calling this function
     */
    void get_json_output(Json::Value& root) const;
}

struct CompUnit: AstNode {
struct Decl: AstNode{
struct FuncDef: AstNode{
struct ConstDecl: AstNode {
...

其中 NodeType 代表了树节点的类型，每个非终结符有自己的 NodeType，所有的终结符认为式 Terminal 类型，NodeType 枚举类定义在abstract_syntax_tree.h 中

公众号：AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

方法一：QQ

方法二：微信：Jiabcdefh