编译原理经典算法的可视化实现 - 图文 下载本文

编译原理经典算法的可视化实现 #include #include”y.tab.h” Char *yylval; %}

9

编译原理经典算法的可视化实现

3 词法分析器动态演示的设计与实现

3.1 词法分析器描述语言

目前有很多通过基于正规表达式构建词法分析器的工具。前面我们已经知道了可以用Lex工具来构建词法分析器。Lex可以广泛地应用于各种预言词法分析器的描述。我们称这种工具为Lex编译器,而Lex编译器的输入称为Lex语言。我们将使用类Lex语言类说明词法分析器,并存储中间结果,用于词法分析器的动态演示。 3.1.1 Lex说明

一个Lex程序由如下三部分组成:

声明部分 %% 转换规则 %% 辅助过程

声明部分包括变量声明,符号常量声明和正规定义。(符号常量是被声明来表示常数的标识符。)正规定义就作为转换规则中正规表达式中的部分。

Lex程序的转换规则是如下形式的语句: P1 {action1} P2 {action2} … …

Pn {actionn}

其中每个pi是一个正规表达式,每个actioni表示当模式i匹配上一个词素后词法分析器要执行的程序段。在Lex中,这些action是用C语言编写的,当然也可以用其他语言来实现。

我们将action所需要的辅助过程放在Lex的第三部分。这些过程也可以单独编译,

10

编译原理经典算法的可视化实现 并与词法分析器一起装载。

由Lex自动生成的词法分析器与语法分析器共同工作的方式如下:首先,语法分析器调用词法分析器后,词法分析器从还未扫描的输入字符串中读字符,而每次读入一个字符,这个过程直到发现能与某个正规表达式匹配的最长前缀。接下来,词法分析器执行那些动作(action)。通常那些动作也会将控制交给语法分析器。接下来,假设不将控制交给语法分析器,那么词法分析器可以继续发现更多的词素,直到某个操作将控制交给语法分析器。词法分析器的这种不断查找词素,直到以显式的调用结束工作的方式,使其可以方便地处理换行、空白符和注释。而词法分析器只返回记号给语法分析器,带有与词素相关信息的属性值是通过全局变量yylval传递的。 3.1.2 超前扫描操作

对于某些程序设计语言结构,词法分析器需要超前扫描词素后面的若干字符来确定一个记号。假设有这样的Fortran语句例子: DO 5 I = 1.25 DO 5 I = 1,25

在Fortran中,除了在注释和Hollerith串中之外,空格不代表任何意义。我们可以认为在词法分析器开始工作时,所有的空格都已经去掉。这样,上面的两个语句就变为如下形式:

DO5I=1.25 DO5I=1,25

在第一个语句中,直到词法分析器发现了小数点后才可以断定DO是标识符DO5I的一部分。在这个语句中,DO是关键字。

在Lex中我们将模式写成y1/y2的形式,其中的y1和y2是正规表达式。而它的意思是当一个字符串与y1匹配时,还需要其后的字符串与y2匹配。这样才算该字符串与y1匹配成功。在超前扫描操作符/后面的正规表达式y2表示需要进一步匹配的内容,这里它只是匹配模式的一个限制,而不是匹配的一部分。例如,将上述语句中的DO识别为关键字的说明如下:

DO/({letter}|{digit})*=({letter}|{digit})*,

根据这个说明,词法分析器在输入缓冲去超前地扫描一串字母或数字,接着扫描等

11

编译原理经典算法的可视化实现 号以及后面的一串字母或数字,随后扫描到逗号才能够判断出这是不是一个合法的赋值语句。但只有超前扫描符前面的D和O才是与模式匹配的词素的部分。经过成功的匹配,yytext指针指向字符D并且yyleng=2.我们要意识到这个简单的超前扫描模式使得当DO后面跟着一些无意义的符号(如7Q)时也会识别出DO,但它绝不会把做为标识符一部分的DO识别为一个词素。 3.1.3 Lex编程

我们在Windows平台下下载安装flex工具并设置好它的环境变量,而由于我们使用的flex是GNU的工具,所以为了方便,采用的C/C++编译器也采用GNU的编译器GCC,当然我们需要的也是Windows版本的GCC。

至此我们已万事俱备,我们可以开始编写Flex的源文件了。

(1)新建文本文件,将其更名为lex.l,当然这名字无特别含义,你可以自己命名,然后在这个文件中写入Flex的源代码。

(2)打开Windows的控制命令台,如图3.1所示,我们对lex.l运行Flex命令,这时我们就可以看到此时文件夹多了一个文件,此文件即是Flex生成扫描器的C代码。

图3.1 Flex编译过程

(3)然后我们用gcc来编译和链接C代码,这样就生成可执行的扫描器。 在这里,我们为了接下来能动态演示词法分析器,我们在模式后面定义了自己的动作,就是匹配完成后,将该单词的类型码和属性值输出到一个文件中。

3.2词法分析器动态演示的事件实现

3.2.1 词法分析器动态演示的执行事件

在这个词法分析器动态演示程序中,当我们点击执行按钮时,程序就会对Richtextbox中的内容生成txt文件,然后用词法分析器对这个文件中的单词进行词法分

12