2.5 Lex在线视频

各位同学大家好

欢迎大家继续来学习词法分析相关的内容

在这节课

我们主要来学习

词法分析器的生成器 Lex

Lex 是一个特殊的小工具

它也被叫做 Lex 编译器

它是依据前面所学过的正规式的描述

来构造词法分析器

Lex 已经被广泛的应用到

很多描述语言的词法分析器当中

Lex 的输入

是用 Lex 语言来编写的

首先我们来学习一下

如何使用 Lex 来建立词法分析器

包括如下的步骤

首先

我们需要编写 Lex 源程序 lex.l

lex.l 当中包括词法分析器的说明

这是使用 Lex 语言来编写的

然后 lex.l 会通过 Lex 的编译器进行编译

得到了C语言程序 lex.yy.c

lex.yy.c 这段程序

就包括了从 lex.l 的正规式

构造出来的状态转换图

以及使用这张状态转换图

识别词法单元的标准子程序

在 lex.l 当中和正规式相关联的动作

是使用C语言来表示的

lex.yy.c 会通过C语言的编译器

来进行编译

从而得到目标程序 a.out

那么 a.out

就可以用来处理我们的输入字符流

那么 a.out 处理完

输入的字符流之后

就可以将它识别为

对应的词法记号

那么 a.out 就是我们识别词法记号序列的词法分析器

我们首先来看一下Lex的工作原理

Lex是根据正规式来构造出 DFA

然后会基于 DFA

生成词法分析程序的主控制程序

也就是说

我们在 lex 的程序当中

只需要把描述匹配规则的正规式写好

那么 Lex 就会自动地去构造对应的DFA

然后基于 DFA

自动的去生成

词法分析程序的主控制程序

lex的实现过程中

我们发现 lex.l 程序编译之后

会得到 lex.yy.c 的程序

也就是 lex是一个寄宿的语言

它需要有宿主程序的

宿主语言的

那么宿主语言

通常是C或者C++等等

在Lex 实现的过程中

每一个匹配动作

相关的代码

都会被放到对应的状态的

处理代码块当中去

Lex 的程序有很多

包括lex flex等等

我们在实验中会使用flex

lex程序通常包括三个部分

声明、翻译规则以及辅助的过程

声明、翻译规则和辅助过程中间

我们使用两个百分号%%

将它们区分开

声明部分

包括变量的声明

常量的声明及正规定义

那么其中正规定义部分

和我们前面学过的是类似的

也可以作为正规式

出现在翻译规则当中

辅助过程作为第三个部分

它包括了动作所要用到的辅助函数

这些函数

我们可以写在其它文件当中

分别进行编译

然后再和这里的词法分析器

进行连接

lex程序的翻译规则

我们会将它写成P1 {动作1}

P2 {动作2} 这样的形式

也就是每一条翻译规则的形式

都是模式 {动作} 这样的形式

每一个模式P是一个正规式

每个动作都用来描述

这个模式匹配词法单元的时候

词法分析器应当执行的程序段

那么在lex当中

这个动作是使用C语言

来编写的程序段

使用 lex 建立的词法分析器

通常是作为语法分析器的

一个子程序来出现

词法分析

每次被语法分析器所调用的时候

它需要逐个的

逐字符的去读取它的剩余的输入

直到它在剩余的收入中

发现一个能和当前某个模式 P

所匹配的最长前缀为止

然后它就去执行和P对应的动作A

非常典型的就是

动作A会把控制返回给语法分析器

如果不是这样的话

比如说 P 描述的是空白或者注释

词法分析器就会继续去寻找下一个词法单元

直到有一个动作

可以引导控制

回到语法分析器为止

词法分析器

仅仅返回一个值

给语法分析器

也就是返回一个记号名

给语法分析器

记号的属性值

是通过共享的变量进行传递的

下面我们来看一个lex的程序

首先我们观察一下

这个程序当中声明的部分

声明部分

我们会定义了一些

在翻译规则当中

需要使用的变量

这个声明当中

我们使用 %{ }%

包围起来

出现在括号当中的任何东西

任何代码

都会被直接复制到

