中南大学编译原理实验报告

1、CENTRAL SOUTH UNIVERSITY 编 译 原 理 实 验 报 告学生姓名 专业班级 学 号 学 院 信息科学与工程学院 指导教师 张修如 实验时间 2015年5月 实验一 计算FIRSTVT集一、实验目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC /JAVA/C#/.NET 。二、实验内容设计一个由正规文法生成FIRSTVT集的算法动态模拟，实现以下功能：1输入一个文法

2、G； 2输出由文法G构造FIRSTVT集的算法；3输出FIRSTVT集。三、实验要求1思想的正确性，采用合适的数据存储结构等；2程序实现的正确性，程序整体结构合理、编程风格规范等； 3程序功能的完善程度，包括功能的基本实现、基本完善、完全实现；    4工作认真、独立完成实验。四、实验步骤1问题理解和分析：充分地分析和理解问题本身，弄清要求做什么； 2确定解决问题的方法：主要是找到解决问题的主要思路，该怎么做；3详细设计和编码：确定算法的主要流程，再进行编程；4程序调试和运行：掌握程序调试和排错的基本方法，增加编程的感觉和解

3、决问题的成就感；5完成实验报告。五、程序设计5.1基本算法 构造集合FIRSTVT(P)的算法 按FIRSTVT(P)的定义，可以用如下两条归则来构造： (1)若有产生式Pa或Qa，则aFIRSTVT(P) (2)若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P) 构造算法： 建立一个二维布尔数组FP,a，使得FP,a为真的条件适当且仅当aFIRSTVT(P)；再用一个栈STACK，把所有初值为真的数组元素FP,a的符号对(P,a)全都放到栈中；算法如下： (1)将布尔矩阵各元素置假；栈置空； (2

4、)按照归则(1)查看产生式，对于Pa或PQa.，置相应FP,a为真，符号对(P,a)入栈； (3)按规则(2)，对栈施加如下操作：弹出栈定符号对记作(Q,a)，查看所有产生式是否有形如PQ产生式，若有，且aFIRSTVT(P)，则将FP,a置为真，并把(P,a)入栈； (4)重复(3)，直到栈空为止。  5.2定义数据结构 在程序中，用两个字符数组vnM和vtN分别用来存储所有的非终结字符集与终结字符集。为了记录非终结符的FIRSTVT集，为此建立一个布尔数组FMN，记录非终结符的FIRSTVT集。比如，Fij=true表示vtj属于FIRST

5、VT(vni)，值为false表示相应的终结符不属于非终结符的FIRSTVT集。 为了简便起见，程序中又构造了一个两维布尔数组firstMM+N来表示推导关系。数组第一维的M个字符代表非终结符；数组第二维的前M个字符代表非终结符，后N个字符代表终结符。以first数组为例，fistiM+j代表非终结符vni=P与非终结符vtj=a有推导关系P a；fistij代表非终结符vni=P与非终结符vtj=Q有推导关系或PQa.。  相关的数据结构定义如下： char vnM,vtN;  /非终结字符与终结字符数组

6、0;bool firstMM+N,lastMM+N; /以布尔数组形式定义推导关系 char vnM,vtN;  /非终结字符与终结字符数组 int stp; /堆栈栈顶指针 符号栈的数据结构： struct relation   int vn;   int vt;   /结构体用来说明终结符vt与非终结符vn之间的关系，若关系存在说明vt属于FIRSTVT(vn)&

7、#160;六、关键代码#include<stdio.h>#include<iostream>#define N 10#define M 10using namespace std;/用于存储FIRSTVT集char FIRSTVT0N,FIRSTVT1N,FIRSTVT2N,FIRSTVT3N,FIRSTVT4N;/接受输入char INPUTNM; /存储FIRSTVT集void setFIRSTVT(char X,int T)void FIRSTVT(char X,int S)void main() int i,j; printf("请输入文法(按两次回车

8、结束):n"); for(i=0;i<N;i+) for(j=0;j<M;j+) scanf("%c",&INPUTij); if(INPUTij='n') break; if(INPUTi0='n') break; /保存FIRSTVT集 for(i=0;INPUTi0!='n'i+) FIRSTVT(INPUTi0,i); printf("FIRSTVT SET:n"); for(i=0;INPUTi0!='n'i+) switch(i) case 0: p

