[educoder实训]用LEX(FLEX)生成PL语言的词法分析器
  • 实验平台Flex (The Fast Lexical Analyzer)https://www.gnu.org/software/flex/
  • 实训目标理解LEX(FLEX)源程序的结构规范,能够设计LEX(FLEX)程序,生成词法分析程序。
  • 词法规则任务中提供了PL 语言单词符号及其种别值。
  • 功能输入一个PL语言源程序文件输出一个文本文件,该文件包括每一个单词及其种别枚举值,每行一个单词
  • 任务描述
    • 第1关:什么是lex/flex? 学习LEX(FLEX)的语法结构,学会如何写LEX程序。
    • 第2关:用FLEX生成PL语言的词法分析器 利用FLEX工具生成PL语言的词法分析器,实现对输入的PL语言源程序进行词法分析,识别出单词符号。

第1关:什么是lex/flex?

任务描述

相信你学习过编译原理之后,一定是跃跃欲试,想要自己实现一个词法分析器,但是呢,别着急动手,要学会站在巨人的肩膀上。你是否发现,自己编写一大段重复或者类似的scanfif语句来识别字符串十分麻烦?实际上,我们已经有了lex这个强大的工具。Lex是Lexical Compiler的缩写,是Unix环境下非常著名的工具,主要功能是生成一个词法分析器(scanner)的C源码,描述规则采用正则表达式(regular expression)。Flex(The Fast Lexical Analyzer)是GNU/Linux下的lex版本。

相关知识

为了完成本关任务,你需要掌握:1.lex/flex的语法结构,2.如何写一条规则。

lex/flex的语法结构

lex/flex是通过处理其源文件来生词法和语法分析器的,源文件的扩展名为.l,其语法被分为三个部分::

/* 定义段 */
%{
%}
%%
/* 规则段 */
%%
/* 用户子程序段 */

三个段用 %% 进行分离。

  1. 定义段,这一部分一般是一些声明及选项设置等。C 语言的注释、头文件包含等一般就放在 %{ %} 之间,这一部分的内容会被直接复制到输出文件的开头部分;
  2. 规则段为一系列匹配模式和动作,模式一般使用正则表达式书写,动作部分为C代码:模式1 {动作1(C代码)},在输入和模式 1 匹配的时候,执行动作部分的代码;规则
  3. 用户子程序段,这里为 C 代码,会被原样复制到输出文件中,一般这里定义一些辅助函数等,如动作代码中使用到的辅助函数。
如何写一条规则

下面通过一个简单的例子来学习如何写一条规则:

/* 这里是定义段 */
%{
/* 这里的部分会被直接拷贝到生成的 .c 文件的开始部分,在这里可以包含需要使用的头文件,如 stdio.h
*/
#include <stdio.h>
%}
/* 下面是规则段 */
%%
/* 这里定义了四条规则,前面的部分是模式,处于一行的开始位置,后面的部分是动作。第一个模式是匹配连续的一个到多个字符,匹配到之后就将其打印出来。注意到 yytext,在输入匹配到该模式的时候,匹配的部分就存储在这个 yytext 里面,这里把它作为字符串直接输出就可以了;第二条规则的模式部分,就是匹配连续的一个或者多个数字,匹配到了之后,也是以字符串的形式输出;第三条规则的模式部分,就是匹配一个换行符了,并且匹配到之后就打印一个新行的信息;第四条规则的模式部分,是一个点。正则表达式里面这个也就是匹配任何除了 \n 之外的字符。因此,下面的规则就是,匹配到字符串,则将该字符串输出,匹配到连续数字,将其输出;匹配到换行符,打印一条信息;匹配到任何其他的字符,则直接忽略*/
[a-zA-Z]+       {printf("get string:%s\n", yytext);}
[0-9]+          {printf("get number:%s\n", yytext);}
\n              {printf("get new line\n"); }
.               { }
/* 下面是用户子程序段 */
%%
int yywrap() { return 1; }
int main(int argc, char** argv) {
    if (argc > 1) {
        if (!(yyin = fopen(argv[1], "r"))) {
            perror(argv[1]);
            return 1;
        }
    }
    while (yylex());
    return 0;
}

编程要求

根据提示,在右侧编辑器补充代码,实现对以小写字母ab结尾的字符串(只包含大小写字母)的识别,如HelloabGoab

注意,你只需要保证合法的输入(以ab结尾的字符串)有结果,不合法的输入将会包含在.规则中。

测试说明

平台会对你编写的代码进行测试:

测试输入:HelloabGoabHiAbabAB

预期输出:

Helloab: Hit!

Goab: Hit!

ab: Hit!

 /* 简单词法分析器 */
 /* 功能:能够识别出以小写字母ab结尾的所有字符串(仅含大小写字母)并给打印'Hit!' */
 /* 说明:在下面的begin和end之间添加代码,已经实现了标识符和整常量的识别,你需要完成剩下的部分,加油吧! */
 /* 提示:你只需要保证合法的输入(以ab结尾的字符串)有结果,不合法的输入将会包含在.规则中~ */
