Pwn进你的心
0%

编译原理-Lab1

Posted on Edited on In 30k 27 mins.

第一个任务

任务目标：

  • 定义一个待实现编译器的语言，用上下文无关文法定义该语言
  • 写出10个该语言编写的程序样例（覆盖所有文法规则），用于后续测试
  • 给该语言起一个名称

上下文无关文法 CFG（Context Free Grammar）是一组替换规则，描述了语句是如何形成

CFG 主要作用是验证一个输入字符串 input 是否符合某个文法 G（与正则表达式比较像，但是比正则表达式功能更强大）

具体的语法细节本人没有详细地了解过，下面给出一个简化的C语言的文法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
G[program]: 
 program → ExtDefList 
 ExtDefList→ExtDef ExtDefList | ε 
 ExtDef→Specifier ExtDecList ; |Specifier FunDec CompSt 
 Specifier→int | float 
 ExtDecList→VarDec | VarDec , ExtDecList 
 VarDec→ID 
 FucDec→ID ( VarList ) | ID ( ) 
 VarList→ParamDec , VarList | ParamDec 
 ParamDec→Specifier VarDec 
 
 CompSt→{ DefList StmList } 
 StmList→Stmt StmList | ε 
 Stmt→Exp ; | CompSt | return Exp ; 
 | if ( Exp ) Stmt | if ( Exp ) Stmt else Stmt | while ( Exp ) Stmt 
 DefList→Def DefList | ε 
 Def→Specifier DecList ; 
 DecList→Dec | Dec , DecList 
 Dec→VarDec | VarDec = Exp 
 Exp →Exp =Exp | Exp && Exp | Exp || Exp | Exp < Exp | Exp <= Exp 
 | Exp == Exp | Exp != Exp | Exp > Exp | Exp >= Exp 
 | Exp + Exp | Exp - Exp | Exp * Exp | Exp / Exp | ID | INT | FLOAT 
 | ( Exp ) | - Exp | ! Exp | ID ( Args ) | ID ( ) 
 Args→Exp , Args | Exp
  • 名称为 mini-c

第二个任务

  • 构建词法、语法分析器
  • 用测试样例覆盖所有文法规则
  • 能检出10个不同的词法错误
  • 具有错误恢复功能，能检出10个不同的语法错误，并提示行号
  • 对正确的样例，输出其语法树

工具 Flex 和 Bison

Flex 是一个生成词法分析器的工具，利用 Flex，我们只需提供词法的正则表达式，就可自动生成对应的C代码

Bison 是一种通用解析器生成器，它将带注释的上下文无关文法转换为使用 LALR(1) 解析器表的确定性 LR 或广义 LR（GLR）解析器

通过联合使用 Flex 和 Bison 来构造词法、语法分析程序，大致流程如下：

词法分析

核心步骤：

  • 设计能准确表示各类单词的正则表达式
  • 用正则表达式表示的词法规则等价转化为相应的有限自动机 FA
  • 将其确定化、最小化，最后依据这个 FA 编写对应的词法分析程序

高级语言的词法分析器，需要识别的单词有五类：

  • 关键字（保留字），运算符，界符，常量，标识符

依据 mini-c 语言的定义，下面给出各单词的种类码和相应符号说明： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
INT → 整型常量
FLOAT → 浮点型常量
ID → 标识符
ASSIGNOP → = 
RELOP → > | >= | < | <= | == | != 
PLUS → + 
MINUS → - 
STAR → * 
DIV → / 
AND → && 
OR → || 
NOT → ! 
TYPE → int | float 
RETURN → return 
IF → if 
ELSE → else 
WHILE → while 
SEMI → ;
COMMA → ,
LP → (
RP → )
LC → { 
RC → }
  • 这里有关的单词种类码：INT,FLOAT,......,WHILE 每一个对应一个整数值作为其单词的种类码
  • 实现时不需要自己指定这个值，当词法分析程序生成工具 Flex 和语法分析程序生成器 Bison 联合使用时，将这些单词符号以 %token 的形式在 Bison 的文件 parser.y 中罗列出来，就可生成头文件 parser.tab.h，以枚举常量的形式给这些单词种类码进行自动编号

在编写 Flex 文件之前，需要先了解 Flex 的文件格式：

1
2
3
4
5
定义部分 
%% 
规则部分 
%% 
用户子程序部分
  • Flex 文件是文件扩展名为 .l 的文本文件
  • 定义部分：
    • 主要包含c语言的一些宏定义，如文件包含、宏名定义，以及一些变量和类型的定义和声明
  • 规则部分：
    • 由规则 正规表达式 动作 组成
    • 词法分析器一旦识别出正规表达式所对应的单词，就会执行动作所对应的操作，返回单词的种类码（常规操作：把读取到的单词以各种形式保存在联合变量 YYLVAL 中）
    • 词法分析器识别出一个单词后，会将该单词保存在 yytext 中，其长度为 yyleng
  • 用户子程序部分：
    • 这部分代码会原封不动的被复制到词法分析器源程序 lex.yy.c 中

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/* yylineno记录行号 */
%option yylineno  
    
/* 定义部分 */
%{
    #include "parser.tab.h"
    #include <string.h>
    #include "def.h"
    int yycolumn = 1;
    #define YY_USER_ACTION yylloc.first_line=yylloc.last_line=yylineno; yylloc.first_column=yycolumn; yylloc.last_column=yycolumn+yyleng-1; yycolumn+=yyleng;
    typedef union{
        int type_int;
        float type_float;
        char type_char;
        char type_id[32];
        struct node *ptr;
    }YYLVAL;
    #define YYSTYPE YYLVAL
%}

/* 匹配:不以数字开头的字符串 */
id [A-Za-z][A-Za-z0-9]* 
/* 匹配:数字 */
int [0-9]+ 
/* 匹配:带有'.'的数字 */
float ([0-9]*\.[0-9]+)|([0-9]+\.[0-9]*) 