词法分析器lex.yy.c当中

不作为正规定义和翻译规则的一部分

那么在后面第三部分的辅助函数

我们也是采用同样的方式

来进行处理的

声明部分

还会包括一些正规定义

每个定义使用一个名字

以及该名字指示的正规式组成

比如说正规定义当中的第一行

delim 它表示的是字符类 空格\t\n

也就是它用来表示

空格、制表符、换行符

这三个字符当中的任意一个

第二行正规定义当中ws

是一个叫空格的定义

空格

它就表示一个或者多个分界符的序列

letter用来表示

大写字母和小写字母当中的任意一个

digit用来表示

0~9数字当中的任意一个

接下来是id

也就是标识符

那么id的定义当中

我们使用了圆括号

它是lex当中的元符号

也就是它的含义

是把一些正规式组成一个整体

那么同样的

竖线也在lex当中

用来表示选择

然后number当中

也就是数的定义当中

我们涉及到用了反斜线\

是作为换码

也就是让 lex 当中元符号的字符

取它自身原本的含义

反斜线点就是取10进制小数点的含义

反斜线减号

也就是使用了减号本身的含义

因为减号在lex当中

也是作为元符号

接下来我们来看一下

翻译规则这一部分

那么我们先看

翻译规则当中的第一条规则

花括号 { } 括起来的ws

也就是我们如果看到了

空格、制表符或者换行符这样的串

那么就不需要有任何的动作发生

也不需要返回分析器

词法分析器

就会继续去识别

其它的词法记号

直到所识别的记号的动作

可以引起返回为止

我们需要注意的是

在lex当中

ws必须由花括号包围起来

这是用来区别和两个字母 ws 所组成的模式

后边的id 和number也是这样的

第二条规则是 while 这条规则

也就是说如果看见了字母 while

那么就返回一个记号

大写的WHILE while这个记号

那么while 记号

用来代表某个整数的常量

语法分析器

会把这个整数理解成while

那么后面它这条规则

是用同样的方法来处理do

我们再来看一下 id 的规则

id 对应的规则中

包含着两个语句

第一个语句是调用的函数install_id( )

这个函数的定义

我们放在了第三个部分

辅助的部分

这个函数返回值

赋给变量yylval

那么这个变量

yylval的定义

是出现在lex的输出lex.yy.C当中

这个变量

它对于（词法）分析器也是可用的

那么yylval的作用

就是

保存返回记号的属性值

id的规则中

第二个语句

return(id) 只能返回记号名

Number对应的规则和 id是类似的

是来解析number

它的返回值

也放到了yylval当中

然后 return 语句用来返回

number记号名

接下来6个关系运算符都使用双引号引起来

使用双引号在 lex 当中

引起来之后

这个字符

就用来表示原来的含义

我们再来看一下辅助过程

辅助过程中

出现的第一个函数是

install_id

我们把其中的详细代码省略掉了

那么我们可以想到

install_id它的主要作用就是

在符号表当中

去查找由模式

id 所能匹配的词法单元

那么在这里

涉及到了两个变量

一个是yytext

一个是yyleng

yytext是一个指针

它用来指向词法单元的开始字符

yyleng是一个整数

它指出来当前词法单元的长度

install_number()

和上面的 install_id() 过程是类似的

只是这里的词法单元

不再是标志符

而是数字

针对关系运算符

都可以返回词法记号RELOP

那么我们也可以使用

yylval的值

来区别不同的关系运算符

我们再来看一下

使用Lex 定义常规的表达式

我们可以使用点来匹配

除了 \n 之外的任意的字符

使用这个小横线-

用来表示范围

比如说 A 到Z a到z 0-9

使用$来表示一行的结尾

我们使用花括号

用来表示一个模式可能出现的次数

比如说

A{1,3}

用来表示A可能出现一次或三次

可以使用小尖角^

用来表示否定

操作符小尖角^

只能出现在左中括号后的

第一个字符位置处

比如说 [^ABC]

此外还有 * | ? + 等等

用来表示一些常用的闭包、逻辑或操作等等

我们再来看一下

lex当中

一些重要的外部变量

那么 lex 当中

