编译原理实验全集

1、文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持目录实验1词法分析错误!未定义书签。1.1.目的 错误！未定义书签。1.2.内容 错误！未定义书签。1.3.知识 错误！未定义书签。1.4.步骤 错误！未定义书签。1.5.问题及解答 错误！未定义书签。1.6.实验报告要求 错误！未定义书签。实验2自顶向下的语法分析 错误！未定义书签。2.1.目的 错误！未定义书签。2.2.知识 错误！未定义书签。2.3.内容 错误！未定义书签。2.4.步骤 错误！未定义书签。2.5.问题及解答 错误！未定义书签。2.6.提高 错误！未定义书签。2.7.实验报告要求 错误！未定义书签。实验3自底向上的

2、语法分析 错误！未定义书签。3.1.目的 错误！未定义书签。3.2.内容 错误！未定义书签。3.3.步骤 错误！未定义书签。3.4.问题 错误！未定义书签。3.5.实验报告要求 错误！未定义书签。实验4语义分析错误！未定义书签。4.1.目的 错误！未定义书签。4.2.知识 错误！未定义书签。4.3.内容 错误！未定义书签。4.4.步骤 错误！未定义书签。4.5.实验报告要求 错误！未定义书签。实验5中间代码生成实验6代码优化与代码生成相关说明实验1、2要求独立完成。实验3、实验4的实现代码（VC+工程）均已调试成功,打包在目录中（Iab3,lab4 ）。希望认真学习的同学多看看。由于时间关系，

3、许多地方还没来 得及做好，本手册的内容可能比较繁琐。欢迎大家提出问题和意见。时间比较紧的同学也 请关注每个实验末尾的实验报告要求。期末实验占10分。实验1词法分析1.1. 目的构造词法分析器，熟悉编译程序词法分析过程。掌握LEX自动生成工具的使用。1.2. 内容从本实验开始，用C语言实现一个编译系统。词法分析是其第一步。采用Lex工具自动生成大大简化了其中的内容。因此本实验的重心并不在如何操作，而是在于怎样编写Lex源程序。而要编写Lex源程序，首先要定义源语言，即该编译系统所实现的语言。这里作为例子，我们以C+为基础，采用其部分单词，因此不妨将我们定义的这种语言称之为Mini C+ 。1.3

4、. 知识Lex是一个词法分析器的自动构造工具。相关资料较多。1.4. 步骤1、在编写LEX源程序前，首先要定义一种高级语言。找出其中所有单词。并进行编码。高级语言可以是已经存在的一种语言，如，C,Pascal,Basic。也可以是自己构造的一种语言。当然，考虑到后续实现的难度，可以简化许多内容。如不考虑数组，不考虑 For循环等。将定义好的单词编码用一个表表达出来。如我们这里的MiniC+的单词定义如下：保留子内部编码运算符号if1+else2-while3*cout4/cin5*>>（输入）6=<<（输出）7<><=内部编码其他符号内部编码8(199

5、)2010211122122313=2414数字2515标识符2616527>=17var28<>18说明：(1) 由于只允许数字，所以不作变量类型。所有类型都是var。(2) 单词编码无任何约束，只要方便可行。要知道，我们构造的是一个独立的自包含的系统。所有的东西都是我们自己定义的。而编码只是便于机器内部识别。只要后面的语法分析，语义分析都按这个编码即可。2、 将flex.rar展开在一个目录中，如E:flex 。3、 根据上述单词编码编写LEX源程序。LEX源程序是纯文本文件，任何文本编辑器均具备这一功能(如用记事本打开即可)。保存时文件名任取。这里假设命名为LexDem

6、o.txt。为后续操作简便，将该文件保存在E:flex子目录中。4、编译LEX源程序。生成 lexyy.c。5、 使用C语言环境打开lexyy.c。编译运行，最终生成lexyy.exe。根据我们现有的情况，可以使用三种方案，任选其一。(建议使用命令行工具，实际上更简单。)(1) 使用 VC建立一个工程(Project)，将lexyy.c加入到该工程。实际上，最好拷贝lexyy.c到相应的目录。然后编译，产生的lexyy.exe文件在该工程目录下的Debug子目录中。(2) 使用VC的命令行工具。格式为：<VC的安装路径 >binCLlexyy.c女口： VC安装在 "Pr