/* 规则部分 */
%%
\/\/[^\n]*  {;} // 匹配单行注释
\/\*(\s|.)*?\*\/ {;} // 匹配多行注释
{int} {yylval.type_int=atoi(yytext); return INT;} // 执行int规则(匹配数字)
{float} {yylval.type_float=atof(yytext); return FLOAT;} // 执行float规则(匹配带有'.'的数字)
"int" {strcpy(yylval.type_id,yytext); return TYPE;} // 匹配int
"float" {strcpy(yylval.type_id,yytext); return TYPE;} // 匹配float
"char" {strcpy(yylval.type_id,yytext); return TYPE;} // 匹配char
"return" {return RETURN;}
"if" {return IF;}
"else" {return ELSE;}
"while" {return WHILE;}
"for" {return FOR;}
{id} {strcpy(yylval.type_id,yytext); return ID;} // 执行id规则(匹配不以数字开头的字符串)

";" {return SEMI;}
"," {return COMMA;}
">"|"<"|">="|"<="|"=="|"!=" {strcpy(yylval.type_id,yytext); return RELOP;}
"=" {return ASSIGNOP;}
"+" {return PLUS;}
"-" {return MINUS;}
"+=" {return COMADD;}
"-=" {return COMSUB;}
"++" {return AUTOADD;}
"--" {return AUTOSUB;}
"*" {return STAR;}
"/" {return DIV;}
"&&" {return AND;}
"||" {return OR;}
"!" {return NOT;}
"(" {return LP;}
")" {return RP;}
"[" {return LB;}
"]" {return RB;}
"{" {return LC;}
"}" {return RC;}
[\n] {yycolumn=1;}
[ \r\t] {;}
.   {printf("Error type A: Mysterious character\"%s\" at line %d,column %d\n",yytext,yylineno,yycolumn);}
%%
    
/* 用户子程序部分 */
int yywrap(){
    return 1;
}

语法分析

语法分析采用生成器自动化生成工具 GNU Bison（前身是 YACC），该工具采用了 LALR(1) 的自底向上的分析技术，完成语法分析

在编写 Bison 文件之前，需要先了解 Bison 的文件格式：

1
2
3
4
5
6
7
8
%{ 
声明部分
%} 
辅助定义部分 
%% 
规则部分 
%% 
用户函数部分

  • Bison 文件是文件扩展名为 .y 的文本文件

  • 声明部分：

    • 包含语法分析中需要的头文件包含，宏定义和全局变量的定义等，这部分会直接被复制到语法分析的C语言源程序中

  • 辅助定义部分：

    • 语义值的类型定义
    • 非终结符的属性值类型说明（非终结符：不是终结符的都是非终结符）
    • 终结符语义值类型定义（终结符：不能单独出现在推导式左边的符号）
    • 优先级与结合性定义

  • 规则部分：

    • 采用 LR 分析法，需要在每条规则后给出相应的语义动作，例如：

      • 规则：Exp → Exp = Exp

      • 语义动作：Exp: Exp ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno); }

  • 用户子程序部分：

    • 这部分代码会原封不动的被复制到词法分析器源程序 lex.yy.c 中

语法分析的过程比较复杂，先看一个案例：

calc.l：Flex 文件

1
2
3
4
5
6
7
8
9
10
11
12
13
%{
#include "calc.tab.h"
%}

%%
[0-9]+          { yylval = atoi(yytext); return T_NUM; }
[-/+*()\n]      { return yytext[0]; }
.               { return 0; /* end when meet everything else */ }
%%

int yywrap(void) { 
    return 1;
}
  • 使用正则匹配数字，将目标数字存储于 yylval 中并返回 T_NUM
  • 使用正则匹配符号，并返回该符号（yytext[0]）

calc.y：Bison 文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
%{
#include <stdio.h>
void yyerror(const char* msg) {}
%}

%token T_NUM

%left '+' '-'
%left '*' '/'

%%

S   :   S E '\n'        { printf("ans = %d\n", $2); }
    |   /* empty */     { /* empty */ }
    ;

E   :   E '+' E         { $$ = $1 + $3; }
    |   E '-' E         { $$ = $1 - $3; }
    |   E '*' E         { $$ = $1 * $3; }
    |   E '/' E         { $$ = $1 / $3; }
    |   T_NUM           { $$ = $1; }
    |   '(' E ')'       { $$ = $2; }
    ;

%%

int main() {
    return yyparse();
}
  • 规则后面 {} 中的是当完成归约时要执行的语义动作
  • 规则左部的E的属性值用$$表示，右部有2个E，其属性值分别用$1和$3表示
    • 例如：A : B '+' C {$$ = $1 + $3;}
    • $$ 代指 A
    • $1 代指 B
    • $2 代指 +
    • $3 代指 C

效果如下：

1
2
3
bison -d -v calc.y
flex calc.l
gcc -o calc calc.tab.c lex.yy.c
1
2
3
4
5
6
7
8
9
➜  demo ./calc
1+2+3
ans = 6
5+5
ans = 10
4+5*4 
ans = 24
(4+5)*4 
ans = 36

Bison 的规则部分非常复杂，总计为以下条目指定了规则：

ExtDefList-外部定义列表：即是整个语法树 

1
2
3
ExtDefList: {$$=NULL;}
            | ExtDef ExtDefList {$$=mknode(EXT_DEF_LIST,$1,$2,NULL,yylineno);} 
            ;
  • mknode：生成一个非叶子树结点（第1个参数代表节点的类型，第2-4个参数代表该节点的子树，第5个参数代表行号）
  • 对于每个 EXTDEFLIST 有2种可能：
    • 外部定义列表为 NULL
    • 外部定义列表不为 NULL，则创建 EXT_DEF_LIST 结点
  • 对于每个 EXT_DEF_LIST 节点有2个子树：
    • 第1个子树对应声明 ExtDef（声明变量，声明数组，声明函数）
    • 第2个子树对应它自身 ExtDefList
    • 代表多个声明 ExtDef（A : B A {...} 这种写法代表存在多个 B）

