编译原理 编译器自动生成工具

• 一、实验目的
• 二、实验任务
• 三、实验内容
• • （一）词法分析程序自动生成工具的使用
  • • 1.学习LEX工具的用法
    • 2.生成LEX版本的TINY词法分析器，与其它部分组合成一个完整的TINY语言编译器，并完成测试验证。（参见tiny编译器的使用.ppt）
  • （二）语法分析程序自动生成工具的使用
  • • 1.学习YACC工具的用法
    • 2.生成YACC版本的TINY语法分析器，与其它部分组合成一个完整的TINY语言编译器，并完成测试验证。
• 四、系统设计
• • 1.编写某语言（如：C-语言）的词法描述文件，生成其词法分析器，并完成测试验证（C_cifa文件夹）
  • 2.编写某语言（如：C-语言）的语法描述文件，生成其语法分析器并完成测试验证
  • • （1）总体思路：
    • （2）具体实现：
    • （3）C-语法分析文件结构：
    • （4）测试
• 五、总结
• 六、附录

工程链接：https://download.csdn.net/download/weixin_43973089/18848398

仅供参考

一、实验目的

• 学习使用词法分析自动工具LEX。
• 学习使用语法分析程序自动生成工具YACC。

二、实验任务

• 使用LEX工具实现编译器的词法分析程序。
• 使用YACC工具实现编译器的词法分析程序。

三、实验内容

（一）词法分析程序自动生成工具的使用

1.学习LEX工具的用法

(1)学习文档“LEX的用法.pdf”

Lex(A Lexical Analyzer Generator)是词法分析程序的生成器，其输入是描述三型语言的正规式，输出是一个相应的正规表达式的词法分析程序。

输入文件.l文件格式：

Definition section
%%
Rules section
%%
C code section
           

三段，用%%来分割，三个section的含义是：

• Definition Section

  它包括两样东西：第 1件是必须插入到应在这一部分中分隔符“% {”和“% }”之间的任何函数外部的任意C代码（请注意这些字符的顺序）。第2件 是正则表达式的名字也得在该部分定义。这个名字的定义写在另一行的第 1列，且其后（后面 有一个或多个空格）是它所表示的正则表达式。

• Rules section

  包含着一些规则。它们由一连串带有 C代码的正则表达式组成；当匹配相对应的正则表达式时，这些C代码就会被执行。

• auxiliary routines

  分包括着一些C代码，它们用于在第2个部分被调用且不在任何地方被定义的辅助程序。如果要将L e x输出作为独立程序来编译，则这一部分还会有一个主程序。当第2个双百分 号无需写出时，就不会出现这一部分（但总是需要写出第 1个百分号）

(2)准备一个LEX工具

提供的“FLEX251.ZIP”无法使用，因此直接在虚拟机中安装FLEX、BISON。

(3)以文档中提供的4个输入文件为例，测试LEX工具（输入文件代码见附录）。

①lex1.l

该样例描述了一个给文本添加行号的扫描程序，它将其输出发送到屏幕上。

文档给出的代码有误，它将rule部分的line也加了{}，结果报错：

原因：未知（因为我加上{}后把}写成

亦可以通过，迷）；

之后进行flex lex1.l，得到lex.yy.c，并编译生成exe文件；

程序运行结果：

没有输出行号，因为这里只是将lex.yy.c编译；

②lex2.l

样例的作用：串指定的唯一行为就是数字序列。 L e x还生成了一个可匹配所有非数字字符的程序，并将它传送到输出中。

之后进行flex lex2.l，得到lex.yy.c，并编译生成exe文件；

程序运行结果：

③lex3.l

该程序的作用：这个Lex 输入将以字符a 开头或结尾的所有输入行均写到输出上，并消除其他行。行的消除是由E C H O规则下的规则引起的，在这个规则中，为 C行为代码编写一个分号就可为正则表达式. * \ n指定“空”行为。

之后进行flex lex3.l，得到lex.yy.c，并编译生成exe文件；

程序运行结果：

④lex4.l

Lex 生成了将所有的大写字母转变成小写字母的程序，但这不包括 C- 风格注释中的字母（即：任何位于分隔符/ * . . . * /之间的字母。

之后进行flex lex4.l，得到lex.yy.c，并编译生成exe文件；

程序测试结果：

测试完成，Lex工具正常；

2.生成LEX版本的TINY词法分析器，与其它部分组合成一个完整的TINY语言编译器，并完成测试验证。（参见tiny编译器的使用.ppt）

