编译原理实验指导

1、编译原理实验指导书淘宝店530213目录编译原理课程实验指导1实验一 源程序预处理2实验二 简单程序设计语言的词法分析器6实验三 递归下降分析法9实验四 预测分析法13实验五 LR语法分析17记住淘宝店5302131编译原理课程实验指导一、课程实验方案1 实验教学目标与基本要求（1）通过实习具有开发基本的词法分析和语法分析算法的能力。（2）了解词法分析和语法分析的工作原理和特点（3）掌握课本所介绍的编译算法的原理和实现2 实验环境介绍实验主要以程序设计实现各种教学课堂中讲过的图形算法为主。程序设计设计语言主要以Visual C+语言为实验平台。3 课程实验内容实验一 源程序预处理实验学时：2学

2、时实验目的：熟悉源程序预处理的任务和要求。实现源程序输入串中注释、续行符的删除，换行符和Tab的替换，大小写字母变换，得到预处理后的文本串，为单词识别做好准备。实验内容：1. 删除注释2. 删除续行符以及后续换行符3. 将换行符和TAB统一替换为空格4. 将大写字母变换为小写字母，或者相反，以实现不区分大小写5. 识别标号区，识别续行标志。实验步骤：（1）熟悉教材关于词法分析中预处理的原理。（2）依照教材关于源程序预处理的算法，使用C/C+语言或其它语言实现该算法。（3）调试、编译、运行程序。实验要求：在下次实验时提交本次实验的实验报告（实验报告包括实验目的、实验内容、实验实现过程、源程序、实

3、验结果、实验体会）。实现代码：#include<fstream.h>#include<iostream.h># include<conio.h>void pro_process(char *);void main( )/定义扫描缓冲区char buf4048='0' /缓冲区清0/调用预处理程序pro_process(buf);/在屏幕上显示扫描缓冲区的内容cout<<buf<<endl;void pro_process(char *buf) ifstream cinf("source.txt",i

