LEX与YACC
一、词法分析程序产生器LEX的用法
1．1 Lex概述
程序设计语言从机器语言发展到今天的象pascal, C等这样的高级语言，使人们可以摆脱与机器有关的细节进行程序设计。但是用高级语言写程序时程序员必须在程序中详尽地告诉计算机系统怎样去解决某个问题，这在某种程度上说也是一件很复杂的工作。
人们希望有新的语言——非常高级的语言，用这种语言程序员仅仅需要告诉计算机系统要解决什么问题，计算机系统能自动地从这个问题的描述去寻求解决问题的途径，或者说将这个问题的描述自动地转换成用某种高级语言如C、FORTRAN表示的程序。这个程序就可以解决给定的问题，这种希望虽然还没有能够完全变成现实，但是在某些具体的问题领域里已经部分地实现了。
这里要介绍的Lex和下章要介绍的Yacc就是在编译程序设计这个领域里的两种非常高级的语言。用它们可以很方便的描述词法分析器和语法分析器，并自动产生出相应的高级语言（C）的程序。
Lex是一个词法分析器（扫描器）的自动产生系统，它的示意图如图1.1。
Lex源程序是用一种面向问题的语言写成的。这个语言的核心是正规表达式（正规式），用它描述输入串的词法结构。在这个语言中用户还可以描述当某一个词形被识别出来时要完成的动作，例如在高级语言的词法分析器中，当识别出一个关键字时，它应该向语法分析器返回该关键字的内部编码。Lex并不是一个完整的语言，它只是某种高级语言（称为lex的宿主语言）的扩充，因此lex没有为描述动作设计新的语言，而是借助其宿主语言来描述动作。我们只介绍C作为lex的宿主语言时的使用方法，在Unix系统中，FORTRAN语言的一种改进形式Ratfor也可以做lex的宿主语言。
图1.1 Lex示意图
Lex自动地表示把输入串词法结构的正规式及相应的动作转换成一个宿主语言的程序，即词法分析程序，它有一个固定的名字yyler，在这里yyler是一个C语言的程序。
Yylex将识别出输入串中的词形，并且在识别出某词形时完成指定的动作。
看一个简单的例子：写一个lex源程序，将输入串中的小写字母转换成相应的大定字母。
程序如下：
%%
[a-z]printf(“%c”.yytext[0]+'A'-'a')；
上述程序中的第一行%%是一个分界符，表示识别规则的开始。第二行就是识别规则。左边是识别小写字母的正规式。右边就是识别出小写字母时采取的动作：将小写字母转换成相应的大写字母。
Lex的工作原理是将源程序中的正规式转换成相应的确定有限自动机，而相应的动作则插入到yylox中适当的地方，控制流由该确定有限自动机的解释器掌握，不同的源程序，这个解释器是相同的。关于lex工作原理的详细情况请参考[3]，这里不多介绍。
1．2 lex源程序的格式
lex源程序的一般格式是：
{辅助定义的部分}
%%
{识别规则部分}
%%
{用户子程序部分}
其中用花括号起来的各部分都不是必须有的。当没有“用户子程序部分”时，第二个%%也可以省去。第一个%%是必须的，因为它标志着识别规则部分的开始，最短的合法的lex 源程序是：
%%
它的作用是将输入串照原样抄到输出文件中。
识别规则都分是Lex源程序的核心。它是一张表，左边一列是正规式，右边一列是相应的动作。下面是一条典型的识别规则：
integer printf（"found keywcrd INT"）;
这条规则的意思是在输入串中寻词形“integer”，每当与之匹配成功时，就打印出“foundkeyword INT”这句话。注意在识别规则中，正规式与动作之间必须用空格分隔开。动作部分如果只是一个简单的C表达式，则可以写在正规式右边同一行中，如果动作需要占两行以上，则须用花括号括起来，否则会出错。上倒也可以写成
integer {printf（"found keyword INT"）;}
下面先介绍识别规则部分的写法，再介绍其余部分。
1.3 Lex用的正规式
一个正规式表示一个字符串的集合。正规式由正文字符与正规式运算符组成．正文字符组成基本的正规式，表示某一个符号串；正规式运算符则将基本的正规式组合成为复杂的正规式，表示字符串的集合。例如：
ab
仅表示字符串ab，而（a b）+ 表示字符串的集合：
｛ab，abab，ababab，…）。
Lex中的正规式运算符有下列十六种：
”\[ ]∧ -？•*+| （）/${} %<>
上述运算符需要作为正文字符出现在正规式中时，必须借助于双引号”或反斜线＼，具体用法是；
xyz“++”或xyz＼+＼+
表示字符串xyz++
为避免死记上述十多个运算符，建议在使用非数字或字母字符时都用双引号或反斜线。
要表示双引号本身可用＼”，要表示反外线用”＼”或\\
前面说过，在识别规则中空格表示正规式的结束，因此要在正规式中引进空格必须借助双引号或反斜线，但出现在方括号[]之内的空格是例外。
几个特殊符号：
＼n是回车换行（newline）
＼t是tab
\b是退格（back space）
下面按照运算符的功能分别介绍上述正规式运算符。
1．字符的集合
用方括号对可以表示字符的集合。正规式
[a b c]
与单个字符a或b或c匹配，在方括号中大多数的运算符都不起作用，只有＼-和∧例外。运算符----表示字符的范围，例如
［a-z 0-9 ＜＞-]
表示由所有小写字母，所有数字、尖括号及下划线组成的字符集合。如果某字符集合中包括-在内，则必须把它写在第一个或最后一个位置上，如
[-+0-9]
与所有数字和正负号匹配。
在字符集合中，运算符∧必须写在第一个位置即紧接在左方括号之后，它的作用是求方括号中除∧之外的字符组成的字符集合相对于计算机的字符集的补集，例如[∧abc]与除去a、b和c以外的任何符号匹配。
运算符＼在方括号中同样发挥解除运算符作用的功能。
2．与任意字符匹配的正规式运算符。形成的正规式与除回车换行符以外的任意字符匹配。
在lex的正规式中，也可以用八进制数字与＼一起表示字符，如
[＼40-＼176]
与ASCII字符集中所有在八进制 40（空格）到八进制176（～）之间的可打印字符匹配。
3．可有可无的表达式
运算得？指出正规式中可有可无的子式，例如
ab?c
与ac或abc匹配，即b是可有可无的。
4．闭包运算
运算符*和十是 Lex正规式中的闭包运算符，它们表示正规式中某子式的重复，例如"a*"表示由0个或多个a组成的字符串的集合，而"a+"表示由1个或多个a 组成的字符串的集合，下面两个正规式是常用的：
[a-z]+
[A-Za-z][A-Za-z 0-9]*
第一个是所有由小写字母组成的字符串的集合，第二个是由字母开头的字母数字串组成的集合。
5、选择和字符组
运算符|表示选择：
（ab|cd）
字符串是什么字符的集合与ab或cd匹配
运算符（）表示一组字符，注意（）与[ ]的区别。（ab）表示字符串ab，而[ab]则表示单个字符a或b。
圆括号（）用于表示复杂的正规式，例如：
（ab|cd+）？（ef）*
与abefef, efef, cdef, cddd匹配，但不与abc, abcd或abcdef匹配。
6、上下文相关性
lex可以识别一定范围的上下文，因此可在一定程度上表示上下文相关性。若某正规式的第一个字符是∧，则仅当该正规出现在一行的开始处时才被匹配，一行的开始处是指整个输入串的开始或者紧接在一个回车换行之后，注意∧还有另一个作作即求补，∧的这两种用法不可能发生矛盾。若某正规式的最后一个字符是$，则仅当该表达式出现在一行的结尾处时才被匹配，一行的结尾处是指该表达式之后紧接一个回车换行。运算符/指出某正规式是否被匹配取决于它的后文，例如: ab/cd，仅在ab之后紧接cd的情况下才与ab匹配。$其实是/的一个特殊情形，例如下面两个正规式等价：
ab$,ab/\ n
某正规式是否被匹配，或者匹配后执行什么样的动作也可能取决于该表达式的前文，前文相关性的处理方法在后面专门讨论，将用到运算符"<>"。
7、重复和辅助定义
当被{}括起来的是数字对时，{}表示重复；当它括起来的是一个名字时，则表示辅助定义的展开。例如：a{1，5} ，表示集合{a.aa.aaa.aaaa.aaaaa}.{digit}则与预先定义的名叫dight的串匹配，并将有定义插入到它在正规式中出现的位置上，辅助定义在后面专门讨论。
最后，符号%的作用是作为lex源程序的段间分隔符。
1．4 Lex源程序中的动作
前面说过当Lex识别出一个词形时，要完成相应的动作。这一节叙述Lex 为描述动作提供的帮助。
首先应指出，输入串中那些不与任何识别规则中的正规式匹配的字符串将被原样照望抄到输出文件中去。因此如果用户不仅仅是希望照抄输出，就必须为每一个可能的词形提供识别规则，并在其中提供相应的动作。用lex为工具写程序语言的词法分析器时尤其要注意。最简单的一种动作是滤掉输入中的某些字符串，这种动作用C的空语句“；”来实现。
例：滤掉输入申中所有空格、tab和回车换行符，相应的识别规则如下：
［\t\n]；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。