本节书摘来自华章出版社《编译与反编译技术》一书中的第2章,第2.5节词法分析器的生成器,作者庞建民,陶红伟,刘晓楠,岳峰,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.5 词法分析器的生成器
鉴于各种不同的高级程序语言中单词的总体结构大致相同,基本上都可用一组正规式来描述,因此,人们希望构造一个自动生成系统:对于一个给定的高级语言,只要给出用来描述其各类单词词法结构的一组正规表达式,以及识别各类单词时词法分析程序应采取的语义动作,则该系统便可自动产生此语言的词法分析程序。
1975年美国Bell实验室的M.Lesk和Schmidt基于正规式与有限自动机的理论研究,用C语言研制了一个词法分析程序的自动生成工具LEX。对任何高级程序语言,用户只需用正规式描述该语言的各个词法类(这一描述称为LEX的源程序),LEX就可以自动生成该语言的词法分析程序。LEX及其编译系统的作用如图2-29所示。
一般而言,LEX源程序由用“%%”分隔的三部分组成:第一部分为声明,第二部分为识别规则,最后一部分为辅助过程。其书写格式为:
声明部分
%%
识别规则部分
%%
辅助过程部分
其中,声明部分和辅助过程部分是任选的,而识别规则部分是必需的。如果辅助过程部分缺省,则第二个分隔符号“%%”可以省去;但如果无声明部分,第一个分隔符号“%%”不能省去,因为第一个分隔符号是用于指示识别规则部分的开始。下面将对这三部分的内容及其书写格式进行概括介绍。
声明部分包括变量说明、标识符常量说明和正规定义等。正规定义中的名字可在识别规则中用作正规式的成分。其中除了正规定义式之外的声明必须用“%{”和“}%”括起来。
识别规则部分是具有如下形式的语句序列:
P1 { 动作1 }
P2 { 动作2 }
…
Pn { 动作n }
其中,Pi是一个正规式,描述一种单词模式;动作i是C语言的程序段,表示当一个串匹配模式Pi时,词法分析器应执行的动作。
辅助过程是对识别规则的补充,识别规则部分中某些动作需要调用的过程,如果不是C 语言的库函数,则要在此给出具体的定义。
下面给出一个简单语言的单词符号的LEX源程序例子,其输出单词的类别编码用整数编码表示。
例2.28 下面是识别表2-1中单词符号的LEX源程序。
/*声明部分*/
letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣z
digit→0∣1∣2∣3∣…∣9
%%
/*识别规则部分*/
(1) while {return (1,_);}
(2) for {return (2,_l);}
(3) if {return (3,_);}
(4) else {return (4,_);}
(5) switch {return (5,_);}
(6) case {return (6,_);}
(7) (letter|_)(letter|_|digit)* {yylval = install_id( );
return(7,yylval);}
(8) digit (digit)* {yylval = install_num( );
return(8,yylval);}
(9) * {return (9,_)}
(10) + {return (10,_)}
(11) - {return (11,_)}
(12) = {return (12,_)}
(13) < {return (13,_)}
(14) <= {return (14,_)}
(15) = = {return (15,_)}
(16); {return (16,_)}
%%
/*辅助过程部分*/
yylval = install_id( ) {
…
/该过程负责把单词插入符号表并返回指针,yytext 指向该单词的第一个字符,yyleng 给出它的长度。如果该单词已经出现在符号表中,则返回指向该单词所在表项的指针,否则为它创建一个新表项,将单词填入该表项中,并返回指向新表项的指针/
}
install_num( ) {
…
/*类似于上面的过程,但单词是常数*/
}
LEX可以用两种方式来使用:一种是将LEX作为一个单独的工具,用以生成所需的识别程序;另一种是将LEX与语法分析器自动生成工具(如YACC)结合起来使用,以生成一个编译程序的扫描器和语法分析器。