编译原理实验五：编译器自动生成工具

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

实验目的

学习使用词法分析自动工具LEX。

实验任务

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

实验内容

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

(b) 准备一个LEX工具，如这里提供的“FLEX251.ZIP”，可上网搜索下载更新的版本。

(c) 以文档中提供的4个输入文件为例，测试LEX工具。有些版本的FLEX需要在辅助程序部分增加yywrap()函数：

int yywrap() {return 1;}

1. 生成LEX版本的TINY词法分析器，与其它部分组合成一个完整的TINY语言编译器，并完成测试验证。（参见tiny编译器的使用.ppt）
2. 编写某语言（如：C-语言）的词法描述文件，生成其词法分析器，与其它部分组合成一个完整的TINY语言编译器，并完成测试验证。（提示：可利用增量编程，修改TINY语言的词法描述文件tiny.l，为C-语言编写词法描述文件。）

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

学习使用语法分析程序自动生成工具YACC；使用YACC工具实现编译器的词法分析程序。

实验内容

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

(b) 准备一个YACC工具，如这里提供的“bison.zip”，可上网搜索下载更新的版本。（有源程序可供参考）

(c) 以文档中提供的输入文件为例，测试YACC工具。需要将两个文件拷贝到特殊目录，详情请阅readme.txt。

1. 生成YACC版本的TINY语法分析器，与其它部分组合成一个完整的TINY语言编译器，并完成测试验证。（提示：全局头文件GLOBALS.H需要替换为YACC目录下的那个。）

（3）编写某语言（如：C-语言）的语法描述文件，生成其语法分析器，与其它部分组合成一个完整的TINY语言编译器，并完成测试验证。（提示：可利用增量编程，修改TINY语言的语法描述文件tiny.y，为C-语言编写语法描述文件，全局头文件GLOBALS.H在替换为YACC目录下的那个后需相应修改。）

实验工具及源代码下载

https://pan.baidu.com/s/14nbZ3Xu5nsaGCRPcycJUHw

密码：msry

实验原理讲解

1、LEX工具的使用

（1）以文档中提供的4个输入文件为例，测试LEX工具。

步骤：

1.将flex.exe复制到tiny.l的目录中

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

3.将main.c lex.yy.c util.c globals.h util.h scan.h放入一个工程中，编译生成.exe文件

FLEX语言的结构如下：

其中，FLEX文件是使用一种特殊的语言——LEX，编写的，它描述了一种语言的词法结构：其中，第一部分为定义，FLEX工具在处理这一部分的时候，会将definitions部分的所有代码原封不动的插入到lex.yy.c（词法分析代码）中，我们可以在这一部分中写程序需要用到的头文件等内容，通常情况下，这些代码被放在放在“%{”和“%}”之内，直接插入lex.yy.c。

第二部分是词法规则部分：格式为【模式 { 动作 }】，其中模式为正则表达式，动作是代码片段。当匹配相对应的正则表达式时，这些代码片段就会被执行。

最后一个部分包括着一些C代码，这些函数被称为辅助函数，它们用于在第2个部分被调用且不在任何地方被定义的辅助程序。如果要将Lex输出作为独立程序来编译，则这一部分还会有一个主程序。LEX对此部份不作任何处理，仅仅将之直接拷贝到输出文件lex.yy.c的尾部。在些部份，可定义对模式进行处理的C语言函数、主函数和yylex要调用的函数yywrap()等。如果用户在其它C模块中提供这些函数，用户代码部份可以省略。

通过执行以上步骤，可以顺利生成对应词法分析代码lex.yy.c。如图是文件夹内部的情况。如果需要正式编译程序进行完整的词法分析，还需要加上主函数部分。

（2）使用增量编程，将tiny词法分析器改为C-词法分析器。

这一部分的代码其实在上面的压缩包里面有。。。。

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

以下是改进后的C-.L源程序：

%{
#include "globals.h"
#include "util.h"
#include "scan.h"
/* lexeme of identifier or reserved word */
char tokenString[MAXTOKENLEN+1];
%}