ExtDef-声明：声明变量，声明数组，声明函数

1
2
3
4
5
ExtDef: Specifier ExtDecList SEMI {$$=mknode(EXT_VAR_DEF,$1,$2,NULL,yylineno);}
        | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);} 
        | Specifier FuncDec CompSt {$$=mknode(FUNC_DEF,$1,$2,$3,yylineno);} 
        | error SEMI {$$=NULL; printf("---缺少分号---\n");}
        ;
  • 对于每个 ExtDef 有4种可能：
    • 对应外部变量声明，生成 EXT_VAR_DEF 节点
    • 对应数组声明，生成 ARRAY_DEF 节点
    • 对应函数声明，生成 FUNC_DEF 节点
    • 对应报错
  • EXT_VAR_DEF，ARRAY_DEF，FUNC_DEF 节点的信息如上

Specifier-类型：表示一个类型 (int,float)

1
2
Specifier: TYPE {$$=mknode(TYPE,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);$$->type=(!strcmp($1,"int")?INT:(!strcmp($1,"float")?FLOAT:CHAR));}
           ;
  • 对于每个 Specifier 有1种可能：
    • 对应类型，生成 TYPE 节点
  • TYPE 节点无子树

ExtDecList-变量名称列表：由一个或多个变量组成，多个变量之间用逗号隔开

1
2
3
ExtDecList: VarDec {$$=$1;} 
            | VarDec COMMA ExtDecList {$$=mknode(EXT_DEC_LIST,$1,$3,NULL,yylineno);}
            ;
  • 对于每个 EXT_DECLIST 有2种可能：
    • 只有一个变量，则直接赋值 VarDec 变量
    • 有多个变量，则生成 EXT_DEC_LIST 节点
  • 对于每个 EXT_DEC_LIST 结点有2个子树：
    • 第1个子树对应变量 VarDec
    • 第2个子树对应它自身 ExtDecList
    • 代表多个变量 VarDec

VarDec-变量名称：由一个 ID 组成

1
2
VarDec: ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // ID结点,标识符符号串存放结点的type_id
        ;
  • 对于每个 VarDec 有1种可能：
    • 由一个 ID 组成，则生成 ID 节点
  • ID 节点无子树

FuncDec-函数声明：包括函数名和参数定义