4、os:in); int i=0; /计数器 char old_c='0',cur_c; /前一个字符，当前字符 bool in_comment=false; /false表示当前字符未处于注释中 while(cinf.read(&cur_c,sizeof(char) /从文件读一个字符 switch(in_comment) case false: if(old_c='/' && cur_c='*') /进入注释 i-; /去除已存入扫描缓冲区的字符/ in_comment=true; else if(old_c='

5、' && cur_c='n') /发现续行 i-; /去除已存入扫描缓冲区的字符 else if(cur_c>='A' && cur_c<='Z') /大写变小写 cur_c+=32; if(cur_c='t' | cur_c='n') /空格取代tab换行 cur_c=' ' bufi+=cur_c; break; case true: if(old_c='*' && cur_c='/') /离开注

6、释 in_comment=false; /end of switch old_c=cur_c; /保留前一个字符 /end of while bufi+='#' /在源程序词尾加字符#实验二 简单程序设计语言的词法分析器实验学时：2学时实验目的：掌握词法分析器的原理将源程序预处理、状态图转换等结合，建立简单的程序设计语言词法分析器实验内容： 要求能对简单程序设计语言进行词法分析，具体内容如下：字符集 a.z, 0.9,+,=,*,;,(,),#若发现字符集之外的字符，即为非法字符，当出现非法字符时终止词法分析器的运行。单词集基本字：begin、end、integer、real标

7、识符：以字母开始的数字字母串无符号整常数无符号实常数运算符：+、*、+、=界符：,、;、(、)、#错误词形：. （前后无数字字符的小数点） 单词编码基本字：begin(, “NUL”、end(), “NUL”、integer(a, “NUL”、real(c, “NUL”标识符：(i, 字符串)无符号整常数：(x, 字符串)无符号实常数：(y, 字符串)运算符；=(=, “NUL”)、+(+, “NUL”)、*(*, “NUL”)、+($, “NUL”)界符：,(, “NUL”)、;(;, “NUL”)、(,C, “NUL”) 、), NUL)、#(#, “NUL”)状态转换图单词分为单字符单词

8、或多字符单词。实验步骤：（1）熟悉习教材关于词法分析的原理。（2）依照教材关于词法分析的算法，使用C/C+语言实现该算法。（3）调试、编译、运行程序。实验要求：在下次实验时提交本次实验的实验报告（实验报告包括实验目的、实验内容、实验实现过程、源程序、实验结果、实验体会）。实现代码：词法分析有5个函数构成，即预处理函数pro_process、扫描函数scanner、拼接函数concat、查基本字表函数reserve和主函数main。#include <iostream.h>#include <fstream.h>#include <string.h>#incl

9、ude <stdlib.h>const short WORDLEN=20;struct code_valchar code; char valWORDLEN;void pro_process(char *);void concat(char ,char);char reserve(char);code_val scanner(char *);void main() char buf4048=0; pro_process(buf); cout<<buf<<endl; ofstream coutf(“Lex_r.txt”,ios:out); code_val t

10、; do t=scanner(buf); /调用一次scanner函数，获得一个单词二元式 coutf<<t.code<<t<<t.val<<endl; while(t.code!=#cout<<”end of lexical analysis”<<endl;实验三 递归下降分析法实验学时：2学时实验目的：掌握递归下降语法分析的原理利用高级语言的递归过程为给定文法的每个非终结符构造对应的递归函数实验内容：若文法不含左递归，并且每个非终结符的所有候选式的首符集都两两不相交，就有可能构造一个不带回溯的自上而下的语法分析程序。这

11、个分析程序是由一组递归过程（函数）组成的，每个过程（函数）对应文法的一个非终结符。如果用某种高级语言写出所有递归过程（函数），那就可以用这个高级语言的编译系统产生整个分析程序。这个分析程序称为递归下降分析器。 用类C语言为文法G的每个非终结符构造对应的递归函数。文法G如下所示：ETEE+TE|TFTT*FT|F(E)|i|x|y实验步骤：（1）熟悉习教材关于语法分析的原理。（2）依照教材关于基于递归下降分析的算法，使用C/C+语言实现该算法。（3）调试、编译、运行程序。实验要求：在下次实验时提交本次实验的实验报告（实验报告包括实验目的、实验内容、实验实现过程、源程序、实验结果、实验体会）。实现

12、代码：假设源程序为“(a+b)*c”，经词法分析，单词二元式序列存放于文件lex_r.txt中。递归下降分析器从文件lex_r.txt读入数据进行处理。每次读入的是单词二元式，即单词的种别(code)和单词的值(val)，而分析器仅使用单词的种别。struct code_val char code; char val20; t;ifstream cinf(“lex_r.txt”,ios:in);void E() T;E;void E() if(t.code= =+) cinf>>t.code>>t.val; T;E; void T() F;T;void T() if(t

13、.code= =*) cinf>>t.code>>t.val; F;T; void F() if(t.code= =() cinf>>t.code>>t.val; E; If(t.code= =) cinf>>t.code>>t.val; else if(t.code= =i | t.code= =x | t.code= =y) cinf>>t.code>>t.val;void main() cinf>>t.code>>t.val; E;实验四 预测分析析法实验学时：4学时实

14、验目的：本实验为综合性实验，综合了栈、表等内容，其目的是在掌握栈、表以及预测分析法原理的基础上，实现预测分析表的建立和控制程序。实验内容： 用类C语言为文法G进行语法分析。文法G如下所示：ETEE+TE|TFTT*FT|F(E)|i|x|y预测分析法是一种不使用递归的语法分析方法，由一张分析表和一个控制程序构成的。一、预测分析表的构造产生式的一般形式为：A1|2|n|若当前输入符号t.codefirst(i)，则用Ai推导；若当前输入符号t.codefollow(A)，则用A推导；除此以外均为错误。候选式的选取是由两个要素决定的：一个是句型中的非终结符A，从它出发进行最左推导；另一个是当前输入

15、符号t.code。可以把上述非终结符A的产生式映射成矩阵M的一行，矩阵M以文法的非终结符为纵坐标（行），以文法的终结符为横坐标（列）。矩阵元素MAx存放着一条关于A的产生式，指出当A面临输入符号x所应采用的候选。若afirst(i)，则MAa=“Ai”；若bfollow(A)，则MAb=“A”。MAc中也可能存放一个“出错标志”，指出A根本不该面临输入符号c，在矩阵M中“出错标志”用空白表示。预测分析表M的构造方法： 构造所有候选式的first集，构造所有的非终结符的follow集； 对于文法G的每个产生式A，执行和； 对于每个终结符afirst()，把A加至MAa； 若first()，则对于

16、每个终结符bfollow(A)，把A加至MAb； 把所有未定义的MAc标上“出错标志”。二、预测分析控制程序设置一个栈stack，用于存放文法符号。初始时，栈底先放一个#，然后放进文法开始符号S。预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code进行，控制程序每次执行下述3种可能的动作之一： 若X和t.code均为#，则分析成功，输入串为合法句子，终止分析过程。 若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等。让X出stack栈，并输入下一个单词二元式。 若X是非终结符，则查预测分析表。若MXt.code存放着关于X的一个产生式，那么，让X出s

17、tack栈，然后把产生式右部符号串按反序一一推进stack栈。若右部符号串为空字，则意味着无任何文法符号进栈。实验步骤：（1）熟悉习教材关于预测分析法的原理。（2）依照教材关于基于预测分析的语法分析算法，使用C/C+语言实现该算法。（3）调试、编译、运行程序。实验要求：在下次实验时提交本次实验的实验报告（实验报告包括实验目的、实验内容、实验实现过程、源程序、实验结果、实验体会）。实现代码：void LL1() struct code_val Char code; char var20;t;ifstream cinf(“lex_r.txt”,ios:in);char stack20=#,S; c

18、har X; int top=1;cinf>>t.code>>t.val;while(1) do x=stacktop-; switch(X) of case #: if(x=t.code) cout>>”Acc”; break; case XVT: if(X= =t.code) cout>>t.code>>t.val; case XVN: if(MXt.code=XX1X2Xk) X1X2Xk按反序进栈; top=top+k; 实验五 LR语法分析实验学时：2学时实验目的： 掌握LR语法分析的基本原理基本原理：把每个句柄的识别（产生式右部的符号串）过程划分为若干状态，每个状态只识别句柄的一个符号，若干个状态就可识别句柄左端的一部分符号。利用高级语言实现LR语法分析器实验内容：文法：（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5）F(E)（6）F i假设分析表用二维数组M存储，栈顶状态用Stop表示，当前输入符号用t.code表示，控制程序的算法可归纳如下：(1) 移进。若MStopt.c