2021-10-23 18:29:32

lex - 计算机领域的词法分析器 免费编辑 修改义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
其他
其他
编辑分类

Lex是Lexical Analyzer Generator(取前三个字母)的缩写,是Unix环境下非常著名的工具,主要功能是生成一个词法分析器(scanner)的C源码,描述规则采用正则表达式(regular expression)。

基本信息

  • 中文名称

    词法分析器生成器

  • 外文名称

    Lexical analyzer generator

  • 缩写

    Lex

  • 运行环境

    Unix环境

  • 主要功能

    生成一个词法分析器的C源码

折叠 编辑本段 生成工具

描述词法分析器的文件*.l,经过lex编译后,生成一个lex.yy.c 的文件,然后由C编译器编译生成一个词法分析器。词法分析器,简单来说,其任务就是将输入的各种符号,转化成相应的标识符(token),转化后的标识符 很容易被后续阶段处理。如图1所示。

它被设计用来对输入字符流进行词法处理。它接受一种高级的、面向问题的说明书,并用它匹配字符串中的字符、生成能够识别正则表达式的程序。正则表达式通过用户输入的代码说明书给入。Lex识别这些表达式,并且将输入流分成一些匹配这些表达式的字符串。在这些字符串的分界处,用户提供的程序片段被执行。Lex代码文件将正则表达式和程序片断关联。对每一条输入到由Lex生成程序的表达式,相应的代码片段被执行。

为了完成任务,除了需要提供匹配的表达式以外,用户还需要提供其它代码,甚至是由其他生成器产生的代码。用户提供一般程序设计语言的代码片断完成程序识别表达式。因此,用户自由编写动作时,并不影响其编写高层的表达式语言来匹配字符串表达式。这就避免迫使用户使用字符串语言来进行输入分析时,也必须使用同样的方法来编写字符处理程序,而这样做有时是不合适的。Lex不是完整的语言,但是是一个新语言的生成器,它可以插入到各种不同的被叫做"宿主语言"的程序设计语言中。就像大多数目的语言可以生成在不同计算机硬件上运行的代码,Lex可以生成不同的宿主语言。宿主语言用于Lex生成输出代码,也用于用户插入程序片断。这使得Lex适用于不同的环境和不同的使用者。每一个应用程序可以是硬件、适用于该任务的宿主语言、用户背景和局部接口属性的直接结合。现在,Lex唯一支持的宿主语言是C,尽管Fortran(形式为Ratfor[2])在过去也被支持。Lex自身存在于UNIX、GCOS和OS/370上;但是Lex生成的代码可以在任何适当的编译器上使用。

Lex将用户输入的表达式和动作actions(在这篇文章中被称作源代码)转换为宿主语言;生成的程序叫做yylexyylex识别字符流中的表达式(本文称作输入流),并且当每一个表达式被检测出来后,输出相应的动作。

过程如图 。

让我们来仔细研究一下这个奇妙的工具吧。先看看Lex文件的结构。 Lex文件结构简单,分为三个部分:

分别是声明,转换规则和其它函数

声明段包括变量的声明、符号常量的声明和正则表达式声明。希望出现在目标C源码中的代码,用%{…%}扩在一起。比如:

正则表达式声明如下

这段正则表达式描述识别数(number)、标识符(id)的"规则"。过一会我们再细说正则表达式。

规则段是由正则表达式和相应的动作组成的。

值得注意的是,lex 依次尝试每一个规则,尽可能地匹配最长的输入流。如果有一些内容根本不匹配任何规则,那么 lex 将只是把它拷贝到标准输出。比如

编译后运行一下,

可以看出lex的确按照最长的规则匹配。

程序段部分放一些扫描器的其它模块,比如一些动作执行时需要的模块。也可以在另一个程序文件中编写,最后再链接到一起。 生成C代码后,需用C的编译器编译。连接时需要指定链接库。gcc的连接参数为 -ll。

正则表达式可以描述有穷状态自动机(finite automata)接受的语言,也就是定义一个可以接受的串的集.lex中用到的正则表达式的一些规则如下:

转义字符(也称操作符):

这些符号有特殊含义,不能用来匹配自身。如果需要匹配的话,可以通过引号(")或者转义符号(\)来指示。比如

C"++" C\+\+

都可以匹配C++

非转义字符:所有除了转义字符之外的字符都是非转义字符。一个非转义字符可以匹配自身。比如

integer

匹配文本中出现的integer。

通配符:通配符就是.(dot),可以匹配任何一个字符。

字符集:用一对[]指定的字符构成一个字符集。比如[abc]表示一个字符集,可以匹配a、b、c中的任意一个字符。使用 – 可以指定范围。比如[a-z]表示可以匹配所有小写字母的字符集。

重复:

* 任意次重复+ 至少一次的重复,相当于xx*? 零次或者一次

选择和分组:|符号表示选择,二者则一;括号表示分组,括号内的组合被看作是一个原子。比如(ab|cd)匹配ab或者cd。

折叠 编辑本段 Lex源代码

一般的Lex源代码格式为

而definitions和user subroutines经常被忽略。第二个%%是可选择的,但是第一个必须存在以标记rules的开始。因此最简单的Lex程序是

(没有definitions和rules),这个程序输入将不加修改地复制到输出。

由上面的Lex程序轮廓可知,规则(rules)反映了用户的控制;它是一个表格,左侧是正则表达式(regular expressions)(参见第3节),而右侧是动作(actions),当表达式被识别出以后,动作的程序片断被执行。所以,一个单独的规则可能是

integer

printf("found keyword INT");

它用于在输入流中寻找字符串中的integer,找到后输出"found keyword INT"。在这个例子中,主程序为C语言并且用C库函数printf打印字符串。用第一个出现的空白符或者制表符作为表达式的结束标记。如果action仅仅是一条简单的C表达式,那么它可以直接写在这一行的右侧;如果是复合表达式或者包含了很多行,则必须用大括号括起来。作为一个更有用的例子--用来将一些英式拼写转换为美式拼写--其词法分析器应该以如下规则开始:

colour

printf("color");

mechanise

printf("mechanize");

petrol

printf("gas");

这些规则是不够强大的,比如pertroleum应该变为gaseum;一种处理它的方法将在下文中予以介绍。

折叠 编辑本段 警告和缺陷

有一些病态的表达式会使由表格转化的确定的自动机成指数增长;幸运的是,这样的情况很少见。

REJECT没有重复扫描输入;而是记住先前扫描的结果。这意味着如果一条规则需要回退发现的上下文,并且REJECT被执行了,用户将不能使用unput来改变输入流中的后续字符。这是对用户操作后续输入的唯一限制。

阅读全文

热点资讯

我的关注