跳转至

词法语法解析

词法分析器

现在我们开始编写 Cminusf 的词法解析器。首先，让我们了解一下 Cminusf 的词法规则，随后将介绍实验要求和细节。

Cminusf 词法

Cminus 是 C 语言的一个子集，该语言的语法在《编译原理与实践》第九章附录中有详细的介绍。而 Cminusf 则是在 Cminus 上追加了浮点操作。

  1. 关键字。
else if int return void while float
  1. 专用符号。
+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */
  1. 标识符 ID 和数值，通过下列正则表达式定义：
letter = a|...|z|A|...|Z
digit = 0|...|9
ID = letter+
INTEGER = digit+
FLOAT = (digit+. | digit*.digit+)
  1. 注释用 /*...*/ 表示，可以超过一行。注释不能嵌套。
/*...*/

请认真阅读 Cminusf 的词法。其词法特性相比 C 语言做了大量简化，比如标识符 student_id 在 C 语言中是合法的，但是在 Cminusf 中是不合法的。

实验内容

本部分需要各位同学在 src/parser/lexical_analyzer.l 文件中根据 Cminusf 的词法规则完成词法分析器。在 lexical_analyzer.l 文件中，你只需在规则部分补全模式和动作即可，能够输出识别出的 token，text，line(刚出现的行数)，pos_start(该行开始位置)，pos_end(结束的位置，不包含)。比如：

文本输入：

void main(void) { return; }

则识别结果应该如下：

Token         Text      Line    Column (Start,End)
282           void      1       (1,5)
284           main      1       (6,10)
272              (      1       (10,11)
282           void      1       (11,15)
273              )      1       (15,16)
276              {      1       (17,18)
281         return      1       (19,25)
270              ;      1       (25,26)
277              }      1       (27,28)

必须维护正确的：token、text。

可以选择性维护的（方便 debug，测试）：line、pos_start、pos_end。

推荐同学们下载 vscode 的插件 lex 和 bison，可以在补全 .l文件和 .y文件的时候提供高亮。

语法分析器

Cminusf 语法

本小节将给出 Cminusf 的语法，我们将 Cminusf 的所有规则分为五类。

  1. 字面量、关键字、运算符与标识符
  2. type-specifier
  3. relop
  4. addop
  5. mulop
  6. 声明
  7. declaration-list
  8. declaration
  9. var-declaration
  10. fun-declaration
  11. local-declarations
  12. 语句
  13. compound-stmt
  14. statement-list
  15. statement
  16. expression-stmt
  17. iteration-stmt
  18. selection-stmt
  19. return-stmt
  20. 表达式
  21. expression
  22. simple-expression
  23. var
  24. additive-expression
  25. term
  26. factor
  27. integer
  28. float
  29. call
  30. 其他
  31. params
  32. param-list
  33. param
  34. args
  35. arg-list

