基于flex的词法分析器的设计和实现

课程设计1基于Flex的词法分析器设计及实现1.1需求分析1.1.1问题定义1、通过对flex基本知识的阅读，了解其工作原理和过程以及其匹配模式和规则，掌握简单的lex语法和规则；2、在上述基础上能够自主编写出简单且可以运行的词法分析器，实现简单的词法分析功能；3、通过实验，设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。1.1.2功能描述本次编制调试的词法分析器基本可以实现如下简单功能：1、可以匹配识别关键字：elseifswitchforintfloatreturnvoidwhile（所有的关键字都是保留字，并且必须是小写）；2、可以匹配识别专用符号：+-*/====!==;,()[]{}/**/；3、标识符（ID）和数字（NU）通过下列正则表达式定义：ID=letterletter*NUM=digitdigit*letter=a|..|z|A|..|Zdigit=0|..|9；4、可以匹配识别空格（空格由空白、换行符和制表符组成，空格通常被忽略，除了它必须分开ID、NUM关键字）；5、可以识别简单的注释（/*注释内容*/）；1.1.3开发环境及工具介绍1、Window环境下载VisualStudio之后，利用其命令提示窗口进行操作。下载并安装Flex。2、vs2010的编译器cl.exe。3、flex:词法分析器Flex是用来生成程序的工具，他们所生成的程序能够处理结构化输入，最初的Flex是用来生成编译器的，但是后来他们被证明在其他领域也非常有效。Flex是一个SourceForge项目。其依赖于GNUm4宏处理器。Linux和BSD都应该有m4，对于Windos用户来说，Flex被包含在CygeinLinux模拟环境中。什么是FLEX？它是一个自动化工具，可以按照定义好的规则自动生成一个C函数yylex()，也成为扫描器（Scanner）。这个C函数把文本串作为输入，按照定义好的规则分析文本串中的字符，找到符合规则的一些字符序列后，就执行在规则中定义好的动作（Action）。例如在规则中可以这样定义：如果遇到一个换行字符\n，那么就把行计数器的值加一。Flex文件就是一个文本文件，内容包括定义好的一系列词法规则。1.2系统概要设计1.2.1系统体系结构Flex源文件（.l）flex词法分析器的C语言源文件（.h）编译此法分析器的课执行程序图1-1体系结构图开始初始化读入需要分析的语句还有单词未分析？读一个字符是字母？是数字？其他单词分析程序输出单词二元式常数分析程序关键字或标识符分析程序结束是否否是是否图1-2词法分析流程图1.2.2系统模块划分Lex工具是一种词法分析程序生成器，它可以根据词法规则说明书的要求来生成单词识别程序，由该程序识别出输入文本中的各个单词。一般可以分为定义部分规则部分用户子程序部分。其中规则部分是必须的，定义和用户子程序部分是任选的。（1）定义部分：定义部分起始于%{符号，终止于%}符号，其间可以是包括include语句、声明语句在内的C语句。这部分跟普通C程序开头没什么区别。（2）规则部分：规则部分起始于%%符号，终止于%%符号，其间则是词法规则。词法规则由模式和动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组成，这些语句用来对所匹配的模式进行相应处理。需要注意的是，lex将识别出来的单词存放在yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多行执行语句，也可以用{}括起来。（3）用户子程序部分：最后一个%%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子程序可以用在前面的动作中，这样就可以达到简化编程的目的。这里需要注意的是，当编译时不带-ll选项时，是必须加入main函数和yywrap(yywrap将下后面说明)。Lex其实就是词法分析器，通过配置文件*.l，依据正则表达式逐字符去顺序解析文件，并动态更新内存的数据解析状态。Lex善长于模式匹配。词法分析的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析的核心任务是扫描、识别单词且对识别出的单词给出定性、定长的处理；实现词法分析程序的常用途径:自动生成,手工生成。1.3详细设计与实现1.3.1Lex代码的设计与实现lex源代码编写通过对flex的语法学习，掌握了编写的基本原则和步骤，因为实验要求编写一个简单地词法分析器，根据实验所要求实现检查分析的功能，实验代码较为简单，以下是自己编写的实验代码：letter[a-zA-Z\_]定义字母letterdight[0-9]定义数字dightID{letter}({letter})*定义单词ID由若干个字母组成NUM{dight}({dight})*定义数字串NUM由若干个数字组成B{letter}({dight}|{letter})*定义标识符B由数字戒字母组成%{intnchar,nword,nline;nchar字符数nword单词数nline行数intline=1;line为当前行数初始化为1%}%%else|if|elseif|switch|for|int|float|return|void|while{nword++;nchar+=yyleng;printf(第%d行:\t,line);printf(关键字：%s\n,yytext);}若匹配上elseintfloat等上述的关键字：单词数+1；字符数增加相应的个数；输出“第line行yytext\n”;{B}{nword++;nchar+=yyleng;printf(第%d行:\t,line);printf(标识符：%s\n,yytext);}{B}{nword++;nchar+=yyleng;printf(第%d行:\t,line);printf(标识符：%s\n,yytext);}若匹配上B标识符：单词数+1；字符数增加相应的个数；输出“第line行标识符：yytext\n”;{NUM}{nword++;nchar+=yyleng;printf(第%d行:\t,line);printf(数字：%s\n,yytext);}若匹配上NUM数字：单词数+1；字符数增加相应的个数；输出“第line行数字：yytext\n”;\+|\-|\*|\/|\|\|\=|\;|\,|\(|\)|\[|\]|\{|\}{nchar+=yyleng;printf(第%d行:\t,line);printf(与%s\n,yytext);}若匹配上+-*/等与：字符数增加相应的个数；输出“第line行与yytext\n”;\\=|\\=|\=\=|\!\=|\/\*|\*\/{nword++;nchar+=yyleng;printf(第%d行:\t,line);printf(与%s\n,yytext);}若匹配上=等与：字符数增加相应的个数；输出“第line行与yytext\n”;[\t]+{nchar++;}若匹配上制表符：字符数+1；无输出；\n{nline++;line++;nchar++;}若匹配上回车\n：字符数+1；行数+1；当前行数line+1；无输出；[^\t\n]+{nword++;nchar+=yyleng;printf(第%d行:\t,line);printf(其他符号：%s\n,yytext);}若匹配上其他符号：字符数增加相应的个数；输出“第line行其他符号：yytext\n”;%%voidmain(){yylex();调用yylex函数printf(字符数：%d\t单词数：%d\t行数：%d\n,nchar,nword,nline);}最后输出字符数、单词数、行数intyywrap(){return1;}最后将这些代码按照flex语法进行整合得到完整flex源码，得到源程序lex1.l；1.3.2定义部分的设计与实现定义部份由C语言代码、模式的宏定义、条件模式的开始条件说明三部份组成。其中，C代码部份由顶行的%{和}%引入，LEX扫描源文件时将%{和}%之间的部分原封不动的拷贝到输出文件lex.yy.c中。上面的定义部分没有条件模式的开始条件说明部分，只有C语言代码、模式的宏定义。模式宏定义是一个正则表达式的定义，如上面所示的INTEGER[-+]?[1-9][0-9]*。正则表达式的匹配如下：模式解释x配置单个字母x.匹配除换行符’\n’之外的任意字符[xyz]匹配x、y或z[abj-oz]匹配a、b、z及j至o之间的字母[^A-Z]除大写字母A-Z之外的其它字符[^A-Z\n]除大写字母A-Z和换行符之外的其它字符r*匹配0个或多个rr+匹配1个或多个rr?匹配0个或1个r1.3.3规则部分的设计与实现规则部份是LEX源文件的核心部份，它包括一组模式和在生成分析器识别相应模式后对相应模式进行处理的C语言动作(Action)。格式如下C语言代码模式1动作1模式2|模式3动作3同定义部分一样，C语言代码必须出现在第一个模式之前，包括在%{和}%之中，且%{必须顶行书写。%{和}%之间的代码部份可用来定义yylex()用到的局部变量。模式必须顶行书写。模式可为正规式或用{}括起且在定义部份定义过的宏名。动作为用{}括起的C代码。且开始括号{与模式之间用白字符隔开，且须和模式在同一行上。注意，在模式后加一|表示模式2和3采用同一动作3.|和模式2以白字符隔开。1.3.4模式匹配模块的设计与实现yylex()函数被调用之后，它首先检查全局文件指针变量yyin是否有定义，如有，则将之设置为将要扫描的文件指针。如无，则设置为标准输入文件stdin.同理，如全局文件指针变量yyout无定义，则将之设置为标准输出文件stdout。若有多个模式与被扫描文件中的字符串相匹配，则yylex()执行能匹配最长字符串的模式，称为“最长匹配原则”；若还有多个模式匹配长度相同的字符串，则yylex()选择在LEX源文件中排列最前面的模式进行匹配，称为“最先匹配原则”。yylex()常通过超前搜索一个字符来实现这样的原则，如果使用超前搜索匹配了某一模式，则yylex()在进行下一次分析前，将回退一个字符。1.4系统分析与测试1.4.1测试用例设计词法分析一个C++程序：#includeiostreamusingnamespacestdintmaincoutHello!endlcoutWelcometoc++!endlReturn1.4.2测试结果1、把lex2源代码保存到flex安装目录中2、进入flex安装目录cdC:\GnuWin32\bin3、调用flex.exeflex.exe-olex2.yy.clex2.l4、调用VS2010编译器cl.exeC:\GnuWin32\bincllex2.yy.c图1-3运行结果15.输入lex2.yy.exe1-1.cpp得到输出结果图1-4运行结果21.5结论1.5.1本文工作和成果本次实验通过对flex基本知识的阅读基本掌握了简单的lex语法和规则，也可以自行设计编制调试一个具体的词法分析程序，不仅加深对了词法分析原理的理解，也初步掌握了在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。1.5.2系统不足与展望实验中在自己编写词法分析器的时候虽然遇到了部分困难，比如在编写的时候代码不能运行、字符的写法不对等等，但是这更加加深了我对flex的理解，学会了lex的使用，虽然这是在Windows环境下运行出来的，不过是通