9、rintf("FIRSTVT("); printf("%c",INPUT00); printf(")="); for(j=0;FIRSTVT0j!='0'j+) printf("%c",FIRSTVT0j); if(FIRSTVT0j+1!='0') printf(","); printf("n"); break; case 1: printf("FIRSTVT("); printf("%c",INPUT

10、10); printf(")="); for(j=0;FIRSTVT1j!='0'j+) printf("%c",FIRSTVT1j); if(FIRSTVT1j+1!='0') printf(","); printf("n"); break; case 2: printf("FIRSTVT("); printf("%c",INPUT20); printf(")="); for(j=0;FIRSTVT2j!='0&#

11、39;j+) printf("%c",FIRSTVT2j); if(FIRSTVT2j+1!='0') printf(","); printf("n"); break; case 3: printf("FIRSTVT("); printf("%c",INPUT30); printf(")="); for(j=0;FIRSTVT3j!='0'j+) printf("%c",FIRSTVT3j); if(FIRSTVT3j+1!

12、='0') printf(","); printf("n"); break; case 4: printf("FIRSTVT("); printf("%c",INPUT40); printf(")="); for(j=0;FIRSTVT4j!='0'j+) printf("%c",FIRSTVT4j); if(FIRSTVT4j+1!='0') printf(","); printf("n"

13、;); break; default :break; printf("n"); system("pause"); 七、实验结果与总结7.1实验结果上图FIRSTVT集的关系矩阵中，内的终结字符属于对应的非终结字符的FIRSTVT集，从上面两个步骤可知用程序运算的结果和分析得到的FIRSTVT集相符合。7.2实验总结通过此次实验，我复习巩固了自下而上的分析方法，其中重点复习了算符优先分析算法，对词法、文法的判断有了较深刻的认识，对算符优先分析算法的FirstVT集和LastVT集的构造有了更加深刻的理解，对其中数据的流向和数据的输出操作有了很清晰的认识，对

14、数据在该实验中的存储和运算有了深刻的理解。同时，此次实验还增强了我的编码能力。实验二 自上而下的语法分析-预测分析法设计与实现一、实验目的加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。二、实验内容用预测分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。三、实验要求1. 对语法规则有明确的定义；2. 编写的分析程序能够对实验一的结果进行正确的语法分析；3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；4.

15、 实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。四、实验步骤1. 定义目标语言的语法规则；2. 求解预测分析方法需要的符号集和分析表；3. 依次读入符号串，根据预测分析的方法进行语法分析，直到源程序结束；4. 对遇到的语法错误做出错误处理。五、程序设计所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL（1）分析器。我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无

16、左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了JAVA语言来编写，其逻辑结构图如下：STACK分析栈输出a1 a2 a3 aian#输入串（源程序）总控程序预测分析表MX1Xn-1Xn#LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），

17、总控程序每次都执行下述三种可能的动作之一：（）若X = a =#，则宣布分析成功，停止分析过程。（）若X = a#，则把X从STACK栈顶弹出，让a指向下一个输入符号。（）若X是一个非终结符，则查看预测分析表M。若MA，a中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为，则不推什么东西进STACK栈）。若MA，a中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分

18、析的。六、关键代码LL1_Analysis.javapackage analyse;import java.io.*;import java.util.Stack;public class LL1_Analysis String terminator;/ 终结符 String nonTerminator;/ 非终结符 String analysisTable;/ 分析表 public Stack<String> stack = null; StringBuffer strArray; / 字符数组 int index = 0;/ 字符数组索引值 / 匹配结果：无效输入，成功（均为#

19、）， 两字符相等（且不等于#）， 弹栈（产生式为）， 压栈（将产生式反序入栈）， 错误（栈值为null） enum Type INVALID_STR, SUCCESS, EQUAL, POP_STACK, PUSH_STR, ERROR FileWriter writer = null; void temp() /* * 执行预测分析法 */ public void run() initialization(); analysis(); public String find (String str1, String str2) void analysis()/ 从输入串数组读一个StringS

