词法分析实验
一、实验题目
编写Tiny语言的词法分析程序。
二、实验目的
1，构造Tiny词法分析程序，程序要求能对输入的字符串流进行词法分析。
2，在实验的过程中，学会应用单词分析的方法——构造NFA（非确定有穷自动机）和DFA（确定有穷自动机）。 3，使用Lex工具分析词法。
三、实验要求
1、独立完成实验
2、由老师现场检查程序代码和运行结果
3、提交代码实验报告：包含程序代码和运行结果截图
四、实验环境
操作系统：Windows/Linux 开发语言：C/C++
开发工具：Cygwin(在windows平台上运行的UNIX模拟环境)；Lex词法分析工具。
五、实验内容
采用下面两种方式对给定的样本语言Tiny实现一个扫描程序： 1、使用Lex自动生成词法分析程序， 2、自己编写一个Tiny词法分析程序。 输出结果包含
1、打印出符号(Token)所在的源代码中的行数，
2、以二元组方式打印符号，例如<1, IF>，
3、打印该符号的类型：（保留字（Reserved word）、特殊符号(Special Symbol)和“其他” (Other)）。 Tiny语言介绍
Tiny语言在语法上是一个由分号分隔开的语句序列。没有过程，没有声明，所有变量都是整形变量。Tiny语言有两个控制语句，分别是if语句和repeat语句。Tiny的记号分为3个典型类型：保留字、特殊符号和“其他”记号。 1，保留字
if、then、else、end、repeat、until、read、write 2，特殊符号 + - * / =<( ); := 3，其他
数(NUM)和标识符(ID)，ID和NUM通过以下正则表达式表示： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9
除了记号之外，Tiny程序还要遵循以下的词法惯例：注释应放在花括号{...}中，且不可嵌套；代码应是自由格式；空白格由空格、换行符和制表符组成。最长子串原则后须接标识记号。
DFA图如下：
示例代码： { Sample program in TINY language - computes factorial } read x; { input an integer } if 0 < x then { don't compute if x <= 0 } fact := 1; repeat fact := fact * x; x := x - 1 until x = 0; write fact { output factorial of x } end
六、实验相关知识
6.1 Lex词法生成器介绍
Lex(Lexical Analyzer)是用C语言开发的一种词法分析器自动生成工具，它提供一种供开发者编写词法规则（正规式等）的语言（Lex语言）以及这种语言的翻译器（这种翻译器将Lex语言编写的规则翻译成为C语言程序）。
6.1.1 Lex的基本原理和使用方法
Lex的基本工作原理为：由正规式生成NFA，将NFA变换成DFA，DFA经化简后，模拟生成词法分析器。
正规式由开发者使用Lex语言编写，其余部分由Lex翻译器完成。 翻译器将Lex源程序翻译成一个名为lex.yy.c的C语言源文件，此文件含有两部分内容：一部分是根据正规式所构造的DFA状态转移表，另一部分是用来驱动该表的总控程序yylex()。当主程序需要从输入字符流中识别一个记号时，只需要调用一次yylex()就可以了。为了使用Lex所生成的词法分析器，我们需要将lex.yy.c程序用C编译器进行编译，并将相关支持库函数连入目标代码。Lex的使用步骤可如下图所示：
Lex 源程序 lx.lLex 翻译器lex.yy.cC编译器a.out词法分析器
图一 生成词法分析器的过程
输入字符流a.out输出记号序列
图二 使用所生成的词法分析器
6.1.2 Lex源程序的写法
Lex源程序必须按照Lex语言的规范来写，其核心是一组词法规则（正规式）。一般来说，一个Lex源程序分为三部分，三部分之间以符号%%分隔。示例程序如表一所示：
第一部分：定义段 %% 第二部分：词法规则段 %% 第三部分：辅助函数段 表一 Lex源程序示例
红色部分可以省略。以%开头的符号和关键字，或者是词法规则段的各个规则一般顶行首写，前面没有空格。 Lex源程序中注释由/*和*/构成，但是注释的行首需要有前导空白。
（1）第一部分定义段的写法 定义段可以分为两部分。
第一部分包含在符号%{和%}之间，用C语言写定义和声明：例如，头文件包含，宏定义，常数定义，全局变量及外部变量定义，函数声明等。这一部分被Lex翻译器处理后会全部拷贝到文件lex.yy.c中。注意，特殊括号%{和%}都必须顶行首写。例如： %{
#define LT 1 int yylval; %}
第二部分是一组正则表达式的定义和状态定义。为了简化词法规则，给一部分正则表达式定义了名字，顶行首写。例如下面这组正规定义分别定义了letter，digit和id所表示的正规式： letter [A-Za-z] digit [0-9]
id {letter}({letter}|{digit})*
第三部分是状态定义，也叫环境定义，它定义了正则表达式时所处状态的名字。状态定义以%s开始，后跟所定义的状态的名字，注意%s也要顶行首写，例如下面一行就定义了一个名为COMMENT的状态和一个名为BAD的状态，状态名之间用空白分隔： %s COMMENT BAD
（2） 第二部分词法规则段的写法：
词法规则段列出的是词法分析器需要匹配的正则表达式，以及匹配该正则表达式后需要进行的相关动作。其例子如下： while {return (WHILE);} do {return (DO);}
{id} {yylval = installID (); return (ID);}
每行都是一条规则。该规则的前一部分是正则表达式，需要顶行首写。后一部分是匹配该正则表达式后需要进行的动作，这个动作是用C语法来写的，被包含在{}之内，被Lex翻译器翻译后会被直接拷贝进lex.yy.c。正则表达式和语义动作之间要有空白隔开。前一部分中的{}里包含的是正则表达式的名字。 若干个正规式也可以匹配同一条语义动作，此时正规式之间要用 | 分隔。 （3）第三部分辅助函数段的写法：
辅助函数段用C语言语法来写，辅助函数一般是在词法规则段中用到的函数。这一部分一般会被直接拷贝到lex.yy.c中。
（4）Lex源程序中词法规则（即正则表达式）的相关规定：
字符 A-Z, 0-9, a-z . - [ ] 含义 构成了部分模式的字符和数字。 匹配任意字符，除了 \\n。 用来指定范围。例如：A-Z 指从 A 到 Z 之间的所有字符。 一个字符集合。匹配括号内的任意字符。如果第一个字符是 ^ 那么它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一个。 匹配 0个或者多个上述的模式。 匹配 1个或者多个上述模式。 匹配 0个或1个上述模式。 作为模式的最后一个字符匹配一行的结尾。 指出一个模式可能出现的次数。例如: A{1,3} 表示 A 可能出现1次或3次。 用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。 否定。 * + ? $ { } \\ ^ | 表达式间的逻辑或。 \一些符号>\字符的字面含义。元字符具有。 / 向前匹配。如果在匹配的模版中的“/”后跟有后续表达式，只匹配模版中“/”前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。 ( ) 将一系列常规表达式分组。 （5）Lex源程序中常用到的变量及函数：
yyin和yyout：这是Lex中本身已定义的输入和输出文件指针。这两个变量指明了lex生成的词法分析器从哪里获得输入和输出到哪里。默认：键盘输入，屏幕输出。
yytext和yyleng：这也是lex中已定义的变量，直接用就可以了。 yytext：指向当前识别的词法单元（词文）的指针 yyleng：当前词法单元的长度。
ECHO：Lex中预定义的宏，可以出现在动作中，相当于fprintf(yyout, “%s”,yytext)，即输出当前匹配的词法单元。
yylex()：词法分析器驱动程序，用Lex翻译器生成的lex.yy.c内必然含有这个函数。
yywrap()：词法分析器遇到文件结尾时会调用yywrap()来决定下一步怎么做： 若yywrap()返回0，则继续扫描；若返回1，则返回报告文件结尾的0标记。由于词法分析器总会调用yywrap，因此辅助函数中最好提供yywrap，如果不提供，则在用C编译器编译lex.yy.c时，需要链接相应的库，库中会给出标准的yywrap函数（标准函数返回1）。
%{ int yywrap(void); %} %% %% int yywrap(void) { return 1; }
Lex源文件中的yywrap函数是必须的,具体的原因就是因为给了这个函数实 现之后就可以不需要依赖flex库了。通常的做法就是直接返回1，表示输入已经结束了。
（6） 词法分析器的状态：
词法分析器在匹配正则表达式时，可以在不同状态下进行。我们可以规定在不同的状态下有不同的匹配方式。每个词法分析器都至少有一个状态，这个状态叫做初始状态，可以用INITIAL或0来表示。如果还需要使用其他状态，可以在定义段用%s 来定义。
使用状态时，可以用如下方式写词法规则：
这两行词法规则表示：在状态state1和state2下，匹配正则表达式p0后执行动作action0，而只有在状态state1下，才可以匹配正规式p1后执行动作action1。如果不指明状态，默认情况下处于初始状态INITIAL。
要想进入某个特定状态，可以在动作中写上这样一句： BEGIN state; 执行这个动作后，就进入状态state。
下面是一段处理C语言注释的例子，里面用到了状态的转换，在这个例子里，使用不同的状态，可以让词法分析器在处于注释中和处于注释外时使用不同的匹配规则： ? %s c_comment %%
7. Lex的匹配策略：
1. 按最长匹配原则确定被选中的单词
2. 如果一个字符串能被若干正规式匹配，则先匹配排在前面的正规式。
6.1.3 Lex生成的词法分析器如何使用
lex常常与语法分析器的生成工具yacc（第三章会讲到）同时使用。此时，一般来说，语法分析器每次都调用一次yylex()获取一个记号。如果想自己写一个程序使用lex生成的词法分析器，则只需要在自己的程序中按需要调用yylex()函数
即可。
七、其他
7.1 关于cygwin
（1）cygwin的官方网站：www.cygwin.com 。
下载地址：https://cygwin.com/setup-x86.exe （2）安装截图
注意：选择Install from Local Directory ?选一个root directory(例如可以选D:\\cygwin，不要选中文路径名) ?选一个Local Package Directory（选择存放安装包的那个目录）?select package，选中Devel下的bison,flex,gcc-core,gcc-g++, make 和Editors 下的vim，其他默认。 （3）Cygwin与 Windows 共享目录
7.2在Cygwin编译链接Lex源程序的命令 1. 用Lex翻译器编译Lex源程序命令 flex filename.l
? 假设filename.l是Lex源程序名，Lex翻译器生成的c源程序名固定为
lex.yy.c。
2. 用gcc编译器编译Lex翻译器生成的c源程序 gcc [-o outfile] lex.yy.c –lfl
? 其中，-lfl是链接flex的库函数的，库函数中可能包含类似yywrap一类
的标准函数。-o outfile是可选编译选项，该选项可将编译生成的可执行程序命名为outfile，如果不写该编译选项，默认情况下生成的可执行程序名为a.out
3. 调用词法分析器yylex()的main函数可以写在Lex源程序的辅助函数部分，也可以写在其他的c文件中。如果main函数写在main.c中，则编译时需要和lex.yy.c一起编译链接，即编译链接命令为： gcc [-o outfile] lex.yy.c main.c –lfl 4. 运行可执行文件a.out的命令 ./a
其中，./表示当前目录