[关闭]
@sangyy 2015-12-27T10:41:32.000000Z 字数 23505 阅读 4841

实验要求

compiler2015

1. 预备阶段

1.1. 熟悉实验环境

安装 Linux，LLVM 3.6.0，GCC，使用GCC/Clang来编译C程序，并运行编译生成的可执行程序。初步熟悉Makefile，了解编译器的过程。

1.2. 熟悉C1语言的特征

C1语言的特征参见附2。用C1语言编写3个以上的程序，其中至少有解决数组排序问题的程序，并使用GCC/Clang编译。
* 注：编译时不需要加任何参数，将C1源文件当成C文件编译即可。
* 注：为了方便调试，可增加scanf、printf等指令。最后务必输出结果，方便我批改
* 注：请在README中说明应执行哪些指令以验证你程序的正确性，并简要描述程序的功能。在doc/中较详细地说明程序的设计思路、如何克服C1简陋的语法造成的困难。

1.3. 初步了解编译过程

阅读教材11.1节和LLVM的资料，了解预处理、编译、连接的含义和命令（写入doc/中），并使用。

1.4. P1提交的目录结构要求

文件名 功能
README 提交内容说明，包含如何编译运行所提交的内容等
Makefile
src/ 存放源程序文件（*.h, *.c）
doc/ 实验设计文档
bin/ 帮助快速编译和运行实验内容的shell脚本文件，不要把编译出的可执行文件放进去! 不要把编译出的可执行文件放进去! 不要把编译出的可执行文件放进去!
test/ 存放测试程序

1.5. 提交细则

src/下放3个以上的C1程序。这些程序都要能输出结果（可以违反C1语法，添加printf），好体现你程序的正确性。
bin/下可以写一个shell脚本，快速运行并编译运行所有程序。（但不强制要求）
Makefile写一个自动编译所有程序的神奇文件，见教程链接。（不强制要求，但是迟早要用的）
README里给出编译和运行程序的指令，如果写了shell脚本，就说明如何调用该脚本。还要简单地注明各个程序的功能。
doc/下详细说明各程序的设计思路，如何克服C1语法的简陋性（如没有for循环，函数不能传参数）。另外要回答第3题，介绍预处理、编译、链接的含义，以及LLVM的相关指令。
目测用不到test/

2. 词法分析

从这次实验开始，我们会学习LLVM提供的教程Kaleidoscope，结合Flex和Bison进行一些扩展。
此外将开始阅读Clang源代码，以增加对一个真实编译器的了解。
我们的目的是使用LLVM、Flex、Bison从头构造一个C1的编译器。下面列出的实验标题可能随课程进度有所改动。

2.1. 理解Kaleidoscope的词法分析过程

2.2. 学习使用Flex

阅读Flex manual和一个简单的表达式语言的词法分析例子，了解Flex的输入词法规范文件的格式，以及Flex生成的词法分析器的接口形式和实现。你可以从flex-2.5.35.tar.gz的examples目录下获得更多使用Flex的例子。

2.3. 用Flex生成C1的词法分析器

2.4. 阅读Clang词法分析文件

建议使用IDE阅读Clang代码，可以使用Code Blocks, Code Lite, Eclipse CDT, NetBeans, Dev C++等。或者用Vim+ctags+cscope
下载3.6.0版本的LLVM和Clang源码，阅读Clang/lib/Lex/和Clang/include/clang/Lex下的源码。

2.5. P2提交的目录结构要求

文件名 功能
README 提交内容说明，包含如何编译运行所提交的内容等
Makefile
src/ 存放源程序文件（*.h, *.cpp）
config/ 存放lex和yacc文件
include/ 头文件
doc/ 实验设计文档
bin/ 帮助快速编译和运行实验内容的shell脚本文件
test/ 存放测试程序

2.6. 提交细则

config/：lexer.l
src/：main.cpp, tok.cpp等，不要放lex自动生成的cpp文件。还有修改后的Kaleidoscope编译器。
include/：tok.h
bin/：可以写一个shell脚本，快速运行并编译运行所有程序。（但不强制要求）
Makefile
README里给出编译和运行程序的指令，简单注明各个程序的功能。
doc/：详细说明程序的设计思路。另外要回答1,2,4题，其中第2题要简介flex词法文件的格式，以及生成的词法分析器的接口。第4题的部分内容已经在讨论课讨论过，但依然要写入文档。此外如果你也可以一些有意思的发现，助教会酌情加分。
test/：P1的3个C1文件。
注：提交前执行make clean，清空bin/里生成的.o和可执行文件，以及flex自动生成生成的cpp文件。