起始符号是 program。文法中用到的 token 均以下划线和粗体标出。

  1. \(\text{program} \rightarrow \text{declaration-list}\)
  2. \(\text{declaration-list} \rightarrow \text{declaration-list}\ \text{declaration}\ |\ \text{declaration}\)
  3. \(\text{declaration} \rightarrow \text{var-declaration}\ |\ \text{fun-declaration}\)
  4. \(\text{var-declaration}\ \rightarrow \text{type-specifier}\ \underline{\textbf{ID}}\ \underline{\textbf{;}}\ |\ \text{type-specifier}\ \underline{\textbf{ID}}\ \underline{\textbf{[}}\ \underline{\textbf{INTEGER}}\ \underline{\textbf{]}}\ \underline{\textbf{;}}\)
  5. \(\text{type-specifier} \rightarrow \underline{\textbf{int}}\ |\ \underline{\textbf{float}}\ |\ \underline{\textbf{void}}\)
  6. \(\text{fun-declaration} \rightarrow \text{type-specifier}\ \underline{\textbf{ID}}\ \underline{\textbf{(}}\ \text{params}\ \underline{\textbf{)}}\ \text{compound-stmt}\)
  7. \(\text{params} \rightarrow \text{param-list}\ |\ \underline{\textbf{void}}\)
  8. \(\text{param-list} \rightarrow \text{param-list}\ \underline{\textbf{,}}\ \text{param}\ |\ \text{param}\)
  9. \(\text{param} \rightarrow \text{type-specifier}\ \underline{\textbf{ID}}\ |\ \text{type-specifier}\ \underline{\textbf{ID}}\ \underline{\textbf{[}}\ \underline{\textbf{]}}\)
  10. \(\text{compound-stmt} \rightarrow \underline{\textbf{\{}}\ \text{local-declarations}\ \text{statement-list}\ \underline{\textbf{\}}}\)
  11. \(\text{local-declarations} \rightarrow \text{local-declarations var-declaration}\ |\ \text{empty}\)
  12. \(\text{statement-list} \rightarrow \text{statement-list}\ \text{statement}\ |\ \text{empty}\)
  13. \(\begin{aligned}\text{statement} \rightarrow\ &\text{expression-stmt}\\\ &|\ \text{compound-stmt}\\\ &|\ \text{selection-stmt}\\\ &|\ \text{iteration-stmt}\\\ &|\ \text{return-stmt}\end{aligned}\)
  14. \(\text{expression-stmt} \rightarrow \text{expression}\ \underline{\textbf{;}}\ |\ \underline{\textbf{;}}\)
  15. \(\begin{aligned}\text{selection-stmt} \rightarrow\ &\underline{\textbf{if}}\ \underline{\textbf{(}}\ \text{expression}\ \underline{\textbf{)}}\ \text{statement}\\\ &|\ \underline{\textbf{if}}\ \underline{\textbf{(}}\ \text{expression}\ \underline{\textbf{)}}\ \text{statement}\ \underline{\textbf{else}}\ \text{statement}\end{aligned}\)
  16. \(\text{iteration-stmt} \rightarrow \underline{\textbf{while}}\ \underline{\textbf{(}}\ \text{expression}\ \underline{\textbf{)}}\ \text{statement}\)
  17. \(\text{return-stmt} \rightarrow \underline{\textbf{return}}\ \underline{\textbf{;}}\ |\ \underline{\textbf{return}}\ \text{expression}\ \underline{\textbf{;}}\)
  18. \(\text{expression} \rightarrow \text{var}\ \underline{\textbf{=}}\ \text{expression}\ |\ \text{simple-expression}\)
  19. \(\text{var} \rightarrow \underline{\textbf{ID}}\ |\ \underline{\textbf{ID}}\ \underline{\textbf{[}}\ \text{expression} \underline{\textbf{]}}\)
  20. \(\text{simple-expression} \rightarrow \text{additive-expression}\ \text{relop}\ \text{additive-expression}\ |\ \text{additive-expression}\)
  21. \(\text{relop}\ \rightarrow \underline{\textbf{<=}}\ |\ \underline{\textbf{<}}\ |\ \underline{\textbf{>}}\ |\ \underline{\textbf{>=}}\ |\ \underline{\textbf{==}}\ |\ \underline{\textbf{!=}}\)
  22. \(\text{additive-expression} \rightarrow \text{additive-expression}\ \text{addop}\ \text{term}\ |\ \text{term}\)
  23. \(\text{addop} \rightarrow \underline{\textbf{+}}\ |\ \underline{\textbf{-}}\)
  24. \(\text{term} \rightarrow \text{term}\ \text{mulop}\ \text{factor}\ |\ \text{factor}\)
  25. \(\text{mulop} \rightarrow \underline{\textbf{*}}\ |\ \underline{\textbf{/}}\)
  26. \(\text{factor} \rightarrow \underline{\textbf{(}}\ \text{expression}\ \underline{\textbf{)}}\ |\ \text{var}\ |\ \text{call}\ |\ \text{integer}\ |\ \text{float}\)
  27. \(\text{integer} \rightarrow \underline{\textbf{INTEGER}}\)
  28. \(\text{float} \rightarrow \underline{\textbf{FLOATPOINT}}\)
  29. \(\text{call} \rightarrow \underline{\textbf{ID}}\ \underline{\textbf{(}}\ \text{args} \underline{\textbf{)}}\)
  30. \(\text{args} \rightarrow \text{arg-list}\ |\ \text{empty}\)
  31. \(\text{arg-list} \rightarrow \text{arg-list}\ \underline{\textbf{,}}\ \text{expression}\ |\ \text{expression}\)

实验内容

本部分需要同学们完成 src/parser/syntax_analyzer.y。与词法分析器相同，你只需要补全代码中规则部分即可。

如果实现正确，该语法分析器可以从 Cminusf 代码分析得到一颗语法树。例如输入

int main(void) { return 0; }

可以得到如下语法树