%{
#include <stdio.h>
%}
%%
 /* begin */
[a-zA-Z]*ab          printf("%s: Hit!\n",yytext);
 /* end */
\n				{}
.				{}
%%
int yywrap() { return 1; }
int main(int argc, char **argv)
{
	if (argc > 1) {
		if (!(yyin = fopen(argv[1], "r"))) {
			perror(argv[1]);
			return 1;
		}
	}
	while (yylex());
	return 0;
}

第2关:用flex生成PL语言的词法分析器

任务描述

经过上个任务的磨砺,相信大家已经熟悉了lex/flex的使用。这一次我们将利用flex工具生成PL语言的词法分析器,要求输入一个PL语言源程序文件demo.pl,输出一个文件tokens.txt,该文件包括每一个单词及其种别枚举值,每行一个单词。

相关知识

为了完成本关任务,你需要掌握:flex的语法和使用规则。本教程会简略的介绍flex的相关知识,没有涉及全部细节,如果有想深入探究的同学,可以参考flex2.5手册。[flex2.5.pdf]

flex的语法以及使用规则

为了激起大家的回忆,这里再给出flex的语法规则以及上个任务中的例子。flex是通过处理其源文件来生词法和语法分析器的,源文件的扩展名为.l,其语法被分为三个部分:

/* 定义段 */
%%
/* 规则段 */
%%
/* 用户子程序段 */

三个段用 %% 进行分离。

  1. 定义段,这一部分一般是一些声明及选项设置等。C 语言的注释、头文件包含等一般就放在 %{ %} 之间,这一部分的内容会被直接复制到输出文件的开头部分;
  2. 规则段为一系列匹配模式和动作,模式一般使用正则表达式书写,动作部分为C代码:模式1 {动作1(C代码)},在输入和模式 1 匹配的时候,执行动作部分的代码;

关于Lex源程序格式的规范,请参看flex手册的第6章 Format of the input file。

下表列出了部分常用的正则表达式,其余的部分参见flex手册的第7章-Patterns。

规则 注意:规则行务必没有缩进,且对应的动作必须在同一行开始。

  1. 用户子程序段,这里为 C 代码,会被原样复制到输出文件中,一般这里定义一些辅助函数等,如动作代码中使用到的辅助函数。

下面看一个简单的例子:

/* 这里是定义段 */
%{
/* 这里的部分会被直接拷贝到生成的 .c 文件的开始部分,在这里可以包含需要使用的头文件,如 stdio.h
*/
#include <stdio.h>
%}
%%
/* 下面是规则段 */
/* 这里定义了四条规则,前面的部分是模式,处于一行的开始位置,后面的部分是动作。第一个模式是匹配连续的一个到多个字符,匹配到之后就将其打印出来。注意到 yytext,在输入匹配到该模式的时候,匹配的部分就存储在这个 yytext 里面,这里把它作为字符串直接输出就可以了;第二条规则的模式部分,就是匹配连续的一个或者多个数字,匹配到了之后,也是以字符串的形式输出;第三条规则的模式部分,就是匹配一个换行符了,并且匹配到之后就打印一个新行的信息;第四条规则的模式部分,是一个点。正则表达式里面这个也就是匹配任何除了 \n 之外的字符。因此,下面的规则就是,匹配到字符串,则将该字符串输出,匹配到连续数字,将其输出;匹配到换行符,打印一条信息;匹配到任何其他的字符,则直接忽略*/
[a-zA-Z]+       {printf("get string:%s\n", yytext);}
[0-9]+          {printf("get number:%s\n", yytext);}
\n              {printf("get new line\n"); }
.               { }
%%
/* 下面是用户子程序段 */
int yywrap() { return 1; }
int main(int argc, char** argv) {
    if (argc > 1) {
        if (!(yyin = fopen(argv[1], "r"))) {
            perror(argv[1]);
            return 1;
        }
    }
    while (yylex());
    return 0;
}

编程要求

根据提示,在右侧编辑器补充代码,设计识别PL语言单词符号的词法分析器。

PL语言单词符号及其种别值

PL语言单词符号及其种别值 注意,这里还有一个类别ERROR,包括不是出现在字符串中的非法字符,有~!@#$%^&_\ 当词法分析器读到非法字符时,应该输出ERROR作为种别值。

识别PL单词的状态图
识别PL单词的状态图

测试说明

平台会对你编写的代码进行测试: 一共有5个测试集。

测试输入1:Test2_1.PLS; 这个测试集主要测试对算术运算符的识别。 需要完成的种别有:IDENT,INTCON,PLUS,MINUS,TIMES,DIVSYM,BECOME。

测试输入2:Test2_2.PLS 这个测试集主要测试对字符常量的识别。 需要完成的种别有:CHARCON。