3. Kaleidoscope语法分析

3.1. 理解Kaleidoscope的语法分析和AST

阅读LLVM教程的第二章、第五章和第七章扩展if/then/else、for循环和变量的词法、语法部分（可忽略代码生成），文法见附5。了解自顶向下的语法分析过程以及AST的结构和创建方法。可通过git clone git@202.38.75.124:comppub查看扩展后的代码(在Kaleidoscope-dump目录下)。回答下列问题：

3.2. 扩展while循环

基于你对if/then/else和for循环的理解，扩展Kaleidoscope编译器，使其支持while循环，并在程序结束后输出AST对应的DOT图。

3.3. P3提交的目录结构要求

文件名 功能
README 提交内容说明，包含如何编译运行所提交的内容等
Makefile
src/ 存放源程序文件（*.h, *.cpp）
include/ 头文件
doc/ 实验设计文档
bin/ 帮助快速编译和运行实验内容的shell脚本文件
test/ 存放测试程序

3.4. 提交细则

src/：toy.cpp, dumpdot.cpp
include/:ast.h, dumpdot.h
bin/：可以写一个shell脚本，快速运行并编译运行所有程序（但不强制要求）
Makefile
README里给出编译和运行程序的指令，简单注明各个程序的功能。
doc/：详细说明程序的设计思路。另外要回答第1题。
test/：目测用不到。

4. C1语言的语法分析与错误恢复

本实验旨在熟悉Bison，并利用Flex和Bison来为C1语言构造词法分析器和语法分析器，所构造的分析器能识别几种错误并从这些错误中恢复，还能输出在自下而上分析时归约所使用的产生式。

4.1. 学习Bison

4.2. 用lex+bison, 为C1语言构造能识别正确C1程序的分析器

C1语言的特征参见附2。在编写C1语言的Lex词法规范文件和Yacc文法规范文件时，可参考ANSI-C语言的lex词法规范和Yacc文法规范。

该项实验的要求：

4.3. 提交细则

doc/：包含一个说明提交内容以及完成/未完成/参考/问题等情况的文档，以及4.1中对Bison的理解、对各个问题的回答
test/：包含至少5个C1程序（要求说明程序的特征）作为测试程序
bin/：包含P4的编译运行脚本文件。
src/：源文件
config/：flex和bison源文件

5. 生成C1的AST

5.1. 理解asgn2ast

注：comppub/ast2ast已于2015-11-05更新
阅读comppub/asgn2ast源码，了解AST的数据结构、构造和使用方法

5.2. 为C1生成AST

5.3. 提交细则

doc/：回答5.1的第2问和5.2的第1问，并说明你代码的设计思路
src/：源文件
include/：头文件
config/：lex和yacc文件
test/：至少3个测试文件，要体现出error和warning
bin/：脚本文件

6. Clang语法分析和静态检查

本实验通过阅读clang源代码中位于lib、include、tools子目录中的部分源程序文件，来理解clang的语法分析和静态语义检查的实现机制

6.1. 编译LLVM+Clang

参照该博客使用ninja编译LLVM和Clang，注意使用与LLVM3.6.0配套的代码。一般来说编译用时在20分钟以内。

6.2. 阅读Clang语法分析文件

本节以编译后的LLVM为根目录进行说明

6.2 提交细则

doc/：回答上面提到的问题
test/：放入cfg.c, fib.c, unreachable.c和DumpCFG一题要求的DOT文件或PNG图

7. 生成IR

注意：P7工作量比较大，请及早准备

7.1 理解Kaleidoscope代码生成

