编译原理试验全集

目录目录TOC\o"1-5"\h\z\o"CurrentDocument"实验1词法分析 2\o"CurrentDocument"目的 2\o"CurrentDocument"内容 2\o"CurrentDocument"知识 2\o"CurrentDocument"步骤 2问题及解答 4实验报告要求 4\o"CurrentDocument"实验2 自顶向下的语法分析 5\o"CurrentDocument"目的 5\o"CurrentDocument"知识 5\o"CurrentDocument"内容 6\o"CurrentDocument"步骤 10问题及解答 10\o"CurrentDocument"提高 10\o"CurrentDocument"实验报告要求 10\o"CurrentDocument"实验3 自底向上的语法分析 12\o"CurrentDocument"目的 12\o"CurrentDocument"内容 12\o"CurrentDocument"步骤 14\o"CurrentDocument"问题 14\o"CurrentDocument"实验报告要求 14\o"CurrentDocument"实验4语义分析 15\o"CurrentDocument"目的 15\o"CurrentDocument"知识 15\o"CurrentDocument"内容 17\o"CurrentDocument"步骤 18实验报告要求 18实验5中间代码生成实验6 代码优化与代码生成1/19编译原理实验指导相关说明实验1、2要求独立完成。实验3、实验4的实现代码（VC++工程）均已调试成功，打包在目录中（lab3,lab4）。希望认真学习的同学多看看。由于时间关系，许多地方还没来得及做好，本手册的内容可能比较繁琐。欢迎大家提出问题和意见。时间比较紧的同学也请关注每个实验末尾的实验报告要求。期末实验占 10分。实验1词法分析目的构造词法分析器，熟悉编译程序词法分析过程。掌握 LEX自动生成工具的使用。内容从本实验开始，用C语言实现一个编译系统。词法分析是其第一步。采用 Lex工具自动生成大大简化了其中的内容。因此本实验的重心并不在如何操作， 而是在于怎样编写Lex源程序。而要编写Lex源程序，首先要定义源语言，即该编译系统所实现的语言。这里作为例子，我们以C++为基础，采用其部分单词，因此不妨将我们定义的这种语言称之为MiniC++。知识Lex是一个词法分析器的自动构造工具。相关资料较多。步骤1、在编写LEX源程序前，首先要定义一种高级语言。找出其中所有单词。并进行编码。高级语言可以是已经存在的一种语言，如， C,Pascal,Basic。也可以是自己构造的一种语言。当然，考虑到后续实现的难度，可以简化许多内容。如不考虑数组，不考虑For循环等。将定义好的单词编码用一个表表达出来。如我们这里的 MiniC++的单词定义如下：保留字内部编码运算符号内部编码其他符号内部编码if1+8(19else2-9)20while3*10;21cout4/11{22cin5**12)23>>（输入）6==13=24<<（输出）7<14数字25>15标识符26<=16,272/19>=17var28<>18说明:（1）由于只允许数字，所以不作变量类型。所有类型都是var。（2）单词编码无任何约束，只要方便可行。要知道，我们构造的是一个独立的自包含的系统。所有的东西都是我们自己定义的。而编码只是便于机器内部识别。只要后面的语法分析，语义分析都按这个编码即可。2、将flex.rar展开在一个目录中，如E:\flex。3、根据上述单词编码编写LEX源程序。LEX源程序是纯文本文件，任何文本编辑器均具备这一功能（如用记事本打开即可）。保存时文件名任取。这里假设命名为LexDemo.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的安装路径>\bin\CLlexyy.c如：VC安装在D:\”ProgramFiles”下。则命令为：D:\"ProgramFiles"\"MicrosoftVisualStudio"\VC98\Bin\CLlexyy.c（3）使用TC命令行工具。<TC的安装路径>\bin\TCClexyy.cD:\TC20\bin\TCClexyy.c6、写一段该语言测试代码进行测试。如：While（i<2）{Cout<<10;}则输出序列为：3,019,015,07、根据单词编码序列对照上面的表进行验证。（1）每个单词对应一对数，第一个数为其编码。第二个数为该单词的附加属性。如无该属性则置0。3/19编译原理实验指导（2）如单词为标识符，其属性应该为符号表的入口地址。但考虑到学词法分析时，还不熟悉符号表的机制，因而暂时也置0问题及解答1、涉及到命令行操作，考虑到仍有许多同学对 DOS命令不熟悉。希望自行加强。2、如采用VisualC++编译，则先要建一个工程，将lexyy.c加入。3、如果采用TC编译，则建议用TCC命令行工具。4、由于LEX只能处理单字节的字符，请在LEX源程序中千万不要用中文注释。保存时一定要看清楚类型，必须是ANSI类型。实验报告要求1、目的2、内容（1）单词及编码定义（设计一种高级语言（或子集）的单词其编码，见前面的表）（2）部分LEX代码（3）测试（写出两个测试句子：所有单词正确，含有错误单词的句子）3、总结（心得）4/19编译原理实验指导实验2实验2自顶向下的语法分析目的在词法分析的基础上，熟悉自顶向下的语法分析方法。体验递归程序的特点。实现界面和业务逻辑代码分离。实现异种平台的访问。培养初步的软件架构的观念。培养软件设计及编程能力。知识终结符、非终结符及产生式所有的组成最终句子的单词即为终结符。非终结符代表的是我们观念上的语法范畴。如主语。谓语，名词等。在高级语言中，语法范畴包括程序、说明语句、可执行语句、IF结构、关系表达式、算术表达式等等。语法及语义分析语法分析只要求验证某个句子是否符合某个文法。关注的是结构。而语义关注的是句子的含义。计算机本身无生命，无所谓真正地理解句子的含义。我们所期望的计算机执行相应的语义是指：当计算机程序扫描到某个句子后，所执行的操作恰好符合这个句子所表达的意思。如扫描到一个“ 3+2”这样一个字符串。自动地把结果 5算出来。而在语法分析中，所作的仅仅是判别这个句子的结构是否合法。并不执行计算。FIRST集与FOLLOW集所谓FIRST集，本质上就是第一个可能出现的符号构成的集合。这个是可以由产生式本身得到的。因为任何句子都是由该文法的产生式推出来的。关于递归下降子程序的编写规则（请注意规则和下面的颜色对应关系）：（1）文法中的每个非终结符对应一个过程（函数）（2）若某个非终结符有多个产生式候选，则根据当前输入符是否在某个候选的Select集选择。每个候选对应一个if分支。（3）选择好候选之后，对产生式候选的右部的符号由左到右依次处理。①若为终结符。则将该符号和当前输入符号进行判等操作 。若相等，继续。否则转③②若为非终结符，则调用该非终结符所对应的过程 。③若当前扫描的符号为当前候选的第一个符号，且当前产生式有£候选.则不作出错处理。否则均出错处理。例1：S今（S）|acharstr口；…〃待检查的串intip; //扫描指针例2:S3（S）Ibcharstr口；…〃待检查的串intip; //扫描指针5/19

