《编译与反编译技术》—第2章2.5词法分析器的生成器

本节书摘来自华章出版社《编译与反编译技术》一书中的第2章,第2.5节词法分析器的生成器,作者庞建民,陶红伟,刘晓楠,岳峰,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.5 词法分析器的生成器
鉴于各种不同的高级程序语言中单词的总体结构大致相同,基本上都可用一组正规式来描述,因此,人们希望构造一个自动生成系统:对于一个给定的高级语言,只要给出用来描述其各类单词词法结构的一组正规表达式,以及识别各类单词时词法分析程序应采取的语义动作,则该系统便可自动产生此语言的词法分析程序。
1975年美国Bell实验室的M.Lesk和Schmidt基于正规式与有限自动机的理论研究,用C语言研制了一个词法分析程序的自动生成工具LEX。对任何高级程序语言,用户只需用正规式描述该语言的各个词法类(这一描述称为LEX的源程序),LEX就可以自动生成该语言的词法分析程序。LEX及其编译系统的作用如图2-29所示。
《编译与反编译技术》—第2章2.5词法分析器的生成器

一般而言,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)结合起来使用,以生成一个编译程序的扫描器和语法分析器。

上一篇:android摇一摇实现(仿微信)


下一篇:[教程] 微信支付如何设置商户支付密钥(密钥Key)