使得词法单元的拼写

对于出现在第三部分当中的

辅助函数是可用的

比如说这里

变量yytext

它就是一个指针

是用来指向外部字符数组的

它的内容是

当前被某个规则所匹配的字符串

yyleng

表示当前yytext当中字符的个数

我们可以在翻译规则当中

写下

这个模式

然后它对应的动作

我们就可以写

printf{"word=%s, length=%d", yytext, yyleng);

然后后边我们直接可以调用yytext yyleng

这样就可以输出当前的字符串

以及它的长度

如果针对当前这个模式

所匹配的字符串

我们希望只输出它的字符串本身

那么就可以写成printf("%s", yytext)

当然也可以

进行简写

直接 printf("%s", yytext) 这一句

就可以写成ECHO

此外还有yyin

用来表示词法分析的输入文件

yyout用来表示

词法分析的输出文件

yyin和yyout

这两个函数

经常和函数yywrap() 连用

如果函数的返回值是1

那么就停止去进行解析

因此

可以用它来解析多个文件

我们的代码可以写在第三段

这样我们就可以解析多个文件

方法就是使用yyin文件指针

指向不同的文件

直到所有的文件

都被解析完成

最后 yywrap()

可以返回 1 来表示解析的结束

yylineno

用来给出当前的行数信息

接下来我们再说一下

lex 当中识别规则二义性的处理方法

首先能够匹配最多字符的规则优先

也就是说

如果同时有两个规则

都可以匹配一个字符串

那么我们选取

能匹配多字符的规则

它是优先的

比如说

我们针对integer

我们写出一个规则

再针对 [a-z]+

我们写出另一个规则

那么这个时候

如果我们输入integers

加上了s

那么我们就不再匹配第一条规则

而是去匹配 [a-z]+ 这条规则

第二

能匹配相同数目的字符的规则

书写顺序在前面的优先

也就是谁写在前面

谁的优先级别

会更高一些

就会优先去进行匹配

假设我们需要去计算

输入文本当中

she 和 he 的个数

那么在碰到she的时候

我们进行匹配 s++

执行 s++ 的动作

然后返回

再碰见 he 的时候

我们统计 h++

然后返回

在碰见 \n 的时候

我们不做什么动作

在碰见其它符号的时候

我们去匹配它

使用 . 分号（即无动作）

用来匹配任意的字符

除了 \n 之外的任意字符

我们再来看几个简单的例子

比如说

我们希望其删除输入当中

每行结尾处所有的空白字符

那么我们就可以直接写

[ \t\n]+$

然后在规则对应的动作方面

我们就直接写一个分号;

这样我们就可以删除输入当中

每行结尾处所有的空白字符

再比如

如果我们希望

将字符串当中的空格

或者制表符

转换为单个的空格

那么我们就再增加一条规则

[ \t]+

对应的动作

我们就写上printf(" ")

这样我们就可以将字符串当中的

空格或者制表符

转换为对应的单个空格

我们再来看一下上机实验的例子

exampl.l这个 lex源程序

前边是变量的声明部分

中间是模式的匹配过程

也就是翻译的规则

最后 main 函数

这个地方

是对应的辅助函数

那么我们在变量的声明部分

定义了 num_lines 和num_chars

用它来进行计数

记行数和字符的数目

然后在翻译规则的部分

我们使用 \n 和 .

用来做模式的匹配

在碰到 \n 的时候

我们的num_lines 就要做 ++

num_chars

需要做 ++ 的操作

然后在碰到其它的符号的时候

只有num_chars 的需要做++的操作

然后在 main 函数当中

我们需要去调用yylex

去使用printf

将所有的行

和字符的数目打印输出

然后如果我们给出一个文本（文件）

这个文本当中

包括这样的三行文本

hello world

wo ai tian an men 的英文

以及hello world i love

那么我们在编译完example.l

lex源程序之后

会得到 lex.yy.exe

这个程序

然后我们使用lex.yy.exe 这个程序

去读取刚才的文本文件

就会得到对应的结果

也就是输出函数等于3

字符的数目等于49

这一讲就到这里

谢谢大家