词法分析程序设计与自动构造.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Compiler,武汉理工大学计算机科学系陈天煌,Compile,词法分析程序设计与自动构造,彭德巍,2011.10.12,主要内容,词法分析程序设计,词法分析程序自动构造,1.,词法分析程序设计,词法分析总控程序见图,1,。,界限符,运算符,字母,数字,结束符“,#”,开始,到输入流中读下一字符,C,har,Char,是什么？,初始化,标识符和关键字,词法分析子程序,无符号数,词法分析子程序,运算符,词法分析子程序,界限符,词法分析子程序,结束,图,1,词法分析总控程序,若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。以无符号数为例：给定语法图,2,，构造自动机见图,3,。,d,.,d,e,+,-,d,图,2,无符号数的语法图,图,3,无符号数的自动机,1,2,3,4,5,6,0,d,d,+,-,.,e,d,.,other,other,d,d,other,e,d,7,e,开始,0,N,，,P,，,j;,1,e,数字,d;,N*10+d,N,是数字？,Y,读字符,char,N,Y,N,整型量,标记,C1,是,吗？,读字符,char,是,e,吗？,是,吗？,1,e,读字符,char,Y,N,Y,N,读字符,char,是数字？,Y,数字,d;N*10+d,N,；,j+1,j,是数字？,Y,读字符,char,ERROR,N,N,实型量,标记,C1,是数字？,Y,数字,d;,P*10+d,P,Y,读字符,char,ERROR,N,N,实型量标记,C1,N,*10,e*P-j,t,结束,Y,N,整数部分,小数部分,是,吗？,是数字？,指数部分,N,图,4,无符号数词法分析流程图,最后可得到无符号数分析算法流图见图,4,。,2.,词法分析程序设计自动构造,Flex,简介,Flex,源文件分析,Flex,词法分析程序设计自动构造演示,实验任务和要求,2.1 Flex,简介,FLEX,通过读取一个有规定格式的文本文件，输出一个如下所示的,C,语言源程序。,输入文件,扩展名为,.l,Flex,输出文件,Lex.yy.c,Flex,源文件格式,LEX,对源文件的格式要求非常严格，所以书写时一定要注意。,LEX,的源文件由三个部份组成，每个部分之间用顶行的“,%”,分割，其格式如下：,定义部份,规则部份,用户附加,C,语言部份,定义部分,定义部份由,C,语言代码、模式的宏定义组成。,除宏定义外，定义部分的其余代码必须用符号,%,和,%,括起来。另外，,flex,使用的,C,语言库文件和外部变量以及部分声明的函数，也应分别置于,%,和,%,之内。,例如下面是一个,flex,语言的说明部分：,%,#include“stdio.h”,int num=0,%,DIGIT,0-9,ID,A-Za-zA-Za-z0-9_*,%,注意：这里起标识符作用的,%,和,%,、,%,必须要顶行写,规则部分,规则部份是,LEX,源文件的核心部份，它包括一组模式和在生成分析器识别相应模式后对相应模式进行处理的,C,语言动作,(Action),。格式如下：,C,语言代码,模式,1,动作,1,模式,2|,模式,3,动作,3,用户附加,C,语言部份,支持规则动作部分所需要的处理过程，是对规则部分中动作的补充。,FLEX,对此部份不作任何处理，仅仅将其直接拷贝到输出文件,lex.yy.c,的尾部。,Flex,中模式的定义,digit 0-9,number (-|+)?digit+,hexnumber 0 x(digit|a-fA-F)+,letter a-zA-Z,identifier (letter|_)(number|letter|_)*,newline n,whitespace t+,string *,comment#*#,Flex,中模式的定义,-PL/0,语言,digit 0-9,letter a-zA-Z,number digit+,identifier letter(letter|digit)*,wrongid (digit+)letter(letter|digit)*,newline n,whitespace t+,Lex.yy.c,中的全局变量和函数,File *yyin/*,指向词法分析器要接收的待分析程序的指,针。如果不指定则默认指向标准输入终端（,键盘）。如果我们待分析的程序是文件形式,我们可以将这个指针指向该文件的地址指针,*/,File *yyout /*,同上，唯一不同是该指针指向输出的文件,。默认指向标准输出终端（屏幕）。我们,可通过重定向该指针改变输出流方向。*,/,Char *yytext/*,指向识别的单词的地址；用来保存扫描,一次匹配的字符串。*,/,Int yyleng /*,匹配的字符串中字符的个数。*,/,Lex.yy.c,中的全局变量和函数,ECHO /*flex,的默认动作，一般来说是输出字符串*,/,yywrap,（）,/*,扫描一次完后要调用的函数，返回一个值，当这个值为,1,的时候分,flex,就不再继续扫描。*,/,yyrestart,（）,/*,重新定向,flex,的输入*,/,Flex,源文件分析,(test.l),%,int wc=0;/*word count*/,%,%,a-zA-Z+wc+;,%,int main(void),int n=yylex();,return n;,int yywrap(void),printf(word count:%dn,wc);,return 1;,Flex,词法分析产生器实现原理,词法分析器自动生成器的核心是,lex,编译器,，,lex,编译器的功能是将,lex,源程序变换为一个能识别该语言单词的词法分析器。而该词法分析器像有穷自动机一样去识别处理单词。,flex,词法分析产生器实现原理,基于,lex,源程序，,lex,编译器的实现步骤大致是：,对,lex,源程序识别规则中的每个,p,i,构造一个相应的,NFA N,i,。,引入唯一初态,S,，从初态,S,通过,弧将所有,NFA N,i,（,i=1,，,，,n,）连接成新的,NFA N,。、两步实际是完成从正规式到非确定有限自动机的构造。,对,NFA N,确定化，产生,DFA N,。,DFA N,最小化。,给出控制程序。产生一个名为,int yylex(),的词法分析函数，将之拷贝到输出文件,lex.yy.c,中。,Flex,词法分析程序设计自动构造演示,Test,Test1,Test2,实验内容和要求,1,、阅读,flex,源文件,test.l,，,test1.l,然后生成相应,lex.yy.c,文件，编译该文件生成相应,exe,文件，然后运行,exe,文件，观察输出。,2,、利用,flex,生成词法分析程序，分别统计标识符，数字和错误标识符的个数，并输出到文件,result.txt,标识符：字母，数字和下划线，仅以字母开始,数字：无符号数字,错误标识符：以数字开始后接字母，形如：,“123a”,，,“62aa12a”,实验内容和要求,3.,利用,flex,生成词法分析程序，识别输入程序中的关键字，标识符，数字，运算符、界符和错误标识符，并输出到文件,result.txt,关键字,：,if then do while string int,标识符,：字母，数字和下划线，仅以字母开始,数字,：无符号数字,错误标识符,：以数字开始后接字母，形如：,“123a”,，,“62aa12a”,运算符,：,+-*/,界符,:,(),;,实验题：词法分析程序设计与自动生成。,上机验收时间：,2010.10.12 18:3021:30,地点：计算机学院实验中心,3,楼,要求：请同学们务必在实验开始前熟悉,C,语言和,flex,，到实验室时主要是进行调试和验收，不参加验收则不能获得实验成绩。,报告提交时间：,2010.10.18-19,上午的课间,