7、ogram Files "下。则命令为：D:"Program Files""Microsoft Visual Studio"VC98Bi nCL lexyy.c(3) 使用TC命令行工具。<TC 的安装路径 >binTCC lexyy.cD:TC20bi nTCC lexyy.c6、写一段该语言测试代码进行测试。如：While (i<2)Cout<<10;则输出序列为：3, 019, 015, 07、根据单词编码序列对照上面的表进行验证。(1) 每个单词对应一对数，第一个数为其编码。第二个数为该单词的附加属性。如

8、无该属性则置 0。（ 2） 如单词为标识符，其属性应该为符号表的入口地址。但考虑到学词法分析时， 还不熟悉符号表的机制，因而暂时也置 01.5. 问题及解答1、涉及到命令行操作，考虑到仍有许多同学对 DOS 命令不熟悉。希望自行加强。2、如 采用 Visual C+ 编译，则先要建一个工程，将 lexyy.c 加入。3、如 果采用 TC 编译，则建议用 TCC 命令行工具。4、由于 LEX 只能处理单字节的字符，请在 LEX 源程序中千万不要用中文注释。保存时一定要看清楚类型，必须是ANSI 类型。1.6. 实验报告要求1、 目 的2、 内 容（ 1） 单词及编码定义（设计一种高级语言（或子集

9、）的单词其编码，见前面的 表）（ 2） 部分 LEX 代码（ 3） 测试（写出两个测试句子：所有单词正确，含有错误单词的句子）3、 总 结（心得）实验2自顶向下的语法分析2.1. 目的在词法分析的基础上，熟悉自顶向下的语法分析方法。体验递归程序的特点。实现界面和业务逻辑代码分离。实现异种平台的访问。培养初步的软件架构的观念。培 养软件设计及编程能力。2.2. 知识2.2.1 终结符、非终结符及产生式所有的组成最终句子的单词即为终结符。非终结符代表的是我们观念上的语法范畴。如主语。谓语，名词等。在高级语言中，语法范畴包括程序、说明语句、可执行语句、IF结构、关系表达式、算术表达式等等。2.2.2

10、 语法及语义分析语法分析只要求验证某个句子是否符合某个文法。关注的是结构。而语义关注的是句子的含义。计算机本身无生命，无所谓真正地理解句子的含义。我们所期望的计算机执行相应的语义是指：当计算机程序扫描到某个句子后，所执行的操作恰好符合这个句子所表达的意思。如扫描到一个“3+2 ”这样一个字符串。自动地把结果5算出来。而在语法分析中，所作的仅仅是判别这个句子的结构是否合法。并不执行计算。2.2.3 FIRST 集与 FOLLOW 集所谓FIRST集，本质上就是第一个可能出现的符号构成的集合。这个是可以由产 生式本身得到的。因为任何句子都是由该文法的产生式推出来的。2.2.4 关于递归下降子程序的

11、编写规则（请注意规则和下面的颜色对应关系）：（1）文法中的 每个非终结符 对应一个 过程（函数）。（2）若某个非终结符有多个产生式候选，则根据当前输入符是否在某个候选的Select集选择。每个候选对应一个if分支。（3）选择好候选之后，对产生式候选的右部的符号由左到右依次处理。 若为终结符。则将该符号和当前输入符号进行判等操作。若相等，继续。否则转 若为非终结符，则调用该非终结符所对应的过程。 若当前扫描的符号为当前候选的第一个符号，且当前产生式有&候选.则不作出错处理。否则均出错处理 。例 1 : S (S)|achar str;/待检查的串int ip;II扫描指针例 2 : S