阅读LLVM教程的第三章、第五章和第七章，学习LLVM生成IR的方法并回答下列问题（你可以使用compub/llvm3.6.0中的网页镜像和复制好的代码）：

  1. 解释教程3.2节中Module、IRBuilder<>的作用；结合教程7.7节，说明: Kaleidoscope的符号表使用了什么结构、如何处理不同作用域的变量重名问题?
  2. 为何使用常量时用的函数名都是get而不是create？
  3. 简要说明声明和定义一个函数的过程（你可以仿照它使C1支持含参数的函数）。
  4. 处理函数定义时只有一个Block，但是我们可以参考If/Then/Else部分，学习如何操作多个Block。此外，请解释为何需要ThenBB = Builder.GetInsertBlock()。
  5. for循环的Codegen有一处不符合C规定，它先执行一遍循环体，再检查循环条件。思考如何修改可以先检查循环条件，如果为真再执行循环体（用在C1中while的Codegen）
  6. 阅读第7章，学习如何使用alloca在栈上为变量分配内存。7.7节的Local Variables很像C1的局部变量，说明在有多层嵌套时它是如何操作符号表的。

7.2 为C1生成IR

  1. 仿照Kaleidoscope，为C1的各种AST结点增加Codegen方法（注意把float换成int，在最后加上mem2reg的优化）
  2. 为了支持一维数组，你会用到GEP来取数组元素，由于它容易引起误解，有一份专门的FAQ。此外定义一维数组可以使用Alloca为一个ArrayType类型的变量分配空间（具体请参考下放的第二个提示）
  3. 仿照Kaleidoscope，支持外部函数声明；
  4. 将IR dump到文件中，并学习llc的使用方法，由IR生成.o文件；
  5. 编写一个静态库，在其中提供一些自定义函数（如printf、scanf等等），将上一步中的.o文件和它链接生成可执行文件。（只要你最终编译出的二进制文件能调用printf即可，不一定要扩展C1使其支持外部函数）

提示：

7.3 扩展C1

你可以考虑如下扩展（当然扩展后必须要生成对应的LLVM IR）

  1. 支持逻辑运算not(!) and(&&) or(||)，支持短路运算
  2. 循环中支持break和continue
  3. 支持含参数的函数
  4. 支持函数带返回值
  5. 支持return语句
  6. 支持多维数组
  7. 支持float类型

7.4 提交细则

附1. 参考资料

附2. C1语言的特征

C1语言是一个类C的小型实验语言。在数据类型上，只支持整数类型和一维整型数组类型。一个C1语言程序文件包含若干常量定义、全局变量声明、无参函数定义，其中必须包含一个名为main的函数，作为程序执行的主函数。函数体中可以有常量定义、变量声明和语句。C1语言有赋值语句、函数调用语句、复合语句、条件语句、循环语句和空语句。
由于上面这些语言概念已为大家熟知，因此不再进行语义解释。下面用习题3.7 所介绍的扩展方式来给C1语言的文法。

CompUnit    → [ CompUnit ] (Decl | FuncDef ) 
                CompUnit代表一个C1程序文件，其中必须包含一个名为main的函数定义FuncDef
                这里假设一个C1程序只存放在一个C1程序文件中
Decl        → ConstDecl | VarDecl
ConstDecl   → const int ConstDef {, ConstDef} ';'
ConstDef    → ident '=' Exp | ident '[' [ Exp ] ']' '=' '{' Exp { ',' Exp } '}'
                ConstDecl常量声明：可以声明一个或多个整型常量、整型常量数组，如：
                const int a[]={2,3};
                声明了长度为2的常量数组a，a[0]、a[1]的值分别为2和3；
                数组在声明时若未指明长度，则长度为初始化表达式中值的个数。
                在程序中，不能对常量重新赋值。
                [注1]
VarDecl     → int Var{, Var}';'
Var         → ident | ident '[' Exp ']' | ident '=' Exp
            | ident '[' [ Exp ] ']' '=' '{' Exp { ',' Exp } '}'
                VarDecl 变量声明：可以声明整型和一维整型数组变量。
                [注2]
FuncDef     → void ident '(' ')' Block
                FuncDef 函数定义：无参函数，且必须有一个名字为main 的函数
Block       →'{' { BlockItem } '}'
BlockItem   → Decl | Stmt
                Block语句块：表示函数体或者复合语句，其中可以包含0个或多个声明或语句
Stmt        → LVal '=' Exp ';' | ident '(' ')' ';' | Block 
            | if '( Cond ')' Stmt [else Stmt ] | while '(' Cond ')' Stmt | ';'
