跳转至

词法语法解析

词法分析器

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

Cminusf 词法

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

1.关键字。

else if int return void while float

2.专用符号。

+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */

3.标识符 ID 和数值，通过下列正则表达式定义：

letter = a|...|z|A|...|Z
digit = 0|...|9
ID = letter+
INTEGER = digit+
FLOAT = (digit+. | digit*.digit+)

4.注释用 /*...*/ 表示，可以超过一行。注释不能嵌套。

/*...*/

请认真阅读 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}\)

为了大家方便，我们提供了 Cminusf 语法的 pdf 文件，可在此下载：Cminusf 语法

实验内容

本部分需要同学们完成 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 2025ustc-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 文件夹中准备了一些通用案例。

# 返回 2025ustc-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 2025ustc-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

拓展阅读

注意

请在完成词法语法解析这一部分的实验后再阅读本小节！

本小节仅作为拓展部分，不计入实验分数！

介绍

在我们完成了本阶段的任务，首次使用 make 编译时，会出现以下警告。

obug@obug-VMware-Virtual-Platform:~/2025ustc-jianmu-compiler/build$ make
[  5%] [BISON][syntax] Building parser with bison 3.8.2
syntax_analyzer.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
syntax_analyzer.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples

这是因为，我们的 cminusf 语法存在一项移进/规约冲突。

进入 2025ustc-jianmu-compiler 仓库下的 src/parser 目录，运行以下命令

bison -v syntax_analyzer.y -Wcounterexamples

在终端的输出中，生成了一个移进/规约冲突的样例：

Example: IF LPARENTHESE expression RPARENTHESE IF LPARENTHESE expression RPARENTHESE statement • ELSE statement
Shift derivation
  selection-stmt
  ↳ 30: IF LPARENTHESE expression RPARENTHESE statement
                                              ↳ 25: selection-stmt
                                                    ↳ 31: IF LPARENTHESE expression RPARENTHESE statement • ELSE statement
Reduce derivation
  selection-stmt
  ↳ 31: IF LPARENTHESE expression RPARENTHESE statement                                                     ELSE statement
                                              ↳ 25: selection-stmt
                                                    ↳ 30: IF LPARENTHESE expression RPARENTHESE statement •

在这里的 IF-IF-ELSE 样例，Shift derivation 把 ELSE 与后面的 IF 匹配，Reduce derivation 把 ELSE 与前面的 IF 匹配，两种处理方式产生了冲突。

我们打开同目录下的 syntax_analyzer.output 文件，这是刚才的命令生成的。

ctrl+F 搜索 conflict，可以看到下详细信息。其中有一句是 shift/reduce conflict on token ELSE。在读到 ELSE 这个 token 时，可以选择将前面的 IF LPARENTHESE expression RPARENTHESE statement 规约成 statement，这种情况下 ELSE 就只能和第一个 IF 匹配；也可以选择继续移进 ELSE，最后在规约时，ELSE 便会与最近的 IF 即第二个 IF 匹配。

显然，第二种是正确的。

State 101

   30 selection-stmt: IF LPARENTHESE expression RPARENTHESE statement •
   31               | IF LPARENTHESE expression RPARENTHESE statement • ELSE statement

    ELSE  shift, and go to state 104

    ELSE      [reduce using rule 30 (selection-stmt)]
    $default  reduce using rule 30 (selection-stmt)

在这里，读到 ELSE 时 Bison 默认采取了移进，舍弃了规约（方括号表示被放弃的动作选项），这也就是我们的程序运行没报错的原因。

如何消除警告

对于我们的实验，这里的警告并无影响，Bison 已经智能地帮我们选择了合理的处理方式。

如果想消除这一项移进/规约冲突，这里提出一种思路：手动设置优先级。我们可以在所有的 token 后加入这两行

%nonassoc Epsilon
%nonassoc ELSE

这里引入了一个虚拟的 token，名为 Epsilon，并规定它的优先级比 ELSE 低。 之后我们可以在 selection-stmt 的前一条规则（即无 ELSE 的）最后一个 token 后面加上 %prec Epsilon，来规定这条规则的优先级是低于 ELSE 的。

在 Bison 中，当遇到移进/归约冲突时，Bison 会比较移进操作所涉及的终结符的优先级和归约操作所涉及规则的优先级。如果规则的优先级低于终结符的优先级，则选择移进；反之则选择归约。

这样，在移进 ELSE 和采用该规则规约之间，由于 ELSE 的优先级比该规则高，就会移进 ELSE。这样就消除了移进/规约冲突。

可以验证，删除 build 文件夹，重新编译，发现没有了移进/规约冲突的警告！