编译原理实践 --词法分析程序的自动生成器LEX

Presentation on theme: "编译原理实践 --词法分析程序的自动生成器LEX"— Presentation transcript:

1 编译原理实践 --词法分析程序的自动生成器LEX

2 由于各种高级程序设计语言的单词形式基本上可以用一组正规式来描述，人们就希望能否构造一个自动生成系统，只要给出程序设计语言的各类单词描述以及识别出各类单词后应输出的结果，这种自动系统便能自动产生此程序设计语言的词法分析程序 Lex就是这样一个工具，他将正规式转换为一个NFA，进而转换为相应的DFA，这个DFA可以识别该正规式所表示的语言的句子

3 LEX简单的介绍 1 LEX(lexical ananlyzer generator) 一个词法分析程序的自动生成器. LEX是1972年贝尔实验室首先在 UNIX上实现的. 2 FLEX(fast lexical ananlyzer generator) 是对LEX的扩充,它可在MS-DOS下运行. 我们这里实际使用的是FLEX,但仍称呼为LEX.

4 LEX简单的介绍 LEX能根据给定的正则表达式自动生成相应的词法分析程序 输入:是用LEX 语言写的源程序 生成:用C语言描述的词法分析程序

5 LEX使用流程 使用LEX的流程如图: LEX源程序 LEX YYLEX.C C编译器 YYLEX.EXE 字符串源程序 符号串源程序
LEX源程序是使用LEX语言编写的词法规则说明,经过LEX翻译后形成目标文件YYLEX.C;再用C编译器对YYLEX.C进行翻译,生成目标程序YYLEX.EXE,它就是词法分析程序,用YYLEX.EXE就可以将字符串源程序转换成符号串源程序.

6 用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或b外的任一个字符.

7 用LEX语言表达正则表达式 (5). 表示除了换行符之外的任一个字符.
(6)”text”表示双引号里的每个字符(包括元字符)都按字符处理,如”ab[01]”就是表示ab[01]是字符串,其中的[和]不是元字符 (7) \ 转义字符 (8){xxx}名字xxx表示的正则表达式。 (9)r|s表示正则表达式r或正则表达式s。 (10)rs表示正则表达式r与正则表达式s的连接。

8 用LEX语言表达正则表达式 (11)(r)表示()内的优先级高于括号外。 (12)r*表示正则表达式r可重复零次或多次。
(15)r{m,n}其中m,n是正整数，表达正则表达式r的 m~n次重复。 (16)r{m}表示正则表达式r的m次重复。 (17)r{m,}表示正则表达式r的m到多次的重复。 (18)^行的开始，$行的结尾

9 用LEX语言表达正则表达式 例： 1)二进制数 (0|1)* 2)以aa或bb开头的由a和b任意组成的字符串
(aa|bb)(a|b)*或(aa|bb)[ab]* 3) 任何一个从0~9的数字: [0-9] 4)长度不超过8的小写字符串 [a-z]{1,8}

10 用LEX语言表达正则表达式 5) 无符号整数 [0-9]+ 6)可带小数点的有符号数
(“+”|”-”)?[0-9]+(“.”[0-9]+)? 7) 可带指数的有符号数 (“+”|”-”)?[0-9]+(“.”[0-9]+)?(E(“+”|”-”)?[0-9]+)? 8)标识符：字母或_开头，后跟字母数字、下划线等字符 [a-zA-Z_]([a-zA-Z_]|[0-9])* 9)空白区 [ \t\n]+

11 元字符约定 元字符约定：可以为正则表达式起名，这些名字也可使用在其他的正则表达式中，需正则表达式放在大括号中。
例如，无符号整数定义为：num=[0-9]+ 其中，num为正则表达式名。 在有符号的整数的定义中，可以引用正则表达式名num: signedNum=(+|-)?{num} 注意：在定义正则表达式名时并不写大括号，只有在使用正则表达式名时才加上大括号。

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

13 LEX源程序结构 LEX源程序是用LEX语言编写的词法规则说明，即用LEX语言对表示高级程序设计语言的单词集的正则表达式进行描述。
1.说明部分 2.识别规则 3.辅助过程。 各部分之间用%%隔开。即： 说明部分 %% 识别规则 %% 辅助过程

14 LEX源程序结构：说明部分 1 说明部分： 用于定义识别规则中要用到的正则表达式名，包括： 变量说明、 标识符常量说明、 正则定义，
C语言的说明信息 （C语言的说明部分必须用分介符%和%括起来）。

15 LEX源程序结构：说明部分 说明部分由如下形式的LEX语句组成： D1 R1 D2 R2 …… Dn Rn
其中，R1，R2，…Rn使用LEX语言表示的正则表达式；D1 ，D2，…Dn是给正则表达式起的名字，称为正则表达式名。 限定在Ri中只能出现字母表∑中的字符，以及前面已经定义过的正则表达式名，这样就可以定义程序语言的单词符号。