20、tring readFromStrArray(StringBuffer strArray) / 输入串指针前移void indexForward() / 返回当前输入串索引int getIndex() / 判断输入串指针是否在合理范围boolean isIndexInStrArray() / 当前字符与栈顶元素匹配public Type match(String pop, String str) boolean isTerminator(String str) boolean isNonTerminator(String str) boolean isValidStr(String str)

21、void printState(String production) String printStrArray() String printStack() /* * 全局初始化 */public void initialization() / 初始化终结符void initTerminator() / 初始化非终结符void initNonTerminator() / 初始化分析表void initAnalysisTable() / 初始化栈void initStack() /* * 从命令行读取输入串 * throws IOException */String readFromConsole

22、() throws IOException 七、实验结果与总结7.1实验结果正确输入下的结果：非法输入下的结果：7.2实验总结通过此次实验，我学习并了解了如何设计、编写和调试预测分析程序，加深了对自上而下分析原理的理解；熟悉了预测分析程序的工作过程以及构造预测分析表的相关原理，并使用JAVA语言直接编写了此语法分析程序。另外，此次实验也让我重新熟悉了JAVA语言的相关内容，加深了对JAVA语言功能的理解。实验三 中间代码生成一、实验目的熟悉算术表达式的语法分析与中间代码生成原理。二、实验内容完成以下描述赋值语句和算术表达式文法的语法制导生成中间代码四元式的过程。GA:AV:=EEE+TE-TT

23、T*FT/FFF(E)iVi说明：终结符号i 为用户定义的简单变量,即标识符的定义。三、实验要求1给出每一产生式对应的语义动作；2设计中间代码四元式的结构（暂不与符号表有关）；3. 输入串应是词法分析的输出二元式序列，即某算术表达式“实验项目一”的输出结果。输出为输入串的四元式序列中间文件；4设计两个测试用例（尽可能完备），并给出程序执行结果四元式序列。四、实验步骤1问题理解和分析：充分地分析和理解问题本身，弄清要求做什么； 2确定解决问题的方法：主要是找到解决问题的主要思路，该怎么做；3详细设计和编码：确定算法的主要流程，再进行编程；4程序调试和运行：掌握程序调试和排错的基本方法，

24、增加编程的感觉和解决问题的成就感；5完成实验报告。五、程序设计5.1 数据结构描述本程序采用的是算符优先文法，文法以及算符优先矩阵是根据第一次实验来修改的，所以主要的数据结构也跟第一次差不多，主要为文法的表示，FirstVT集和LastVT集以及算符优先矩阵：struct infochar left;vector<string> right;vector<char> first;vector<char> last;算符优先矩阵采用二维字符数组表示的：char mtr99; /算符优先矩阵5.2程序结构描述：本程序一共有10个功能函数：void get();

25、/获取文法void print(); /打印文法void fun(); /求FirstVT 和 LastVTvoid fun_show(); /打印FirstVT 和 LastVTvoid matrix(); /求算符优先矩阵void matrix_show(); /打印算符优先矩阵void test(); /测试文法int cmp(char a,char b); /比较两个运算符的优先级 1 0 -1void out(char now,int avg1,int avg2); /打印四元式int ope(char op,int a,int b); /定义四元式计算方法六、关键代码#includ

26、e <iostream>#include <string>#include <VECTOR>#include <stack>using namespace std;struct infochar left;vector<string> right;vector<char> first;vector<char> last;vector<info> lang;char mtr99; /算符优先矩阵stack<char> sta;void get(); /获取文法void print(); /

27、打印文法void fun(); /求FirstVT 和 LastVTvoid fun_show(); /打印FirstVT 和 LastVTvoid matrix(); /求算符优先矩阵void matrix_show(); /打印算符优先矩阵void test(); /测试文法int cmp(char a,char b); /比较两个运算符的优先级 1 0 -1void out(char now,int avg1,int avg2); /打印四元式int ope(char op,int a,int b); /定义四元式计算方法int main()int choose;get();fun();matrix();while(1)cout << "*" << endl;cout << " 打印文法请按 1" << endl;cout << " 查看FirstV