编译原理实践

1、编译原理实践-词法分析程序的自动生成器LEX由于各种高级程序设计语言的单词形式基本上可以用一组正规式来描述，人们就希望能否构造一个自动生成系统，只要给出程序设计语言的各类单词描述以及识别出各类单词后应输出的结果，这种自动系统便能自动产生此程序设计语言的词法分析程序Lex就是这样一个工具，他将正规式转换为一个NFA，进而转换为相应的DFA，这个DFA可以识别该正规式所表示的语言的句子 LEX简单的介绍简单的介绍1 LEX(lexical ananlyzer generator) 一个词法分析程序的自动生成器. LEX是1972年贝尔实验室首先在 UNIX上实现的.2 FLEX(fast lexi

2、cal ananlyzer generator) 是对LEX的扩充,它可在MS-DOS下运行. 我们这里实际使用的是FLEX,但仍称呼为LEX.LEX简单的介绍简单的介绍3 LEX能根据给定的正则表达式自动生成相应的词法分析程序. LEX的输入是用LEX 语言写的源程序, 生成一个用C语言描述的词法分析程器,所以LEX本身就相当于LEX语言写的编译程序. LEX生成的目标程序包含一个状态转换矩阵和一个控制执行程序. LEX使用流程使用流程使用LEX的流程如图:LEX源程序LEXYYLEX.CYYLEX.CC编译器YYLEX.EXEYYLEX.EXE字符串源程序符号串源程序LEX源程序是使用LE

3、X语言编写的词法规则说明,经过LEX翻译后形成目标文件YYLEX.C;再用C编译器对YYLEX.C进行翻译,生成目标程序YYLEX.EXE,它就是词法分析程序,用YYLEX.EXE就可以将字符串源程序转换成符号串源程序.用用LEX语言表达正则表达式语言表达正则表达式LEX的输入是LEX源程序.首先介绍如何表示正则 表达式.LEX表示正则表达式时采用一些元字符* + ( ) | “ “等,表示方法如下. (1)对于单个的字母a,就直接表示成a,如a,+,-等 . (2)abc表示字符a,b,或c中的任一个,如01 表示0或1 (3)a-d表示字符a,b,c或d中的任一个. (4)ab表示除了a或

4、b外的任一个字符.用用LEX语言表达正则表达式语言表达正则表达式(5). 表示除了换行符之外的任一个字符.(6)”text”表示双引号里的每个字符(包括元字符)都按字符处理,如”ab01”就是表示ab01是字符串,其中的和不是元字符(7) 转义字符(8)xxx名字xxx表示的正则表达式。(9)r|s表示正则表达式r或正则表达式s。(10)rs表示正则表达式r与正则表达式s的连接。用用LEX语言表达正则表达式语言表达正则表达式(11)(r)表示()内的优先级高于括号外。(12)r*表示正则表达式r可重复零次或多次。(13)r+表示正则表达式r可重复一次或多次。(14)r?表示r是一个可选的正则表

5、达式。(15)rm,n其中m,n是正整数，表达正则表达式r的 mn次重复。(16)rm表示正则表达式r的m次重复。(17)rm,表示正则表达式r的m到多次的重复。(18)行的开始，$行的结尾用用LEX语言表达正则表达式语言表达正则表达式例：1)二进制数 (0|1)*2)以aa或bb开头的由a和b任意组成的字符串 (aa|bb)(a|b)*或(aa|bb)ab*3) 任何一个从09的数字:0-94)长度不超过8的小写字符串a-z1,8用用LEX语言表达正则表达式语言表达正则表达式5) 无符号整数0-9+6)可带小数点的有符号数(“+”|”-”)?0-9+(“.”0-9+)?7) 可带指数的有符号

6、数(“+”|”-”)?0-9+(“.”0-9+)?(E(“+”|”-”)?0-9+)?8)标识符：字母或_开头，后跟字母数字、下划线等字符a-zA-Z_(a-zA-Z_|0-9)*9)空白区 tn+LEX有一个重要的元字符约定是用大括号指出正则表达式的名字。在前面已经提到过可以为正则表达式起名，这些名字也可使用在其他的正则表达式中，而为了将正则表达式名和普通的字符序列区分开来，将正则表达式放在大括号中。 例如，无符号整数定义为：num=0-9+ 其中，num为正则表达式名。在有符号的整数的定义中，可以引用正则表达式名num: signedNum=(+|-)?num 注意：在定义正则表达式名时并

7、不写大括号，只有在使用正则表达式名时才加上大括号。用用LEX语言表达正则表达式语言表达正则表达式LEX有个特征，在方括号（表示字符类）中，大多数的元字符都丧失了其特殊状况，且不必用引号括起来。甚至如果可以首先将连字符列出来的话，则也可以将其看作字符。因此，可将前一个数字的正则表达式(“+”|”-”)写作-+，但不能写成+-，这是因为元字符“-”用于表示字符的一个范围。又例如：.”?表示了句号、引号和问号3个字符中的任一个字符，此时，这三个字符在方括号中都丧失了它们元字符的含义。但是有一些字符即使是在方括号中也仍是元字符，如和。如果要得到像反斜杠这种真正的字符就必须在字符前加一个反斜杠。由于引号