LVal        → ident| ident '[' Exp ']'
Cond        → Exp RelOp Exp
RelOp       →'==' | '!=' | '<' | '>' | '<=' | '>='
Exp         → Exp BinOp Exp | UnaryOp Exp | '(' Exp ')' | LVal | number
BinOp       → '+' | '−' | '*' | '/' | '%'
UnaryOp     → '+' | '−'
                运算符的优先级和结合性与C语言中的一样

注1：对于ConstDef定义中初始化表达式Exp和数组长度Exp是否能使用之前已经声明的const变量，gcc4.6.3和clang3.3有不同的处理语义，具体举例说明如下(为简便起见，省略编译器的版本号)：

注2：对于Var定义中初始化表达式Exp和数组长度Exp是否能使用已经声明的变量，gcc和clang也有不同的处理语义，处理规则与上述的ConstDef中的类似，这里不再赘述。类似地，你需要选择其一作为C1语言的语义约束规定，你需要确保这种选择与上面关于ConstDef中的语义约束规定相一致。

附3. Bison生成的分析器源码中使用的一些表及其含义

以下内容来自Bison-2.4.1源码中src/tables.h里的注释：
YYTRANSLATE = vector mapping yylex's token numbers into bison's  token numbers.
YYTNAME = vector of string-names indexed by bison token number.
YYTOKNUM = vector of yylex token numbers corresponding to entries in YYTNAME.
YYRLINE = vector of line-numbers of all rules.  For yydebug printouts.
YYRHS = vector of items of all rules.  This is exactly what RITEMS contains.  For yydebug and for semantic parser.
YYPRHS[R] = index in YYRHS of first item for rule R.
YYR1[R] = symbol number of symbol that rule R derives.
YYR2[R] = number of symbols composing right hand side of rule R.
YYSTOS[S] = the symbol number of the symbol that leads to state S.
YYDEFACT[S] = default rule to reduce with in state s, when YYTABLE doesn't specify something else to do.  Zero means the default is an error.
YYDEFGOTO[I] = default state to go to after a reduction of a rule that generates variable NTOKENS + I, except when YYTABLE specifies something else to do.
YYPACT[S] = index in YYTABLE of the portion describing state S. The lookahead token's type is used to index that portion to find out what to do.  If the value in YYTABLE is positive, we shift the token and go to that state. If the value is negative, it is minus a rule number to reduce by.  If the value is zero, the default action from YYDEFACT[S] is used.
YYPGOTO[I] = the index in YYTABLE of the portion describing what to do after reducing a rule that derives variable I + NTOKENS.  This portion is indexed by the parser state number, S, as of before the text for this nonterminal was read.  The value from YYTABLE is the state to go to if the corresponding value in YYCHECK is S.
YYTABLE = a vector filled with portions for different uses, found via YYPACT and YYPGOTO.
YYCHECK = a vector indexed in parallel with YYTABLE.  It indicates, in a roundabout way, the bounds of the portion you are trying to examine. Suppose that the portion of YYTABLE starts at index P and the index to be examined within the portion is I.  Then if YYCHECK[P+I] != I, I is outside the bounds of what is actually allocated, and the default (from YYDEFACT or YYDEFGOTO) should be used.  Otherwise, YYTABLE[P+I] should be used.
YYFINAL = the state number of the termination state.
YYLAST ( = high) the number of the last element of YYTABLE, i.e., sizeof (YYTABLE) - 1. 

附4. bison-examples的说明

本压缩包围绕2个小型编程语言：L-expr（简单的表达式语言）、L-asgn（赋值语句序列语言），给出如何利用Flex和Bison构造编译器，其中涉及程序位置跟踪、符号表的管理、抽象语法树的构造、错误信息管理等。

1. L-expr语言的文法

input ::= ε  | input line
line ::= EOL | expr EOL
expr ::= NUMBER 
            | expr PLUS expr    # PLUS  – ‘+’加号
            | expr MINUS expr   # MINUS – ‘-’减号
            | expr MULT expr    # MULT  – ‘*’乘号
            | expr DIV expr     # DIV   – ‘/’除号
            | MINUS expr        # MINUS – ‘-’负号
            | expr EXPON expr   # EXPON – ‘^’乘幂
            | LB expr RB        # LB, RB – ‘(’, ’)’ 左右括号

