助教：胡光能，解定宝 编译原理讲师：戴新宇

Presentation on theme: "助教：胡光能，解定宝 编译原理讲师：戴新宇"— Presentation transcript:

1 助教：胡光能，解定宝 编译原理讲师：戴新宇 hugn@nlp.nju.edu.cn
实验一 讲解 with pure C 助教：胡光能，解定宝 编译原理讲师：戴新宇 2014年3月20日

2 Phases of a Compiler Lexical Analyzer Syntax Analyzer Symbol Table
Char Stream Token Stream Syntax Tree Semantic Analyzer Intermediate Code Generator Code Generator Machine Code 实验目的：实现类C（C--)语言的编译器 四个阶段：【词法分析和语法分析】，语义分析，中间代码生成，机器代码生成 Symbol Table

3 Outline 提交说明 实验任务（必做 + 选做） 编译环境及过程 实验讲解 词法分析与flex 语法分析与bison 文法二义性消除
语法树创建与打印 文法符号结点的数据结构 语法解析的错误恢复 本次实验任务：输入：C--源文件；输出：C--语法分析树

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

5 实验任务 必做： 选做： 预备：熟悉 C--文法和实验要求 错误类型1: 词法错误(词法未定义字符) 错误类型2: 语法错误(如[3,9])
选做1：两种风格的注释：//, /* */ 选做2：八进制数：012 选做3：十六进制：0xa, 0Xa, 0xA, 0XA 选做4：指数形式的浮点数：1E1, 01e1

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

7 -ll: lib of lex -lfl: lib of flex -ly: lib of yacc
编译 方法 Flex lex.yy.c ex1.l Bison ex1.tab.c ex1.y GCC parser flex ex1.l bison -d ex1.y gcc -o parser ex1.tab.c -ll (-lfl) -ll: lib of lex -lfl: lib of flex -ly: lib of yacc

8 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

9 启动语法分析器 int main(int argc, char** argv){ if(argc <= 1) return 1; FILE* f = fopen(argv[1],"r"); if(!f) { perror(argv[1]); return 1; } yyrestart(f); //输入文件指针置为 yyin = f yyparse(); //main函数启动解析器 return 0; } 从main函数中启动语法解析器

10 Flex预定义变量 yytext, yyleng: 词素字符串 yylineno: %option yylineno
yylval: 全局变量，当前词法单元的属性值 {id} { strncpy(id_lexeme, yytext, yyleng); yylval.pNode = createNode( …); return ID; } %union { int val ; char* str; struct Node* pNode; }

11 保留字和标识符 %{ Declarations %} Definitions %% Rules //将保留字置于标识符{id}之前 subroutines

12 文法二义性: 操作符优先级与结合性 %{ 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

13 文法二义性: IF-ELSE配对 Stmt: IF LP Exp RP Stmt | IF LP Exp RP Stmt ELSE Stmt
%nonassoc IFX %nonassoc ELSE Stmt: IF LP Exp RP Stmt %prec IFX | IF LP Exp RP Stmt ELSE Stmt

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

15 文法符号结点的数据结构 保存的信息：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 参考资料 Aho 编译原理： 斯坦福 编译原理： 指导攻略： 可变参数个数: 错误恢复：
斯坦福 编译原理： 指导攻略： 可变参数个数: 错误恢复：