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

词法分析程序设计与自动构造第一页，共二十四页，2022年，8月28日主要内容词法分析程序设计词法分析程序自动构造第二页，共二十四页，2022年，8月28日1.词法分析程序设计词法分析总控程序见图1。

界限符运算符字母数字结束符“#”开始到输入流中读下一字符CharChar是什么？初始化标识符和关键字词法分析子程序无符号数词法分析子程序运算符词法分析子程序界限符词法分析子程序结束图1词法分析总控程序第三页，共二十四页，2022年，8月28日

若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。以无符号数为例：给定语法图2，构造自动机见图3。

d.de+-d图2无符号数的语法图第四页，共二十四页，2022年，8月28日图3无符号数的自动机1234560dd+ε-.ed.otherotherddothered7e第五页，共二十四页，2022年，8月28日开始0N，P，j;1e数字d;N*10+dN是数字？Y

读字符charNYN整型量标记C1是’－’吗？

读字符char是’e’吗？是’－’吗？－1e

读字符charYNYN

读字符char是数字？Y数字d;N*10+dN；j+1j是数字？Y

读字符charERRORNN实型量标记C1是数字？Y数字d;P*10+dPY

读字符charERRORNN实型量标记C1N*10e*P-jt结束YN整数部分小数部分是’．’吗？是数字？指数部分N图4无符号数词法分析流程图最后可得到无符号数分析算法流图见图4。

第六页，共二十四页，2022年，8月28日2.词法分析程序设计自动构造Flex简介Flex源文件分析Flex词法分析程序设计自动构造演示实验任务和要求

第七页，共二十四页，2022年，8月28日2.1Flex简介

FLEX通过读取一个有规定格式的文本文件，输出一个如下所示的C语言源程序。第八页，共二十四页，2022年，8月28日Flex源文件格式

LEX对源文件的格式要求非常严格，所以书写时一定要注意。

LEX的源文件由三个部份组成，每个部分之间用顶行的“%%”分割，其格式如下：

定义部份

％％

规则部份

％％

用户附加C语言部份第九页，共二十四页，2022年，8月28日

定义部分定义部份由C语言代码、模式的宏定义组成。除宏定义外，定义部分的其余代码必须用符号%{和%}括起来。另外，flex使用的C语言库文件和外部变量以及部分声明的函数，也应分别置于%{和%}之内。第十页，共二十四页，2022年，8月28日例如下面是一个flex语言的说明部分：%{

#include“stdio.h”intnum=0%}DIGIT

[0-9]ID

[A-Za-z][A-Za-z0-9_]*%%注意：这里起标识符作用的%%和%{、%}必须要顶行写第十一页，共二十四页，2022年，8月28日规则部分规则部份是LEX源文件的核心部份，它包括一组模式和在生成分析器识别相应模式后对相应模式进行处理的C语言动作(Action)。格式如下：

C语言代码

模式1动作1

模式2|

模式3动作3第十二页，共二十四页，2022年，8月28日用户附加C语言部份支持规则动作部分所需要的处理过程，是对规则部分中动作的补充。FLEX对此部份不作任何处理，仅仅将其直接拷贝到输出文件lex.yy.c的尾部。第十三页，共二十四页，2022年，8月28日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"#"[^#]*"#"第十四页，共二十四页，2022年，8月28日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]+第十五页，共二十四页，2022年，8月28日中的全局变量和函数File*yyin

/*指向词法分析器要接收的待分析程序的指

针。如果不指定则默认指向标准输入终端（

键盘）。如果我们待分析的程序是文件形式

我们可以将这个指针指向该文件的地址指针*/File*yyout/*同上，唯一不同是该指针指向输出的文件

。默认指向标准输出终端（屏幕）。我们

可通过重定向该指针改变输出流方向。*/Char*yytext/*指向识别的单词的地址；用来保存扫描

一次匹配的字符串。*/Intyyleng

/*匹配的字符串中字符的个数。*/第十六页，共二十四页，2022年，8月28日中的全局变量和函数ECHO/*flex的默认动作，一般来说是输出字符串*/yywrap（）/*扫描一次完后要调用的函数，返回一个值，当这个值为1的时候分flex就不再继续扫描。*/yyrestart（）/*重新定向flex的输入*/第十七页，共二十四页，2022年，8月28日Flex源文件分析(test.l)%{intwc=0;/*wordcount*/%}%%[a-zA-Z]+{wc++;}%%intmain(void){intn=yylex();returnn;}intyywrap(void){printf("wordcount:%d\n",wc);return1;}第十八页，共二十四页，2022年，8月28日Flex词法分析产生器实现原理词法分析器自动生成器的核心是lex编译器，lex编译器的功能是将lex源程序变换为一个能识别该语言单词的词法分析器。而该词法分析器像有穷自动机一样去识别处理单词。第十九页，共二十四页，2022年，8月28日flex词法分析产生器实现原理基于lex源程序，lex编译器的实现步骤大致是：

⑴对lex源程序识别规则中的每个pi构造一个相应的NFANi。

⑵引入唯一初态S，从初态S通过ε弧将所有NFANi（i=1，…，n）连接成新的NFAN’。⑴、⑵两步实际是完成从正规式到非确定有限自动机的构造。

⑶对NFAN’确定化，产生DFAN。

⑷DFAN最小化。

⑸给出控制程序。产生一个名为intyylex()的词法分析函数，将之拷贝到输出文件中。第二十页，共二十四页，2022年，8月28日Flex词法分析程序设计自动构造演示

TestTest1Test2第二十一页，共二十四页，2022年，8月28日实验内容和要求1、阅读flex源文件test.l，test1.l然后生成相应文件，编译该文件生成相应exe文件，然后运行exe文件，观察输出。2、利用flex生成词法分析程序，分别统计标识符，数字和错误标识符的个数，并输出到文件result.txt

标识符：字母，数字和下划线，仅以字母开始

数字：无符号数字

错误标识符：以数字开始后接字母，形如：“123a”，“62aa12a”第二十二页，共二十四页，2022年，8月28日实验内容和要求3.利用flex生成词法分析程序，识别输入程序中的关键字，标识符，数字，运算符、界符和错误标识符，并输出到文件result.txt关键字：ifthendowhilestringint标识符：字母，数字和下划线，仅以字母开始

数字：无符号数字

错误标识符：以数字开始后接字母，形如：“123a”，“62aa12a”运算符：+-*/><