2. L-asgn语言的文法

input   ::= ε | input line
line    ::= EOL 
            | asgnexp ';' EOL
asgnexp ::= IDENTIFIER ASGN exp # ASGN  - ‘=’赋值号
expr    ::= NUMBER
            | IDENTIFIER        # IDENTIFIER – 标识符
            | expr PLUS expr    # PLUS  – ‘+’   加号
            | expr MINUS expr   # MINUS – ‘-’减号
            | expr MULT expr    # MULT  – ‘*’乘号
            | expr DIV expr     # DIV   – ‘/’ 除号
            | MINUS expr        # MINUS – ‘-’负号
            | expr EXPON expr   # EXPON – ‘^’乘幂
            | LB expr RB        # LB, RB – ‘(’, ’)’ 左右括号

在L-asgn语言中，标识符代表变量，标识符需要先赋值再使用。如果程序使用了未赋值的变量，则需要给出警告并默认初值为0。

3. bison-examples.zip的文件目录结构说明。

|- README           对本压缩包的说明文档
|- Makefile         用于构造语言的词法、语法分析器并将它们编译成可执行文件
|- run.sh           以./run.sh x y命令启动bin子目录下的x编译器编译test子目录下的y程序
|- config           存放语言的词法和语法文法文件
    |- expr.lex     L-expr的Flex词法规范。
                    以-oexpr.lex.c选项执行flex，会根据该文件生成词法分析器expr.lex.c
    |- expr.y       L-expr的Yacc语法规范，它利用Yacc提供的优先级声明来消除文法的二义性。该语法规范内嵌有边分析边对表达式求值的语义动作。
                    以-b expr -o expr.tab.c选项执行Bison，会根据该文件生成语法分析器expr.tab.c以及词法、语法分析都需使用的符号声明头文件expr.tab.h
    |- expr1.y      L-expr的Yacc语法规范，它通过增加文法非终结符，将文法改写成无二义的文法。可以用Bison处理该文件，生成expr1.tab.h(.c)。该语法规范内嵌有边分析边对表达式求值的语义动作。
    |- exprL.y      L属性定义举例：L-expr的Yacc语法规范，在规则中嵌入打印行号的语义动作，行号通过全局变量传递。
    |- exprL1.y     L属性定义举例：L-expr扩展语言略(每行开始增加行号)的Yacc语法规范，在规则中嵌入打印源程序中所给行号的语义动作。
    |- midrule.y    L属性定义举例：使用$<val>N引用语义值栈中任意位置的语义值，N可以为正整数、0、负整数，<val>为所引用的语义值的类型。
    |- asgn.lex     L-asgn的Flex词法规范。
    |- asgn.y       L-asgn的Yacc语法规范。该语法规范内嵌有边分析边对赋值语句求值的语义动作。
    |- asgn1.y      L-asgn的Yacc语法规范，它与asgn.y的区别在于引入一个表示双目运算符的非终结符op。
    |- asgn2ast.y   L-asgn的Yacc语法规范。该语法规范内嵌有边分析边构造抽象语法树的语义动作。
    |- asgn_err.lex L-asgn的Flex词法规范，它与asgn.lex的区别在于引入统计尚未匹配的左括号数的全局量lparen_num，以便在词法分析的过程中进行括号匹配跟踪。
    |- asgn_err.y   L-asgn的Yacc语法规范。它与asgn_err.lex协作，支持对不合法的L-asgn程序的分析，提供错误恢复以及错误信息的记录并在分析结束时集中输出。
|- include          存放用户自定义的头文件
    |-util.h        存放一些实用的宏、类型声明、函数声明，如动态分配相关的宏定义(如NEW, NEW0)；线性表、线性表迭代器的数据结构的定义以及相关接口函数的声明。
    |-common.h      编译器需要使用的一些公共的声明和定义，如符号表的结构、错误信息的结构、错误容器（或称错误工厂）的结构、语法树及其结点的结构定义，相关函数的声明等等
    |-op.h          保存所处理的运算符及其对应的文本信息的配置文件
    |-errcfg.h      保存所处理的错误类别及其对应的提示信息的配置文件
