任课老师：戴新宇 助教： 尚迪(shangd@nlp.nju.edu.cn) 胡光能(hugn@nlp.nju.edu.cn) 实验一 词法分析和语法分析 任课老师：戴新宇 助教： 尚迪(shangd@nlp.nju.edu.cn) 胡光能(hugn@nlp.nju.edu.cn) 2014年3月20日

编译器模块分解图 词法分析 语法分析 C--源代码 字符 语法树 单元 汇编代码 语义分析 中间代码生成 机器代码生成 实验目的：实现类C（C--)语言的编译器 四个阶段：【词法分析和语法分析】，语义分析，中间代码生成，机器代码生成 http://www.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/00/Slides00.pdf

概要 提交说明 实验任务（必做 + 选做） 编译环境及过程 实验讲解 词法分析与flex 语法分析与bison Flex Bison 本次实验任务：输入：C--源文件；输出：C--语法分析树

提交说明 地址：ftp://114.212.190.181: 22 用户名和密码：upload upload 格式：学号+实验编号命名的压缩包 (zip/rar) 如：121220000_lab1.rar 截止日期：4月12日 晚上12：00之前 内容： 源程序(ex1.l, ex1.y; 额外的.c文件) 可执行程序(命名为 parser) 报告PDF(完成的功能点，编译步骤，实现方法，结点的数据结构表示；不超过3页) 备注：可重新提交 加后缀：121220000_lab1_1.rar 121220000_lab1_2.rar

实验任务 必做：(./parser test.cmm) 选做： 无错误：打印语法树 识别错误类型1: 词法错误 识别错误类型2: 语法错误 选做1：两种风格的注释：//, /* */ 选做2：八进制数：012 选做3：十六进制：0xa, 0Xa, 0xA, 0XA 选做4：指数形式的浮点数：1E1, 01e1

if (a[1][2]==0) i=1 else i = 0; } int main() { int I = 1; int j = ~I; } int inc() { int i; i = i+1; } Error type 1 at line 4: Mysterious character '~' int main() { float a[10][2]; int i; a[5,3] = 1.5; if (a[1][2]==0) i=1 else i = 0; } Error type 2 at line 4: syntax error Error type 2 at line 5: syntax error

编译环境及过程 ./parser test.c //测试命令 GNU Flex, GNU Bison, GCC, Linux Ubuntu sudo apt-get install flex sudo apt-get install bison 源文件{ex1.l, ex1.y}  可执行程序parser Flex： ex1.l  lex.yy.c Bison: ex1.y  ex1.tab.c GCC： *.c  parser ./parser test.c //测试命令

-ll: lib of lex -lfl: lib of flexx -ly: lib of yacc 编译方法 Flex lex.yy.c ex1.l ex1.tab.c ex1.y Bison GCC parser 编译命令： flex ex1.l bison -d ex1.y gcc -o parser ex1.tab.c http://stackoverflow.com/questions/1553744/how-does-gcc-recognize-that-lfl-corresponds-to-flex-library -ll: lib of lex -lfl: lib of flexx -ly: lib of yacc

Flex & Bison #include “ex1.tab.h” #include "lex.yy.c" %{ ex1.l Declarations #include “ex1.tab.h” %} Definitions (RegEx) %% Rules subroutines (e.g main) %{ ex1.y Declarations #include "lex.yy.c" %} Definitions (%Token) %% Productions subroutines http://dinosaur.compilertools.net/ http://www.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/050%20Flex%20In%20A%20Nutshell.pdf http://www.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/120%20Introducing%20bison.pdf

Flex： .l文件格式 %{ Declarations %} Definitions %% Rules //将保留字置于标识符{id}之前 subroutines

Flex： 一个简单的flex程序 flex test.l gcc lex.yy.c –lfl –o parser {comment} {comment2} {ws} Int Float struct return while if else {int} {float} {id} ";“ ",“ "=“ "<“ …… flex test.l gcc lex.yy.c –lfl –o parser ./parser test.cmm

Flex：你需要做的内容 id {letter}({letter}|{digit})* {id} { yytext, yyleng: 词素字符串 yylineno: %option yylineno yylval: 全局变量，当前词法单元的属性值 id {letter}({letter}|{digit})* {id} { printf("Line %d:(ID , %s)\n",yylineno,yytext); } {id} { //printf("Line %d:(ID , %s)\n",yylineno,yytext); yylval = (struct treeNode*)malloc(sizeof(struct treeNode)); yylval->lineno = yylineno; yylval->type = 1; yylval->tokentype = 26; yylval->name = malloc(strlen(yytext)+1); strcpy(yylval->name,yytext); return ID; } http://cs.nju.edu.cn/dxy/%E5%AE%9E%E9%AA%8C1.pdf

Bison: .y文件格式 %{ Declarations %} Definitions //优先级与结合性 %% Productions subroutines %right ASSIGNOP %left AND %left RELOP %left PLUS MINUS %left STAR DIV %right NOT UMINUS %left DOT LB RB LP RP http://cs.nju.edu.cn/dxy/%E9%99%84%E5%BD%95A.pdf Exp | MINUS EXP %prec UMINUS

Bison语法树创建与打印 多叉树的构建： struct Node* createNode(int arity, …); 递归层次的前序遍历 Exp : ID { $$ = createNode(1,$1); } Exp : MINUS EXP { $$ = createNode(2,$1,$2); } #include<stdarg.h> struct Node* createNode(int arity, …); 递归层次的前序遍历 void printNode(struct Node* root, int nLayer); printf http://www.cplusplus.com/reference/cstdarg/va_start/

Bison文法符号结点的数据结构 保存的信息：struct Node{ … }; 结点类型： 非终结符，终结符(数, 标识符…) 结点名字： Exp，TYPE，ID 所在行号： %option yylineno 字符串属性值：TYPE.int，ID.lexeme 数值属性值：INT，FLOAT 多叉树孩子：int arity, struct Node* children[N]; //vector<Node*> -…(可扩展) Pure C implementation

yyerror(char* str){ printf(“syntax error\n”); } 语法解析的错误恢复产生式 Bison在当前状态对yylex()返回的token没有定义 时即发生了语法错误，调用yyerror: yyerror(char* str){ printf(“syntax error\n”); } Bison不断丢弃词法单元直至遇到同步 单元 (例如：分号，右括号 ) 机制：错误恢复产生式 Stmt: error SEMI 本科教学版：4.9.4 P175 http://oreilly.com/linux/excerpts/9780596155971/error-reporting-recovery.html

Warning！！！ 任何形式的代码抄袭都是不能容忍的 一旦发现，抄袭者和被抄袭者均为0分