编译原理课程第4讲.ppt

《编译原理课程第4讲.ppt》由会员分享，可在线阅读，更多相关《编译原理课程第4讲.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、温故知新温故知新正规式正规式计算机计算机计算机计算机实现实现实现实现状态转换图状态转换图不确定有不确定有不确定有不确定有限自动机限自动机限自动机限自动机确定有限确定有限确定有限确定有限自动机自动机自动机自动机等价等价等价等价子集构造法子集构造法子集构造法子集构造法最简确定最简确定最简确定最简确定有限自动有限自动有限自动有限自动机机机机等价等价等价等价非形式化非形式化非形式化非形式化描述的语描述的语描述的语描述的语言言言言状态列举法状态列举法状态列举法状态列举法合并不可区别状态合并不可区别状态合并不可区别状态合并不可区别状态手工实现手工实现手工实现手工实现用正规式语法结构来指导构造过程用正规式语

2、法结构来指导构造过程用正规式语法结构来指导构造过程用正规式语法结构来指导构造过程？词法分析器的生成器词法分析器的生成器词法分析器的生成器词法分析器的生成器2.5 词法分析器的生成器词法分析器的生成器 用用Lex建立词法分析器的步骤建立词法分析器的步骤Lex编译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.ca.outa.out输入流输入流记号序列记号序列2.5 词法分析器的生成器词法分析器的生成器LexLex程序包括三个部分程序包括三个部分 声明声明声明声明 翻译规则翻译规则翻译规则翻译规则 辅助过程辅助过程辅助过程辅助过程Lex程序的翻译规则程序的翻译规则

3、p p1 1 动作动作动作动作11 p p2 2 动作动作动作动作22 p pn n 动作动作动作动作n n 2.5 词法分析器的生成器词法分析器的生成器例例-声明部分声明部分%/*常常常常量量量量LT,LT,LE,LE,EQ,EQ,NE,NE,GT,GT,GE,GE,WHILE,WHILE,DO,DO,ID,ID,NUMBER,RELOPNUMBER,RELOP的定义的定义的定义的定义*/%/*正规定义正规定义正规定义正规定义 */delimdelim t n t n wswsdelimdelim+letterletterA A Za Za z zdigitdigit00 99ididlet

4、ter(letter|digit)letter(letter|digit)*numbernumberdigitdigit+(.digit(.digit+)?(E+)?(E+?digit?digit+)?)?2.5 词法分析器的生成器词法分析器的生成器例例-翻译规则部分翻译规则部分wsws/*没有没有没有没有动动动动作，也不返回作，也不返回作，也不返回作，也不返回 */whilewhilereturn(WHILE);return(WHILE);dodoreturn(DO);return(DO);ididyylval=install_id();return(ID);yylval=install_i

5、d();return(ID);numbernumber yylval=install_num(yylval=install_num();return);return(NUMBER);(NUMBER);“”“”yylval=LT;return(RELOP);yylval=LT;return(RELOP);“=”“=”yylval=LE;return(RELOP);yylval=LE;return(RELOP);“=”“=”yylval=EQ;return(RELOP);yylval=EQ;return(RELOP);“”“”yylval=NE;return(RELOP);yylval=NE;re

6、turn(RELOP);“”“”yylval=GT;return(RELOP);yylval=GT;return(RELOP);“=”“=”yylval=GE;return(RELOP);yylval=GE;return(RELOP);2.5 词法分析器的生成器词法分析器的生成器例例-辅助过程部分辅助过程部分install_ id()install_ id()/*把把把把词词词词法法法法单单单单元装入符号表并返回指元装入符号表并返回指元装入符号表并返回指元装入符号表并返回指针针针针。yytextyytext指向指向指向指向该词该词该词该词法法法法单单单单元的第一个字符，元的第一个字符，元的第一

7、个字符，元的第一个字符，yylengyyleng给给给给出的它的出的它的出的它的出的它的长长长长度度度度*/install_num()install_num()/*类类类类似似似似上上上上面面面面的的的的过过过过程程程程，但但但但词词词词法法法法单单单单元元元元不不不不是是是是标标标标识识识识符符符符而而而而是是是是数数数数 */2.5 词法分析器的生成器词法分析器的生成器int num_lines=0,num_chars=0;int num_lines=0,num_chars=0;%n +num_lines;+num_chars;n +num_lines;+num_chars;.+num_c