|- src              存放源程序文件
    |-list.c        线性表的接口函数的实现（采用链式结构存储）、线性表迭代器Iterator的接口函数的实现
    |-symtab.c      符号表的接口函数的实现（采用链地址结构的Hash表存储）
    |-error.c       错误信息及其管理的接口函数的实现
    |-ast.c         抽象语法树相关的接口函数的实现
    |- expr.1ex.c, expr.tab.h, expr.tab.c, expr1.tab.c
利用Bison和Flex处理config目录下的expr.lex, expr.y, expr1.y生成的词法、语法分析器的源代码文件。
    |- asgn.1ex.c, asgn.tab.h, asgn.tab.c, asgn1.tab.c, asgn2ast.tab.c 利用Bison和Flex处理config目录下的asgn.lex, asgn.y, asgn1.y, asgn2ast.y生成的词法、语法分析器的源代码文件。
    |- asgn_err.1ex.c, asgn_err.tab.h, asgn_err.tab.c 利用Bison和Flex处理config目录下的asgn_err.lex, asgn_err.y生成的词法、语法分析器的源代码文件。
|- bin              存放可执行文件
    |- expr, expr1, asgn, asgn1, asgn2ast, asgn_err 执行make或者make expr ( 或expr1, asgn, asgn1, asgn2ast, asgn_err)后得到的L-expr、L-asgn语言的编译器的可执行文件
|- test             存放测试程序
    |- expr.in      一个合法的L-expr程序
    |- asgn.in      一个合法的L-asgn程序
    |- asgn_err.in  一个不合法的L-asgn程序

4. 如何使Flex和Bison生成的分析器能跟踪程序位置

bison-examples中config/asgn.lex和asgn.y给出了如何使生成的分析器能跟踪程序位置的示例。这里简述要点：

  1.     %{int yycolumn = 1;
  3.     #define YY_USER_ACTION yylloc.first_line = yylloc.last_line = yylineno; \
  4.     yylloc.first_column = yycolumn; yylloc.last_column = yycolumn+yyleng-1; \
  5.     yycolumn += yyleng;
  6.     %}
  7.     %option yylineno

5. 利用预编译指令灵活处理诸如错误类别等的可配置信息

在bison-examples中使用预编译指令灵活处理错误类别以及操作符等可配置的信息，并根据实际的配置信息生成相关类型和全局变量等。这里以操作符为例，简述处理方法：

6. 引入宏NEW和NEW0来简化对各类结点的动态创建和清0操作的代码编写

    #define NEW(p)  ((p) = malloc(sizeof *(p)))
    #define NEW0(p) memset(NEW(p), 0, sizeof *(p))

若要构建结点类型为A的结点，则可以：

    A *p, *q;
    NEW(p);         // 创建A类型的结点，使p指向A类型的结点
    NEW0(q);        //创建A类型的结点并将所创建的结点清0，使q指向该结点

7. 引入设计模式和工厂模式

8. 在Yacc文法描述文件中处理L属性定义

其中，sum_of_the_five_previous_values文法符号对应的规则中$<val>0、 $<val>-1、$<val>-2、$<val>-3、$<val>-4分别表示栈中a_5、{ $<val>$ = $<val>3 + 1; }、{ $<val>$ = 3; }、a_2、a_1文法符号的语义值。

附5. Kaleidoscope文法

identifierexpr  ::= identifier | identifier '(' expression* ')'
numberexpr ::= number
parenexpr ::= '(' expression ')'
binop ::= '=' | '+' | '-' | '*' | '<'
binoprhs ::= (binop primary)*
expression ::= primary binoprhs
prototype ::= id '(' id* ')'
definition ::= 'def' prototype expression
external ::= 'extern' prototype
toplevelexpr ::= expression
top ::= definition | external | toplevelexpr | ';'

primary ::= identifierexpr |numberexpr | parenexpr
            | ifexpr | forexpr  // ch5
            | varexpr  // ch7
// ch5
ifexpr ::= 'if' expression 'then' expression 'else' expression
forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression

// ch7
varexpr ::= 'var' identifier ('=' expression)? 
            (',' identifier ('=' expression)?)* 'in' expression

//extend
whileexpr ::= 'while' expression expression
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注