（1）TINY词法分析器：

根据cifa文件夹（实验一中的手工词法分析器）中的其余文件，与lex版本的scan.c扫描程序文件lex.yy.c一起生成cifa.exe文件；

这里需要将makefile中的scan.c替换为lex.yy.c；

接着通过make指令得到cifa.exe可执行文件：

测试样例文件sample.tny得到：

词法分析器正常！

（2）完整TINY编译器（mytiny文件夹）

生成步骤：

①得到TINY的词法文件tiny.l

②输入命令“FLEX tiny.l”生成lex.yy.c

③将lex.yy.c 与其余部分文件放入一个工程中，编译生成tiny.exe编译器

④用tiny.exe程序测试sample.tny得到结果，用tm运行sample.tm文件；

这里直接将tiny_tm中的相关文件复制进来，包括tiny.l输入文件也是，将makefile中的scan.c换成flex生成的lex.yy.c；

执行make指令得到可执行程序tiny.exe（编译器）：

通过./tiny.exe生成sample.tm输出文件如下，样例文件见附录；

通过tm虚拟机来运行sample.tm三地址码文件：

可以看出编译器正常！

（二）语法分析程序自动生成工具的使用

1.学习YACC工具的用法

(1)学习文档“YACC的用法.pdf”

类似于词法分析文件lex，语法描述语言YACC文件的格式也由三部分组成：定义、规则、函数。

