lex一个词法分析器的生成器_翻译版.doc
《lex一个词法分析器的生成器_翻译版.doc》由会员分享,可在线阅读,更多相关《lex一个词法分析器的生成器_翻译版.doc(70页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Lex-词法分析器生成器(M.E.Lesk,E.Schmidt著,中文翻译)Lex - 词法分析器生成器 M. E. Lesk 与 E. SchmidtBell LaboratoriesMurray Hill, New Jersey 07974 翻译:寒蝉退士译者声明:译者对译文不做任何担保,译者对译文不拥有任何权利并且不负担 任何责任和义务。原文:http:/cm.bell-摘要 Lex 帮助书写其控制流由在输入流中的正则表达式的实例来导向的程序。它适合于编辑器脚本类型的变换,和为解析例程做准备工作而分解输入。Lex 源码是正则表达式和相应的程序片段的表格。Lex 把这个表格变换成读取输入流
2、、复制它到输出流、并把输入划分到匹配给定表达式的字符串中的一个程序。随着每个这种字符串被识别出来,相应的程序片段就被执 行。表达式通过用 Lex 生成的确定有限自动机来识别。用户书写的程序片段按照对应的正则表达式在输入流中出现的次序来执行。 用 Lex 写成的词法分析程序接受有歧义的规定,并在每个输入点上选择最长的匹配可能。如果需要,在输入上进行实质的超前查看(lookahead),但输入流会被 回退(backup)到当前划分的结束处,所以用户有操纵它的普遍自由。 Lex 可以生成用 C 语言或 Ratfor 语言写的分析器,Ratfor 可以自动的转换成可移植的 Fortran。它可以在 P
3、DP-11 UNIX、 Honeywell GCOS 和 IBM OS 系统上得到。本手册只讨论在 UNIX 系统上的生成 C 语言的分析器,这是在 UNIX 第 7 版中唯一支持的 Lex 形式。设计 Lex 时简化了与编译器的编译系统 Yacc 的交接。 July 21, 1975 真的不掉线吗?、?目录真的不掉线吗?、?真的不掉线吗?、? 1. 介 绍 2. Lex 源码 3. Lex 正则表达式 4. Lex 动作 5. 歧 义源规则 6. Lex 源定义 7. 用 法 8. Lex 与 Yacc 9. 例 子 10. 左 上下文敏感 11. 字符集 12. 源格式总结 13. 告诫和
4、缺陷 14. 致 谢 15. 引 用1. 介绍 Lex 是设计用于字符输入流的词法处理的一个程序生成器。它接受高级的、面向问题的对字符串匹配的规定,并生成识别正则表达式的通用语言写的一个程序。正则表达式在用户给 Lex 的源规定中指定。Lex写出的代码识别在输入流中的这些表达式,并把输入流划分到匹配这些表达式的字符串中。在字符串间的分界上执行用户提供的程序片段。Lex源文件对正则表达式关联上程序片段。随着每个表达式出现在给 Lex 写出的程序的输入中,相应的程序片段就被执行。用户提供超出表达式所需要的额外代码来完成他的任务,可能包括用其他生成器写出的代码。生成的识别表达式的程序采用用户的程序片
5、段所采用的通用编程语言。因此,提供了高级表达式语言来写要被匹配的字符串表达式,而用户写动作的自由不受侵犯。这避 免了强制希望使用字符串操纵语言做输入分析的用户、去使用同样的并且经常不适合字符串处理的语言来书写处理程序。 Lex不是完整的语言,而是体现了可增加到叫做“宿主语言”的不同编程语言中的新语言特征的一个生成器。正如同通用语言可以生成在不同计算机硬件上运行的代 码,Lex可以写出不同宿主语言的代码。宿主语言被用于Lex生成的输出代码和用户增加的程序片段。还为不同的宿主语言提供兼容的运行时间库。这使 真的不掉线吗?、?Lex 适应不同的环境和不同的用户。每个应用都可以被定向到适合这个任务的硬
6、件和宿主语言、用户背景和本地实现性质的各种组合上。目前唯一支持的宿主语言是 C,尽管过去曾经支持过 Fortran(Ratfor 2形式)。Lex 自身存在于UNIX、GCOS 和 OS/370;但 Lex 生成的代码可以采用于存在适当的编译器的任何地方。 Lex 把用户的表达式和动作(在本文中叫做源码)转换成宿主通用语言;生成的程序叫做 yylex。yylex 程序将识别在流(在本文中叫做输入)中的表达式,并在检测到的时候执行给每个表达式的动作。参见图 1。 +-+源码 - | Lex | - yylex +-+ +-+输入 - | yylex | - 输出 +-+Lex 概述图 1作为一个
7、平凡的例子,考虑从输入中删除所有行结束处的空白或 tab 的程序。 % t+$ ;就是所需要的。这个程序包含标记规则开始的一个 % 分界符和一个规则。这个规则包含匹配在行结束处之前的空白或tab(按照 C 语言约定写为 t)字符的一个或多个实例的一个正则表达式。方括号指示由空白和 tab 构成的字符类;同于 QED,+ 指示“一或多个”;而 $ 指示“行结束”。没有指定动作,所以 Lex 生成的程序(yylex)将忽略这些字符。所有其他东西都被复制。要把任何余下的空白或 tab 的字符串改变为一个单一的空白,可增加另一个规则: % t+$ ; t+ printf( );为这个源码生成的有限自动
8、机将立刻扫描这两个规则,在空白或 tab 的字符串的终止处观察是否有一个换行字符,并执行想要的规则动作。第一个规则匹配在行结束处的所有空白或 tab 的字符串,而第二个规则匹配所有余下的空白或 tab 的字符串。Lex 可以单独的用做简单变换,或在词法层次上聚集(gather)出的分析和统计。Lex 还可以与解析器一起使用而进行词法分析阶段;交接 Lex 与 Yacc 3 是特别容易的。Lex 程序只识别正则表达式;Yacc 写出接受一大类上下文无关文真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?
9、真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?真的不掉线吗?、?法的解析器,但是需要底层的分析器来识别输入记号(token)。所以,Lex 和 Yacc 真的不掉线吗?、?真的不掉线吗?、?的组合经常是适当的。在用做后面的解析器生成器的预处理器的时候,Lex 用来划分输入流,而解析器生成器指派文法结构到结果的词法块(piece)。这种情况下的(编译器的前半部分)控制流在图 2 中展示。其他生成器或手工写的额外的程序可以轻易的增加到 Lex 写出的程序。 词法规则 文法规则 | | v v +-+ +-+ | Lex | | Yacc
10、 | +-+ +-+ | | v v +-+ +-+ 输入 - | yylex | - | yyparse | - 解析后的输入 +-+ +-+Lex 与 Yacc 一起图 2Yacc 用户会发现 yylex 的名字就是 Yacc 期望词法分析器叫的名字,所以 Lex 采用这个名字简化了交接。Lex 从源码中的正则表达式生成一个确定有限自动机4。为了节省空间,这个自动机是解释的而不是编译的。结果仍是一个快速的分析器。特别是,Lex程序识别和划分输入流所花费的时间正比于输入的长度。Lex规则的数目或规则的复杂性在决定速度上都不重要,除了包含前向(forward)上下文的规则需要大量的重新扫描之外
11、。与规则的数目和复杂性一起增加的是 自动机的大小,因此也是 Lex 生成的程序的大小。 在 Lex 写出的程序中,用户的片段(表示在找到每个正则表达式时要进行的动作)被收集一起成为 switch语句中各个 case。自动机的解释器导向控制流。提供给用户在包含动作的例程中插入声明或增加语句,或者在这些动作例程之外增加例程的机会。 Lex 不受限制于可在提前查看一个字符基础上得到解释的源码。例如,如果有两个规则一个查找 ab 而另一个查找 abcdefg,则在输入流是 abcdefh 的时候,Lex 将识别 ab 并留下输入指针正好在 cd 之前。这种回退比起简单语言的处理要更加高代价。 2. L
12、ex 源码 Lex 源码的一般格式为: 定义%规则%用户子例程这里的定义和用户子例程部分经常被省略。第二个 % 是可选的,但是需要第一个来标记规则的开始。绝对极小的 Lex 程序是 %(没有定义,没有规则)它被变换成无改变的复制输入到输出的一个程序。 在上述 Lex 程序的轮廓中,规则代表用户的控制决定;它们是个表格,在其中左列包含正则表达式(参见章节 3)而右列包含动作,在识别了表达式的时候要执行的程序片段。所以如下一个单独规则 integer printf(found keyword INT);在输入流中查找 integer 字符串并在它出现的时候打印消息“found keyword IN
13、T”。在这个例子中宿主过程语言是 C 并使用 C 库函数 printf 打印这个字符串。表达式的结束通过第一个空白或 tab 字符来指示。如果动作只是一个单一的 C 语言表达式,它可以给出在这行的右侧;如果它是复合的或多余一行,则应当包围在花括号中。作为稍微有用一些的例子,假设想要把一些美式拼写改为英式拼写。 Lex 规则如下 colour printf(color);mechanise printf(mechanize);petrol printf(gas);将是一个好的开始。这些规则非常不够,因为单词 petroleum 将变成 gaseum;后面会讨论处理它的方式。 3. Lex 正则表
14、达式 正则表达式的定义非常类似于 QED5 中的定义。正则表达式指定要被匹配的一组字符串。它包含文本字符(它匹配被比较的字符串中的相应的字符)和操作符字符(它指定重复、选择和其他特征)。字母表字母和数字总是文本字符;所以正则表达式 integer匹配字符串 integer 只要它出现,而表达式 a57D查找字符串 a57D。 操作符操作符字符有 - ? . * + | ( ) $ / % 如果它们被用做文本字符,应当使用转义(escape)。引号操作符()指示在一对引号之间包含的任何东西都被当作文本字符。所以 xyz+匹配字符串 xyz+,在它出现的时候。注意可以引用字符串的一部分。引用普通字
15、符是无害和没有必要的;表达式 xyz+同于上面的表达式。所以通过引用用做文本字符的所有非字母数字字符,用户可以避免记住上面的操作字符列表,并在 Lex 进一步扩展这个列表的时候是安全。 还可以通过前导一个 来把一个操作符字符转义为一个文本字符,比如 xyz+是上述表达式的另一个更少可读性的等价者。引用机制的另一个用处是把空白介入到表达式中;如上所述正常情况下空白或 tab 结束一个规则。不包含在 (见后)内的任何空白字符必须被引用。还识别使用 的一些常见的 C 转义: n 是换行、t 是 tab 而 b 是退格(backspace)。要录入 自身需使用 。因为换行在一个表达式中是非法的,必须使
16、用 n;不需要转义 tab 和退格。除了空白、tab、换行和上述列表中字符之外的所有字符总是文本字符。 字符类字符类可以使用运算符对 来指定。构造 abc 匹配一个单一字符,可以是 a、b 或 c。在方括号内,忽略多数字符的意义。只有三个字符特殊: 它们是 - 和 。- 字符指示范围。例如 a-z0-9_指示包含所有小写字母、数字、尖括号和下划线的字符类。可以按任意次序给出范围。使用不都是大写字母、不都是小写字母、或不都是数字的在任何一对字符之间 的“-”都是依赖实现的并会得到一个警告消息。(比如,0-z 在 ASCII 中比在 EBCDIC 中有更多字符)。如果需要在字符类中包含字符 - ,
17、它应当在第一个或最后一个位置上;所以 -+0-9匹配所有数字和两个算符。 在字符类中, 操作符必须出现为左方括号后的第一个字符;它只是结果的字符串关于计算机字符集的补集。所以 abc匹配除了 a、b 或 c 的所有字符,包括了特殊或控制字符;而 a-zA-Z是不是字母的任何字符。 字符提供在字符类方括号内的正常转义。 任意字符 为了匹配最任何的字符,操作符字符 . 是除了换行之外所有字符的类。转义八进制数是可能的,尽管是不可移植的: 40-176匹配在 ASCII 字符集中所有可打印字符,从八进制的 40(空白)到八进制的 176(波浪线)。可选的表达式 操作符 ? 指示表达式的一个可选元素。
18、所以 ab?c匹配 ac 或者 abc。 重复的表达式 操作符 * 和 + 指示类的重复。 a*是任何数目的连续的 a 字符,包括零个;而 a+是 a 的一个或多个实例。例如 a-z+是所有小写字母的字符串。而 A-Za-zA-Za-z0-9*指示开始于字母字符的所有字母数字的字符串。这是识别计算机语言中标识符的典型表达式。选择和组合 操作符 | 指示选择: (ab|cd)匹配要么 ab 要么 cd。注意使用圆括号作为组合,尽管它们在最外层不是必须的; ab|cd就足够了。可以使用圆括号形成更复杂的表达式: (ab|cd+)?(ef)*匹配字符串如 abefef、efefef、cdef 或 c
19、ddd;但不匹配 abc、abcd 或 abcdef。上下文敏感Lex 会识别少量的外围上下文。两个最简单的这种操作符是 和 $。如果一个表达式的第一个字符是 ,这个表达式将只在一行的开始处被匹配(在一个换行字符之后,或在输入流的开始处)。这永不会冲突于 的其他意义,即表示字符类的补集,因为它只适用在 操作符内。如果最后的字符是 $,则这个表达式只在一行的结束处被匹配(在立即跟随着换行的时候)。$ 操作符是指示尾随上下文的 / 操作符字符的特殊情况。表达式 ab/cd匹配字符串 ab,但只在它跟随着 cd 的时候。所以 ab$同于 ab/n左上下文在 Lex 中通过在章节 10 中解说的开始条
20、件来处理。如果一个规则只在 Lex 自动机解释器处在开始条件 x 下的时候执行,这个规则应前导着 使用了尖括号操作符字符。如果我们把“在一行的开始处”考虑为开始条件 ONE,则 操作符将等价于 后面会详细解说开始条件。 重复和定义 操作符 指定要么重复(如果包围了数字)要么定义展开(如果包围了一个名字),例如 digit查找叫做 digit 的一个预定义的字符串并把它插入到这个表达式中这一点上。在 Lex 输入中这种定义在规则前面的第一部分中给出。相反的 a1,5查找 a 的 1 到 5 次出现。最后,初始的 % 是特殊的,它作为 Lex 源码分段的分隔符。 4. Lex 动作 当按如上规定所
21、写出的表达式被匹配了的时候,Lex 就执行相应的动作。本章节描述 Lex 辅助书写动作的某些特征。注意有一个缺省动作把输入复制到输出。它进行在所有没有匹配的字符串上。所以希望抛弃整个输入而不产生任何输出的 Lex 用户必须提供匹配所有东西的规则。当与 Yacc 一起使用 Lex 的时候,这是正常情况。你可能认为动作就是替代复制输入到输出而所要做的;所以一般而言,只做复制的规则可以省略。从规则中被忽略了的、并出现在了输入中 的字符组合好象应该被打印在输出中,以此引起对规则有缺口的注意。可以做的最简单的事情是忽略输入。指定一个 C 空语句 ; 作为动作导致这种结果。常见的规则是 tn ;它导致三个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- lex 一个 词法 分析器 生成器 翻译
限制150内