>--+ program
|  >--+ declaration-list
|  |  >--+ declaration
|  |  |  >--+ fun-declaration
|  |  |  |  >--+ type-specifier
|  |  |  |  |  >--* int
|  |  |  |  >--* main
|  |  |  |  >--* (
|  |  |  |  >--+ params
|  |  |  |  |  >--* void
|  |  |  |  >--* )
|  |  |  |  >--+ compound-stmt
|  |  |  |  |  >--* {
|  |  |  |  |  >--+ local-declarations
|  |  |  |  |  |  >--* epsilon
|  |  |  |  |  >--+ statement-list
|  |  |  |  |  |  >--+ statement-list
|  |  |  |  |  |  |  >--* epsilon
|  |  |  |  |  |  >--+ statement
|  |  |  |  |  |  |  >--+ return-stmt
|  |  |  |  |  |  |  |  >--* return
|  |  |  |  |  |  |  |  >--+ expression
|  |  |  |  |  |  |  |  |  >--+ simple-expression
|  |  |  |  |  |  |  |  |  |  >--+ additive-expression
|  |  |  |  |  |  |  |  |  |  |  >--+ term
|  |  |  |  |  |  |  |  |  |  |  |  >--+ factor
|  |  |  |  |  |  |  |  |  |  |  |  |  >--+ integer
|  |  |  |  |  |  |  |  |  |  |  |  |  |  >--* 0
|  |  |  |  |  |  |  |  >--* ;
|  |  |  |  |  >--* }

这一部分必须严格遵守我们给出的语法，输出必须与标准程序输出完全一致。

实验要求

仓库目录结构

与本次实验有关的文件如下。

|-- CMakeLists.txt
|-- build # 在编译过程中产生，不需要通过 git add 添加到仓库中
|-- src
|   |-- CMakeLists.txt
|   |-- common
|   `-- parser
|       |-- CMakeLists.txt
|       |-- lexer.c
|       |-- lexical_analyzer.l # 你需要修改本文件
|       |-- parser.c
|       `-- syntax_analyzer.y # 你需要修改本文件
`-- tests
     |-- 1-parser
     |   |-- input # 针对 Lab1 的测试样例
     |   |-- output_standard # 助教提供的标准参考结果
     |   |-- output_student # 测试脚本产生的你解析后的结果
     |   |-- cleanup.sh
     |   `-- eval_phase1.sh # 阶段一测试用的脚本
     |   `-- eval_phase2.sh # 阶段二测试用的脚本
     `-- testcases_general # 整个课程所用到的测试样例

编译、运行和评测

首先将你的实验仓库克隆的本地虚拟机中。要编译和运行词法分析器，请按照以下步骤在本地虚拟机中进行操作：

编译

$ cd 2024ustc-jianmu-compiler
$ mkdir build
$ cd build
# 使用 cmake 生成 makefile 等文件
$ cmake ..
# 使用 make 进行编译
$ make

这里如果 make 编译比较慢，可以 通过 -j选项开启更多的内核并行编译，会加快编译的效率。

如果不清楚自己虚拟机的内核数量，可以使用 htop指令查看，这里给出一个例子：

image-20240915145113114

如上图，助教的虚拟机拥有 20 个内核，在编译的时候可以使用 16 个内核同时编译（不建议全部使用）。

$ make -j 16

如果构建成功，你会在 build 文件夹下找到 lexer 和 parser 可执行文件，用于对 Cminusf 文件进行词法和语法分析。

$ ls lexer parser
lexer parser

$ ./lexer
usage: lexer input_file

运行

我们在 tests/testcases_general 文件夹中准备了一些通用案例。

# 返回 2024ustc-jianmu-compiler 的根目录
$ cd ${WORKSPACE}

# 运行 lexer，进行词法分析
$ ./build/lexer tests/testcases_general/1-return.cminus
Token         Text      Line    Column (Start,End)
282           void      1       (1,5)
284           main      1       (6,10)
272              (      1       (10,11)
282           void      1       (11,15)
273              )      1       (15,16)
276              {      1       (17,18)
281         return      1       (19,25)
270              ;      1       (25,26)
277              }      1       (27,28)

# 运行 parser，解析 1-return.cminus 输出语法树
$ ./build/parser ./tests/testcases_general/1-return.cminus
>--+ program
|  >--+ declaration-list
|  |  >--+ declaration
|  |  |  >--+ fun-declaration
|  |  |  |  >--+ type-specifier
|  |  |  |  |  >--* void
|  |  |  |  >--* main
|  |  |  |  >--* (
|  |  |  |  >--+ params
|  |  |  |  |  >--* void
|  |  |  |  >--* )
|  |  |  |  >--+ compound-stmt
|  |  |  |  |  >--* {
|  |  |  |  |  >--+ local-declarations
|  |  |  |  |  |  >--* epsilon
|  |  |  |  |  >--+ statement-list
|  |  |  |  |  |  >--+ statement-list
|  |  |  |  |  |  |  >--* epsilon
|  |  |  |  |  |  >--+ statement
|  |  |  |  |  |  |  >--+ return-stmt
|  |  |  |  |  |  |  |  >--* return
|  |  |  |  |  |  |  |  >--* ;
|  |  |  |  |  >--* }

测试

