C-Minus 源代码 语法分析

一、实现目标

  在上一篇文章（C-Minus词法分析）中，我们实现了对C-Minus语言（C语言子集）书写的源代码进行词法分析，并打印分析结果；关于C-Minus语法的详细内容请参考上篇文章。而在本篇文章中，我们将运用语法分析相关知识，编写一个程序对使用类C语言书写的源代码进行语法分析，并打印分析结果。
  至少实现最低要求：输出语法分析树，并能定位错误信息。
  实现方式：可以选择手工编写（递归下降 / LL 分析 / LR 分析法）或者使用类似 Bison/Yacc 工具编写。

二、实现过程

1. 综述

  本篇文章采用了Flex/Bison工具实现语法分析。
  Flex是一个生成词法分析器的工具，可以将输入按照正则表达式识别为定义的Token，当Flex词法分析器与Bison连用时，Flex的返回值包括两部分：Token以及对应的Value，通过在 .l 文件中对 yylval 赋值并返回Token，Bison就可以将对应的值压入栈中，进行规约操作。
  Bison可以生成语法分析器，解析输入流中的Token，采用自底向上LALR的分析方法。当Bison读入一个终结符（Token），它会将该终结符及其语义值一起压入堆栈，这个堆栈叫做分析器堆栈。把一个Token压入堆栈通常叫做移进。在Bison分析文件的过程中，我们能够通过编写自己的代码并在action部分调用函数实现分析语法树的构建。

2. 实现功能介绍

（1）检测词法错误

 /*错误*/
{AERROR} {hasFault=1;printf("Error type A at line %d: Mystirious charachter '%s'\n",yylineno,yytext);
}

  由于Flex的匹配规则是从上到下、按照匹配长度决定优先级，通过在syntax_tree.l文件中action的最后部分添加对于任意字符的匹配AERROR，可以实现对未定义字符的检测，并将该错误字符输出。

（2）检测文法错误

// 错误处理
void yyerror(char *msg)
{hasFault = 1;fprintf(stderr, "Error type B at Line %d, %s ,before %s\n", yylineno, msg, yytext);
}

  Bison在对定义的语法和指定文件进行分析过程中，会调用Flex,进行移进、规约操作，在分析过程中，如果产生了语法错误，Bison会调用yyerror函数并停止分析。这时我们可以自己定义yyerror函数，输出语法错误的具体位置。

（3）生成语法分析树

// 抽象语法树
typedef struct treeNode{// 行数int line;// Token类型char* name;// fchild是第一个孩子节点，next是兄弟节点，使用孩子兄弟表示法struct treeNode *fchild,*next;// 联合体，同一时间只能保存一个成员的值，分配空间是其中最大类型的内存大小union{// id内容或者type类型（int/float）char* id_type;// 具体的数值int intval;float fltval;};
}* Ast,* tnode;

  通过自定义的语法分析树节点结构体以及构造函数，我们可以实现语法分析过程中构建语法分析树。

// 所有节点数量
int nodeNum;
// 存放所有节点
tnode nodeList[5000];
int nodeIsChild[5000];
// 设置节点打印状态
void setChildTag(tnode node);

  通过存储分析过程中构造的节点以及该节点的类型（子节点/根节点），可以在遍历完文件、构造完语法分析树后从根节点进行先序遍历，从而打印树结构。

/*syntax_tree.l 文件*/
{TYPE} {yylval.type_tnode=newAst("TYPE",0,yylineno);return TYPE;}
{STRUCT} {yylval.type_tnode=newAst("STRUCT",0,yylineno);return STRUCT;}
{RETURN} {yylval.type_tnode=newAst("RETURN",0,yylineno); return RETURN;}
{IF} {yylval.type_tnode=newAst("IF",0,yylineno);return IF;}
{ELSE} {yylval.type_tnode=newAst("ELSE",0,yylineno); return ELSE;}