1
2
3
4
FuncDec: ID LP VarList RP {$$=mknode(FUNC_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数名存放在$$->type_id
         | ID LP RP {$$=mknode(FUNC_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数名存放在$$->type_id
         | error RP {$$=NULL; printf("---函数左括号右括号不匹配---\n");}
         ;
  • 函数名 ID 存放在 $$->type_id
  • 对于每个 FuncDec 有3种可能：
    • 对应一个带参数的函数，则生成 FUNC_DEC 节点（带参）
    • 对应一个不带参数的函数，则生成 FUNC_DEC 节点（不带参）
    • 对应报错
  • 对于每个 FUNC_DEC 结点有1个子树或者无子树：
    • 第1个子树对应参数定义列表 VarDec

ArrayDec-数组声明

1
2
3
ArrayDec: ID LB Exp RB {$$=mknode(ARRAY_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
          | ID LB RB {$$=mknode(ARRAY_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
          | error RB {$$=NULL;printf("---数组定义错误---\n");}
  • 对于每个 ArrayDec 有3种可能：
    • 对应静态数组，则生成 ARRAY_DEC 节点（带有表达式 Exp）
    • 对应动态数组，则生成 ARRAY_DEC 节点
    • 对应报错
  • 对于每个 ARRAY_DEC 结点有1个子树或者无子树：
    • 第1个子树对应表达式 Exp

VarList-参数定义列表：由一个到多个参数定义组成，用逗号隔开

1
2
3
VarList: ParamDec {$$=mknode(PARAM_LIST,$1,NULL,NULL,yylineno);}
         | ParamDec COMMA VarList {$$=mknode(PARAM_LIST,$1,$3,NULL,yylineno);}
         ;
  • 对于每个 VarList 有2种可能：
    • 对应一个参数 ParamDec，则生成 PARAM_LIST 节点
    • 对应用逗号隔开的多个参数 ParamDec，则生成 PARAM_LIST 节点
  • 对于每个 PARAM_LIST 结点有1个或2个子树：
    • 第1个子树对应参数定义 ParamDec
    • 第2个子树对应它自身 PARAM_LIST

ParamDec-参数定义：固定由一个类型和一个变量组成

1
2
ParamDec: Specifier VarDec {$$=mknode(PARAM_DEC,$1,$2,NULL,yylineno);}
          ;
  • 对于每个 ParamDec 有1种可能：
    • 对应一个类型 Specifier 和一个变量 VarDec，则生成 PARAM_DEC 节点
  • 对于每个 PARAM_DEC 节点有2个子树：
    • 第1个子树对应类型 Specifier
    • 第2个子树对应一个变量 VarDec

CompSt-复合语句：左右分别用大括号括起来，中间有定义列表和语句列表

1
2
3
CompSt: LC DefList StmList RC {$$=mknode(COMP_STM,$2,$3,NULL,yylineno);}
        | error RC {$$=NULL; printf("---复合语句内存在错误---\n");}
        ;
  • 对于每个 CompSt 有2种可能：
    • 对应一个由 {} 包裹起来的子语句，则生成 COMP_STM 节点
    • 对应报错
  • 对于每个 COMP_STM 节点有2个子树：
    • 第1个子树对应定义列表 DefList
    • 第2个子树对应语句列表 StmList

StmList-语句列表：由“0”个或多个语句 Stmt 组成

1
2
3
StmList: {$$=NULL;}
         | Stmt StmList {$$=mknode(STM_LIST,$1,$2,NULL,yylineno);}
         ;
  • 对于每个 StmList 有2种可能：
    • 对应 NULL
    • 对应多个语句 Stmt，则生成 STM_LIST 节点
  • 对于每个 STM_LIST 节点有2个子树：
    • 第1个子树对应语句 Stmt
    • 第2个子树对应它自身 StmList

Stmt-语句：可能为表达式，复合语句，return 语句，if 语句，if-else 语句，while 语句，for 语句

1
2
3
4
5
6
7
8
Stmt: Exp SEMI {$$=mknode(EXP_STMT,$1,NULL,NULL,yylineno);}
      | CompSt {$$=$1;} // 复合语句结点直接最为语句结点,不再生成新的结点
      | RETURN Exp SEMI {$$=mknode(RETURN,$2,NULL,NULL,yylineno);}
      | IF LP Exp RP Stmt %prec LOWER_THEN_ELSE {$$=mknode(IF_THEN,$3,$5,NULL,yylineno);}
      | IF LP Exp RP Stmt ELSE Stmt {$$=mknode(IF_THEN_ELSE,$3,$5,$7,yylineno);}
      | WHILE LP Exp RP Stmt {$$=mknode(WHILE,$3,$5,NULL,yylineno);}
      | FOR LP Exp RP Stmt {$$=mknode(FOR,$3,$5,NULL,yylineno);}
      ;
  • 对于每个 Stmt 有7种可能：
    • 对应基础表达式 Exp，则生成节点 EXP_STMT
    • 对应符合语句 CompSt
    • 对应 RETURN Exp，则生成节点 RETURN
    • 对应 IF ELSE-IF 语句，则生成节点 IF_THEN
    • 对应 IF ELSE 语句，则生成节点 IF_THEN_ELSE
    • 对应 WHILE 语句，则生成节点 WHILE
    • 对应 FOR 语句，则生成节点 FOR

DefList-定义列表：由“0”个或多个定义语句组成

1
2
3
DefList: {$$=NULL; }
         | Def DefList {$$=mknode(DEF_LIST,$1,$2,NULL,yylineno);}
         ;
  • 对于每个 DefList 有2种可能：
    • 对应 NULL
    • 对应多个定义 Def，则生成 DEF_LIST 节点

Def-定义：定义一个或多个定义语句，由分号隔开

1
2
3
Def: Specifier DecList SEMI {$$=mknode(VAR_DEF,$1,$2,NULL,yylineno);}
     | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);}
     ;
  • 对于每个 Def 有2种可能：
    • 对应变量的定义，则生成 VAR_DEF 节点
    • 对应数组的定义，则生成 ARRAY_DEF 节点

DecList-语句列表：由一个或多个语句组成，由逗号隔开，最终都成一个表达式

1
2
3
DecList: Dec {$$=mknode(DEC_LIST,$1,NULL,NULL,yylineno);}
         | Dec COMMA DecList {$$=mknode(DEC_LIST,$1,$3,NULL,yylineno);}
         ;
  • 对于每个 DecList 有2种可能：
    • 对应一个语句 Dec，则生成 DEC_LIST 节点
    • 对应用逗号隔开的多个 Dec，则生成 DEC_LIST 节点

Dec-语句：一个变量名称或者一个赋值语句（变量名称等于一个表达式）

1
2
3
Dec: VarDec {$$=$1;}
     | VarDec ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");}
     ;
  • 对于每个 Dec 有2种可能：
    • 对应一个变量名称 VarDec
    • 对应一个赋值语句，则生成 ASSIGNOP 节点

Exp-表达式：代表数字或是数字之间的运算，和函数调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Exp: Exp ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");} // $$结点type_id空置未用,正好存放运算符
     | Exp AND Exp {$$=mknode(AND,$1,$3,NULL,yylineno);strcpy($$->type_id,"AND");}
     | Exp OR Exp {$$=mknode(OR,$1,$3,NULL,yylineno);strcpy($$->type_id,"OR");}
     | Exp RELOP Exp {$$=mknode(RELOP,$1,$3,NULL,yylineno);strcpy($$->type_id,$2);} // 词法分析关系运算符号自身值保存在$2中
     | Exp PLUS Exp {$$=mknode(PLUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"PLUS");}
     | Exp MINUS Exp {$$=mknode(MINUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"MINUS");}
     | Exp STAR Exp {$$=mknode(STAR,$1,$3,NULL,yylineno);strcpy($$->type_id,"STAR");}
     | Exp DIV Exp {$$=mknode(DIV,$1,$3,NULL,yylineno);strcpy($$->type_id,"DIV");}
     | Exp COMADD Exp {$$=mknode(COMADD,$1,$3,NULL,yylineno);strcpy($$->type_id,"COMADD");}
     | Exp COMSUB Exp {$$=mknode(COMSUB,$1,$3,NULL,yylineno);strcpy($$->type_id,"COMSUB");}
     | LP Exp RP {$$=$2;} /* 遇到左右括号,可直接忽略括号,Exp的值就为括号里面的Exp */
     | MINUS Exp %prec UMINUS {$$=mknode(UMINUS,$2,NULL,NULL,yylineno);strcpy($$->type_id,"UMINUS");}
     | NOT Exp {$$=mknode(NOT,$2,NULL,NULL,yylineno);strcpy($$->type_id,"NOT");}
     | AUTOADD Exp {$$=mknode(AUTOADD_L,$2,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOADD");}
     | AUTOSUB Exp {$$=mknode(AUTOSUB_L,$2,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOSUB");}
     | Exp AUTOADD {$$=mknode(AUTOADD_R,$1,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOADD");}
     | Exp AUTOSUB {$$=mknode(AUTOSUB_R,$1,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOSUB");}
     | ID LP Args RP {$$=mknode(FUNC_CALL,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数调用后面的括号部分,只需要把括号里面的内容传入即可
     | ID LP RP {$$=mknode(FUNC_CALL,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数调用后面的括号部分没有参数
     | ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
     | INT {$$=mknode(INT,NULL,NULL,NULL,yylineno);$$->type_int=$1;$$->type=INT;}
     | FLOAT {$$=mknode(FLOAT,NULL,NULL,NULL,yylineno);$$->type_float=$1;$$->type=FLOAT;}
     | CHAR {$$=mknode(CHAR,NULL,NULL,NULL,yylineno); $$->type_char=$1;$$->type=CHAR;}
     ;
  • 对于每个 Exp 有23种可能：
    • 前10种可能分别对应：等于 ASSIGNOP，和 AND，或 OR，二元运算符 RELOP，加 PLUS，减 MINUS，乘 STAR，除 DIV，加等于 COMADD，减等于 COMSUB，都会生成对应的节点
    • 第11种可能分别对应：左右括号
    • 第12,13种可能分别对应：负操作和非操作，分别生成 UMINUS 和 NOT 节点
    • 第14-17种可能分别对应：加加 AUTOADD 和减减 AUTOSUB 的左右操作，分别生成4种类型的节点
    • 第18,19种可能对应：函数的有参调用和无参调用，都生成 FUNC_CALL 节点
    • 最后4种可能对应：ID，INT，FLOAT，CHAR

Args-用逗号隔开的参数（和参数定义 ParamDec 不同）

1
2
3
Args: Exp COMMA Args {$$=mknode(ARGS,$1,$3,NULL,yylineno);}
      | Exp {$$=mknode(ARGS,$1,NULL,NULL,yylineno);}
      ;
  • 参数 Args 只在函数调用时使用
  • 对于每个 Args 有2种可能：
    • 对应用逗号隔开的多个 Exp
    • 对应一个 Exp

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
%define parse.error verbose // 指示bison生成详细的错误消息
%locations // 记录行号
    
/* 声明部分 */
%{
#include "stdio.h"
#include "math.h"
#include "string.h"
#include "def.h"
extern int yylineno;
extern char *yytext;
extern FILE *yyin;
void yyerror(const char* fmt, ...);
void display(struct node *,int);
%}

/* 辅助声明部分 */
/* Bison中默认将所有的语义值都定义为int类型,可以通过定义宏YYSTYPE来改变值的类型
如果有多个值类型,则需要通过在Bison声明中使用%union列举出所有的类型 */
%union {
  int type_int;
  float type_float;
  char type_char;
  char type_id[32];
  struct node *ptr;
};

/* %type 定义非终结符的语义值类型: %type <union 的成员名> 非终结符 */
/* %type <ptr> program ExtDefList:表示非终结符ExtDefList属性值的类型对应联合中成员ptr的类型,在本实验中对应一个树结点的指针 */
%type <ptr> program ExtDefList ExtDef Specifier ExtDecList FuncDec ArrayDec CompSt VarList VarDec ParamDec Stmt StmList DefList Def DecList Dec Exp Args

/* %token 定义终结符的语义值类型: %token <union 的成员名> 终结符  */
/* %token <type_id> ID:表示识别出来一个ID标识符后,标识符的字符串值保存在成员type_id */
%token <type_int> INT // 指定INT的语义值是type_int,由词法分析得到的数值
%token <type_id> ID RELOP TYPE // 指定ID,RELOP的语义值是type_id,由词法分析得到标识符字符串
%token <type_float> FLOAT // 指定ID的语义值是type_float,由词法分析得到的数值
%token <type_char> CHAR // 指定ID的语义值是type_char,由词法分析得到的数值
%token LP RP LC RC LB RB SEMI COMMA
%token PLUS MINUS STAR DIV COMADD COMSUB ASSIGNOP AND OR NOT IF ELSE WHILE FOR RETURN
    
/* 优先级 */
%left COMADD COMSUB /* %left:表示左结合,前面符号的优先级低 */
%left ASSIGNOP
%left OR
%left AND
%left RELOP
%left PLUS MINUS
%left STAR DIV
%right UMINUS NOT AUTOADD AUTOSUB /* %right:定义一个优先级更高的单目,符号UMINUS */
%nonassoc LOWER_THEN_ELSE /* %nonassoc:没有结合性一般与%prec结合使用,表示该操作有同样的优先级 */
%nonassoc ELSE

/* 规则部分 */
%%
program: ExtDefList { display($1,0);} /* 归约到program,显示语法树(display是自己实现的,用于可视化AST的函数) */
         ;
/* ExtDefList-外部定义列表:即是整个语法树 */
ExtDefList: {$$=NULL;} // 整个语法树为空 
            | ExtDef ExtDefList {$$=mknode(EXT_DEF_LIST,$1,$2,NULL,yylineno);} // 每一个EXTDEFLIST的结点,其第1棵子树对应一个外部变量声明或函数
            ;
/* ExtDef-外部声明:声明外部变量或者声明函数 */
ExtDef: Specifier ExtDecList SEMI {$$=mknode(EXT_VAR_DEF,$1,$2,NULL,yylineno);} // 该结点对应一个外部变量声明
        | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);} // 数组定义
        | Specifier FuncDec CompSt {$$=mknode(FUNC_DEF,$1,$2,$3,yylineno);} // 该结点对应一个函数定义,类型+函数声明+复合语句
        | error SEMI {$$=NULL; printf("---缺少分号---\n");}
        ;
/* Specifier-类型:表示一个类型(int,float) */
Specifier: TYPE {$$=mknode(TYPE,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);$$->type=(!strcmp($1,"int")?INT:(!strcmp($1,"float")?FLOAT:CHAR));}
           ;
/* ExtDecList-变量名称列表:由一个或多个变量组成,多个变量之间用逗号隔开 */
ExtDecList: VarDec {$$=$1;} // 每一个EXT_DECLIST的结点,其第一棵子树对应一个变量名(ID类型的结点),第二棵子树对应剩下的外部变量名
            | VarDec COMMA ExtDecList {$$=mknode(EXT_DEC_LIST,$1,$3,NULL,yylineno);}
            ;
/* VarDec-变量名称:由一个ID组成 */
VarDec: ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // ID结点,标识符符号串存放结点的type_id
        ;
/* FuncDec-函数声明:包括函数名和参数定义 */
FuncDec: ID LP VarList RP {$$=mknode(FUNC_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数名存放在$$->type_id
         | ID LP RP {$$=mknode(FUNC_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数名存放在$$->type_id
         | error RP {$$=NULL; printf("---函数左括号右括号不匹配---\n");}
         ;
/* ArrayDec-数组声明 */
ArrayDec: ID LB Exp RB {$$=mknode(ARRAY_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
          | ID LB RB {$$=mknode(ARRAY_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
          | error RB {$$=NULL;printf("---数组定义错误---\n");}
/* VarList-参数定义列表:由一个到多个参数定义组成,用逗号隔开 */
VarList: ParamDec {$$=mknode(PARAM_LIST,$1,NULL,NULL,yylineno);}
         | ParamDec COMMA VarList {$$=mknode(PARAM_LIST,$1,$3,NULL,yylineno);}
         ;
/* ParamDec-参数定义:固定由一个类型和一个变量组成 */
ParamDec: Specifier VarDec {$$=mknode(PARAM_DEC,$1,$2,NULL,yylineno);}
          ;
/* CompSt-复合语句:左右分别用大括号括起来,中间有定义列表和语句列表 */
CompSt: LC DefList StmList RC {$$=mknode(COMP_STM,$2,$3,NULL,yylineno);}
        | error RC {$$=NULL; printf("---复合语句内存在错误---\n");}
        ;
/* StmList-语句列表:由0个或多个语句stmt组成 */
StmList: {$$=NULL;}
         | Stmt StmList {$$=mknode(STM_LIST,$1,$2,NULL,yylineno);}
         ;
/* Stmt-语句:可能为表达式,复合语句,return语句,if语句,if-else语句,while语句,for语句 */
Stmt: Exp SEMI {$$=mknode(EXP_STMT,$1,NULL,NULL,yylineno);}
      | CompSt {$$=$1;} // 复合语句结点直接最为语句结点,不再生成新的结点
      | RETURN Exp SEMI {$$=mknode(RETURN,$2,NULL,NULL,yylineno);}
      | IF LP Exp RP Stmt %prec LOWER_THEN_ELSE {$$=mknode(IF_THEN,$3,$5,NULL,yylineno);}
      | IF LP Exp RP Stmt ELSE Stmt {$$=mknode(IF_THEN_ELSE,$3,$5,$7,yylineno);}
      | WHILE LP Exp RP Stmt {$$=mknode(WHILE,$3,$5,NULL,yylineno);}
      | FOR LP Exp RP Stmt {$$=mknode(FOR,$3,$5,NULL,yylineno);}
      ;
/* DefList-定义列表:由0个或多个定义语句组成 */
DefList: {$$=NULL; }
         | Def DefList {$$=mknode(DEF_LIST,$1,$2,NULL,yylineno);}
         ;
/* Def-定义:定义一个或多个语句语句,由分号隔开 */
Def: Specifier DecList SEMI {$$=mknode(VAR_DEF,$1,$2,NULL,yylineno);}
     | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);}
     ;
/* DecList-语句列表:由一个或多个语句组成,由逗号隔开,最终都成一个表达式 */
DecList: Dec {$$=mknode(DEC_LIST,$1,NULL,NULL,yylineno);}
         | Dec COMMA DecList {$$=mknode(DEC_LIST,$1,$3,NULL,yylineno);}
         ;
/* Dec-语句:一个变量名称或者一个赋值语句(变量名称等于一个表达式) */
Dec: VarDec {$$=$1;}
     | VarDec ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");}
     ;
/* Exp-表达式 */
Exp: Exp ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");} // $$结点type_id空置未用,正好存放运算符
     | Exp AND Exp {$$=mknode(AND,$1,$3,NULL,yylineno);strcpy($$->type_id,"AND");}
     | Exp OR Exp {$$=mknode(OR,$1,$3,NULL,yylineno);strcpy($$->type_id,"OR");}
     | Exp RELOP Exp {$$=mknode(RELOP,$1,$3,NULL,yylineno);strcpy($$->type_id,$2);} // 词法分析关系运算符号自身值保存在$2中
     | Exp PLUS Exp {$$=mknode(PLUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"PLUS");}
     | Exp MINUS Exp {$$=mknode(MINUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"MINUS");}
     | Exp STAR Exp {$$=mknode(STAR,$1,$3,NULL,yylineno);strcpy($$->type_id,"STAR");}
     | Exp DIV Exp {$$=mknode(DIV,$1,$3,NULL,yylineno);strcpy($$->type_id,"DIV");}
     | Exp COMADD Exp {$$=mknode(COMADD,$1,$3,NULL,yylineno);strcpy($$->type_id,"COMADD");}
     | Exp COMSUB Exp {$$=mknode(COMSUB,$1,$3,NULL,yylineno);strcpy($$->type_id,"COMSUB");}
     | LP Exp RP {$$=$2;} /* 遇到左右括号,可直接忽略括号,Exp的值就为括号里面的Exp */
     | MINUS Exp %prec UMINUS {$$=mknode(UMINUS,$2,NULL,NULL,yylineno);strcpy($$->type_id,"UMINUS");}
     | NOT Exp {$$=mknode(NOT,$2,NULL,NULL,yylineno);strcpy($$->type_id,"NOT");}
     | AUTOADD Exp {$$=mknode(AUTOADD_L,$2,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOADD");}
     | AUTOSUB Exp {$$=mknode(AUTOSUB_L,$2,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOSUB");}
     | Exp AUTOADD {$$=mknode(AUTOADD_R,$1,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOADD");}
     | Exp AUTOSUB {$$=mknode(AUTOSUB_R,$1,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOSUB");}
     | ID LP Args RP {$$=mknode(FUNC_CALL,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数定义后面的括号部分,只需要把括号里面的内容传入即可
     | ID LP RP {$$=mknode(FUNC_CALL,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数定义后面的括号部分没有参数
     | ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
     | INT {$$=mknode(INT,NULL,NULL,NULL,yylineno);$$->type_int=$1;$$->type=INT;}
     | FLOAT {$$=mknode(FLOAT,NULL,NULL,NULL,yylineno);$$->type_float=$1;$$->type=FLOAT;}
     | CHAR {$$=mknode(CHAR,NULL,NULL,NULL,yylineno); $$->type_char=$1;$$->type=CHAR;}
     ;
/* Args-用逗号隔开的参数 */
Args: Exp COMMA Args {$$=mknode(ARGS,$1,$3,NULL,yylineno);}
      | Exp {$$=mknode(ARGS,$1,NULL,NULL,yylineno);}
      ;

%%
int main(int argc, char *argv[]){
  yyin=fopen(argv[1],"r");
  if (!yyin) 
    return 0;
  yylineno=1;
  yyparse();
  return 0;
}

#include<stdarg.h>
void yyerror(const char* fmt, ...)
{
  va_list ap;
  va_start(ap, fmt);
  fprintf(stderr, "Grammar Error at Line %d Column %d: ", yylloc.first_line,yylloc.first_column);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, ".\n");
}

生成抽象语法树

AST 不同于推导树，去掉了一些修饰性的单词部分，简明地把程序的语法结构表示出来，后续的语义分析、中间代码生成都可以通过遍历抽象语法树来完成

其实在语法分析的过程中，已经调用了可视化抽象语法树的函数 display：

1
program: ExtDefList { display($1,0);} /* 归约到program,显示语法树(display是自己实现的,用于可视化AST的函数) */

它的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
void display(struct node* T,int indent){
    if(T){
        switch (T->kind){
            case EXT_DEF_LIST:  
                display(T->ptr[0],indent);
                display(T->ptr[1],indent);
                break;
            case EXT_VAR_DEF:
                printf("%*c%s\n",indent,' ',"外部变量定义：");     
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent+5,' ',"变量名：");
                display(T->ptr[1],indent+5);
                break;
            case FUNC_DEF:
                printf("%*c%s\n",indent,' ',"函数定义：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                display(T->ptr[2],indent+5);
                break;
            case ARRAY_DEF:
                printf("%*c%s\n",indent,' ',"数组定义：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case FUNC_DEC:
                printf("%*c%s%s\n",indent,' ',"函数名：",T->type_id);
                printf("%*c%s\n",indent,' ',"函数型参：");
                display(T->ptr[0],indent+5);
                break;
            case ARRAY_DEC:
                printf("%*c%s%s\n",indent,' ',"数组名：",T->type_id);
                printf("%*c%s\n",indent,' ',"数组大小：");
                display(T->ptr[0],indent+5);
                break;
            case EXT_DEC_LIST:
                display(T->ptr[0],indent+5);
                if(T->ptr[1]->ptr[0]==NULL)
                    display(T->ptr[1],indent+5);
                else
                    display(T->ptr[1],indent);
                break;
            case PARAM_LIST:
                display(T->ptr[0],indent);
                display(T->ptr[1],indent);
                break;
            case PARAM_DEC:
                display(T->ptr[0],indent);
                display(T->ptr[1],indent);
                break;
            case VAR_DEF:
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case DEC_LIST:
                printf("%*c%s\n",indent,' ',"变量名：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent);
                break;
            case DEF_LIST:
                printf("%*c%s\n",indent+5,' ',"LOCAL VAR_NAME：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent);
                break;
            case COMP_STM:
                printf("%*c%s\n",indent,' ',"复合语句：");
                printf("%*c%s\n",indent+5,' ',"复合语句的变量定义：");
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent+5,' ',"复合语句的语句部分：");
                display(T->ptr[1],indent+5);
                break;
            case STM_LIST:
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent);
                break;
            case EXP_STMT:
                printf("%*c%s\n",indent,' ',"表达式语句：");
                display(T->ptr[0],indent+5);
                break;
            case IF_THEN:
                printf("%*c%s\n",indent,' ',"条件语句（if-else）：");
                printf("%*c%s\n",indent,' ',"条件：");
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent,' ',"IF语句：");
                display(T->ptr[1],indent+5);
                break;
            case IF_THEN_ELSE:
                printf("%*c%s\n",indent,' ',"条件语句（if-else-if）：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case WHILE:
                printf("%*c%s\n",indent,' ',"循环语句（while）：");
                printf("%*c%s\n",indent+5,' ',"循环条件：");
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent+5,' ',"循环体：");
                display(T->ptr[1],indent+5);
                break;
            case FOR:
                printf("%*c%s\n",indent,' ',"循环语句（for）：");
                printf("%*c%s\n",indent+5,' ',"循环条件：");
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent+5,' ',"循环体：");
                display(T->ptr[1],indent+5);
                break;
            case FUNC_CALL:
                printf("%*c%s\n",indent,' ',"函数调用：");
                printf("%*c%s%s\n",indent+5,' ',"函数名：",T->type_id);
                printf("%*c%s\n",indent+5,' ',"第一个实际参数表达式：");
                display(T->ptr[0],indent+5);
                break;
            case ARGS:
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case ID:
                printf("%*cID： %s\n",indent,' ',T->type_id); // 控制新的一行输出的空格数,indent代替%*c中*
                break;
            case INT:
                printf("%*cINT： %d\n",indent,' ',T->type_int);  
                break;
            case FLOAT:
                printf("%*cFLOAT： %f\n",indent,' ',T->type_float);  
                break;
            case CHAR:
                printf("%*cCHAR： %c\n",indent,' ',T->type_char);
            case ARRAY:
                printf("%*c数组名称： %s\n",indent,' ',T->type_id);  
                break;
            case TYPE:
                if(T->type==INT)
                    printf("%*c%s\n",indent,' ',"类型：int");
                else if(T->type==FLOAT)
                    printf("%*c%s\n",indent,' ',"类型：float");
                else if(T->type==CHAR)
                    printf("%*c%s\n",indent,' ',"类型：char");
                else if(T->type==ARRAY)
                    printf("%*c%s\n",indent,' ',"类型：char型数组");
                break;
            case ASSIGNOP:
            case OR:
            case AUTOADD_L:
            case AUTOSUB_L:
            case AUTOADD_R:
            case AUTOSUB_R:
            case AND:
            case RELOP:
            case PLUS:
            case MINUS:
            case STAR:
            case DIV:
            case COMADD:
            case COMSUB:
                printf("%*c%s\n",indent,' ',T->type_id);
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case RETURN:
                printf("%*c%s\n",indent,' ',"返回语句：");
                display(T->ptr[0],indent+5);
                break;  
        }
    }
}
  • 其实就是根据不同的节点来进行不同的操作

在语法分析中使用的，用于创建新节点的函数 mknode 的实现如下：

1
2
3
4
5
6
7
8
9
struct node *mknode(int kind,struct node *first,struct node *second, struct node *third,int pos ){
  struct node *tempnode = (struct node*)malloc(sizeof(struct node));
  tempnode->kind = kind;
  tempnode->ptr[0] = first;
  tempnode->ptr[1] = second;
  tempnode->ptr[2] = third;
  tempnode->pos = pos;
  return tempnode;
}

编译与结果

编译命令：

1
2
3
flex lexer.l # 生成lexer.yy.c
bison -d -v parser.y # 生成parser.tab.h, parser.tab.c 
gcc display.c parser.tab.c lex.yy.c -lfl -o test1

测试文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int a,b,c;//可改错误1：缺少分号
float m,n;
char c1,c2;//增加char类型
char a[10];//增加数组的定义
int fibo(int a)
{/*注释部分自动去掉*/
	int i;
	if(a == 1 || a == 2){
	  return 1;
        }
	for(i<15){//增加了for语句循环
          i++;
	}
	return fibo(a-1)+fibo(a-2);
}
int main()//注释部分自动去掉
{
	int m,n,i;
	char c;
	float ar[20];
	m=read();
	i=1;
	i++;
	--i;//加了自增和自减
	m+=i+15;//加了复合赋值运算
	while(i <= m){
		n=fibo(i);
		write(n);
		i=i+1;
	}
	return 1;
}

最终结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
➜  exercise-1 ./test1 test.c
 外部变量定义：
     类型：int
     变量名：
          ID： a
          ID： b
          ID： c
 外部变量定义：
     类型：float
     变量名：
          ID： m
          ID： n
 外部变量定义：
     类型：char
     变量名：
          ID： c1
          ID： c2
 数组定义：
     类型：char
     数组名：a
     数组大小：
          INT： 10
 函数定义：
     类型：int
     函数名：fibo
     函数型参：
          类型：int
          ID： a
     复合语句：
          复合语句的变量定义：
               LOCAL VAR_NAME：
                    类型：int
                    变量名：
                         ID： i
          复合语句的语句部分：
               条件语句（if-else）：
               条件：
                    OR
                         ==
                              ID： a
                              INT： 1
                         ==
                              ID： a
                              INT： 2
               IF语句：
                    复合语句：
                         复合语句的变量定义：
                         复合语句的语句部分：
                              返回语句：
                                   INT： 1
               循环语句（for）：
                    循环条件：
                    <
                         ID： i
                         INT： 15
                    循环体：
                    复合语句：
                         复合语句的变量定义：
                         复合语句的语句部分：
                              表达式语句：
                                   AUTOADD
                                        ID： i
               返回语句：
                    PLUS
                         函数调用：
                              函数名：fibo
                              第一个实际参数表达式：
                                   MINUS
                                        ID： a
                                        INT： 1
                         函数调用：
                              函数名：fibo
                              第一个实际参数表达式：
                                   MINUS
                                        ID： a
                                        INT： 2
 函数定义：
     类型：int
     函数名：main
     函数型参：
     复合语句：
          复合语句的变量定义：
               LOCAL VAR_NAME：
                    类型：int
                    变量名：
                         ID： m
                    变量名：
                         ID： n
                    变量名：
                         ID： i
               LOCAL VAR_NAME：
                    类型：char
                    变量名：
                         ID： c
               LOCAL VAR_NAME：
               数组定义：
                    类型：float
                    数组名：ar
                    数组大小：
                         INT： 20
          复合语句的语句部分：
               表达式语句：
                    ASSIGNOP
                         ID： m
                         函数调用：
                              函数名：read
                              第一个实际参数表达式：
               表达式语句：
                    ASSIGNOP
                         ID： i
                         INT： 1
               表达式语句：
                    AUTOADD
                         ID： i
               表达式语句：
                    AUTOSUB
                         ID： i
               表达式语句：
                    COMADD
                         ID： m
                         PLUS
                              ID： i
                              INT： 15
               循环语句（while）：
                    循环条件：
                    <=
                         ID： i
                         ID： m
                    循环体：
                    复合语句：
                         复合语句的变量定义：
                         复合语句的语句部分：
                              表达式语句：
                                   ASSIGNOP
                                        ID： n
                                        函数调用：
                                             函数名：fibo
                                             第一个实际参数表达式：
                                                  ID： i
                              表达式语句：
                                   函数调用：
                                        函数名：write
                                        第一个实际参数表达式：
                                             ID： n
                              表达式语句：
                                   ASSIGNOP
                                        ID： i
                                        PLUS
                                             ID： i
                                             INT： 1
               返回语句：
                    INT： 1