编译原理经典算法的可视化实现 #include
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