12、(S)| &char str;II待检查的串 int ip;II扫描指针void S() /只有一个非终结符Svoid S() /只有一个非终结符Sif(strip= ' / 处理 S (S)候选if(strip= ' ip+ ; S();ip+ ; S();if(strip= ' ' ip+;if(strip= ' ' ip+;else error();else error(); /不是第1个符号，出错。else if(strip= '' / 处理 S a 候选else if(strip= ' ' ip+

13、;ip+; else/对应第1符号/不作出错处理 。error(); /但无&候选项，必须出错。需要注意的是，本例比较的是字符。而本实验中用的是符号(单词)编码，是经过词法分析后的编码。也就是后面定义的token数组相当于本例的str。这点变通能力希望大家有。关于这三条规则的具体运用，可看模板代码。实现了两个非终结符，其余的需要 同学们自己去实现。2.3. 内容输入输出装置(界面)输入串词法分析程序分析编码及属性表本实验的目标是实现乘方几种运算语法是否正确一个文本计算器的语法检验。要实现实数的加、 。这几币卜'运算构成了'种优先级。因此文法的减、乘、除、表达和课堂上不一

14、样根据需要设计所有的非终结符。可以以产生式为核心。在设计的过程中逐步引入 非终结符。<E>T <L><A><A>f + <L><A><A>f - <L><A><A>£<L>-><M> <B><B>-> * <M> <B><B>-> / <M> <B><B>£<M <N> <C><C&g

15、t;f *<N> <C>/此括号非彼括号，故用引号括起来。/经过词法分析，数字被认为是终结符。<N>t“ ( “ <E>“)”<N>t $n um<N>f £非终结符定义符号定义符号定义<E>算术表达式<A>消除左递归的算术子表达式<L>优先级为 3的子项<B>消除左递归且优先级为3的子项<M>优先级为 2的子项<C>消除左递归且优先级为2的子项<N>优先级为1的子项说明：优先级的编号越小，其运算（归约）的次序先。2.32 基于L

16、EX自动构造器地词法分析程序的重构（任选）对于大型编译系统而言，往往存在多遍扫描的可能性。将词法分析程序构造成独 立的过程有很大的好处。但对于我们这个小型的文本计算器而言。将词法分析构造成依附于语法分析的子过程可能更加合理。因此我们需要对词法分析程序进行重构。本实验只要求实现表达式的求值。因此，只需要使用原来集合的部分单词。对词法分析程序进行重构，使之成为语法分析程序的子程序。通过全局变量的方式加工数据，输入表达式串，输出编码及属性序列，分别存放在两个全局的整型数组中。因此需要作如下变更：（1）单词的编码在语法分析和词法分析中都需要，因而同一集中在一个头文件token.h中。以后，无论是词法、

17、语法、语义分析，均用这套编码。以下是部分语句：/*/*+*/*/#ifndef TOKEN/*终结符定义#defi ne $add 20#defi ne $sub 21*/#defi ne $assig n37/*=*/#defi ne $num38/*常数*/#defi ne $eps40/*£*/*非终结符定义*/*逻辑表达说明*/#defi ne _E113/*<E>算术表达式 */（2） 定义两全局整型数tokens和attribs分别用于表示词法分析后的单词编码和属性对集。该定义在token.h中，其定义格式如下：#define MAXTOKEN100int t

18、okensMAXTOKEN;/* 单词编码序列，可容纳 100 个*/int attribsMAXTOKEN;/* 单词属性编码序列*/int ip;/* 当前符号 ( 单词编码 )指针*/#endif将上述 token.h 加入到 Lex 文件的第 1 部分，替换掉原来的定义。%#define YYSTYPEdouble#include <ctype.h>#include <stdlib.h>#include "types.h"#include "hash.h" #include "token.h" floa

19、t val=0;%( 3) 第 2 部分为正规式单词的定义。实际这里只用到数字，也可以不变。写入到( 4) 每扫描到一个单词，对应的处理动作为：将该 单词的编码和属性分别tokens 和 attribs 数组中。具体在 Lex 第 3 部分如下编程："+" addToken($add,0);"-" addToken($sub,0);digits sscanf(yytext,"%f",&val); / 数字。将数字的值拷贝进整型变量 val 其中 addToken(int token, int attrib)函数定义在第 4 部

20、分：void addToken(int token,int attr) if(ip<MAXTOKEN) tokensip=token; attribsip=attr; ip+;( 建议大家统一再看看 expToken.txt 源文件。)lexyy()( 5) 主程序无需打开输出文件，每扫描到一个单词，系统会自动用相应的代码块， 即，调用 addToken 函数执行相应的工作。这都在 Lex 自动生成的函数 内部处理。因此语法分析主程序只需要调用 lexyy() 函数即可。自编代码的词法分析器构造(任选)该程序相对而言较为简单，以下列举词法分析主程序。详细内容见参考代码。/ 从流中读取一个

21、单词 int lexyy() char ch=' 'if(bufChar=' ')while(isBlank(ch) ch=fgetc(stream); /跳过所有的空格回车else ch=bufChar; bufChar=' 'if(ch='+')/使用了超前搜索的情况/ 用空格清掉超期搜索字符。return $add;else if(ch='-')return $sub;else if(ch='*')return $mul;else if(ch='/')return $div;e

22、lse if(ch='(')return $llbr;else if(ch=')')return $lrbr;else if(ch='#')return $sharp;else if(isDigit(ch) bufChar=ch;wip=0;return readNum();于 curValue 变量。/超期搜索缓冲/ 单词指针清 0/ 读取整个数字， 返回数字的单词编码，而数字的值暂存elseerror(" 词法错误 "); return 0;主程序的编写void main() /*执行词法分析*/lexyy();/*执行语

23、法分析*/E();/*调用开始符号所对应的过程进行分析。*/printf("语法正确.");/*如能执行到这里，证明中途没出错*/若上述代码放在LEX文件中，请把中文注释去掉，同时保存类型设为ANSI。2.4. 步骤1、重构词法分析程序设计文法定义不回溯且考虑到三种优先级的表达式计算的文法，前面是一参考实现。最好能根据要求独立设计文法。2、建立C语言工程建立语法分析主程序文件，假定命名为：express.c。同时将该 token.h加入。3、编写递归下降程序根据文法，按要求在express中编写递归下降子程序。如感觉比较困难，请参照递归下降法。4、编写测试主程序(基本要求)

24、构造一命令行的输入程序，即输入表达式串。输出语法分析成功与否。输出结果 为“语法正确”“语法错误”。5、程序系统调试验证结果2.5. 问题及解答请大家提出意见和建议，以便改进本手册。2.6. 提高1、实现一个完整的高级语言子集。2、建立图形界面，对本实验内容进行包装。3、 选取针对某些结构化文档，如XML建立语法分析器。2.7. 实验报告要求考虑到大家的实际情况，实验报告只要求实现基于字符的分析过程。其提纲如下：1、目的2、内容先介绍下该程序主要功能(1) 文法E T E ' E'=+TE £ T F T 'T'=*F T£ F (E)|i(

25、2) 递归下降过程(附上代码)（ 3 ） 测试用例3、总结（心得）实验3自底向上的语法分析3.1. 目的1、掌握 SLR 法进行语法分析的原理。2、设计相应得数据结构及编码，实施算法的相关要素的机内表示。3、 掌握语法分析器的设计与调试；3.2. 内容1、算法的数据结构（ 1）分析表分析表采用二维持数组，其中第 0 行存放表头。int atMAXROWMAXCOL;（2）堆栈/分析表由于符号栈与状态栈通常同步操作，可将二栈合二为一。堆栈元素可用结构体包装相 应的数据。/代表非终结符和终结符 （由于符号栈和状态栈均为同步操作。通过结构体的方式实现堆栈 合并 ）typedef struct Tch

26、ar name;/名称 （便于外部输出 ）int code;/编码 （便于内部处理 ）int state;/状态int value;/该非终结符的值Token;/堆栈类型typedef struct S1 Token bodyMAXSIZE;/堆栈体int ip; TokenStack;（ 3 ）产生式的表示/栈顶指针/产生式候选记录表 typedef struct Production char leftName;/左部名称int leftCode;/左部编码int rightLen;/右部长度，决定出栈数。 Prod;2、程序模块的划分（1）堆栈操作的相关函数（ 2）分析表操作（ 3 ）主

27、分析过程/对一个输入符号执行分析/说明：由于堆栈集成为一个，所以堆栈操作可以不指出堆栈变量。int analysis(TokenStack *s,int code) int curState,curOp,pi;/当前状态，操作，产生式编号curState=getState(s);/获取当前状态curOp=getOperate(curState,code);/ 获取当前操作if(curOp=-1) error(" 分析表中未定义 ");if(curOp=ACC) printf("n 输入串正确 ");exit(0);else if(curOp>R)

28、pi=curOp-R;for(int i=0;i<ppi.rightLen;i+) / pop(s);/输入串正确出口/归约代码/ 去掉 R 标识，得到产生式编号 查对应的产生式候选登记表/出栈。curState=getState（s）; /获取当前栈顶状态。 curOp=getOperate（curState,ppi.leftCode）; /查 Goto 表获取跳转的状态。/ 符号栈入栈 ./状态入栈（即查Goto表对应的值，所以G与S必须相等）/（ 语法分析阶段：不考虑语义，故value 参数为 0）push(s,ppi.leftName,ppi.leftCode,curOp-S,0

29、);outputStacks(s);opState=0;/当前为归约状态else if(curOp>S) /Si 入栈push(s,getName(code),code,curOp-S,0); / 当前符号、状态入栈outputStacks(s); opState=1;else/当前为移进状态error(" 语法错误 !");/return 0;（4）主程序及输入输出（5）错误处理3、测试要求（1） 成功的输入串（2）词法错误串（3）语法错误串3.3. 步骤1、建立 C 语言工程2、加入单词编码头文件。3、编写相关代码4、在命令行下运行，进行测试。3.4. 问题时间关

30、系，许多地方还没来得及作好，但欢迎大家提出问题。3.5. 实验报告要求1、目的2、内容（ 1） 数据结构设计：文字描述，不要求写代码（ 2） 主要模块： 主分析过程 （ 代码或流程图 ） 堆栈操作：push、pop（将函数名写出） 分析表操作： （将函数名写出） 词法分析辅助过程： （将函数名写出） 输入输出及错误处理： （将函数名写出）（期末考试实验占 10 分。其中本实验将根据内容记分，并直接记入期末成绩。可 参考所附代码，如自己有另外实现也可，需提交代码）（ 3 ） 测试： 语法正确的表达式。 语法错误的表达式。 词法错误的表达式。3、总结（心得）实验 4 语义分析4.1. 目的1、属性

31、文法及语法制导翻译和递归下降的语法分析结合，构造语义分析程序。2、以表达式文法为例，构造文本计算器演示程序。4.2. 知识1、设计属性文法。以一个例子加以说明：考察文法 G（E）: ET LL+ T L|T$num我们可以从以下几个方面去理解。（ 1） 下标的含义首先考虑到产生式中不止一个E,在语法分析中由于在不同的时间不同的地方处理，因而不会产生歧义。但在语义分析中，任何一个符号的属性都可在上下文中出现，因而有 必要加以区分。通常通过设置下标的方式来区分。L +TL 1有了下标 L 和 L1 就能加以区分。可以这么说，L、L1 不是“同个”非终结符，但是是“同类”非终结符。因此，属性文法设计

32、的第一步就是把同一产生式候选中的相同符号加以下标。（2）属性的设计属性是为每个符号配置的。终结符得属性通常通过词法分析得到。非终结符的属性通 常为上下文的属性计算得到。首先考虑全局的，即整个文法最终要求什么。将其数据化作为开始符号得属性。在上例中，表达式最终是求若干个数之和的结果值。 因此为非终结符 E配备一个属性s,表示E 所展开的子表达式的值。再考虑叶子结点能够获取到什么信息。叶子都是终结符,信息实际上是通过词法分析 获取的单词语义。 如“2”,分析程序扫描到文本字符“ 2”,将其转换成二进制的值2。但在语法分析中,只是将其解释为“数字” ,用 $num 表示。而二进制的值 2 只是作为

33、$num 的一个属性 ,不妨记为 $num.v 。最后考虑语法树中的支干结点需要传递些什么数据, 根据相应的数据定义相应的属性。 设计属性时,必须明确两点：3、支干（非叶子,非根）结点的属性主要功能是传递数据和中间计算。要按树的遍历顺 序来考虑。因为无论是自顶向下还是自底向上,本质上都是对树的一次遍历（这点在 上课实讲过） 。4、 一个结点可以有多个属性。本例中，非终结符L结点不仅负责传递属性，还要完成计i表示输入属性,算。定义两个属性变量,2+ 3 + 5的属性文法语法树(3) 属性的计算规则设计规则： 根据实例语法树，考虑其自左至右遍历的顺序。分析其数据传递和计算方法。 结合产生式。将传递

34、和计算规则提炼到产生式中。如上例，设计的属性文法如下:E T L.i=T.s L E.s=L.sL + T L i.i=L.i+T.s L 1 L.s=L 1 .sL £ L. s=L.iT $num T.s=$ nu m.v5、如何根据属性文法设计递归下降子程序关于递归下降的语义分析，清华版的教材没有提及。国防科大版的教材有初步的介绍。 这里以一个简单的例子说明如何实现。继续考察上例，即将表达式中的加法单独抽取出来，其语义就是加法。(1) 每个非终结符对应一个过程(2) 继承属性作为输入参数(3) 综合属性作为返回值如：E->T L.i=T.s L E.s=L.sfloat E() float Ts,Ls;/Ts,Ls分别表示 T.s、L.两个属性Ts=T();Ls=L(Ts);return Ls;4.3. 内容本实验的主要内容在于实现一个文本计算器。1、 属性文法设计 由于使用了递归下降的语法分析，则必须考虑是否为 LL 文法。针对表达式文法，需 要选用消除了左递归的文法。根据教材上的版本进行改造，考虑了四则混合运算的情况。 设计文法如下：E T L.i=T.s L E.s=L.sL + T L 1.i=L.i+T.s L 1 L.s=L 1.sL - T L 1.i=L.i-T.s L1 L.s=L1.sL £ L.s=L.iT F