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

词法分析程序设计与自动构造,彭德巍 2011.10.12,主要内容,词法分析程序设计 词法分析程序自动构造,1.词法分析程序设计,词法分析总控程序见图1。,界限符,运算符,字母,数字,结束符“#”,开始,Char是什么？,初始化,标识符和关键字 词法分析子程序,无符号数 词法分析子程序,运算符 词法分析子程序,界限符 词法分析子程序,结束,图1 词法分析总控程序,若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。以无符号数为例：给定语法图2，构造自动机见图3。,开始,0N，P，j; 1e,数字d; N*10+dN,是数字？,Y,N,Y,N,整型量 标记C1,是吗？,是e吗？,是吗？,1e,Y,N,Y,N,是数字？,Y,数字d;N*10+dN； j+1j,是数字？,Y,ERROR,N,N,实型量 标记C1,是数字？,Y,数字d; P*10+dP,Y,ERROR,N,N,实型量标记C1,N*10e*P-j t,结束,Y,N,整数部分,小数部分,是吗？,是数字？,指数部分,N,图4 无符号数词法分析流程图,最后可得到无符号数分析算法流图见图4。,2.词法分析程序设计自动构造,Flex简介 Flex源文件分析 Flex词法分析程序设计自动构造演示 实验任务和要求,2.1 Flex简介,FLEX通过读取一个有规定格式的文本文件，输出一个如下所示的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 “0x“(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源程序识别规则中的每个pi构造一个相应的NFA Ni。 引入唯一初态S，从初态S通过弧将所有NFA Ni（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” 运算符：+ - * / 界符: ( ) , ;,实验