digit       [0-9]
number      {digit}+
letter      [a-zA-Z]
identifier  {letter}+
newline     \n
whitespace  [ \t]+

%%

"if"            {return IF;}
"while"          {return WHILE;}
"else"          {return ELSE;}
"return"         {return RETURN;}
"int"          {return INT;}
"void"         {return VOID;}
"="            {return ASSIGN;}
"=="             {return EQ;}
"<"             {return LT;}
"<="             {return LTEQ;}
">"             {return RT;}
">="             {return RTEQ;}
"!="             {return UNEQ;}
"+"             {return PLUS;}
"-"             {return MINUS;}
"*"             {return TIMES;}
","             {return NOB;}
"/"             {return OVER;}
"("             {return LPAREN;}
")"             {return RPAREN;}
";"             {return SEMI;}
"["             {return MLPAREN;}
"]"             {return MRPAREN;}
"{"             {return LLPAREN;}
"}"             {return LRPAREN;}
{number}        {return NUM;}
{identifier}    {return ID;}
{newline}       {lineno++;}
{whitespace}    {/* skip whitespace */}
"/*"            {     char c;
                      char d='f';
                      do
                      {     c = input();
                            if (c == EOF) break;
                            if (c == '\n') lineno++;
                            if (c == '*'){
                                c = input();
                                if (c == '/') d = 'a';
                            }
                      } while (d == 'f');
                }
.               {return ERROR;}

%%
TokenType getToken(void)
{    static int firstTime = TRUE;
     TokenType currentToken;
     if (firstTime)
     {     firstTime = FALSE;
           lineno++;
           yyin = source;
           yyout = listing;
     }
     currentToken = yylex();
     strncpy(tokenString,yytext,MAXTOKENLEN);
     if (TraceScan) {
        fprintf(listing,"\t%d: ",lineno);
        printToken(currentToken,tokenString);
     }
     return currentToken;
}
           

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

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

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

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

最终的C-词法分析器包含以下这些组件：

2、YACC工具的使用

（1）以文档中提供的输入文件为例，测试YACC工具。

步骤：（与LEX词法分析类似）

1、将语法分析YACC工具BISON和语法描述文件.Y放入同一个文件夹内。

2、命令行中输入“bison .y类型的文件名”就可以生成语法分析代码.Y.tab.C。

3、将生成的语法分析代码与其他部件组合在一起，就可以生成完整的语法分析器。

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

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

规则部分包括修改的BNF格式中的文法规则以及将在识别出相关的文法规则时被执行的C代码中的动作。文法规则中使用的元符号惯例如下：通常，竖线被用作替换(也可分别写出替换项)。

最后是用户自定义函数部分，辅助程序部分包括了过程和函数声明，这个部分也可为空。此部分与词法分析中无太大差别。

（2）编写某语言（如：C-语言）的语法描述文件，生成其语法分析器。

由于C-的语法与TINY十分不同，根据实验指导书上C-的29条语法规则，参照TINY.Y中的格式，进行编写：

上图展示的是C-语法分析文件的其中一部分，完整代码太长，没办法全部贴出，具体实现部分在文件夹的【Cminus增量语法】文件夹下。

实现完上面的C-语法描述文件后，我们通过更改一系列TINY语言中使用过的辅助文件如utils.c、globals.h等，让它们适应C-的语法特点（主要是关键字的实现有差别）之后生成一个工程，即可完成C-的语法分析器构造。

上面这个代码，压缩包里面也有，下载一下吧，emmm。。。

3、生成完整编译器

这是这个实验指导书上规定的最后一步，但是我很不理解，为什么到这里只实现了词法和语法的时候，就要去要求，能生成整个编译器呢？？

明显，是实验的安排出现了问题。

整体的编译器还需要语义分析、代码生成，甚至如果需要一个能够执行C-代码的虚拟机环境！！这个地方当时助教验收，很多人都是懵的，如果之后这个实验还有这个需求，那我也没有办法，直接用TINY语言的去验收吧。

【下面展示的是有源代码的TINY编译器的生成过程】