• Definition Section

  定义部分包括Yacc需要用来建立分析程序的有关记号、数据类型以及文法规则的信息。它还包括了必须在它的开始时直接进入输出文件的任何C代码(主要是其他源代码文件的#include指示)。说明文件的这个部分可以是空的。

  在Ya c c的%记号(% t o k e n)中声明符号记号，如程序清单5 - 1中的记号N U M B E R。这样的记号被Ya c c赋予了不会与任何字符值相冲突的数字值。Ya c c将这些记号定义作为 # d e f i n e语句插入到输入代码中。因此，在输出文件中就可能会找到行#define NUMBER 258 作为Ya c c对说明文件中的%token NUMBER声明的对应。

• Rules section

  规则部分包括修改的B N F格式中的文法规则以及将在识别出相关的文法规则时被执行的 C代码中的动作(即：根据L A L R ( 1 )分析算法，在归约中使用 )。文法规则中使用的元符号惯例如 下：通常，竖线被用作替换 (也可分别写出替换项)。用来分隔文法规则的左右两边的箭头符号 →在Ya c c中被一个冒号取代了，而且必须用分号来结束每个文法规则。

• auxiliary routines

  辅助程序部分包括了过程和函数声明，除非通过 # i n c l u d e文件，否则它们会不适用，此外还需要被用来完成分析程序和 /或编译程序。这个部分也可为空，此时第 2个双百分号元符号可从说明文件中省略掉。

Ya c c坚持自己生成(而不是引入)，但是它又必须适用于编译程序的许多其他部分 (尤其是扫描程序)。正是由于这个原因，Ya c c就有一个可用的选项，自动产生包含了该信息的头文件，而这个头文件将被包括在需要定义的任何其他文件中。这个头文件通常叫作 y . t a b . h或y t a b . h，并且它与- d选项(用于h e a D e r文件)一起生成。

• 规则识别

  当识别一个文法规则时，规则中的每个符号都拥有一个值，除非它被参数改变了，该值将被认为是一个整型 (稍后将会看到这种情况)。这些值由Ya c c保存在一个与分析栈保持平行的值栈 (value stack)中。每个在栈中的符号值都可通过使用以 ‘$‘开始的伪变量来引用。’$$‘代表刚才被识别出来的非终结符的值，也就是在文法规则左边的符号。伪变量’$ 1’、‘$2’、'$3’等等都代表了文法规则右边的每个连续的符号。

(2) 准备一个YACC工具

提供的bison不可用，直接在虚拟机中apt-get install了bison；

(3)以文档中提供的输入文件为例，测试YACC工具（输入样例见附录）

文档中的输入文件为一个简单计算器程序的Ya cc定义 ，写成test.y文件后测试：

可以看出此语法分析正确，并且，语法制导定义部分完全正确；

2.生成YACC版本的TINY语法分析器，与其它部分组合成一个完整的TINY语言编译器，并完成测试验证。

(1)语法分析器

这里的语法分析器构造依然使用makefile的方式实现：

除了tiny.tab.c语法分析程序是YACC生成的，其它的程序均来自实验一提供的bison文件，测试文件就是.pdf中提供的样例，测试结果如下（未截全图）：

语法分析器正常；

(2)TINY编译器

TINY语言编译器使用验证Lex的，只需要将语法分析部分改为自己的YACC版本即可：

①globals.h中加入：

②修改makefile文件（改为LEX和YACC生成的词法、语法分析版本）：

③make生成可执行文件文件tiny.exe（编译器）、tm（虚拟机）

使用编译器将sample.tny转换为.tm三地址码文件：

生成的tiny.tm文件如下：

④测试

通过生成的tm虚拟机运行tiny.exe编译器生成的三地址码文件tiny.tm：

可以看到该sample.tny文件就是求阶乘，并且编译器转换后的tm文件可以正确运行！

测试正确！

编译器没有问题！

四、系统设计

1.编写某语言（如：C-语言）的词法描述文件，生成其词法分析器，并完成测试验证（C_cifa文件夹）

（可利用增量编程，修改TINY语言的词法描述文件tiny.l，为C-语言编写词法描述文件。）

C-的词法规则结构要比TINY复杂，同时，TINY词法中也含有一些C-没有的关键字，比如repeat这些。由于C-的定义与tiny有所区别，只需要根据C-的规则，对TINY.L进行增删操作即可。

• C-词法规则（.l文件编写）

  **第一部分：**宏定义和词法正则表达式描述，这些根据文档中的定义就可以完成，且C-的词法分析器与TINY一样，需要包含globals.h中的宏定义、SCAN.h中的扫描文件方法，这些头文件都需要包含进去。

  

  第二部分是匹配规则部分：这里将TINY的关键字全部修改为C-语言的关键字，同时结合实验二中所做的词法分析程序，将字符的返回标记全部更改好。通过增量编程的思想，在TINY.L中对相关语句进行修改即可。

  

  注释部分参考了LEX用法.pdf中的第四个例子；

第三部分是用户自定义函数。这一部分与TINY没有差别。

• 通过flex工具与.l文件生成词法分析文件

  

最后，我们还需要对TINY编译器中的其他组件——utils.c、globals.h等文件进行修改，使其符合C-语言的关键字标准。主要是将utils.c中的printtoken函数，更改为适应C-词法分析的关键字代码即可，做出符合增量编程的一些调整，就可以组合成完整的C-词法分析器。

其余部分文件全来自于我的实验3中的词法分析部分；

• 测试

  依然是使用makefile文件（用于生成可执行程序）：

  

  

  测试样例就是.pdf文件中的样例test.C-，如下图：

  

  通过C_cifa.exe运行测试test.C-文件（仅截取部分结果，详细见源程序）：

  

  运行正确！

2.编写某语言（如：C-语言）的语法描述文件，生成其语法分析器并完成测试验证

（可利用增量编程，修改TINY语言的语法描述文件tiny.y，为C-语言编写语法描述文件）

（1）总体思路：

根据C-的规则在Yacc的规则区域声明所有的合法产生式，Yacc会帮助我们自动完成规约。为了完成语法树的建立，需要在每条产生式的规约发生时定义动作进行树的更新：当遇到终结符时，将Token记录于树节点中，当遇到非终结符时，利用Yacc在规约过程中保存的状态栈，将子指针指向栈中的非终结符（$1，$2等代表此位置保存的状态），并附加一些节点性质（如参数列表，定义变量）的信息，直至完成整个分析。

在Yacc的c语言区域重载yyerror函数，使得语法分析出错时输出当前的Token与相应的位置。

为了使得Yacc定义的合法Token能被Lex接收，同时Lex分析得到的Token能被Yacc获取，并且需要保存数据用于词法的扫描与语法树的打印，在全局变量中定义树的结构，树的操作，节点的类型以及词法与语法的检查与转换，声明函数，在词法分析与语法分析中别实现获取Token、打印词法与建立语法树，打印语法树的实例。

（2）具体实现：

• 第1部分是定义区块

  第一个是Y Y S T Y P E的定义(T r e e N o d e本身被定义在g l o b a l s . h中)，这样就允许了Ya c c分析程序构造出一个语法树。第 2个是全程s a v e d N a m e变量的定义，它被用作暂时储存要被插入到还没构造出的树节点中的标识符串，而此时已能在输入中看到这些串了。最后，s a v e d T r e e被用来暂时储存由y y p a r s e过程产生的语法树(y y p a r s e本身可以仅返回一个整型标志)。

  

  同时，需要在.y描述文件中定义词素（因为在第二部分会用到），因此这里需要用%token的方式定义，同时因为这里定义了，那么globals.h中的词素定义就需要删除，否则定义冲突；

  

• 第2部分是规则描述部分

  下面讨论一下与C-的每个文法规则相结合的动作 (这些规则与第3章的程序清单3 - 1中所给出的B N F差不多相同)。在绝大多数情况下，这些动作表示与该点上的分析树相对应的语法树的构造。特别地，需要从 u t i l包调用到n e w S t m t N o d e和n e w E x p N o d e来分配新的节点，而且也需要指派新树节点的合适的子节点。

  以var结点的文法与动作为例：

  

  var是声明变量部分的结点，其中有两种声明（普通变量以及数组变量），可以看到分别对应着newExpNode（Idk）与newEXpNode（ArrIdK）两个结点的声明函数前者直接建立节点后赋上名字即可，后者较繁琐，它需要将数组[]中的exp表达式赋值给var的子结点；

  以select_stmt IF表达式的的文法与动作为例：

  

  这里的if表达式有两种，分别是带else的和不带else的，前者只需要考虑IfK结点的前两个子结点（分别对应判断条件exp、执行代码stmt），将第三个子结点赋值为NULL即可；而后者因为含有else，因此IfK结点还需要将第三个子结点赋值为stmt（表示条件不成立时执行的代码）；

  其余的文法和动作不再赘述，参见文档C_.y；

• 第三部分是辅助程序部分

  Ya c c说明的辅助过程部分 包括了3个过程——y y e r r o r、 y y l e x和p a r s e——的定义。p a r s e过程是由主程序调用，它将调用 Ya c c定义的分析过程y y p a r s e并且返回保存的语法树。

  

  之所以需要 y y l e x过程是因为Ya c c假设这是扫描程序过程的名称，而它又在外部被定义为 g e t T o k e n。写出了这个定义就使得Ya c c生成的分析程序可在对别的代码文件只作出最小的改变的情况下就可与编译程序一起工作。

  

  在出现错误时，y y e r r o r过程由Ya c c调用：它将一定的有用信息(如行号)打印到列表文件上。它使用的是Ya c c的内置变量y y c h a r，y y c h a r包含了引起错误的记号的记号号码。

（3）C-语法分析文件结构：

由语法描述文件C_.y生成的C_tab.c 、C_tab.h文件作为语法分析部分、C-.l词法描述文件生成的lex.yy.c文件作为词法分析部分；

（4）测试

在C_tab.h文件中包含记号的定义（就像上面提到的yyac将所有定义转为数字），因此在原来的globals.h文件中的相应定义部分就不需要了，删去即可；

其余文件均是用的实验三中的语法分析程序，只要稍作改动即可；

编写的可执行程序生成文件makefile如下：

经过make指令后生成exe文件：

验证该语法分析程序，依然使用上面提到的test.c-文件：

可以看出语法分析程序正确！

五、总结

本次实验是基于词法分析自动生成工具FLEX和语法分析自动生成工具YACC来进行；相比于前两次实验其实并没有添加太多的新知识，而只是将我们手工编写的词法分析程序与语法分析程序替换成了YACC、FLEX生成的词法、语法分析程序；

因此本次实验的主要任务其实就是理解词法分析描述.l文件与语法分析描述.y文件，并且自己编写C-语言的相关文件；在编写的过程中也遇到了不少难题，包括编写的文法与动作一直执行失败等等问题，好在与同学们交流学习后慢慢的解决了。

总的来说，本次实验收获还是很大的，学习了FLEX、YACC自动生成工具的使用以及原理，这样的话就可以很简单的扩展到其它的语言，进而完成自动分析的工作。

六、附录

文件目录：

1.cs

2.Tinycifa （Tiny的词法自动分析工具，lex.yy.c就是使用flex生成的）

3.Tinyyufa（Tiny的词法自动分析工具，tiny.tab.c与tiny.tab.h就是使用bison生成的）

4.mytiny（使用自动分析工具后整合成的tiny编译器）

5.C_cifa（C-语言的词法自动分析工具，lex.yy.c是使用flex生成的）

6.C_yufa（C-语言的语法自动分析工具，C_.tab.c与C_.tab.h是bison生成的）

tiny的五个测试文档：

1.lex1.l

2.lex2.l

3.lex3.l、lex4.l

4.tiny.y（语法分析中用到的测试文档）