测试样例分为两个部分，分别是 tests/testcases_general 和 lab1 限定的 tests/1-parser。

我们重点使用 tests/1-parser 考察语法分析器的正确性。其结构如下：

.
|-- input # 输入目录，包含 xxx.cminus 文件
|   |-- easy
|   |-- hard
|   `-- normal
|-- output_standard # 助教标准输出目录，包含 xxx.syntax_tree 文件
|   |-- easy
|   |-- normal
|   |-- hard
|   `-- testcases_general
|-- output_student # 学生输出目录，测试过程中产生 xxx.syntax_tree 文件
|   |-- easy
|   |-- hard
|   |-- normal
|   `-- testcases_general
|-- eval_phase1.sh # 阶段一的测试脚本
|-- eval_phase2.sh # 阶段二的测试脚本
`-- cleanup.sh

我们使用 diff 命令进行结果比较：

$ cd 2024ustc-jianmu-compiler
$ export PATH="$(realpath ./build):$PATH"
$ cd tests/1-parser
$ parser input/normal/local-decl.cminus > output_student/normal/local-decl.syntax_tree
$ diff output_student/normal/local-decl.syntax_tree output_standard/normal/local-decl.syntax_tree
[输出为空，代表没有区别，该测试通过]

我们提供了 eval_phase1.sh 等脚本进行快速批量测试。

该脚本有两种使用方法：

  • 使用 -all参数一键测试 4 个测试集的所有样例。并会在最后给出 正确的样例个数，如下。
innerpeace@innerpeace:~/stl_debug/tests/1-parser$ ./eval_phase1.sh  -all
[info] Found 6 valid files in /home/innerpeace/stl_debug/tests/1-parser/input/easy
...
[info] Analyzing id.cminus
[info] Comparing id.cminus...
[info] id.cminus is correct!
[info] Score for /home/innerpeace/stl_debug/tests/1-parser/input/easy: 6/6
[info] Found 7 valid files in /home/innerpeace/stl_debug/tests/1-parser/input/normal
...
[info] Analyzing skip_spaces.cminus
[info] Comparing skip_spaces.cminus...
[info] skip_spaces.cminus is correct!
[info] Score for /home/innerpeace/stl_debug/tests/1-parser/input/normal: 7/7
[info] Found 6 valid files in /home/innerpeace/stl_debug/tests/1-parser/input/hard
...
[info] Analyzing You_Should_Pass.cminus
[info] Comparing You_Should_Pass.cminus...
[info] You_Should_Pass.cminus is correct!
[info] Score for /home/innerpeace/stl_debug/tests/1-parser/input/hard: 6/6
[info] Found 21 valid files in /home/innerpeace/stl_debug/tests/1-parser/../testcases_general
...
[info] Analyzing 9-assign_cast.cminus
[info] Comparing 9-assign_cast.cminus...
[info] 9-assign_cast.cminus is correct!
[info] Score for /home/innerpeace/stl_debug/tests/1-parser/../testcases_general: 21/21
[info] Total score for all testcases: 40/40

一共有 40 个测试样例。

  • 第一个参数可以是 easy、 normal、 hard 以及 testcases_general，并且有第二个可选参数，用于批量 diff 和助教提供的标准参考结果进行比较。

第二个参数为 no/yes/verbose

  • no：不进行 diff
  • yes：进行 diff
  • verbose：进行 diff，并得到更详细的输出

脚本运行后会将生成结果放在 tests/1-parser/output_student 文件夹里，而助教的参考输出则在 tests/1-parser/output_standard 中。

innerpeace@innerpeace:~/stl_debug/tests/1-parser$ ./eval_phase1.sh  easy yes
[info] Analyzing expr.cminus
[info] Comparing expr.cminus...
[info] expr.cminus is correct!
[info] Analyzing FAIL_comment2.cminus
error at line 1 column 1: syntax error
[info] Comparing FAIL_comment2.cminus...
[info] FAIL_comment2.cminus is correct!
[info] Analyzing FAIL_comment.cminus
error at line 1 column 4: syntax error
[info] Comparing FAIL_comment.cminus...
[info] FAIL_comment.cminus is correct!
[info] Analyzing FAIL_function.cminus
error at line 3 column 1: syntax error
[info] Comparing FAIL_function.cminus...
[info] FAIL_function.cminus is correct!
[info] Analyzing FAIL_id.cminus
error at line 1 column 6: syntax error
[info] Comparing FAIL_id.cminus...
[info] FAIL_id.cminus is correct!
[info] Analyzing id.cminus
[info] Comparing id.cminus...
[info] id.cminus is correct!
[info] Score for /home/innerpeace/stl_debug/tests/1-parser/input/easy: 6/6