8、hars;.+num_chars;%main()main()yylex();yylex();printf(#of lines=%d,#of chars=%dn,num_lines,num_chars);printf(#of lines=%d,#of chars=%dn,num_lines,num_chars);上机实验例子上机实验例子上机实验例子上机实验例子example.lexample.l2.5 词法分析器的生成器词法分析器的生成器hello worldwo ai tian an men hello world i love上机实验例子上机实验例子上机实验例子上机实验例子example.l

9、example.llex.yy.exelex.yy.exe#of lines=3,#of chars=49本本 章章 要要 点点源程序源程序字符流字符流顺顺序序组组合合词法词法单元单元词法词法记号记号模模式式非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组组合合串串语言语言集集合合集集合合字母表字母表名名字字连接连接 指数指数和和 LUM连接连接 LM闭包闭包 L*正闭包正闭包 L+计算机计算机计算机计算机实现实现实现实现状态状态转换转换图图不确不确不确不确定有定有定有定有限自限自限自限自动机动机动机动机确定确定确定确定有限有限有限有限自动自动自动自动机机机机等等等等价价价价

10、子集构子集构子集构子集构造法造法造法造法最简最简最简最简确定确定确定确定有限有限有限有限自动自动自动自动机机机机状态列举法状态列举法状态列举法状态列举法合并不合并不合并不合并不可区别可区别可区别可区别状态状态状态状态手工手工手工手工实现实现实现实现正规式语正规式语正规式语正规式语法结构法结构法结构法结构Lex作业作业1 1、从、从、从、从ftpftp下载下载下载下载“软件学院编译原理实践软件学院编译原理实践软件学院编译原理实践软件学院编译原理实践.zip.zip”，阅读教程中有关，阅读教程中有关，阅读教程中有关，阅读教程中有关PL/0PL/0词法分析器的源代码。词法分析器的源代码。词法分析器的

11、源代码。词法分析器的源代码。2 2、从、从、从、从ftpftp下载下载下载下载“lex_lex_实验实验实验实验.zip.zip”，按照，按照，按照，按照“flex “flex 说明说明说明说明.txt”.txt”要求要求要求要求完成如下上机题完成如下上机题完成如下上机题完成如下上机题(选作选作选作选作)：1 1、编写一个词法分析器，它针对输入文件，实现以下功能：、编写一个词法分析器，它针对输入文件，实现以下功能：、编写一个词法分析器，它针对输入文件，实现以下功能：、编写一个词法分析器，它针对输入文件，实现以下功能：1 1）每遇到你的学号，就输出你的名字，对于其他的串原样输出。）每遇到你的学号

12、，就输出你的名字，对于其他的串原样输出。）每遇到你的学号，就输出你的名字，对于其他的串原样输出。）每遇到你的学号，就输出你的名字，对于其他的串原样输出。2 2）统计输入文件中字母的数目。）统计输入文件中字母的数目。）统计输入文件中字母的数目。）统计输入文件中字母的数目。例如：（以肖永跃的上机题为例）：例如：（以肖永跃的上机题为例）：例如：（以肖永跃的上机题为例）：例如：（以肖永跃的上机题为例）：输入文件如下所示：输入文件如下所示：输入文件如下所示：输入文件如下所示：200213001 hello world200213001 hello worldwo ai tian an men wo ai tian an men hello world i lovehello world i love200213001200213001输出应该如下所示：输出应该如下所示：输出应该如下所示：输出应该如下所示：肖永钦肖永钦肖永钦肖永钦 hello world hello worldwo ai tian an menwo ai tian an menhello world i lovehello world i love肖永钦肖永钦肖永钦肖永钦#of ids=11,#of chars=66#of ids=11,#of chars=66