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

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

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

2 编译器模块分解图 词法分析 语法分析 C--源代码 字符 语法树 单元 汇编代码 语义分析 中间代码生成 机器代码生成
实验目的：实现类C（C--)语言的编译器 四个阶段：【词法分析和语法分析】，语义分析，中间代码生成，机器代码生成

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

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

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

6 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

7 编译环境及过程 ./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 //测试命令

8 -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 -ll: lib of lex -lfl: lib of flexx -ly: lib of yacc

9 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

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

11 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

12 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; }

13 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 Exp | MINUS EXP %prec UMINUS

14 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

15 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

16 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

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