编译原理实验指导书前言编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。

在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。

本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。

书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。

实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。

实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。

只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。

通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。

并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。

由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。

这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。

它们现已成为UNIX的标准应用程序同UNIX一起发行。

与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。

这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。

我们实验采用的就是for dos的FLEX和BISON。

本书有关的编译工具及其源程序例子，可到BISON的网站上下载。

关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。

目录实验一词法分析器设计实验 (1)实验二用递归下降法实现语法分析实验 (6)实验三熟悉FLEX使用方法 (10)附录一词法分析器生成工具FLEX简介 (15)附录二语法分析器生成工具YACC简介 (22)参考文献 (28)实验一词法分析器的设计【实验目的】1．掌握生成词法分析器的方法，加深对词法分析原理的理解。

2．掌握设计、编制并调试词法分析程序的思想和方法。

3．本实验是高级语言程序设计、数据结构和编译原理中词法分析原理等知识的综合。

【实验性质】综合性实验（学时数：2H）【实验内容及要求】1．设计并实现一个四则运算的计算器,通过命令行方式启动,可以通过键盘输入整个算式,然后直接显示结果。

将换行作为分隔符，把输入分隔为一个个算式。

2．使用C语言设计、编写、调试一个词法分析子程序。

3．实验前请仔细阅读实验预习提示，已经附有完整的源代码,请在实验报告中画出该分析器所实现的状态转换图。

4．提交的实验报告中要有实验名称、实验目的、实验内容、实验程序清单、调试过程和运行结果，程序的主要部分做出功能说明，并有实验收获体会或改进意见等内容。

5．进阶实验:扩展原有计算器,使其可以支持括号和负数运算。

6．本实验建议学时数为2学时【实验预习提示】1.词法分析器的功能和输出格式词法分析器的功能是输入以字符串表示的源程序，输出单词符号或单词符号序列。

词法分析器的单词符号常常表示成以下的二元组(单词的种别码，单词符号的属性值)。

本实验是用于计算器的词法分析器，只需处理运算符和数值。

2.“超前搜索”方法词法分析时，常常会用到超前搜索方法。

如当前待分析字符串为“a>+”,当前字符为’>’，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。

于是分析器读入下一个字符’+’，这时可知应将’>’解释为大于运算符。

但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。

3.词法分析程序主程序的算法思想算法的基本思想是根据扫描到单词符号的第一个字符的种类，拼写出相应的单词符号，其实现的基本任务是从字符串表示的源程序中识别出相应的具有独立意义的单词符号。

主程序示意图如图1.1所示。

1图1.1 词法分析主程序示意图4.补充知识:(1)避免重复包含。

在头文件token.h中，有这样的代码段：#ifndef TOKEN_H_INCLUDED#define TOKEN_H_INCLUDED…#endif这是为了防止多次用#include包含引起多重定义错误而采用的技巧。

头文件用#include 包含自己所依赖的其他所有头文件，可以让代码中只需书写一次include,且当依赖关系发生改变时较容易修改。

但如果多个头文件这样书写，会报类型或宏的重复定义错误，一次可以采用这个技巧，根据开头的#ifndef语句，避免产生多重定义的错误。

(2)在执行语句sscanf(token->str,"%lf",&token->value);时，会出现null pointer assignment错误，这是因为没有给指针初始化。

5.参考源程序实验二用递归下降法实现语法分析【实验目的】1.掌握用递归下降分析法进行语法分析的方法。

加深对自顶向下语法分析原理的理解。

2.掌握设计、编制并调试自顶向下语法分析程序的思想和方法。

3.本实验是高级语言程序设计、数据结构和编译原理中词法分析、自顶向下语法分析原理等知识的综合。

由于语法分析是在词法分析的基础上进行的，且词法分析器输出的结果即单词符号或单词符号序列是语法分析的输入。

【实验性质】综合性实验（学时数：2H）【实验要求】1.调用实验一的get_token函数进行词法分析，使用递归下降法作语法分析器，实现计算器的功能。

2.实验前请仔细阅读实验预习提示，参考所附完整的源代码,请在实验报告中写出该分析器所使用的语法规则。

3. 本实验建议学时2学时。

【实验预习提示】1、语法分析程序的算法思想（1）主程序示意图如图4.1所示。

图4.1 递归下降法语法分析主程序示意图（2）递归下降分析程序示意图如图4.2所示。