测试输入3:Test2_3.PLS 这个测试集主要测试对比较运算符的识别。 需要完成的种别有:IDENT,EQL,NEQ,LSS,LEQ,GTR,GEQ。

测试输入4:Test2_4.PLS 这个测试集是一个完整PL源程序。 需要完成的种别有:所有PL可以识别的种别。

测试输入5:Test2_5.PLS 这个测试集是一个完整PL源程序中间插入了非法字符,需要将其识别出来。 需要完成的种别有:所有PL可以识别的种别+ERROR。

 /* PL词法分析器 */
 /* 功能:能够识别出PL支持的所有单词符号并给出种别值 */
 /* 说明:在下面的begin和end之间添加代码,已经实现了标识符和整常量的识别,你需要完成剩下的部分,加油吧! */
 /* 提示:因为是顺序匹配,即从上至下依次匹配规则,所以需要合理安排顺序~ */
%{
#include <stdio.h>
%}
 /* begin */
INTCON	0|(\-?[1-9][0-9]*) 
IDENT	[A-Za-z][A-Za-z0-9]*
CHARCON \'[^']*\'
PLUS    \+
MINUS   \-
TIMES   \*
DIVSYM  \/
EQL     \=
NEQ     \<\>
LEQ     \<\= 
GEQ     \>\=
LSS     \<
GTR     \>
LBRACK  \[
RBRACK  \]
LPAREN  \(
RPAREN  \)
COMMA   \,
SEMICOLON \;
PERIOD  \.
BECOME  \:\=
COLON   \:
ERROR   [~!@#$%^&_\\]
 /* end */

%%
 /* begin */
of     	        {printf("%s: OFSYM\n", yytext);}
array		    {printf("%s: ARRAYSYM\n", yytext);}
program		    {printf("%s: PROGRAMSYM\n", yytext);}
mod		        {printf("%s: MODSYM\n", yytext);}
and		        {printf("%s: ANDSYM\n", yytext);}
or		        {printf("%s: ORSYM\n", yytext);}
not		        {printf("%s: NOTSYM\n", yytext);}
begin		    {printf("%s: BEGINSYM\n", yytext);}
end		        {printf("%s: ENDSYM\n", yytext);}
if		        {printf("%s: IFSYM\n", yytext);}
then		    {printf("%s: THENSYM\n", yytext);}
else		    {printf("%s: ELSESYM\n", yytext);}
while		    {printf("%s: WHILESYM\n", yytext);}
do		        {printf("%s: DOSYM\n", yytext);}
call		    {printf("%s: CALLSYM\n", yytext);}
const		    {printf("%s: CONSTSYM\n", yytext);}
type		    {printf("%s: TYPESYM\n", yytext);}
var		        {printf("%s: VARSYM\n", yytext);}
procedure		{printf("%s: PROCSYM\n", yytext);}
{INTCON}		{printf("%s: INTCON\n", yytext);}
{IDENT}			{printf("%s: IDENT\n", yytext);}
{CHARCON}		{printf("%s: CHARCON\n", yytext);}
{PLUS}			{printf("%s: PLUS\n", yytext);}
{MINUS}			{printf("%s: MINUS\n", yytext);}
{TIMES}			{printf("%s: TIMES\n", yytext);}
{DIVSYM}		{printf("%s: DIVSYM\n", yytext);}
{EQL}			{printf("%s: EQL\n", yytext);}
{NEQ}			{printf("%s: NEQ\n", yytext);}
{LEQ}			{printf("%s: LEQ\n", yytext);}
{GEQ}			{printf("%s: GEQ\n", yytext);}
{LSS}			{printf("%s: LSS\n", yytext);}
{GTR}			{printf("%s: GTR\n", yytext);}
{LBRACK}		{printf("%s: LBRACK\n", yytext);}
{RBRACK}		{printf("%s: RBRACK\n", yytext);}
{LPAREN}		{printf("%s: LPAREN\n", yytext);}
{RPAREN}		{printf("%s: RPAREN\n", yytext);}
{COMMA}			{printf("%s: COMMA\n", yytext);}
{SEMICOLON}		{printf("%s: SEMICOLON\n", yytext);}
{PERIOD}		{printf("%s: PERIOD\n", yytext);}
{BECOME}	    {printf("%s: BECOME\n", yytext);}
{COLON}			{printf("%s: COLON\n", yytext);}
{ERROR}			{printf("%s: ERROR\n", yytext);}
 /* end */
\n				{}
.				{}
%%

int yywrap() { return 1; }
int main(int argc, char **argv)
{
	if (argc > 1) {
		if (!(yyin = fopen(argv[1], "r"))) {
			perror(argv[1]);
			return 1;
		}
	}
	while (yylex());
	return 0;
}

参考文章:

© 版权声明
THE END
喜欢就支持以下吧
点赞1赞赏
分享
评论 抢沙发

请登录后发表评论