基于lex和yacc的词法分析器+语法分析器.zip

# **C-- 编译器实现** # **一、使用说明** 运行环境：Ubuntu 14.04 Ubuntu 16.04 本编译器所支持的词法和语法请参考第二第三小节 解压压缩包 运行命令 ``` unzip compiler.zip ``` 进入文件夹运行命令 ``` ./compiler test.cmm ``` 其中test.cmm可以替换成其他文件 如果报错，则输出错误行号输出语法树 产生语法树所用的产生式的推导/规约序列  ...  # **二、词法分析** ## 1.概述 词法分析器的作用是读取源程序生成词法单元，并过滤掉注释和空白。项目中的词法分析使用了lex 。 ## 2.词元类型说明 ### INT INT表示的是整型常数。一个十进制整数由0~9十个数字组成，数字与数字中间没有空格之类 的分隔符。 除0之外，十进制整数的首位数字不为0。 八进制或十六进制的形式。八进制整数由0-7八个数字组成并以数字0开头。 十六进制整数由0-9、a-f十六个数字组成并以0x开头。 ## FLOAT FLOAT表示的是浮点型常数。一个浮点数由一串数字与一个小数点组成，小数点的前后必须有数字出现。 浮点型常数还可以以指数形式表示。指数形式的浮点数必须包括基数、指数符号和指数三个 部分，且三部分依次出现。基数部分由一串数字（0~9）和一个小数点组成，小数点可以出 现在数字串的任何位置；指数符号为E或e；指数部分由可带-或者不带的一串数字组成，-必 须出现在数字串之前。 # ID ID表示的是标识符。标识符由大小写字母、数字以及下划线组成，但必须以字母或者下划线 开头。  ​  # **三、语法分析** ## 1.概述 语法分析接收词法分析器提供的记号串，检查记号串是否能由 c-- 规定的文法产生，并提示错误信息。 ## 2.语法规则 Program ExtDefList 一段程序可以看作是定义的集合 ExtDefList ExtDef ExtDefList  描述的是定义的集合 ExtDef Specifier Dec SEMI | Specifier FunDec CompSt | VOID FunDec CompSt 定义：全局变量的定义、有返回值函数的定义、无返回值函数的定义 Specifier TYPE int或者float VarDec ID 变量的声明，即标识符 FunDec ID LP VarList RP //含参函数头的定义 func(a) | ID LP RP //不含参函数头定义. func() | MAIN LP RP 函数的声明：含参函数的声明，不含参数函数的声明，main函数的声明 VarList ParamDec 函数参数列表，这里只支持一个参数的参数列表 ParamDec Specifier VarDec 参数列表中，每个变量的声明例如int a CompSt LC DefListAndStmtList RC 函数体，由花括号包裹的定义和statement列表 DefListAndStmtList Def DefListAndStmtList | Stmt DefListAndStmtList  | declaration和statement的集合 StmtExp SEMI |CompSt |RETURN Exp SEMI |IF LP Exp RP Stmt |IF LP Exp RP Stmt ELSE Stmt |WHILE LP Exp RP Stmt | FOR LP Exp SEMI Exp SEMI Exp RP Stmt | FOR LP SEMI Exp SEMI Exp RP Stmt | FOR LP Exp SEMI SEMI Exp RP Stmt | FOR LP Exp SEMI Exp SEMI RP Stmt | FOR LP SEMI Exp SEMI RP Stmt | FOR LP SEMI SEMI RP Stmt |EASY SEMI statement的定义：函数体，return语句，if语句，while循环，for循环，break语句，continue语句等 Def Specifier Dec SEMI 局部变量的声明 Dec VarDec |VarDec ASSIGNOP Exp 局部变量声明的写法：形如a 或者 a=1 Exp Exp ASSIGNOP Exp | Exp RELOP Exp | Exp PLUS Exp | Exp MINUS Exp | Exp STAR Exp | Exp DIV Exp |MINUS Exp |ID LP Exp RP |ID LP RP | ID | INT | FLOAT 赋值语句，布尔表达式，加减乘除语句，取相反数，函数使用，标示符等语句 与C语言的区别： - 程序不必满足有且只有一个main函数的条件 - 函数没有必要先声明再使用 - for 循环的第一个表达式，不支持声明局部变量 ## 3.语法树输出实现 使用一个多叉树和一个单项链表构造并输出语法树 多叉树的实现：多叉树的主要作用是构造各个子语法树（以非终结符为单位） - type：节点类型。type=0，代表为中间节点，type=1，代表叶子节点data：节点值（终结符或非终结符） - length：子节点个数 - leaves是一个节点指针的数组，长度固定为9，其中有效值个数为length个，存储指向 子节点的指针 ```c //树节点 typedef struct TreeNode{ int type; int length; struct TreeNode\* leaves[9]; char\* data; }TreeNode, \*Tree; ``` #### 多叉树操作 对于终结符，创建一个叶子节点，参数为终结符的值。默认type=1 ，length=0，叶子节点指针均指向空 ```c //创建叶子节点 Tree createLeaf(char\* rootData){ int i = 0; Tree T = (Tree)malloc(sizeof(TreeNode)); if (T != NULL){ T -> type = 1; T -> data = rootData; T -> length = 0; for (i = 0 ; i < 9 ; i++){ T -> leaves[i] = NULL; } }else{ exit(-1); } return T; } ``` 对于非终结符，创建一个中间节点，并连接对应的子节点。参数为非终结符值、子节点 指针数组、子节点个数，type = 0 ```c //链接叶子节点和根节点 Tree createTree(char\* root, TreeNode\*\* leaves, int length){ int i = 0; Tree T = (Tree)malloc(sizeof(TreeNode)); if (T == NULL){ exit(-1); }else{ T -> type = 0; T -> data = root; T -> length = length; for (i = 0 ; i < 9 ; i++){ T -> leaves[i] = leaves[i]; } } } ``` 链表实现：链表的主要作用是按照语法分析（自底向上）顺序存储终结符子语法树，用以连 接各子语法树 data：指向一棵子语法树根节点的指针