8、在方括号内已失去了它们的元字符的含义，所以不能用引号，因此就表示了真正的字符和。LEX源程序结构源程序结构 LEX源程序是用LEX语言编写的词法规则说明，即用LEX语言对表示高级程序设计语言的单词集的正则表达式进行描述。LEX源程序分三个部分： 1.说明部分 2.识别规则 3.辅助过程。各部分之间用%隔开。即： 说明部分 % 识别规则 % 辅助过程 LEX源程序结构：说明部分源程序结构：说明部分1 说明部分： 用于定义识别规则中要用到的正则表达式名，包括： 变量说明、 标识符常量说明、 正则定义， C语言的说明信息（C语言的说明部分必须用分介符%和%括起来）。LEX源程序结构：说明部分源程序结

9、构：说明部分说明部分由如下形式的LEX语句组成： D1 R1 D2 R2 Dn Rn其中，R1，R2，Rn使用LEX语言表示的正则表达式；D1，D2，Dn是给正则表达式起的名字，称为正则表达式名。限定在Ri中只能出现字母表中的字符，以及前面已经定义过的正则表达式名，这样就可以定义程序语言的单词符号。 LEX源程序结构：说明部分源程序结构：说明部分例如，用LEX语句写的标识符和无符号整数的定义如下：标识符：letter a-zA-Z identifier letter+无符号整数：digit 0-9 num digit+C语言的说明信息主要包括将来生成的词法分析程序要使用的一些库文件和全局变量的

10、声明。%和% 中间的内容会原封不动地复制到LEX生成的词法分析程序的最前部。LEX源程序结构：说明部分源程序结构：说明部分例如下面的一段代码：% #include int lineno=1; %line (.*)n/表示一行字符LEX源程序结构：识别规则源程序结构：识别规则2 识别规则用正则表达式给出单词的定义，以及在识别出该正则表达式以后要执行的程序片段，具有如下形式的语句： P1 动作1 P2 动作2 Pn 动作n其中，Pi（i=1，2，3n）是一个用LEX语言描述的正则表达式，也即是单词符号；动作i是C语言的程序语句，表示当在识别出形为Pi的单词符号时，词法分析应执行的动作。该动作一般是

11、返回单词的单词记号及单词值。例如：LEX源程序结构：识别规则源程序结构：识别规则 %line printf(“%5d %s”,lineno+,yytext);这段代码表示识别出一行字符后，输出行号以及这行字符，然后行号递增。yytext是LEX的内部命字，它的内容就是正则表达式line匹配的字符串。LEX源程序中的识别规则完全决定了词法分析程序的功能。该词法分析程序只能识别P1，P2，Pn这些单词符号。识别出的单词符号保存在yytext中。LEX源程序结构：辅助过程源程序结构：辅助过程3辅助过程给出用户所需要的其他操作，它是识别部分某些动作需要调用的过程。如果不是C语言的库函数，则要在此给出具

12、体的定义。这些程序也可以存入另外的程序文件中，单独编译，最后和词法分析程序连接装配到一起。例如：下段辅助过程：%main()yylex();return 0;LEX源程序结构：辅助过程源程序结构：辅助过程int yywrap()return 1;这段代码包含了一个调用函数yylex()的main()过程。yylex()是由LEX构造的过程的名字，该过程进行词法分析。运行运行FLEX将上述三段代码连在一起，假设保存在名为exam1.lex的文件中，最好与FLEX在同一目录下，那么，在DOS下进入FLEX所在的目录，FLEX运行就可以产生词法分析程序，运行的命令(根据自己情况更改路径)运行运行FL

13、EX这样就会在同一目录下产生一个文件LEX.YY.C，这就是根据exam1.lex由LEX生成的词法分析程序。接下来可以对LEX.YY.C进行编译（可以用Visual C+ 6.0，或者Turbo C等）从而得到可执行文件LEX.YY.EXE，执行该文件，随意输入一行字符串，按回车则在屏幕上显示该字符串。一些常用一些常用LEX内部名字及含义内部名字及含义在上例中的LEX源程序中包含的C程序中，引用了一个LEX内部命令yytext,下面给出一些常用的LEX内部命字及其含义如下：lex.yy.c LEX输出文件名yylex LEX扫描例程yytext 当前行为匹配的串yyin LEX 输入文件（默

14、认为stdin,即键盘）；yyout LEX输出文件 （默认为stdout，即显示器）input LEX缓冲的输入例程；ECHO LEX默认行为，即将yytext()打印到yyoutyywrap 这一函数在文件（或输入）的末尾调用。如果函数的返回值是1，就停止解析。 举例举例1.例子 exam2.txt这段代码由LEX产生的程序的功能是：输入以字符a开头或结尾的任意字符串，则将该字符串显示出来，而对去其他的输入串则不能输出。因为在LEX代码中，识别出.*n描写的单词后，没有动作，所以就没有输出。对于ends_with_a和begins_with_a描述的单词，用ECHO输出到yyout.这个LEX输入还有一个值得注意的特征：所列的规则具有二义性（ambiguous）,这是因为输入串可匹配多个规则。实际上，无论它是否以a开头或结尾，都可与表达式.*n匹配。LEX有一个解决这种二义性的优先权系统。首先，LEX总是匹配可能的最长子串（因此LEX总是生成符合最长