16 LEX源程序结构：说明部分 例如，用LEX语句写的标识符和无符号整数的定义如下： 标识符：letter [a-zA-Z]
identifier {letter}+ 无符号整数：digit [0-9] num {digit}+ C语言的说明信息主要包括将来生成的词法分析程序要使用的一些库文件和全局变量的声明。%{和% }中间的内容会原封不动地复制到LEX生成的词法分析程序的最前部。

17 LEX源程序结构：说明部分 例如下面的一段代码： %{ #include <stdio.h> int lineno=1; %}
//表示一行字符

18 LEX源程序结构：识别规则 2 识别规则 用正则表达式给出单词的定义，以及在识别出该正则表达式以后要执行的程序片段，具有如下形式的语句：
P1 {动作1} P2 {动作2} …… Pn {动作n} 其中，Pi（i=1，2，3……n）是一个用LEX语言描述的正则表达式，也即是单词符号；动作i是C语言的程序语句，表示当在识别出形为Pi的单词符号时，词法分析应执行的动作。该动作一般是返回单词的单词记号及单词值。

19 LEX源程序结构：识别规则 例如： %% {line }{printf(“%5d %s”,lineno++,yytext);}
这段代码表示识别出一行字符后，输出行号以及这行字符，然后行号递增。yytext是LEX的内部命字，它的内容就是正则表达式line匹配的字符串。 LEX源程序中的识别规则完全决定了词法分析程序的功能。该词法分析程序只能识别P1，P2，…Pn这些单词符号。识别出的单词符号保存在yytext中。

20 LEX源程序结构：辅助过程 3辅助过程 给出用户所需要的其他操作，它是识别部分某些动作需要调用的过程。如果不是C语言的库函数，则要在此给出具体的定义。这些程序也可以存入另外的程序文件中，单独编译，最后和词法分析程序连接装配到一起。 例如：下段辅助过程： %% main() {yylex(); return 0; }

21 LEX源程序结构：辅助过程 int yywrap() { return 1; }
这段代码包含了一个调用函数yylex()的main()过程。yylex()是由LEX构造的过程的名字，该过程进行词法分析。

22 运行FLEX 将上述三段代码连在一起，假设保存在名为exam1.lex的文件中，最好与FLEX在同一目录下，那么，在DOS下进入FLEX所在的目录，FLEX运行就可以产生词法分析程序，运行的命令(根据自己情况更改路径)

23 运行FLEX 这样就会在同一目录下产生一个文件LEX.YY.C，这就是根据exam1.lex由LEX生成的词法分析程序。接下来可以对LEX.YY.C进行编译（可以用Visual C++ 6.0）从而得到可执行文件LEX.YY.EXE，执行该文件，随意输入一行字符串，按回车则在屏幕上显示该字符串。

24 一些常用LEX内部名字及含义 在上例中的LEX源程序中包含的C程序中，引用了一个LEX内部命令yytext,下面给出一些常用的LEX内部命字及其含义如下： lex.yy.c LEX输出文件名 yylex LEX扫描例程 yytext 当前被某规则匹配的字符串 yyin LEX 输入文件（默认为stdin,即键盘）； yyout LEX输出文件 （默认为stdout，即显示器） input LEX缓冲的输入例程； ECHO LEX默认行为，即将yytext()打印到yyout yywrap 这一函数在文件（或输入）的末尾调用。如果函数的返回值是1，就停止解析。

25 举例 1.例子 exam2.txt 这段代码由LEX产生的程序的功能是：输入以字符a开头或结尾的任意字符串，则将该字符串显示出来，而对其他的输入串则不能输出。因为在LEX代码中，识别出.*\n描写的单词后，没有动作，所以就没有输出。对于{ends_with_a}和 {begins_with_a}描述的单词，用ECHO输出到yyout. 这个LEX输入还有一个值得注意的特征：所列的规则具有二义性（ambiguous）,这是因为输入串可匹配多个规则。实际上，无论它是否以a开头或结尾，都可与表达式.*\n匹配。

26 LEX有一个解决这种二义性的优先权系统。首先，LEX总是匹配可能的最长子串（因此LEX总是生成符合最长子串原则的扫描程序）。其次，如果最长子串仍与两个或更多个规则匹配，LEX就选取列在前面的规则。正是由于这个原因，上面的LEX输入文件就将{ends_with_a} ECHO ;和{begins_with_a} ECHO;放在前面，如果按下面的顺序列出 .*\n; {ends_with_a} ECHO ; {begins_with_a} ECHO; 则不会有任何输出。

27 2.pl0程序的词法分析程序 3.扫描器，用于计算一个文件中的字符数，单词数和行数（类似Unix 中的wc 程序）