# lab1 实验报告

PB20111654 李晓奇

## 实验要求

完成*cminus*语言的语法分析器和词法分析器。具体任务是补全文件`lexical_analyzer.l`和`syntax_analyzer.y`。使得输入*cminus*代码后，可以经lexer转变为记号流，或者经过parser(调用lexer)分析语法是否合规。

## 实验难点

- 理解flex和bison的工作机制

- 设计合适的token简化设计

- lexer针对注释的规则撰写

## 实验设计

#### 1）文法符号的设计

因为本质是翻译文法规则，所以定义文法中出现的一系列文法符号就是核心所在。而为了flex和bison的交互，仔细设计二者共享的token就很重要。

我的整体设计是：

- 对文法符号串进行全大写

- 适当简写，如STMT统一代指STATEMENT，DEC代指DECLARATION等，这个在注释中有标注

- 终止符由下划线`_`开始

这样定义的不必要符号特别多，典型的是针对规则`relop → <= ∣ < ∣ > ∣ >= ∣ == ∣ !=`的终止符定义，在书写匹配规则的时候，发现为这条规则的每个选择都写一遍太麻烦，对比一些示例后仔细想了想，应该不会对后续的编译流程产生影响，我就将这条规则的算术运算符统一规定为：`_RELOP`。这样，对于这条规则，词法方面只要利用选择规则识别、将具体字符串拷贝、位置按长度修改即可，而语法方面只需要连接节点即可，避免了两方面都要进行的六次重复。

所有的token如下：

```
%token <node> ERROR
%type <node> TYPE_SPEC RELOP ADDOP MULOP
%type <node> DEC_LIST DEC VAR_DEC FUN_DEC LOCAL_DEC
%type <node> COM_STMT STMT_LIST STMT EXPR_STMT ITER_STMT SELC_STMT RET_STMT
%type <node> EXPR SIMPLE_EXPR VAR ADD_EXPR TERM FACTOR INTEGER FLOAT CALL
%type <node> PARAM PARAMS PARAM_LIST ARGS ARG_LIST

%token <node> _IF _ELSE _WHILE _RETURN _INT _FLOAT _VOID 
%token <node> _ASSIGN _RELOP _ADD_OP _MUL_OP
%token <node> _L_SQUARE _R_SQUARE _L_PARE _R_PARE _L_BRACKET _R_BRACKET
%token <node> _SEMI _COMMA _ID _INTEGER _FLOATPOINT

%type <node> program

%start program
```

#### 2）匹配后的动作

根据我的理解，在数据结构上，两部分程序分别完成两件事：

1. 词法分析识别出终止符，构造对应的节点(叶节点)，传递给parser

2. 语法分析根据得到的终止符进行归约，不断构造归约后的父节点，并与子节点连接直至树根

当语法分析归约到顶点即*program*时，将这个根节点置为全局变量`gt`的root值，由此语法树分析完成，可以用来进行后续分析，或者在本次实验中用来遍历打印语法树。

所以匹配后的动作：

- 词法分析：利用`pass_node()`构建并传递叶节点

- 语法分析：根据归约使用的文法，将子节点归约/连接至父节点，要注意空节点的情况。

#### 3）针对注释的正则表达式

这个容易出现匹配不到多行、贪婪匹配等问题，BUG基本都在这里。

查阅[资料](http://westes.github.io/flex/manual/Start-Conditions.html)后发现可以利用flex的start-condition解决，官方也提供了匹配多行注释相应的解决方案，稍加修改就可以拿来用了。

## 实验结果验证

就多行注释匹配做一个验证，书写`tmp.cminus`文件如下：

```c
/* 
  This is a bad comment use */
  and should fail the parser.

*/

int mian()
{
    int a = 1;   
}
```

词法分析：

```
$ ./build/lexer ./tmp.cminus
Token          Text    Line    Column (Start,End)
278             and    3    (2,5)
278          should    3    (6,12)
278            fail    3    (13,17)
278             the    3    (18,21)
278          parser    3    (22,28)
.269               *    5    (0,1)
269               /    5    (1,2)
263             int    7    (0,3)
278            mian    7    (4,8)
272               (    7    (8,9)
273               )    7    (9,10)
274               {    8    (0,1)
263             int    9    (4,7)
278               a    9    (8,9)
266               =    9    (10,11)
279               1    9    (12,13)
276               ;    9    (13,14)
275               }    10    (0,1)
```

可见只匹配了最近的回注释`*/`标记

语法分析：

```c
error at line 3 column 2: syntax error
```

在第三行报错，符合预期。

## 实验反馈

实验文档挺清晰的～