编译原理实验指导voidS(){//只有一个非终结符Sif(str[ip]==’('){//处理S个(S)候选ip++;S();if(str[ip]==’)’)ip++;elseerror();)elseif(str[ip]==’a’){//处理S->a候选ip++;}else //对应第1符号error(); //但无b候选项，必须出错。voidS(){ //只有一个非终结符Sif(str[ip]=='('){ip++;S();if(str[ip]==')')ip++;elseerror();//不是第1个符号，出错。}elseif(str[ip]=='a'){ip++;} 〃不作出错处理。需要注意的是，本例比较的是字符。而本实验中用的是符号（单词）编码，是经过词法分析后的编码。也就是后面定义的 token数组相当于本例的str。这点变通能力希望大家有。关于这三条规则的具体运用，可看模板代码。实现了两个非终结符，其余的需要同学们自己去实现。内容本实验的目标是实现一个文本计算器的语法检验。要实现实数的加、减、乘、除、

乘方几种运算。这几种运算构成了三种优先级。因此文法的表达和课堂上不一样。根据需要设计所有的非终结符。可以以产生式为核心。在设计的过程中逐步引入非终结符。<E>一<L><A><A>一+<L><A><A>--<L><A><A>一£<L>-><M><B><B>->*<M><B><B>->/<M><B><B>一£6/19编译原理实验指导<M>f<N><C><C>f**<N><C><N>f"（”<E>“）” 〃此括号非彼括号，故用引号括起来。<N>f$num 〃经过词法分析，数字被认为是终结符。<N>f£非终结符定义符号定义符号定义<E>算术表达式<A>消除左递归的算术子表达式<L>优先级为3的子项<B>消除左递归且优先级为3的子项<M>优先级为2的子项<C>消除左递归且优先级为2的子项<N>优先级为1的子项说明：优先级的编号越小，其运算（归约）的次序先。基于LEX自动构造器地词法分析程序的重构（任选）对于大型编译系统而言，往往存在多遍扫描的可能性。将词法分析程序构造成独立的过程有很大的好处。但对于我们这个小型的文本计算器而言。将词法分析构造成依附于语法分析的子过程可能更加合理。因此我们需要对词法分析程序进行重构。本实验只要求实现表达式的求值。因此，只需要使用原来集合的部分单词。对词法分析程序进行重构，使之成为语法分析程序的子程序 。通过全局变量的方式加工数据，输入表达式串，输出编码及属性序列，分别存放在两个全局的整型数组中。因此需要作如下变更：（1）单词的编码在语法分析和词法分析中都需要，因而同一集中在一个头文件token.h中。以后，无论是词法、语法、语义分析，均用这套编码。以下是部分语句：#ifndefTOKEN/*终结符定义*/#define$add20/*+*/#define$sub21/**/(((#define$assign37/*^*/#define$num38/*常数*/#define$eps40/*£*/7/19编译原理实验指导/*非终结符定义*/ /*逻辑表达 说明*/#define_E113 /*<E> 算术表达式*/(2) 定义两全局整型数 tokens口和attribs[]分别用于表示词法分析后的单词编码和属性对集。该定义在token.h中，其定义格式如下：#defineMAXTOKEN100inttokens[MAXTOKEN];/*单词编码序列，可容纳 100个*/intattribs[MAXTOKEN]; /*单词属性编码序列 */intip; /*当前符号(单词编码)指针 */#endif将上述token.h加入到Lex文件的第1部分，替换掉原来的定义。%{#defineYYSTYPEdouble#include<ctype.h>#include<stdlib.h>#include"types.h"#include"hash.h"#include"token.h"floatval=0;%}(3)第2部分为正规式单词的定义。实际这里只用到数字，也可以不变。(4)每扫描到一个单词，对应的处理动作为：将该单词的编码和属性分别写入到tokens和attribs数组中。具体在Lex第3部分如下编程："+" {addToken($add,0);}"-" {addToken($sub,0);}…{digits}{sscanf(yytext,"%f",&val); //数字。将数字的值拷贝进整型变量 val。其中addToken(inttoken,intattrib) 函数定义在第4部分：voidaddToken(inttoken,intattr){if(ip<MAXTOKEN){tokens[ip]=token;attribs[ip]=attr;ip++;}}建议大家统一再看看expToken.txt源文件。(5)主程序无需打开输出文件，每扫描到一个单词，系统会自动用相应的代码块，8/19

编译原理实验指导即，调用addToken函数执行相应的工作。这都在 Lex自动生成的函数lexyy()内部处理。因此语法分析主程序只需要调用 lexyy()函数即可。自编代码的词法分析器构造(任选)该程序相对而言较为简单，以下列举词法分析主程序。详细内容见参考代码。//从流中读取一个单词intlexyy(){charch='';if(bufChar=='')while(isBlank(ch))ch=fgetc(stream);//跳过所有的空格回车else{//else{//使用了超前搜索的情况ch=bufChar;bufChar='';//bufChar='';//用空格清掉超期搜索字符。if(ch=='+')return$add;elseif(ch=='-')return$sub;elseif(ch=='*')return$mul;elseif(ch=='/')return$div;elseif(ch=='(')return$llbr;elseif(ch==')')return$lrbr;elseif(ch=='#')return$sharp;elseif(isDigit(ch))bufChar=ch;//超期搜索缓冲wip=0;bufChar=ch;//超期搜索缓冲wip=0;//单词指针清0returnreadNum();//读取整个数字，返回数字的单词编码，而数字的值暂存returnreadNum();于curValue变量。elseerror("词法错误");9/19编译原理实验指导return0;)主程序的编写voidmain(){/*执行词法分析*/lexyy();/*执行语法分析*/E(); /*调用开始符号所对应的过程进行分析。*/printf("语法正确.")； /*如能执行到这里，证明中途没出错 */)若上述代码放在LEX文件中，请把中文注释去掉，同时保存类型设为 ANSI。步骤1、重构词法分析程序设计文法定义不回溯且考虑到三种优先级的表达式计算的文法，前面是一参考实现。最好能根据要求独立设计文法。2、建立C语言工程建立语法分析主程序文件，假定命名为：express.c。同时将该token.h加入。3、编写递归下降程序根据文法，按要求在express中编写递归下降子程序。如感觉比较困难，请参照递归下降法4、编写测试主程序(基本要求)构造一命令行的输入程序，即输入表达式串。输出语法分析成功与否。输出结果为“语法正确”“语法错误”。5、程序系统调试验证结果问题及解答请大家提出意见和建议，以便改进本手册。提高1、实现一个完整的高级语言子集。2、建立图形界面，对本实验内容进行包装。3、选取针对某些结构化文档，如XML建立语法分析器。实验报告要求考虑到大家的实际情况，实验报告只要求实现基于字符的分析过程。其提纲如下：1、目的2、内容10/19编译原理实验指导先介绍下该程序主要功能文法E今TE’ E’二+TE’I£T今FT’T’=*FT’l£Ff（E）li递归下降过程（附上代码）测试用例3、总结（心得）11/19编译原理实验指导实验3实验3自底向上的语法分析目的1、掌握SLR法进行语法分析的原理。2、设计相应得数据结构及编码，实施算法的相关要素的机内表示。3、掌握语法分析器的设计与调试；内容1、算法的数据结构（1）分析表分析表采用二维持数组，其中第0行存放表头。intat[MAXROW][MAXCOL]; 〃分析表（2）堆栈由于符号栈与状态栈通常同步操作，可将二栈合二为一。堆栈元素可用结构体包装相应的数据。〃代表非终结符和终结符（由于符号栈和状态栈均为同步操作。通过结构体的方式实现堆栈合并）typedefstructT{charname; 〃名称（便于外部输出）intcode; 〃编码（便于内部处理）intstate; 〃状态intvalue; 〃该非终结符的值}Token;〃堆栈类型typedefstructS1{Tokenbody[MAXSIZE]; 〃堆栈体intip; 〃栈顶指针}TokenStack;（3）产生式的表示〃产生式候选记录表typedefstructProduction{charleftName; 〃左部名称intleftCode; 〃左部编码intrightLen; 〃右部长度，决定出栈数。}Prod;12/19

编译原理实验指导2、程序模块的划分（1）堆栈操作的相关函数（2）分析表操作（3）主分析过程〃对一个输入符号执行分析〃说明：由于堆栈集成为一个，所以堆栈操作可以不指出堆栈变量。intanalysis(TokenStack*s,intcode){intcurState,curOp,pi; 〃当前状态，操作，产生式编号curState=getState(s); 〃获取当前状态curOp=getOperate(curState,code); 〃获取当前操作if(curOp==-1)error("分析表中未定义")；if(curOp==ACC){〃输入串正确出口〃归约代码〃去掉R〃输入串正确出口〃归约代码〃去掉R标识，得到产生式编号)elseif(curOp>R){pi=curOp-R;〃出栈。for(inti=0;i<p[pi].rightLen;i++){〃查对应的产生式候选登记表〃出栈。pop(s);）curState=getState（s）; 〃获取当前栈顶状态。curOp=getOperate（curState,p[pi].leftCode）;//查Goto表获取跳转的状态。〃符号栈入栈.〃状态入栈（即查Goto表对应的值，所以G与S必须相等）//（语法分析阶段：不考虑语义，故value参数为0）push(s,p[pi].leftName,p[pi].leftCode,curOp-S,0);outputStacks(s);opState=0; 〃当前为归约状态)elseif(curOp>S){ //Si入栈push(s,getName(code),code,curOp-S,0);//当前符号、状态入栈outputStacks(s);opState=1; 〃当前为移进状态)else13/19编译原理实验指导error（"语法错误!"）； 〃return0;）（4）主程序及输入输出（5）错误处理3、测试要求（1）成功的输入串（2）词法错误串（3）语法错误串步骤1、建立c语言工程2、加入单词编码头文件。3、编写相关代码4、在命令行下运行，进行测试。问题时间关系，许多地方还没来得及作好，但欢迎大家提出问题。实验报告要求1、目的2、内容数据结构设计：文字描述，不要求写代码主要模块：①主分析过程（代码或流程图）堆栈操作：push、pop…（将函数名写出）分析表操作：（将函数名写出）④词法分析辅助过程：（将函数名写出）输入输出及错误处理：（将函数名写出）（期末考试实验占10分。其中本实验将根据内容记分，并直接记入期末成绩。可参考所附代码，如自己有另外实现也可，需提交代码）测试：语法正确的表达式。②语法错误的表达式。③词法错误的表达式。3、总结（心得）14/19编译原理实验指导实验4语义分析目的1、属性文法及语法制导翻译和递归下降的语法分析结合，构造语义分析程序。2、以表达式文法为例，构造文本计算器演示程序。知识1、设计属性文法。以一个例子加以说明：考察文法G（E）:E3TLL—+TLI£T3$num我们可以从以下几个方面去理解。下标的含义首先考虑到产生式中不止一个E，在语法分析中由于在不同的时间不同的地方处理，因而不会产生歧义。但在语义分析中，任何一个符号的属性都可在上下文中出现，因而有必要加以区分。通常通过设置下标的方式来区分。L3+TL1有了下标L和L1就能加以区分。可以这么说，L、L1不是“同个”非终结符，但是是“同类”非终结符。因此，属性文法设计的第一步就是把同一产生式候选中的相同符号加以下标。（2）属性的设计属性是为每个符号配置的。终结符得属性通常通过词法分析得到。非终结符的属性通常为上下文的属性计算得到。首先考虑全局的，即整个文法最终要求什么。将其数据化作为开始符号得属性。在上例中，表达式最终是求若干个数之和的结果值。因此为非终结符E配备一个属性s，表示E所展开的子表达式的值。再考虑叶子结点能够获取到什么信息。叶子都是终结符，信息实际上是通过词法分析获取的单词语义。如“2”，分析程序扫描到文本字符“2”，将其转换成二进制的值2。但在语法分析中，只是将其解释为“数字”，用$num表示。而二进制的值2只是作为$num的一个属性,不妨记为$num.v。最后考虑语法树中的支干结点需要传递些什么数据，根据相应的数据定义相应的属性。设计属性时，必须明确两点：3、支干（非叶子，非根）结点的属性主要功能是传递数据和中间计算。要按树的遍历顺序来考虑。因为无论是自顶向下还是自底向上，本质上都是对树的一次遍历（这点在上课实讲过）。15/19编译原理实验指导4、一个结点可以有多个属性。本例中，非终结符L结点不仅负责传递属性，还要完成计算。定义两个属性变量，i表示输入属性，s表示计算结果。2+3+5的属性文法语法树(3)属性的计算规则设计规则：①根据实例语法树，考虑其自左至右遍历的顺序。分析其数据传递和计算方法。②结合产生式。将传递和计算规则提炼到产生式中。如上例，设计的属性文法如下：E3T{L.i=T.s}L{E.s=L.s}L3+T{L1.i=L.i+T.s}L1{L.s=L1.s}L3£{L.s=L.i}T3$num{T.s=$num.v}5、如何根据属性文法设计递归下降子程序关于递归下降的语义分析，清华版的教材没有提及。国防科大版的教材有初步的介绍。这里以一个简单的例子说明如何实现。继续考察上例，即将表达式中的加法单独抽取出来，其语义就是加法。每个非终结符对应一个过程继承属性作为输入参数综合属性作为返回值如：//E->T{L.i=T.s}L{E.s=L.s}floatE(){16/19编译原理实验指导floatTs,Ls;//Ts,Ls分别表示T.s、L.两个属性Ts=T();Ls=L(Ts);returnLs;)内容本实验的主要内容在于实现一个文本计算器。属性文法设计由于使用了递归下降的语法分析，则必须考虑是否为LL文法。针对表达式文法，需要选用消除了左递归的文法。根据教材上的版本进行改造，考虑了四则混合运算的情况。设计文法如下：EfT{L.i=T.s}L{E.s=L.s}Lf+T{L1.i=L.i+T.s}L1{L.s=L1.s}Lf-T{L1.i=L.i-T.s}L1{L.s=L1.s}Lf£{L.s=L.i}TfF{R.i=F.s}R{T.s=R.s}Rf*F{R1.i=R.i