《词法分析程序设计与自动构造.ppt》由会员分享，可在线阅读，更多相关《词法分析程序设计与自动构造.ppt（24页珍藏版）》请在金锄头文库上搜索。
1、武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌词法分析程序设计与自动构造彭德巍2011.10.12武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌主要内容词法分析程序设计词法分析程序自动构造武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌1.1.词法分析程序设计词法分析程序设计词法分析总控程序见图词法分析总控程序见图1。 界限符界限符运算符运算符字母字母数字数字结结 束束 符符“#”开始开始到到 输输 入入 流流 中中 读读 下下 一一 字字 符符C CharCharChar是是 什什 么么？初始化初始化标识符和关键字标识符和关键字词法分析子程序词法分析子
2、程序无符号数无符号数词法分析子程序词法分析子程序运算符运算符词法分析子程序词法分析子程序界限符界限符词法分析子程序词法分析子程序结束结束图图1 词法分析总控程序词法分析总控程序武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。以无符号数为例：给定语法图移条件，那么自动机就成为一个程序了。以无符号数为例：给定语法图2 2，构造自动机见图构造自动机见图3 3。 d.de+ +- -d图图2 无符号数的语法图无符号数的语法图武汉理工大
3、学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌图图3 无符号数的自动机无符号数的自动机12345 560dd+ +- -.ed.otherotherddothered7e武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌开始开始0N，P，j;1e数字数字d;N*10+dN N是数字？是数字？Y 读字符读字符charN NYN N整型量整型量标记标记C1是是 吗？吗？ 读字符读字符char是是e吗吗？是是 吗？吗？1 1e 读字符读字符charYN NYN N 读字符读字符char是数字？是数字？Y数字数字d;N*10+dN N；j+1j+1j是数字？是数字？Y 读字符读字符cha
4、rERRORN NN N实型量实型量标记标记C1是数字？是数字？Y数字数字d;P*10+dP PY 读字符读字符charERRORN NN N实型量标记实型量标记C1N N*10e*P-je*P-j t结束结束YN N整整数数部部分分小小数数部部分分是是吗？吗？是数字？是数字？指指数数部部分分N N图图4 4 无符号数词法分析流程图无符号数词法分析流程图最后可得到无符号数分析算法流图见图最后可得到无符号数分析算法流图见图4 4。 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌2.2.词法分析程序设计自动构造词法分析程序设计自动构造FlexFlex简介简介FlexFlex源文件分析
5、源文件分析FlexFlex词法分析程序设计自动构造演示词法分析程序设计自动构造演示实验任务和要求实验任务和要求 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌2.1Flex简介FLEX通过读取一个有规定格式的文本文件，输出一个如下所示的C语言源程序。输入文件扩展名为.lFlex输出文件Lex.yy.c武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌Flex源文件格式LEX对源文件的格式要求非常严格，所以书写时一定要注意。LEX的源文件由三个部份组成，每个部分之间用顶行的“%”分割，其格式如下：定义部份规则部份用户附加C语言部份武汉理工大学计算机科学系陈天煌武汉理工大学
6、计算机科学系陈天煌定义部分定义部份由C语言代码、模式的宏定义组成。除宏定义外，定义部分的其余代码必须用符号%和%括起来。另外，flex使用的C语言库文件和外部变量以及部分声明的函数，也应分别置于%和%之内。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例如下面是一个flex语言的说明部分：%#include“stdio.h”intnum=0%DIGIT0-9IDA-Za-zA-Za-z0-9_*%注意：这里起标识符作用的%和%、%必须要顶行写武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌规则部分规则部份是LEX源文件的核心部份，它包括一组模式和在生成分析器识别相应模
7、式后对相应模式进行处理的C语言动作(Action)。格式如下：C语言代码模式1动作1模式2|模式3动作3武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌用户附加C语言部份支持规则动作部分所需要的处理过程，是对规则部分中动作的补充。FLEX对此部份不作任何处理，仅仅将其直接拷贝到输出文件lex.yy.c的尾部。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌Flex中模式的定义digit0-9number(-|+)?digit+hexnumber0x(digit|a-fA-F)+lettera-zA-Zidentifier(letter|_)(number|letter|
8、_)*newlinenwhitespacet+string*comment#*#武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌Flex中模式的定义-PL/0语言digit0-9lettera-zA-Znumberdigit+identifierletter(letter|digit)*wrongid(digit+)letter(letter|digit)*newlinenwhitespacet+武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌Lex.yy.c中的全局变量和函数File*yyin/*指向词法分析器要接收的待分析程序的指针。如果不指定则默认指向标准输入终端
9、（键盘）。如果我们待分析的程序是文件形式我们可以将这个指针指向该文件的地址指针*/File*yyout/*同上，唯一不同是该指针指向输出的文件。默认指向标准输出终端（屏幕）。我们可通过重定向该指针改变输出流方向。*/Char*yytext/*指向识别的单词的地址；用来保存扫描一次匹配的字符串。*/Intyyleng/*匹配的字符串中字符的个数。*/武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌Lex.yy.c中的全局变量和函数ECHO/*flex的默认动作，一般来说是输出字符串*/yywrap（）/*扫描一次完后要调用的函数，返回一个值，当这个值为1的时候分flex就不再继续扫描
10、。*/yyrestart（）/*重新定向flex的输入*/武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌Flex源文件分析(test.l)%intwc=0;/*wordcount*/%a-zA-Z+wc+;%intmain(void)intn=yylex();returnn;intyywrap(void)printf(wordcount:%dn,wc);return1;武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌Flex词法分析产生器实现原理词法分析器自动生成器的核心是lex编译器，lex编译器的功能是将lex源程序变换为一个能识别该语言单词的词法分析器。而该词法
11、分析器像有穷自动机一样去识别处理单词。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌flex词法分析产生器实现原理基于lex源程序，lex编译器的实现步骤大致是：对lex源程序识别规则中的每个pi构造一个相应的NFANi。引入唯一初态S，从初态S通过弧将所有NFANi（i=1，n）连接成新的NFAN。、两步实际是完成从正规式到非确定有限自动机的构造。对NFAN确定化，产生DFAN。DFAN最小化。给出控制程序。产生一个名为intyylex()的词法分析函数，将之拷贝到输出文件lex.yy.c中。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌FlexFlex词法分析程
12、序设计自动构造演示词法分析程序设计自动构造演示TestTest1Test2武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌实验内容和要求1、阅读flex源文件test.l，test1.l然后生成相应lex.yy.c文件，编译该文件生成相应exe文件，然后运行exe文件，观察输出。2、利用flex生成词法分析程序，分别统计标识符，数字和错误标识符的个数，并输出到文件result.txt标识符：字母，数字和下划线，仅以字母开始数字：无符号数字错误标识符：以数字开始后接字母，形如：“123a”，“62aa12a”武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌实验内容和要求3
13、.利用flex生成词法分析程序，识别输入程序中的关键字，标识符，数字，运算符、界符和错误标识符，并输出到文件result.txt关键字关键字：ifthendowhilestringint标识符标识符：字母，数字和下划线，仅以字母开始数字数字：无符号数字错误标识符错误标识符：以数字开始后接字母，形如：“123a”，“62aa12a”运算符运算符：+-*/=界符界符:(),;武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌实验题：词法分析程序设计与自动生成。实验题：词法分析程序设计与自动生成。上机验收时间：上机验收时间：2010.10.12 18:3021:30地点：计算机学院实验中心地点：计算机学院实验中心3楼楼要求：请同学们务必在实验开始前熟悉要求：请同学们务必在实验开始前熟悉C语言语言和和flex，到实验室时主要是进行调试和验收，到实验室时主要是进行调试和验收，不参加验收则不能获得实验成绩。不参加验收则不能获得实验成绩。报告提交时间：报告提交时间：2010.10.18-19上午的课间上午的课间
