下载文档原格式
Lex和Y acc工具介绍――编译原理的实用工具1.词法分词器生成工具lexLex的主要功能是生成一个词法分析器(scanner)的C源码。
描述词法分析器的文件，经过lex编译后，生成一个lex.yy.c的文件，然后由C编译器编译生成一个词法分析器。
词法分析器，简单来说，其任务就是将输入的各种符号，转化成相应的标识符(token)，转化后的标识符很容被后续阶段处理。
过程如错误！未找到引用源。
图1现在这个lex 文件可以用来生成一个统计行数、字符个数和单词个数的工具。
规则段是由正则表达式和相应的动作组成的。
p 1 {action 1}p 2 {action 2}……p n {action n }值得注意的是，lex 依次尝试每一个规则，尽可能地匹配最长的输入流。
如果有一些内容根可以看出lex的确按照最长的规则匹配。
程序段部分放一些扫描器的其它模块，比如一些动作执行时需要的模块。
也可以在另一个程序文件中编写，最后再链接到一起。
生成C代码后，需用C的编译器编译。
连接时需要指定链接库。
gcc的连接参数为 -ll。
2.正则表达式正则表达式可以描述有穷状态自动机(Finite Automata)接受的语言，也就是定义一个可以接受的串的集合。
转义字符（也称操作符）：" \ [ ] ^ - ? . * + | ( ) $ / { } % < >这些符号有特殊含义，不能用来匹配自身。
如果需要匹配的话，可以通过引号(’’)或者转义符号(\)来指示。
比如C”++”C\+\+都可以匹配C++。
非转义字符：所有除了转义字符之外的字符都是非转义字符。
一个非转义字符可以匹配自身。
比如integer匹配文本中出现的integer。
通配符：通配符就是”.”（dot），可以匹配任何一个字符。
字符集：用一对[]指定的字符构成一个字符集。
比如[abc]表示一个字符集，可以匹配a、b、c中的任意一个字符。
使用–可以指定范围。
基于LEX的C语言词法分析器下面是一个基于LEX的C语言词法分析器的示例代码：```c#include <stdio.h>%}letter [a-zA-Z]digit [0-9]id {letter}({letter}，{digit})*number {digit}+(\.{digit}+)?([eE][+-]?{digit}+)?%%{number} { printf("Number: %s\n", yytext); }{if} { printf("If: %s\n", yytext); }{else} { printf("Else: %s\n", yytext); }{while} { printf("While: %s\n", yytext); }{for} { printf("For: %s\n", yytext); }{id} { printf("Identifier: %s\n", yytext); }[ \t\n]+ // ignore white space. { printf("Unrecognized character: %c\n", yytext[0]); }%%int maiyylex(;return 0;```在上述代码中，首先是一些初始化的定义，定义了一些正则表达式模式，例如`letter`表示字母，`digit`表示数字，`id`表示标识符，`number`表示数字。
然后是各个模式的匹配规则和对应的处理逻辑。
其中，`{number}`表示如果匹配到了数字模式，就打印出该数字；`{if}`、`{else}`、`{while}`、`{for}`和`{id}`分别表示匹配到了if、else、while、for关键字和标识符，就打印出对应的信息；`[ \t\n]+`表示忽略空格和换行符；`.`表示匹配到了其他未定义的字符，就打印出异常信息。
LEX介绍LEX（Lexical Analyzer Generator）即词法分析器生成工具是1972年贝尔实验室的M.E.Lesk和E.Schmidt在UNIX操作系统上首次开发的。
GNU同时推出了和LEX完全兼容的FLEX（Fast Lexical Analyzer Genrator）。
下面用到的例子都是基于flex的。
LEX工作原理：LEX通过对源文件的扫描，经过宏替换将规则部分的正则表达式转换成与之等价的DFA，并产生DFA的状态转换矩阵（稀疏矩阵）；利用该矩阵和源文件的C代码产生一个名为int yylex()的词法分析函数，将yylex()函数拷贝到输出文件lex.yy.c中。
函数yylex()以在缺省条件下的标准输入（stdin）作为词法分析的输入文件。
输入文件（扩展名为.l）LEX输出文件lex.yy.cLex源文件格式为：定义部分%%规则部分%%用户附加的C语言代码例1：int num_chars=0,num_lines=0;/*定义两个全局变量，一个及字符数，一个记行数.注意：该语句不能顶行*/%%\n ++num_chars++; ++num_lines;. ++num_chars;%%int main(){yylex();printf(“%d,%d”, num_chars,num_lines);}int yywrap()/*文件结束处理函数，当yylex()读到文件结束标记EOF时，调用该函数时会，用户必须提供该函数，否则会提示编译出错*/{return 1;//返回1表示文件扫描结束，不必再扫描别的文件}lex 的输入文件分成三个段，段间用%% 来分隔。
由于必须存在一个规则段，第一个%% 总是要求存在模式LEX的模式是机器可读的正则表达式。
表意字符匹配字符. 除换行外的所有字符\n 换行* 0 次或无限次重复前面的表达式+ 1 次或更多次重复前面的表达式? 0 次或1 次出现前面的表达式^ 行的开始$ 行的结尾a|b a 或者b(ab)+ 1 次或玩多次重复ab"a+b" 字符串a+b 本身（C 中的特殊字符仍然有效）[] 字符类[^ab] 除a,b 外的任意字符[a^b] a, ^, b 中的一个[az] 从a 到z 中的任意字符[a\-z] a,-,z 中的一个[a-z] a, z 中的一个<EOF> 匹配文件结束标记表1 ：简单模式匹配在方括号（[]）中，通常的操作失去了本来含意。
实验二C-语言的词法分析器（基于Lex）1. 课程设计目标自动构造C-语言的的词法分析器，要求能够掌握编译原理的基本理论,，理解编译程序的基本结构，掌握编译各阶段的基本理论和技术，掌握编译程序设计的基本理论和步骤.，增强编写和调试高级语言源程序的能力，掌握词法分析的基本概念和实现方法，熟悉C-语言的各种Token。
2. 分析与设计基于Parser Genarator的词法分析器构造方法Lex输入文件由3个部分组成：定义集（definition），规则集（rule）和辅助程序集（auxiliary routine）或用户程序集（user routine）。
这三个部分由位于新一行第一列的双百分号分开，因此，Lex输入文件的格式如下{definitions}%%{rules}%%{auxiliary routines}而且第一部分用“%{”和“%}”括起来。
第一和第三个部分为C语言的代码和函数定义，第二个部分为一些规则。
定义正则表达式如下ID = letter letter*NUM = digit digit*Letter = a|…|z|A|…|ZDig it = 0|…|9Keyword = else|if|int|return|void|whileSpecial symbol = +|-|*|/|<|<=|>|>=|==|!=|=|;|，|（|）|[|]|{|}|/*|*/White space = “ ”Enter = \n在lex中的构造letter [A-Za-z]digit [0-9]id ({letter}|[_])({letter}|{digit}|[_])*error_id ({digit})+({letter})+num {digit}+whitespace [ \t]+enter [\n]+在Lex中的规则定义构造定义识别保留字规则"int"|"else"|"return"|"void"|"if"|"while"{Upper(yytext,yyleng);printf("%d 行",lineno);printf("%s reserved word\n",yytext);}//保留字定义识别数字规则{num}{printf("%d 行",lineno);printf("%s NUM\n",yytext);}//数字定义识别专用符号规则","|";"|"("|")"|"{"|"}"|"*"|"/"|"+"|"-"|">"|"<"|">="|"<="|"=="|"!="|"="|"/*"|"*/" {printf("%d 行",lineno);printf("%s special symbol\n",yytext);}//特殊符号定义识别标识符规则{id}{printf("%d 行",lineno);printf("%s ID\n",yytext);}//标识符定义识别错误的字符串规则当开头为数字的后面为字母的字符串时，是错误的标识符。
词法分析程序自动工具使用说明1．建立工作文件夹如D:\LEX2．将词法分析工具flex.exe 拷入到该文件夹3．建立LEX源文件如：用文本编辑器建立lextemp.txt源文件%{#include <stdio.h>#define BEGIN 101#define END 202%}digit [0-9]alpha [a-z]alnum [a-z0-9]%%begin {out(BEGIN,"begin");}end {out(END,"end");}"*" {out(303,"*");}"+" {out(404,"+");}{alpha}{alnum}* {out(505,yytext);}"=" {out(606,"=");}%%out(int c,char *val){printf("word:%d, %s\n",c,val);}4．建立简单语言的源程序文件如：用文本编辑器建立data.txt文件beginabcd=100efg=200gh123=300abcd=abcd*efgh+gh123end5．在DOS运行flex 生成目标文件lex.yy.c flex lex源文件名如：d:\lex\flex lextemp.txt6.进入VC，对lex.yy.c进行修改(1)增加或修改main()函数增加打开程序文件的语句int main(void){int c;if ((yyin=fopen("data.txt","r"))==NULL){printf("can’t open the file\n");exit(0);}yylex();return 0;}(2)增加函数int yywrap(){return 0;}（3）尾部这二行屏蔽// #if YY_MAIN// #Endif7.运行得到结果识别出的单词将在屏幕输出，通过修改out 函数可改为输出到一文件中。
lex用法
"lex"是一种文本分析工具，主要用于编写词法分析器。
它能够根据用户所定义的模式匹配规则，自动生成C语言代码实现词法分析功能。
具体来说，使用"lex"需要以下几个步骤：
1. 编写"lex"文件：该文件包含"lex"语法及模式匹配规则，决定了如何从输入的字符流中识别
和提取出各种符号和单词。
2. 使用"lex"命令编译生成C程序：命令格式为: `lex -o output.c input.l`，其中"output.c"为生成
的C源程序文件，"input.l"为"lex"文件名。
3. 编译并链接生成的C程序：使用C语言编译器（如gcc）编译生成的C源程序文件，并将其与主程序进行链接，形成可执行文件。
4. 运行程序并测试：将待分析的文本输入到程序中，程序会按照模式匹配规则进行词法分析，并输出分析结果。
"lex"的优点在于可以大大简化词法分析器的编写和维护工作，同时也增强了程序的可读性和
可移植性。
它常被用于编写编译器、解释器、文本编辑器等需要对文本内容进行识别和分析的应
用程序中。
Lex - 词法分析器生成器1．FLEX简介单词的描述称为模式(Lexical Pattern)，模式一般用正规表达式进行精确描述。
FLEX通过读取一个有规定格式的文本文件，输出一个如下所示的C语言源程序。
FLEX的输入文件称为LEX源文件，它内含正规表达式和对相应模式处理的C语言代码。
LEX源文件的扩展名习惯上用.l表示。
FLEX通过对源文件的扫描自动生成相应的词法分析函数 int yylex()，并将之输出到名规定为lex.yy.c的文件中。
实用时，可将其改名为lexyy.c。
该文件即为LEX的输出文件或输出的词法分析器。
也可将 int yylex()加入自已的工程文件中使用。
2．模式简介LEX的模式的格式(也称为规则)是机器可读的正规表达式，正规表达工是用连接、并、闭包运算递归生成的。
为了方便处理，LEX在此基础上增加了一些运算。
下列是按运算优先级由高往低排正规表列的LEX的达式的运算符。
“\[]^-?.*+|()/${}%<>关于LEX的模式定义，可参见下页附表1.13．LEX源文件格式LEX对源文件的格式要求非常严格，比如若将要求顶行书写的语句变成非顶行书写就会产生致命错误。
而LEX本身的查错能力很弱，所以书写时一定要注意。
LEX的源文件由三个部份组成，每个部分之间用顶行的“%%”分割，其格式如下：定义部份％％规则部份％％用户附加C语言部份3.1定义部份定义部份由C语言代码、模式的宏定义、条件模式的开始条件说明三部份组成。
其中，C代码部份由顶行的%{和}%引入，LEX扫描源文件时将%{和}%之间的部分原封不动的拷贝到输出文件lex.yy.c中.附表1.1 LEX 的模式定义宏名2 宏定义2……例如：DIGIT [0-9]ID [A-Za-z][A-Za-z0-9_]*宏名是以字母和下划线”_”开始，以字母、数字和下划线组成的字符串，且大小写敏感。
宏名必须顶行写，宏名和宏定义必须写在同一行上。
基于LEX的C语言词法分析器
一、LEX语法简介
（一）文件结构
Lex文件结构简单，分为三个部分：
声明段包括变量的声明、符号常量的声明和正则表达式声明。
希望出现在目标C源码中的代码，用%{…%}扩在一起。
比如：
正则表达式声明的格式为“命名表达式”，比如：
功能函数即为正常的C语言代码，遵守C语言代码格式即可。
（二）Lex特性简介
1．Lex依次尝试每一个规则，尽可能地匹配最长的输入流。
2．如果有一些内容根本不匹配任何规则，那么L ex将把它拷贝到标准输出。
二、正则表达式简介
在编写处理字符串的程序或网页时，经常会有查找符合某些复杂规则的字符串的需要。
正则表达式就是用于描述这些规则的工具。
换句话说，正则表达式就是记录文本规则的代码。
在这里，只用到了字符转义、重复、字符类、反义、贪婪与懒惰等较为基础的语法。
以下就简单对涉及到的语法进行介绍。
（一）字符转义
例如，.*在正则表达式中表示匹配所有，因此若要匹配.或*，则需要对其进行转义，即\.和\*。
（二）重复
在对数字和标识符等进行匹配时，字符位数不止一位，但遵守相同的规则，因此使用“重复”进行匹配。
例如，对数字进行匹配：[0-9]+，“+”表示至少重复一次，即数字长度至少为1。
例如，对标识符进行匹配，由于C语言标识符必须以下划线或字母开头，所以规则为：[_|A-Za-z]+(_|[A-Za-z]|[0-9])*。
“[_|A-Za-z]+”表示必须以下划线或字母开头，“(_|[A-Za-z]|[0-9])*”表示之后可以跟字母数字下划线，但是也可以不跟，这就是“+”和“*”所表示的“重复”的不同之处。
（三）字符类与反义
对没有预定义元字符的字符集合，需要在方括号里将其列出，例如，[aeiou]就是对任何一个英文元音字母的匹配，同理，[0-9]代表的含义与元字符\d完全一致，都是对一位数字进行的匹配。
有时需要查找不属于某个能简单定义的字符类的字符。
比如想查找除了数字以外，其它任意字符都行的情况，这时需要用到反义：
对于元字符，其反义即为其大写：\D，匹配非数字的字符。
更为普遍的表达方式如下：
[^aeiou]，匹配除了aeiou这几个字母以外的所有字符。
（四）贪婪与懒惰
与Lex对规则的处理类似，正则表达式也会在匹配整个表达式的前提下，匹配尽可能多的字符，这就是“贪婪”。
有时，需要匹配尽可能少的字符，就是“懒惰”匹配，具体的例子如下：
a.*?b，由于.*后加了?，表示“懒惰”匹配，因此会匹配最短的，以a开始，以b结束的字符。
例如字符串aabab，“贪婪”匹配的结果是aabab，而“懒惰”匹配的结果则是aab。
三、词法分类识别
这里，将源程序中的字符分为七类。
由于字符串对于词法分析以及后续的语法分析的意义不大，因此，这里将其单独列为一类；由于头文件的声明中会出现“<”“>”“””等分隔符，尤其是“<”和“>”，会与运
算符中的大于小于号产生冲突，因此这里把头文件也单独列为一类。
（一）保留字
C语言共有32个保留字，如图：
（二）标识符
C语言标识符的要求是，必须以下划线或者字母开头，之后可以跟字母、数字、下划线。
（三）常数
由于常数的表达方式较多，这里只是代表性地选取了几种方式进行识别。
（四）操作符
C语言操作符包括一元操作符、二元操作符和三元操作符。
（五）字符串
这里的字符串是指包围在单引号或双引号内的字符串。
（六）分隔符
这里选取了以下经常见到的分隔符：
（七）头文件
头文件的格式有一下两种：
四、词法识别分类规则
（一）常数的识别
根据上述对常数识别的需求，构造出了如下正则表达式：
这里，为了美观，以“|”为分隔符，对表达式进行了换行处理，每一行对应一个常数类别。
第一行，表示对整数和浮点数进行匹配；
第二行，先对整数或浮点数进行匹配，之后匹配e或E，最后匹配一个整数，即123.456e+789的形式，即科学计数法；
第三行，先匹配数字0，之后匹配字母x或X，最后匹配0-9及a-f或A-F的字符，即0x123abc的形式，即16进制表示法。
（二）保留字的识别
C语言中有32个保留字，且区分大小写，因此，这里构造如下正则表达式进行匹配：
可见，只需简单的将各个保留字通过“|”符号进行连接，即可实现对所有保留字的识别。
（三）分隔符的识别
由于分隔符中存在与正则表达式中元字符相冲突的字符，如“.”，“[”等，因此需要对这些产生冲突的符号进行转义，构造如下正则表达式：
（四）标识符的识别
根据上述的C语言标识符的要求，构造如下正则表达式：
此处涉及正则表达式语法较为简单，不再赘述。
（五）操作符的识别
由于操作符中，存在大量运算符号与正则表达式的元字符冲突，因此，根据C语言中的三种操作符，构造以下正则表达式：
可以看到表达式中含有大量转义字符，使得原本容易识别的C语言操作符变得难以分辨，但根据“|”连接符的指示，单个单个的分析，还是很容易明白的。
（六）其他字符的识别
对于空白、换行、注释、头文件等的识别，规则较为简单，这里不再一一举出。
五、词法识别分类顺序
由于Lex对正则表达式的支持并不完全，因此存在不同表达式匹配同一字符串的现象。
这里，为了减少这种现象的发生，降低出错率，对规则的优先级进行了调整，以更好的满足设计需求。
这里从两方面进行说明，一是标识符和保留字的识别顺序，二是一、二、三元操作符的识别顺序。
（一）标识符和保留字的识别顺序
由于标识符的识别规则会同时把保留字当做标识符进行匹配，从而产生错误，因此，需要调换这两条规则的匹配优先级，调整的结果如图所示：
这样就能保证，Lex在进行词法分析时，优先将满足保留字匹配规则的字符串匹配出来，从而避免误判。
（二）一、二、三元操作符的识别顺序
由于C语言中存在多元操作符，因此在对操作符进行匹配的时候，就要考虑到将其完整匹配，而不是将一个多元操作符分为多个一元操作符进行匹配。
这里，就需要对正则表达式内匹配规则的顺序进行一个调整，即对位数多的操作符优先进行匹配，具体的做法就是，将其匹配规则提前，如下所示：
这样在对操作符进行匹配时，就能够正确进行匹配，不产生错误和冲突。
六、测试代码
为了检验该词法分析器是否能实现词法分析，根据功能需求，设计了如下测试代码ori.c：
对头文件、两种注释方式、四种类型的数字、一元和三元运算符、字符串、分隔符、标识符、保留字在词法上进行了相关的构造。
由于未涉及语义分析，因此，为了便于做词法分析，代码加入了各种类型的语句，但只是形式，不能正常运行。
七、结果分析
程序运行命令：
其中lex.l即为编写的Lex源代码；lex.yy.x是上一步flex 对lex.l源代码进行处理，生成的文件；用gcc对lex.yy.c进行编译，生成可执行二进制文件flex；运行flex，将对ori.c文件进行词法分析。
以下为程序分析结果：
可以看出，该词法分析器能够正常运行，对程序的词法进行了准确率较高的识别。
但是，仍然存在一些问题，比如，对于负数无法进行识别，程序会将负号识别为操作符，这一错误无法通过调整优先级进行改正，需要对正则表达式进行进一步改进。
由于减号和负号的适用场合较为复杂，之前尝试着使用正则表达式的“负向零宽断言”语法进行匹配，但发现Lex无法识别该语法，导致无法运行，目前暂时还未想到解决办法。
另外一点是，Lex只能进行语法分析，且没有错误处理机制，要做到错误处理，只有在语义层使用Yacc进行处理。
因此，若出现词法错误，Lex会直接把无法识别的字符打印出来，而不对其进行进一步的处理，也未提供相关功能。
八、参考文献
《程序设计语言编译原理》，陈火旺等著，国防工业出版社.
正则表达式30分钟入门教程，/tools/zhengze.html
Yacc 与 Lex 快速入门，/developerworks/cn/linux/sdk/lex/ Lex Manual Page，/magic/man2html/1/lex。