图4.2 递归下降分析程序示意图2.参考源程序parser.c：实验三熟悉FLEX使用方法【实验目的】1．掌握FLEX基本使用方法2．掌握如何将通过FLEX生成的C语言模块加入到自已的程序中【实验要求】1．编制FLEX源程序,分别统计文本文件a.txt中出现的标识符和整数个数,并显示之。

标识符定义为字母开头，后跟若干个字母，数字或下划线。

整数可以带+或-号，也可不带，且不以0开头。

非单词和非整数则忽略不记，将之滤掉不显示。

2．编制一FLEX源程序,分别求出文件hh.c中字母,数字,回车符的个数。

3．思考：若main函数不在FLEX中实现，应该如何实现？4．本次实验建议学时2学时。

【实验预习提示】参见附录一。

在看懂的基础上将之调试通过。

实验四用FLEX和BISON自动实现计算器【实验目的】熟练掌握FLEX和BISON，并通过其生成词法和语法分析器，实现实验一和实验二的加算器功能【实验要求】1．通过FLEX生成一词法分析器函数，其功能同实验一中词法分析器函数类似。

2．通过BISON生成一语法分析器。

参造附录，读懂所附源程序。

3．生成一工程文件，调用1和2中生成的函数，实现计算器的功能4．本实验建议学时2学时。

【实验预习提示】1．由于FLEX生成的C程序模块lex.yy.c过于复杂，基本不可读，所以不要直接修改它，可将它看成一个“黑箱”，即不需要清楚知道其内部结构，只需要知道其接口即可。

可通过修改FLEX源程序间接修改之。

关于lex.yy.c中常用变量和函数，在附录中有详细说明。

2．编制语法分析器mycalc.y，通过BISON生成y.tab.c和y.tab.h。

命令为：bison --yacc -dv mycalc.y使用BISON代替了YACC,默认生成的文件是mycalc.c和mycalc.h，所以在添加了—yacc参数，可以生成与YACC同名的文件3．编制词法分析器mycalc.l，通过FLEX生成lex.yy.c。

命令为：flex mycalc.l4．生成一工程文件，不妨取名为test.prj，将文件lex.yy.c、y.tab.c和y.tab.h，加入之。

源程序参考如下：(1)mycalc.l附录一词法分析器生成工具FLEX简介1．FLEX简介单词的描述称为模式(Lexical Pattern)，模式一般用正规表达式进行精确描述。

FLEX 通过读取一个有规定格式的文本文件，输出一个如下所示的C语言源程序。

FLEX的输入文件称为LEX源文件，它内含正规表达式和对相应模式处理的C语言代码。

LEX源文件的扩展名习惯上用.l表示。

FLEX通过对源文件的扫描自动生成相应的词法分析函数 int yylex()，并将之输出到名规定为lex.yy.c的文件中。

实用时，可将其改名为lexyy.c。

该文件即为LEX的输出文件或输出的词法分析器。

也可将 int yylex()加入自已的工程文件中使用。

2．模式简介LEX的模式的格式(也称为规则)是机器可读的正规表达式，正规表达工是用连接、并、闭包运算递归生成的。

为了方便处理，LEX在此基础上增加了一些运算。

下列是按运算优先级由高往低排列的LEX的正规表达式的运算符。

“\[]^-?.*+|()/${}%<>关于LEX的模式定义，可参见下页附表1.13．LEX源文件格式LEX对源文件的格式要求非常严格，比如若将要求顶行书写的语句变成非顶行书写就会产生致命错误。

而LEX本身的查错能力很弱，所以书写时一定要注意。

LEX的源文件由三个部份组成，每个部分之间用顶行的“%%”分割，其格式如下：定义部份％％规则部份％％用户附加C语言部份3.1定义部份定义部份由C语言代码、模式的宏定义、条件模式的开始条件说明三部份组成。

其中，C代码部份由顶行的%{和}%引入，LEX扫描源文件时将%{和}%之间的部分原封不动的拷贝到输出文件lex.yy.c中.附表1.1 LEX 的模式定义模式的宏定义部份如同C语言中的宏定义，通过宏名定义一个模式，这样，可以简化在源文件中多次出现的正规表达式的书写。

格式为：宏名1 宏定义1宏名2 宏定义2……例如：DIGIT [0-9]ID [A-Za-z][A-Za-z0-9_]*宏名是以字母和下划线”_”开始，以字母、数字和下划线组成的字符串，且大小写敏感。

宏名必须顶行写，宏名和宏定义必须写在同一行上。

宏名和宏定义之间以不包括换行符的白字符(空格符、TAB符、换行符)隔开。

条件模式的开始条件说明格式如下：％start s1 s2 s3其中，s1、s2、s3为条件名。