/*syntax_tree.y 文件*/
/*High-level Definitions*/
Program:ExtDefList {$$=newAst("Program",1,$1);nodeList[nodeNum]=$$;nodeNum++;};
ExtDefList:ExtDef ExtDefList {$$=newAst("ExtDefList",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}| {$$=newAst("ExtDefList",0,-1);nodeList[nodeNum]=$$;nodeNum++;};

  词法分析过程中，在.l文件中生成叶节点（终结符号），语法分析过程中，在.y文件中生成其他节点（非终结符），构建语法分析树。

3. 代码详解

（1）syntax_tree.l

该文件是Flex文件格式，定义了词法分析器的规则，和实验一不同的是头文件部分和antion部分，同时由于flex只是被bison调用，所以无需在该文件中定义main函数。

/* bison语法分析，对每条规则 按照孩子兄弟表示法建立语法结点 */
%{
#include<unistd.h>
#include<stdio.h>   
#include "syntax_tree.h"
%}

  头文件中，由于在语法分析中我们需要检测到终结符，所以需要构造语法分析树的叶节点，同时为了将结果传给Bison，需要引入.y文件编译生成的Token表头文件。

/*第三部分 操作 action 这里面的注释必须顶格一个空格*/
%%/*跳过空白和注释*/
{SPACE} {}
{COMMENT} {}
{EOL} {}/*关键字*/
{TYPE} {yylval.type_tnode=newAst("TYPE",0,yylineno);return TYPE;}
{STRUCT} {yylval.type_tnode=newAst("STRUCT",0,yylineno);return STRUCT;}
{RETURN} {yylval.type_tnode=newAst("RETURN",0,yylineno); return RETURN;}
{IF} {yylval.type_tnode=newAst("IF",0,yylineno);return IF;}
{ELSE} {yylval.type_tnode=newAst("ELSE",0,yylineno); return ELSE;}
{WHILE} {yylval.type_tnode=newAst("WHILE",0,yylineno); return WHILE;}/*数字类型错误*/
{INT_HEX_ERROR} {printf("INT_HEX_ERROR at line %d: charachters \"%s\"\n",yylineno,yytext);}
{INT_OCT_ERROR} {printf("INT_OCT_ERROR at line %d: charachters \"%s\"\n",yylineno,yytext);}
{INT_BIN_ERROR} {printf("INT_BIN_ERROR at line %d: charachters \"%s\"\n",yylineno,yytext);}/*数字类型表示*/
{INT} {yylval.type_tnode=newAst("INT",0,yylineno); return INT;}
{FLOAT} {yylval.type_tnode=newAst("FLOAT",0,yylineno); return FLOAT;}

  在action部分，我们需要将词法分析的结果返回给语法分析器，因此需要用yylval传递节点变量（该记号的语义值），同时将解析的Token类型也告诉Bison。

（2）syntax_tree.y

%union{tnode type_tnode;// 这里声明double是为了防止出现指针错误（segmentation fault）double d;
}/*声明记号*/
%token <type_tnode> INT FLOAT
%token <type_tnode> TYPE STRUCT RETURN IF ELSE WHILE ID COMMENT SPACE SEMI COMMA ASSIGNOP PLUS
%token <type_tnode> MINUS STAR DIV AND OR DOT NOT LP RP LB RB LC RC AERROR RELOP EOL%type  <type_tnode> Program ExtDefList ExtDef ExtDecList Specifire StructSpecifire 
%type  <type_tnode> OptTag Tag VarDec FunDec VarList ParamDec Compst StmtList Stmt DefList Def DecList Dec Exp Args

  在%union中我们需要定义除了int外的类型，因为在声明记号时，该记号的类型决定了我们用yyval传值的类型，而在之前的.l文件中我将叶节点(tnode)类型作为传值的内容，因此我在这里将Token的类型声明为tnode。非终结符同理，用来构造语法分析树。

/*优先级*/
/*C-minus中定义的运算符的优先级，并没有包括所有C语言的*/
%right ASSIGNOP
%left OR
%left AND
%left RELOP
%left PLUS MINUS
%left STAR DIV
%right NOT 
%left LP RP LB RB DOT%nonassoc LOWER_THAN_ELSE 
%nonassoc ELSE

Stmt:Exp SEMI {$$=newAst("Stmt",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}|Compst {$$=newAst("Stmt",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|RETURN Exp SEMI {$$=newAst("Stmt",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|IF LP Exp RP Stmt %prec LOWER_THAN_ELSE {$$=newAst("Stmt",5,$1,$2,$3,$4,$5);nodeList[nodeNum]=$$;nodeNum++;}|IF LP Exp RP Stmt ELSE Stmt {$$=newAst("Stmt",7,$1,$2,$3,$4,$5,$6,$7);nodeList[nodeNum]=$$;nodeNum++;}|WHILE LP Exp RP Stmt {$$=newAst("Stmt",5,$1,$2,$3,$4,$5);nodeList[nodeNum]=$$;nodeNum++;};

  为了避免C-minus语法中的二义性、移进规约冲突，我定义了运算符的优先级、嵌套if-else的优先级。%left表示左结合，%right表示右结合，%nonassoc表示不可结合，解决了运算、if-else嵌套的冲突。

/*High-level Definitions*/
Program:ExtDefList {$$=newAst("Program",1,$1);nodeList[nodeNum]=$$;nodeNum++;};
ExtDefList:ExtDef ExtDefList {$$=newAst("ExtDefList",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}| {$$=newAst("ExtDefList",0,-1);nodeList[nodeNum]=$$;nodeNum++;};
ExtDef:Specifire ExtDecList SEMI    {$$=newAst("ExtDef",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}    |Specifire SEMI	{$$=newAst("ExtDef",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}|Specifire FunDec Compst	{$$=newAst("ExtDef",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;};
ExtDecList:VarDec {$$=newAst("ExtDecList",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|VarDec COMMA ExtDecList {$$=newAst("ExtDecList",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;};

  根据C-minus文件中给出的文法生成式，我对Bison文件产生式部分进行了定义。该部分可以用来进行规约操作，当进行规约时，在action部分构造新的语法分析树节点。$$表示左边的非终结符，$1、$2表示产生式右边第一个、第二个终结符/非终结符。
  为了输出最后的分析树结构，我定义了nodeNum变量表示节点数量，定义了nodeList数组存放节点指针。

（3）syntax_tree.h

该文件定义了一些结构体、全局变量、函数声明。

// 行数
extern int yylineno;
// 文本
extern char* yytext;
// 错误处理
void yyerror(char *msg);

  定义了全局变量，声明了错误处理函数。

// 抽象语法树
typedef struct treeNode{// 行数int line;// Token类型char* name;// fchild是第一个孩子节点，next是兄弟节点，使用孩子兄弟表示法struct treeNode *fchild,*next;// 联合体，同一时间只能保存一个成员的值，分配空间是其中最大类型的内存大小union{// id内容或者type类型（int/float）char* id_type;// 具体的数值int intval;float fltval;};
}* Ast,* tnode;

  抽象语法树节点结构体，当节点为TYPE、ID、INT、FLOAT时，我们需要另外存储该节点的属性值，这里用到了Union，每个节点最多只有一个联合体中的属性值会被赋值。

// 构造抽象语法树(节点)
Ast newAst(char* name,int num,...);
// 先序遍历语法树
void Preorder(Ast ast,int level);

  由于分析树采用的是孩子兄弟表示法，不清楚每个节点有几个子节点，因此采用变长参数，需要引入头文件 stdarg.h

// bison是否有词法语法错误
int hasFault;

  由于Bison在检测到错误时会调用yyerror并停止分析，而我们需要在分析完文件并确定没有错误后输出分析树，所以定义该变量，如果在分析过程中遇到错误，那么在文件扫描结束后就不会输出分析树结构。

（4）syntax_tree.c

该文件实现了syntax_tree.h中定义的函数以及主函数main

树节点构造函数

Ast newAst(char *name, int num, ...)
{// 生成父节点tnode father = (tnode)malloc(sizeof(struct treeNode));// 添加子节点tnode temp = (tnode)malloc(sizeof(struct treeNode));if (!father){yyerror("create treenode error");exit(0);}father->name = name;// 参数列表，详见 stdarg.h 用法va_list list;// 初始化参数列表va_start(list, num);// 表示当前节点不是终结符号，还有子节点if (num > 0){// 第一个孩子节点temp = va_arg(list, tnode);setChildTag(temp);father->fchild = temp;// 父节点行号为第一个孩子节点的行号father->line = temp->line;// 多个节点，继续添加if (num >= 2){for (i = 0; i < num - 1; ++i){temp->next = va_arg(list, tnode);temp = temp->next;// 该节点为其他节点的子节点setChildTag(temp);}}}else //表示当前节点是终结符（叶节点）或者空的语法单元，此时num表示行号（空单元为-1）,将对应的值存入union{father->line = va_arg(list, int);// strcmp()==0 表示相同if ((!strcmp(name, "ID")) || (!strcmp(name, "TYPE"))){char *str;str = (char *)malloc(sizeof(char) * 40);strcpy(str, yytext);father->id_type = str;// father->id_type = (char*)malloc(sizeof(char)*40);// strcpy(father->id_type,yytext);}else if (!strcmp(name, "INT")){father->intval = atoi(yytext);}else{father->fltval = atof(yytext);}}return father;
}

  Ast构造函数采用变长参数，对于构建叶节点、构建父节点能够进行不同的处理，同时判断Token类型，将TYPE、ID、INT、FLOAT的属性值存入结构体的union中。如果有多个子节点，则进行子节点的添加。兄弟孩子表示法，左子树为第一个孩子节点，右子树为该节点的兄弟节点。

语法树遍历函数

// 父节点->左子节点->右子节点....
void Preorder(Ast ast, int level)
{// printf(" into ");if (ast != NULL){// 层级结构缩进for (i = 0; i < level; ++i){printf(" ");}// printf(" rline ");if (ast->line != -1){// printf(" prnt ");// 打印节点类型printf("%s", ast->name);// 根据不同类型打印节点数据if ((!strcmp(ast->name, "ID")) || (!strcmp(ast->name, "TYPE"))){printf(": %s", ast->id_type);}else if (!strcmp(ast->name, "INT")){printf(": %d", ast->intval);}else if (!strcmp(ast->name, "FLOAT")){printf(": %f", ast->fltval);}else{// 非叶节点打印行号printf("(%d)", ast->line);}}printf("\n");// printf(" fchild ");Preorder(ast->fchild, level + 1);// printf(" next ");Preorder(ast->next, level);}// printf(" return ");
}

  采用先序遍历，先遍历根节点，再遍历左子树、右子树，并且对不同的节点类型进行不同内容的输出。

设置节点类型(根节点/其他节点)

// 设置节点打印状态 该节点为子节点
void setChildTag(tnode node)
{int i;for (i = 0; i < nodeNum; i++){if (nodeList[i] == node){nodeIsChild[i] = 1;}}
}

  在C语言中，比较两个指针是否相等时，比较的是指针指向的内存地址是否相同，因此可以用指针数组来存放节点，并且进行比较。在构造函数中，对于添加的子节点，设置该节点标签为子节点类型。

主函数

// 主函数 扫描文件并且分析
// 为bison会自己调用yylex()，所以在main函数中不需要再调用它了
// bison使用yyparse()进行语法分析，所以需要我们在main函数中调用yyparse()和yyrestart()
int main(int argc, char **argv)
{int j;printf("start analysis\n");if (argc < 2){return 1;}for (i = 1; i < argc; i++){// 初始化节点记录列表nodeNum = 0;memset(nodeList, 0, sizeof(tnode) * 5000);memset(nodeIsChild, 0, sizeof(int) * 5000);hasFault = 0;FILE *f = fopen(argv[i], "r");if (!f){perror(argv[i]);return 1;}yyrestart(f);yyparse();fclose(f);// 遍历所有非子节点的节点if (hasFault)continue;for (j = 0; j < nodeNum; j++){if (nodeIsChild[j] != 1){Preorder(nodeList[j], 0);}}}
}

  在主函数中体现了节点存储、寻找根节点的过程。如果词法语法分析没有错误的话，就进行树结构输出。对于节点数组中唯一的非子节点，就一定是语法分析树的根节点，对该节点进行先序遍历输出。

三、测试结果

1. 工程文件以及编译过程

  syntax_tree.c syntax_tree.h 是语法分析树的C文件，包含主函数
  base_false.cmm base_true.cmm input.c是测试文件
  parser 是gcc编译的可执行文件


(1) syntax_tree.y 是bison文件
  用 bison -d filename 编译
  syntax_tree.tab.c syntax_tree.tab.h 是编译bison生成的
(2) syntax_tree.l 是flex文件
  用 flex filename 编译
  lex.yy.c 是编译flex生成的
(3) 总体编译过程
  bison -d syntax_tree.y
  flex syntax_tree.l
  gcc syntax_tree.tab.c syntax_tree.c lex.yy.c -lfl -ly -o parser

2. 执行测试程序

（1）base_true.cmm

struct Complex
{float real, image;
};int main()
{struct Complex x;x.image = 1.5;
}

执行结果如下：

  没有词法、语法错误，输出了完整的语法分析树，并且能够识别出数字的值。

（2）Base_false.cmm

struct Complex
{float real, image;
};int main()
{struct Complex x;float a[10] = 1.5;int i = 100;x.image = ~i;if (a[1][2] == 0) i =1 else i =0;
}

  能够识别词法错误、语法错误，不输出语法分析树。

（3）input.c

int inc()
{int i = 1;i = i+1;
}

分析结果：

  对比可知分析结果正确

3. 遇到的问题及解决

  (1) 在实现语法树输出时，我最开始的实现方法是在.y文件的action部分，当规约到Program类型时就进行先序遍历输出，但是我发现这样只能输出函数的语法树。后来采用定义全局变量数组存放所有节点，最后判断节点类型只遍历根节点
  (2) 在.y文件union中我一开始只定义了tnode类型的别名，但是这样会出现段错误segmentation fault，我查阅了相关资料也不清楚原因，但是当我增加了另一个变量声明double后这个错误就消失了，个人理解是因为tnode是指针类型，占用内存较小，但是却被赋予了较大的内存地址，而加了double后union开辟的内存空间是按照较大的变量类型(double类型)来计算的，所以避免了段错误。

---

本文为原创，如有错误欢迎指正，感谢阅读。
下文是完整源码，建议阅读并理解上文部分，下文只作为参考。

---

四、源码放送

1. syntax_tree.l

/*按照C-Tokens文件中要求定义对终结符建立叶子结点，返回Token19-10-26
*//*第一部分 头文件和变量*/
%{#include <stdlib.h>#include <stdio.h>#include "syntax_tree.h"#include "syntax_tree.tab.h"
%}/*flex属性,记录符号所在行号*/
%option yylineno/*第二部分 定义正则表达式*/
/*十进制*/
INT_DEC 0|[1-9][0-9]*
/*十六进制*/
INT_HEX 0[xX][a-fA-F0-9]+
/*八进制*/
INT_OCT 0[1-7][0-7]*
/*二进制*/
INT_BIN 0[bB][01]+
/*INT类型汇总*/
INT {INT_HEX}|{INT_DEC}|{INT_OCT}|{INT_BIN}|{INT_HEX_ERROR}|{INT_OCT_ERROR}|{INT_BIN_ERROR}
/*浮点数-科学计数法*/
FLOAT ((([0-9]+\.[0-9]*)|([0-9]*\.[0-9]+)|INT)[Ee][-+]?[0-9]+)|({INT}\.[0-9])
/*词法分析输出错误，但是语法分析当做INT进行处理*/
/*十六进制错误*/
INT_HEX_ERROR 0[xX][a-fA-F0-9]*[g-zG-Z]+[a-fA-F0-9]*
/*八进制错误*/
INT_OCT_ERROR 0[0-7]*[89]+[0-7]*
/*二进制错误*/
INT_BIN_ERROR 0[bB][01]*[2-9]+[01]*/*标识符*/
ID [a-z_A-Z][a-z_A-Z0-9]*/*关键字*/
STRUCT struct
RETURN return
IF if
ELSE else
WHILE while
TYPE int|float/*符号*/
SEMI  ;
COMMA ,
ASSIGNOP  =
PLUS  \+
MINUS \-
STAR  \*
DIV   \/
AND   &&
DOT   \.
NOT   \!
LP    \(
RP    \)
LB    \[
RB    \]
LC    \{
RC    \}
RELOP >|<|>=|<=|==|!=/*注释*/
COMMENT ("//".*)|("/*"([*]*(([^*/])+([/])*)*)*"*/")
/*空白符*/
SPACE [ \f\r\t\v]+
/*换行*/
EOL \n
/*未定义字符*/
AERROR ./*第三部分 操作 action 这里面的注释必须顶格一个空格*/
%%/*跳过空白和注释*/
{SPACE} {}
{COMMENT} {}
{EOL} {}/*关键字*/
{TYPE} {yylval.type_tnode=newAst("TYPE",0,yylineno);return TYPE;}
{STRUCT} {yylval.type_tnode=newAst("STRUCT",0,yylineno);return STRUCT;}
{RETURN} {yylval.type_tnode=newAst("RETURN",0,yylineno); return RETURN;}
{IF} {yylval.type_tnode=newAst("IF",0,yylineno);return IF;}
{ELSE} {yylval.type_tnode=newAst("ELSE",0,yylineno); return ELSE;}
{WHILE} {yylval.type_tnode=newAst("WHILE",0,yylineno); return WHILE;}/*数字类型错误*/
{INT_HEX_ERROR} {printf("INT_HEX_ERROR at line %d: charachters \"%s\"\n",yylineno,yytext);}
{INT_OCT_ERROR} {printf("INT_OCT_ERROR at line %d: charachters \"%s\"\n",yylineno,yytext);}
{INT_BIN_ERROR} {printf("INT_BIN_ERROR at line %d: charachters \"%s\"\n",yylineno,yytext);}/*数字类型表示*/
{INT} {yylval.type_tnode=newAst("INT",0,yylineno); return INT;}
{FLOAT} {yylval.type_tnode=newAst("FLOAT",0,yylineno); return FLOAT;}/*符号*/
{SEMI} {yylval.type_tnode=newAst("SEMI",0,yylineno); return SEMI;}
{COMMA} {yylval.type_tnode=newAst("COMMA",0,yylineno); return COMMA;}
{ASSIGNOP} {yylval.type_tnode=newAst("ASSIGNOP",0,yylineno); return ASSIGNOP;}
{PLUS} {yylval.type_tnode=newAst("PLUS",0,yylineno); return PLUS;}
{MINUS} {yylval.type_tnode=newAst("MINUS",0,yylineno); return MINUS;}
{STAR} {yylval.type_tnode=newAst("STAR",0,yylineno); return STAR;}
{DIV} {yylval.type_tnode=newAst("DIV",0,yylineno); return DIV;}
{AND} {yylval.type_tnode=newAst("AND",0,yylineno); return AND;}
{DOT} {yylval.type_tnode=newAst("DOT",0,yylineno); return DOT;}
{NOT} {yylval.type_tnode=newAst("NOT",0,yylineno); return NOT;}
{LP} {yylval.type_tnode=newAst("LP",0,yylineno); return LP;}
{RP} {yylval.type_tnode=newAst("RP",0,yylineno); return RP;}
{LB} {yylval.type_tnode=newAst("LB",0,yylineno); return LB;}
{RB} {yylval.type_tnode=newAst("RB",0,yylineno); return RB;}
{LC} {yylval.type_tnode=newAst("LC",0,yylineno); return LC;}
{RC} {yylval.type_tnode=newAst("RC",0,yylineno); return RC;}
{RELOP} {yylval.type_tnode=newAst("RELOP",0,yylineno); return RELOP;}/*标识符*/
{ID} {yylval.type_tnode=newAst("ID",0,yylineno); return ID;}/*错误*/
{AERROR} {hasFault=1;printf("Error type A at line %d: Mystirious charachter '%s'\n",yylineno,yytext);
}
%%/*第四部分 函数 function*/
int yywrap()
{/*此函数必须由用户提供,或者声明 %option noyywrap当词法分析程序遇到文件结尾时，它调用例程yywrap()来找出下一步要做什么如果返回0，扫描程序继续扫描，如果返回1，扫描程序就返回报告文件结尾*/return 1;
}

2. syntax_tree.y

/*
*bison语法分析，对每条规则 按照孩子兄弟表示法建立语法结点
*/
%{
#include<unistd.h>
#include<stdio.h>   
#include "syntax_tree.h"
%}%union{tnode type_tnode;// 这里声明double是为了防止出现指针错误（segmentation fault）double d;
}/*声明记号*/
%token <type_tnode> INT FLOAT
%token <type_tnode> TYPE STRUCT RETURN IF ELSE WHILE ID COMMENT SPACE SEMI COMMA ASSIGNOP PLUS
%token <type_tnode> MINUS STAR DIV AND OR DOT NOT LP RP LB RB LC RC AERROR RELOP EOL%type  <type_tnode> Program ExtDefList ExtDef ExtDecList Specifire StructSpecifire 
%type  <type_tnode> OptTag Tag VarDec FunDec VarList ParamDec Compst StmtList Stmt DefList Def DecList Dec Exp Args/*优先级*/
/*C-minus中定义的运算符的优先级，并没有包括所有C语言的*/
%right ASSIGNOP
%left OR
%left AND
%left RELOP
%left PLUS MINUS
%left STAR DIV
%right NOT 
%left LP RP LB RB DOT%nonassoc LOWER_THAN_ELSE 
%nonassoc ELSE/*产生式*/
/*$$表示左表达式 ${num}表示右边的第几个表达式*/
%%
/*High-level Definitions*/
Program:ExtDefList {$$=newAst("Program",1,$1);nodeList[nodeNum]=$$;nodeNum++;};
ExtDefList:ExtDef ExtDefList {$$=newAst("ExtDefList",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}| {$$=newAst("ExtDefList",0,-1);nodeList[nodeNum]=$$;nodeNum++;};
ExtDef:Specifire ExtDecList SEMI    {$$=newAst("ExtDef",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}    |Specifire SEMI	{$$=newAst("ExtDef",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}|Specifire FunDec Compst	{$$=newAst("ExtDef",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;};
ExtDecList:VarDec {$$=newAst("ExtDecList",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|VarDec COMMA ExtDecList {$$=newAst("ExtDecList",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;};
/*Specifire*/
Specifire:TYPE {$$=newAst("Specifire",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|StructSpecifire {$$=newAst("Specifire",1,$1);nodeList[nodeNum]=$$;nodeNum++;};
StructSpecifire:STRUCT OptTag LC DefList RC {$$=newAst("StructSpecifire",5,$1,$2,$3,$4,$5);nodeList[nodeNum]=$$;nodeNum++;}|STRUCT Tag {$$=newAst("StructSpecifire",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;};
OptTag:ID {$$=newAst("OptTag",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|{$$=newAst("OptTag",0,-1);nodeList[nodeNum]=$$;nodeNum++;};
Tag:ID {$$=newAst("Tag",1,$1);nodeList[nodeNum]=$$;nodeNum++;};
/*Declarators*/
VarDec:ID {$$=newAst("VarDec",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|VarDec LB INT RB {$$=newAst("VarDec",4,$1,$2,$3,$4);nodeList[nodeNum]=$$;nodeNum++;};
FunDec:ID LP VarList RP {$$=newAst("FunDec",4,$1,$2,$3,$4);nodeList[nodeNum]=$$;nodeNum++;}|ID LP RP {$$=newAst("FunDec",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;};
VarList:ParamDec COMMA VarList {$$=newAst("VarList",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|ParamDec {$$=newAst("VarList",1,$1);nodeList[nodeNum]=$$;nodeNum++;};
ParamDec:Specifire VarDec {$$=newAst("ParamDec",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;};/*Statement*/
Compst:LC DefList StmtList RC {$$=newAst("Compst",4,$1,$2,$3,$4);nodeList[nodeNum]=$$;nodeNum++;};
StmtList:Stmt StmtList{$$=newAst("StmtList",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}| {$$=newAst("StmtList",0,-1);nodeList[nodeNum]=$$;nodeNum++;};
Stmt:Exp SEMI {$$=newAst("Stmt",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}|Compst {$$=newAst("Stmt",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|RETURN Exp SEMI {$$=newAst("Stmt",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|IF LP Exp RP Stmt %prec LOWER_THAN_ELSE {$$=newAst("Stmt",5,$1,$2,$3,$4,$5);nodeList[nodeNum]=$$;nodeNum++;}|IF LP Exp RP Stmt ELSE Stmt {$$=newAst("Stmt",7,$1,$2,$3,$4,$5,$6,$7);nodeList[nodeNum]=$$;nodeNum++;}|WHILE LP Exp RP Stmt {$$=newAst("Stmt",5,$1,$2,$3,$4,$5);nodeList[nodeNum]=$$;nodeNum++;};
/*Local Definitions*/
DefList:Def DefList{$$=newAst("DefList",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}| {$$=newAst("DefList",0,-1);nodeList[nodeNum]=$$;nodeNum++;};
Def:Specifire DecList SEMI {$$=newAst("Def",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;};
DecList:Dec {$$=newAst("DecList",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|Dec COMMA DecList {$$=newAst("DecList",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;};
Dec:VarDec {$$=newAst("Dec",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|VarDec ASSIGNOP Exp {$$=newAst("Dec",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;};
/*Expressions*/
Exp:Exp ASSIGNOP Exp{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp AND Exp{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp OR Exp{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp RELOP Exp{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp PLUS Exp{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp MINUS Exp{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp STAR Exp{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp DIV Exp{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|LP Exp RP{$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|MINUS Exp {$$=newAst("Exp",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}|NOT Exp {$$=newAst("Exp",2,$1,$2);nodeList[nodeNum]=$$;nodeNum++;}|ID LP Args RP {$$=newAst("Exp",4,$1,$2,$3,$4);nodeList[nodeNum]=$$;nodeNum++;}|ID LP RP {$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp LB Exp RB {$$=newAst("Exp",4,$1,$2,$3,$4);nodeList[nodeNum]=$$;nodeNum++;}|Exp DOT ID {$$=newAst("Exp",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|ID {$$=newAst("Exp",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|INT {$$=newAst("Exp",1,$1);nodeList[nodeNum]=$$;nodeNum++;}|FLOAT{$$=newAst("Exp",1,$1);nodeList[nodeNum]=$$;nodeNum++;};
Args:Exp COMMA Args {$$=newAst("Args",3,$1,$2,$3);nodeList[nodeNum]=$$;nodeNum++;}|Exp {$$=newAst("Args",1,$1);nodeList[nodeNum]=$$;nodeNum++;};
%%

3. syntax_tree.h

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>  // 变长参数函数 头文件// 行数
extern int yylineno;
// 文本
extern char* yytext;
// 错误处理
void yyerror(char *msg);// 抽象语法树
typedef struct treeNode{// 行数int line;// Token类型char* name;// fchild是第一个孩子节点，next是兄弟节点，使用孩子兄弟表示法struct treeNode *fchild,*next;// 联合体，同一时间只能保存一个成员的值，分配空间是其中最大类型的内存大小union{// id内容或者type类型（int/float）char* id_type;// 具体的数值int intval;float fltval;};
}* Ast,* tnode;// 构造抽象语法树(节点)
Ast newAst(char* name,int num,...);// 先序遍历语法树
void Preorder(Ast ast,int level);// 所有节点数量
int nodeNum;
// 存放所有节点
tnode nodeList[5000];
int nodeIsChild[5000];
// 设置节点打印状态
void setChildTag(tnode node);// bison是否有词法语法错误
int hasFault;

4. syntax_tree.c

#include "syntax_tree.h"// 用于遍历
int i;Ast newAst(char *name, int num, ...)
{// 生成父节点tnode father = (tnode)malloc(sizeof(struct treeNode));// 添加子节点tnode temp = (tnode)malloc(sizeof(struct treeNode));if (!father){yyerror("create treenode error");exit(0);}father->name = name;// 参数列表，详见 stdarg.h 用法va_list list;// 初始化参数列表va_start(list, num);// 表示当前节点不是终结符号，还有子节点if (num > 0){// 第一个孩子节点temp = va_arg(list, tnode);setChildTag(temp);father->fchild = temp;// 父节点行号为第一个孩子节点的行号father->line = temp->line;// 多个节点，继续添加if (num >= 2){for (i = 0; i < num - 1; ++i){temp->next = va_arg(list, tnode);temp = temp->next;// 该节点为其他节点的子节点setChildTag(temp);}}}else //表示当前节点是终结符（叶节点）或者空的语法单元，此时num表示行号（空单元为-1）,将对应的值存入union{father->line = va_arg(list, int);// strcmp()==0 表示相同if ((!strcmp(name, "ID")) || (!strcmp(name, "TYPE"))){char *str;str = (char *)malloc(sizeof(char) * 40);strcpy(str, yytext);father->id_type = str;// father->id_type = (char*)malloc(sizeof(char)*40);// strcpy(father->id_type,yytext);}else if (!strcmp(name, "INT")){father->intval = atoi(yytext);}else{father->fltval = atof(yytext);}}return father;
}// 父节点->左子节点->右子节点....
void Preorder(Ast ast, int level)
{// printf(" into ");if (ast != NULL){// 层级结构缩进for (i = 0; i < level; ++i){printf(" ");}// printf(" rline ");if (ast->line != -1){// printf(" prnt ");// 打印节点类型printf("%s", ast->name);// 根据不同类型打印节点数据if ((!strcmp(ast->name, "ID")) || (!strcmp(ast->name, "TYPE"))){printf(": %s", ast->id_type);}else if (!strcmp(ast->name, "INT")){printf(": %d", ast->intval);}else if (!strcmp(ast->name, "FLOAT")){printf(": %f", ast->fltval);}else{// 非叶节点打印行号printf("(%d)", ast->line);}}printf("\n");// printf(" fchild ");Preorder(ast->fchild, level + 1);// printf(" next ");Preorder(ast->next, level);}// printf(" return ");
}// 错误处理
void yyerror(char *msg)
{hasFault = 1;fprintf(stderr, "Error type B at Line %d, %s ,before %s\n", yylineno, msg, yytext);
}// 设置节点打印状态 该节点为子节点
void setChildTag(tnode node)
{int i;for (i = 0; i < nodeNum; i++){if (nodeList[i] == node){nodeIsChild[i] = 1;}}
}// 主函数 扫描文件并且分析
// 为bison会自己调用yylex()，所以在main函数中不需要再调用它了
// bison使用yyparse()进行语法分析，所以需要我们在main函数中调用yyparse()和yyrestart()
int main(int argc, char **argv)
{int j;printf("start analysis\n");if (argc < 2){return 1;}for (i = 1; i < argc; i++){// 初始化节点记录列表nodeNum = 0;memset(nodeList, 0, sizeof(tnode) * 5000);memset(nodeIsChild, 0, sizeof(int) * 5000);hasFault = 0;FILE *f = fopen(argv[i], "r");if (!f){perror(argv[i]);return 1;}yyrestart(f);yyparse();fclose(f);// 遍历所有非子节点的节点if (hasFault)continue;for (j = 0; j < nodeNum; j++){if (nodeIsChild[j] != 1){Preorder(nodeList[j], 0);}}}
}