大学学生实验报告
开课学院及实验室：年月日
实验目的
设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。
针对表达各类词语的一组正规表达式，设计一个确定化的最简的有限自动机，对输入的符号串进行单词划分及词类识别。
实验容
将词法分析器分解为以下几个部分：
1.正规表达式的解析：将正规表达式中的符号分解为常量字符、正规表达
式标识符和正规表达式运算符，然后基于正规表达式运算将正规表达式
分解为更小的正规表达式（通过正规表达式运算符进行串接）。
2.正规表达式到NFA的转换：根据转换规则，基于正规表达式运算，将正
规表达式转换为非确定有限自动机，并确定各类词的终止状态。
3.NFA的确定化：通过计算各状态的传递闭包，将NFA确定化，并确定
各类词的终止状态。
4.最小化：通过子集法，求得最简的确定有限自动机，并确定各类词的终
止状态。
例如：分析C语言子集的词法
1）关键字
main if else int return void while （都是小写）2）专用符号
= + —* / < <= < >= = = != ；：，{ } [ ] ( )
3）其他模式（正规表达式）
STRING::=" [^"]*
ID::=letter(letter|digit)*
INT::=digit digit*
letter::= a|…|z|A|…|Z
digit::= 0|…|9
4）空格由空白、制表符和换行符组成
空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。
部分单词符号对应的种别码
词法分析程序的功能
输入：所给文法的源程序字符串
输出：二元组（syn, token或sum）构成的序列。其中syn 为单词种别码；token 为存放的单词自身字符串；sum为整型常量（作为常量的值）。实现时，可将单词的二元组用结构进行处理
代码：
#include
#include
using namespace std;
int main(){
int i=0,j,k=0; //k判断是保留字还是id
char a[7][10] = {"main","if","else","int","return","void","while"};//保留字数组
char s;
char token[40] = {"\0"};
cout<<"请输入字符"< s=getchar(); while(s!=EOF){ //不是结束字符 if(s==' '||s=='\n'||s=='\t'){ //过滤空格，换行 s=getchar(); } else if((s>='a'&&s<='z')||(s>='A'&&s<='Z')){//判断是id还是保留字 token[i++]=s; s=getchar(); while((s>='a'&&s<='z')||(s>='A'&&s<='Z')||(s>='0'&&s<='9')){//取接下来字符 token[i++]=s; s=getchar(); } for(j=0;j<7;j++){//判断是否为保留字 if(strcmp(token,a[j])==0){ cout< k=1; break; } } if(k==0){//为id cout<<"10,"< } memset(token,0,sizeof(token));//获取数组清零i=0; k=0; } else if(s>='0'&&s<='9'){//判断INT int flag=1; while(flag){ token[i++]=s; s=getchar(); if(!(s>='0'&&s<='9')){//不是数字 flag=0; cout<<"20,"< memset(token,0,sizeof(token)); i=0; } } } else if(s=='='){//判断= s=getchar(); if(s=='='){ cout<<"39,=="< s=getchar(); } else{cout<<"21,="< } else if(s=='+'){//判断+ cout<<"22,"< s=getchar(); } else if(s=='-'){//判断- cout<<"23,"< s=getchar(); } else if(s=='*'){//判断* cout<<"24,"< s=getchar(); } else if(s=='/'){//判断/ cout<<"25,"< s=getchar(); } else if(s=='('){//判断( cout<<"26,"< s=getchar(); } else if(s==')'){//判断) cout<<"27,"< s=getchar(); } else if(s=='['){//判断[ cout<<"28,"< s=getchar(); } else if(s==']'){//判断] cout<<"29,"< s=getchar(); } else if(s=='{'){//判断{ cout<<"30,"< s=getchar(); } else if(s=='}'){//判断} cout<<"31,"< s=getchar(); } else if(s==','){//判断, cout<<"32,"< s=getchar(); } else if(s==':'){//判断: cout<<"33,"< s=getchar(); } else if(s==';'){//判断; cout<<"34,"< s=getchar(); } else if(s=='>'){//判断>或>= s=getchar(); if(s=='='){ cout<<"37,>="< s=getchar(); } else{cout<<"35,>"< else if(s=='<'){//判断<或<= s=getchar(); if(s=='='){ cout<<"38,<="< s=getchar(); } else{cout<<"36,<"< else if(s=='!'){ s=getchar(); if(s=='='){ cout<<"40,!="< s=getchar(); } } } } 试验结果： 课程实验报告课程名称：《编译原理》 专业班级：计算机科学与技术11级10班 学号：XXXXXXX 姓名：X X 指导教师：刘铭 报告日期：2014年6月16日 计算机科学与技术学院 目录 目录 (2) 1 实验一词法分析 (3) 1.1实验目的 (3) 1.2实验要求 (3) 1.3算法思想 (4) 1.4实验程序设计说明 (5) 1.5词法分析实现 (6) 1.6词法实验结果及结果分析 (12) 2 实验二语法分析 (13) 2.1 实验目的 (13) 2.2 实验要求 (13) 2.3 算法思想 (13) 2.4 实验程序设计说明 (15) 2.5 语法分析实现 (15) 4 实验中遇到的问题及解决 (22) 参考资料 (23) 1 实验一词法分析 1.1 实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 1.2 实验要求 1、待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ：= + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码： 表1 各种单词符号对应的种别码 3、词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； 编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。 实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则 《LL（1）分析器的构造》实验报告 一、实验名称 LL(1)分析器的构造 二、实验目的 设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。 三、实验内容和要求 设计并实现一个LL(1)语法分析器，实现对算术文法: G[E]:E->E+T|T T->T*F|F F->(E)|i 所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。 实验要求: 1、检测左递归，如果有则进行消除； 2、求解FIRST集和FOLLOW集； 3、构建LL(1)分析表； 4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。 四、主要仪器设备 硬件：微型计算机。 软件： Code blocks（也可以是其它集成开发环境）。 五、实验过程描述 1、程序主要框架 程序中编写了以下函数，各个函数实现的作用如下： void input_grammer(string *G);//输入文法G //将文法G预处理得到产生式集合P，非终结符、终结符集合U、u， int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GG int* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空 string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST集 string FIRST(string U,string u,string* first,string s)；//求符号串s=X1X2...Xn的FIRST集 string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表 void analyse(string **table,string U,string u,int t,string s)；//分析符号串s 2、编写的源程序 #include 编译原理实验报告 姓名： 学号： 班级： 学院： 南昌大学信息工程学院计算机系 2014年6月 目录 实验一 (3) 实验二 (8) 实验三 (15) 实验1 词法分析程序的设计 学生姓名：学号：专业班级： 实验类型：□验证□综合□设计□创新实验日期：实验成绩： 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数0 |（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）* 如有余力，则进一步分析八进制和十六进制整数，其正规式如下： 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < =<= >=( ) ；{ } 关键字main if then else while do int (可根据需要添加) 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: "; 南华大学 计算机科学与技术学院 实验报告 （ 2018~2019学年度第二学期） 课程名称编译原理 实验名称词法分析器的设计与 实现 姓名学号 专业班级 地点教师 1.实验目的及要求 实验目的 加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。 实验要求 1.对单词的构词规则有明确的定义； 2.编写的分析程序能够正确识别源程序中的单词符号； 3.识别出的单词以 <种别码，值 >的形式保存在符号表中，正确设计和维护 符号表； 4.对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误 提示，保证顺利完成整个源程序的词法分析； 2.实验步骤 1.词法分析规则 <标识符 >::=< 字母 >|< 标识符 ><字母 >|< 标识符 ><数字 > <常数 >::=< 数字 >|< 数字序列 ><数字 > <数字序列 >:: ＝<数字序列 ><数字 >|< 数字 >|<.> <字母 >::=a|b|c|??|x|y|z <数字 >::=0|1|2|3|4|5|6|7|8|9 <运算符 >::=< 关系运算符 >|< 算运算符 >|< 运算符 >|< 位运算符 >|< 运算符 > <算数运算符 >:: ＝+|-|*|／|...|-- <关系运算符 >:: ＝<|>|!=|>=|<=|== <运算符 >::=&&| || |！ <位运算符 >::=&| | |！ <运算符 >::==|+=|-=|/=|*= <分界符 >:: ＝ ,|;|(|)|{|}|：| // |/**/ <保留字 >:: ＝ main|if|else|while|do|for|...|void 2.符号的 符号种符号种 main0>26 if1>=27 else2<28 while3<=29 do4!30 for5!=31 实验3LL(１)文法构造 一、实验目的 熟悉LL（1）文法的分析条件，了解ＬＬ（1）文法的构造方法。 二、实验内容 1、编制一个能够将一个非LL(1）文法转换为LL（1)文法； 2、消除左递归; 3、消除回溯。 三、实验要求 1、将一个可转换非LL（1）文法转换为LL（1）文法，要经过两个阶段，１）消除文 法左递归,2）提取左因子，消除回溯。 2、提取文法左因子算法: 1）对文法G的所有非终结符进行排序 2)按上述顺序对每一个非终结符Pi依次执行： for（ｊ=１; j< i-1;ｊ＋＋) 将Pj代入Pi的产生式(若可代入的话）； 消除关于Pｉ的直接左递归: Pｉ-> Piα|β，其中β不以Pi开头,则修改产生式为: Pi —＞βPi′ Pi′—> αPi′｜ε ３）化简上述所得文法。 3、提取左因子的算法： A —＞δβ1|δβ2|…|δβn｜γ１|γ２|…|γm (其中,每个γ不以δ开头) 那么,可以把这些产生式改写成 A —> δA′|γ1| γ２…|γm A′—＞β１｜β2|…｜βn 4、利用上述算法，实现构造一个ＬL（1）文法： 1）从文本文件g.tｘt中读入文法,利用实验1的结果，存入实验1设计的数据结构； 2）设计函数ｒｅｍｏve_left＿recursion（）和remｏｖe_left_genｅ()实现消除左递归和提取左因子算法,分别对文法进行操作，消除文法中的左递归和提出左因 子; 3）整理得到的新文法; 4）在一个新的文本文件neｗg.txｔ输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的 方式输出。 四、实验环境 PC微机 ＤＯS操作系统或Ｗindows操作系统 Ｔuｒbo Ｃ程序集成环境或Visual C++ 程序集成环境 五、实验步骤 １、学习LL（1)文法的分析条件； 2、学习构造LL（1)文法的算法; 3、结合实验１给出的数据结构,编程实现构造LL（1)文法的算法； ４、结合实验１编程和调试实现对一个具体文法运用上述算法，构造它的LL(１)文法形式; 5、把实验结果写入一个新建立的文本文件。 六、测试数据 输入数据： 编辑一个文本文文件g.ｔxt，在文件中输入如下内容: ? 正确结果： 本实验的输出结果是不唯一的,根据消除左递归是选择非终结符号的顺序不同, 或选择新的非终结符号的不同,可能会得到不同的结果，下面只是可能的一个结果： 1、 P->Ｐ之类的)，也不含以ε为右部的产生式。 一个文法要能进行LL（1)分析,那么这个文法应该满足：无二义性，无左递归,无左 院系：计算机科学学院 专业、年级： 07计科2大班 课程名称：编译原理 学号姓名： 指导教师： 2010 年11月17 日 组员学号姓名 实验 名称 实验一：词法分析实验室9205 实验目的或要求 通过设计一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 具体要求：输入为某语言源代码，达到以下功能： 程序输入/输出示例：如源程序为C语言。输入如下一段： main() { int a,b; a=10; b=a+20; } 要求输出如下（并以文件形式输出或以界面的形式输出以下结果）。 （2，”main”） （5，”（“） （5，”）“） （5，”{“} （1，”int”） （2，”a”） （5，”,”） （2，”b”） （5，”;”） （2，”a”） （4，”=”） （3，”10”） （5，”;”） （2，”b”） （4，”=”） （2，”a”） （4，”+”） （3，”20”） （5，”;”） （5，”}“） 要求： 识别保留字：if、int、for、while、do、return、break、continue等等，单词种别码为1。 其他的标识符，单词种别码为2。常数为无符号数，单词种别码为3。 运算符包括：+、-、*、/、=、>、<等；可以考虑更复杂情况>=、<=、!= ；单词种别码为4。分隔符包括：“，”“；”“（”“）”“{”“}”等等，单词种别码为5。 编译原理上机实验试题 一、实验目的 通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术， 如何针对确定的有限状态自动机进行编程序；熟悉和 掌握程序设计语言的语法分析程序的设计原理、熟悉 和掌握算符优先分析方法。 二、实验要求 本实验要求：①要求能熟练使用程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）； ③要编写出完成相应任务的程序并在计算机上准确 地运行；④实验结束后要写出上机实验报告。 三、实验题目 针对下面文法G(S)： S→v = E E→E+E│E-E│E*E│E/E│（E）│v │i 其中，v为标识符，i为整型或实型数。要求完成 ①使用自动机技术实现一个词法分析程序； ②使用算符优先分析方法实现其语法分析程序，在 语法分析过程中同时完成常量表达式的计算。 1、题目（见“编译原理---实验题目.doc，“实验题目”中的第一项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理： (1)单词分类：标识符，保留字，常数，运算符，分隔符等等 (2)单词类型编码 (3)自动机 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。 1、题目（见“编译原理---实验题目.doc，“实验题目”中的第二项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理：构造出算法优先关系表 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。 实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中得单词包括五个关键字begｉｎ、end、if、then、elsｅ；标识符；无符号常数；六种关系运算符；一个赋值符与四个算术运算符，试构造能识别这些单词得词法分析程序（各类单词得分类码参见表Ｉ）。 表Ｉ语言中得各类单词符号及其分类码表 输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。 输出：把所识别出得每一单词均按形如(CLASS，VＡLUE）得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数，CＬASS字段为相应得类别码得助记符;V AL ＵＥ字段则就是该标识符、常数得具体值；对于关键字与运算符,采用一词一类得编码形式，仅需在二元式得CLASS字段上放置相应单词得类别码得助记符，V ALUE字段则为“空". 三、实现方法与环境 词法分析就是编译程序得第一个处理阶段，可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BＮF)，用手工得方式（例如可用Ｃ语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成，即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程 实验一文法的机内表示与输入输出 实验题目：文法的机内表示与输入输出 实验目的：输入文法，按照所提供的各种要求输出所需结果。 实验准备：在学习了规则和有关文法的一些基本概念后，用本实验来加深各个概念间的关系。例如规则、文法、识别符、Chomsky文法、终结符、 非终结符等。 设计考虑： 实验代码： #include 《编译原理》实验报告软件131 陈万全132852 一、需求分析 通过对一个常用高级程序设计语言的简单语言子集编译系统中词法分析、语法分析、语义处理模块的设计、开发，掌握实际编译系统的核心结构、工作流程及其实现技术，获得分析、设计、实现编译程序等方面的实际操作能力，增强设计、编写和调试程序的能力。 通过开源编译器分析、编译过程可视化等扩展实验，促进学生增强复杂系统分析、设计和实现能力，鼓励学生创新意识和能力。 1、词法分析程序设计与实现 假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序。 输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。 输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。 2、语法分析程序设计与实现 选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的 一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式>→<项> | <算术表达式>+<项> | <算术表达式>-<项> <项>→<因式>|<项>*<因式>|<项>/<因式> <因式>→<运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和i 代表，则G2可写成： G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID······输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。 3、语义分析程序设计与实现 对文法G2[<算术表达式>]中的产生式添加语义处理子程序，完成运算对象是简单变量（标识符）和无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。 输入：包含测试用例（由标识符、无符号数和+、?、*、/、(、)构成的算术表达式）的源程序文件。 输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。 若源程序中有错误，应指出错误信息 二、设计思路 1、词法分析程序设计与实现 1)单词分类 为了编程的实现。我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。 编译原理实验指导书 主编：徐静李娜 信息与电气工程学院 2010年3月 概述 一、本课程实验的目的和任务 编译原理是一门实践性很强的课程，只有通过实践，才能真正掌握。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的3个环节──词法分析、语法分析（包括语义处理、产生无优化的目标指令）、连接调试，进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试，再连接在一起总调。 二、实验方法 任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践全过程。故本实验将定义一个简化的语言── C语言的一个子集作为源语言，设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程，利用上机时间进行输入和调试。 三、实验报告的规范和要求 每个实验完成后写出实验报告。实验报告的内容包括如下内容： 一、实验目的 二、程序设计时采用的算法和方法 三、输入的源程序 四、词法分析程序清单和输出结果。 五、心得体会 实验一词法分析 一、实验目的： （1）通过设计编制调试一个具体的词法分析程序，理解词法分析在编译程序中的作用。 （2）加深对有穷自动机模型的理解。 （3）掌握词法分析程序的实现方法和技术。 （4）用C语言对一个简单语言的子集编制一个一遍扫描的程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。 二、实验预习提示 1. 词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式（单词种别码，单词符号的属性值）。本实验中，采用的是一类符号一种别码的方式。 2. 单词的BNF表示 <标识符>→ <字母><字母数字串> <字母数字串>→<字母><字母数字串>|<数字> <字母数字串>| <下划线><字母数字串>|ε <无符号整数>→<数字> <数字串> <数字串>→<数字><数字串>|ε <加法运算符>→+ <减法运算符>→- <大于关系运算符>→> <大于等于关系运算符>→>= 3. “超前搜索”方法 大学学生实验报告 开课学院及实验室：年月日 实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 针对表达各类词语的一组正规表达式，设计一个确定化的最简的有限自动机，对输入的符号串进行单词划分及词类识别。 实验容 将词法分析器分解为以下几个部分： 1.正规表达式的解析：将正规表达式中的符号分解为常量字符、正规表达 式标识符和正规表达式运算符，然后基于正规表达式运算将正规表达式 分解为更小的正规表达式（通过正规表达式运算符进行串接）。 2.正规表达式到NFA的转换：根据转换规则，基于正规表达式运算，将正 规表达式转换为非确定有限自动机，并确定各类词的终止状态。 3.NFA的确定化：通过计算各状态的传递闭包，将NFA确定化，并确定 各类词的终止状态。 4.最小化：通过子集法，求得最简的确定有限自动机，并确定各类词的终 止状态。 例如：分析C语言子集的词法 1）关键字 main if else int return void while （都是小写）2）专用符号 = + —* / < <= < >= = = != ；：，{ } [ ] ( ) 3）其他模式（正规表达式） STRING::=" [^"]* ID::=letter(letter|digit)* INT::=digit digit* letter::= a|…|z|A|…|Z digit::= 0|…|9 4）空格由空白、制表符和换行符组成 空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。 部分单词符号对应的种别码 词法分析程序的功能 输入：所给文法的源程序字符串 输出：二元组（syn, token或sum）构成的序列。其中syn 为单词种别码；token 为存放的单词自身字符串；sum为整型常量（作为常量的值）。实现时，可将单词的二元组用结构进行处理 代码： #include 编译原理实验报告 合肥工业大学计算机科学与技术 完成日期：2013.6.3 实验一词法分析设计 一、实验功能： 对输入的txt文件内的内容进行词法分析： 由文件流输入test.txt中的内容， 对文件中的各类字符进行词法分析 打印出分析后的结果； 二、程序结构描述：（源代码见附录） 1、利用Key[]进行构造并存储关键字表；利用optr[]进行构造并存储运算符表；利用separator[]进行构造并存储分界符表； 2、bool IsKey(string ss) {}判断是否是关键字函数若是关键字返回true,否则返回false; bool IsLetter(char c) {}判断当前字符是否字母，若是返回true,否则返回false; bool IsDigit(char c) {}判断当前字符是否是数字，若是返回true,否则返回false； bool IsOptr(string ss) {}判断当前字符是否是运算符，若是返回true，否则返回false； bool IsSeparator(string ss) {}判断当前字符是否是分界符，若是返回true，否则返回false； void analyse(ifstream &in) {}分析函数构造； 关系运算符通过switch来进行判断； 三、实验结果 实验总结： 词法分析的程序是自己亲手做的，在实现各个函数时花了不少功夫， 1、要考虑到什么时候该退一字符，否则将会导致字符漏读甚至造成字符重复读取。 2、在实现行数和列数打印时要考虑到row++和line++应该放在什么位置上才可以，如当读取一个\n时line要增加一，而row需要归0处理，在读取某一字符串或字符后row需要加一； 3、对于关系运算符用switch结构进行选择判断即可解决一个字符和两个字符的运算符之间的差异； 4、将自己学过的知识应用到实践中是件不怎么容易的事情，只有亲身尝试将知识转化成程序才能避免眼高手低，对于知识的理解也必将更加深刻。 实验2 词法分析程序的设计 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数0 | (（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*) 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < = ( ) ； 关键字if then else while do 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 五、实验步骤 1、根据正规式，画出状态转换图； 学生学号实验课成绩 武汉理工大学 学生实验报告书 实验课程名称编译原理 开课学院计算机科学与技术学院 指导老师姓名饶文碧 学生姓名 学生专业班级 —学年第学期 实验课程名称：编译原理 实验项目名称单词的词法分析实验成绩 实验者专业班级组别 同组者实验日期 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 完成对某一种常用高级语言（如Pascal、C语言、PL/0语言）的各类单词进行词法分析，即对源程序从左到右进行扫描，对组成源程序的字符串拼接成为单词；并把其转换成属性字输出。 实验要求： （1）选择常用高级程序设计语言（如 Pascal、C语言、PL/0语言）的源程序作为词法分析对象。 （2）根据教学要求和学生具体情况，从上列语言之一中选取它的一个适当大小的子集，可以选取一类典型单词，也可以尽可能使各种类型的单词都能兼顾到。其基本要求是：对源程序从左到右进行扫描，对组成源程序的字符串拼接成为单词，并把其转换成属性字输出。 二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） #include 《编译原理》实验报告 班级：计C104 姓名：李云霄 学号：108490 实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。 二、实验内容 选取无符号数的算术四则运算中的各类单词为识别对象，要求将其中的各个单词识别出来。 输入：由无符号数和+，－，*，/, ( , ) 构成的算术表达式，如1.5E+2－100。 输出：对识别出的每一单词均单行输出其类别码（无符号数的值暂不要求计算）。 三、实现方法与环境 1、首先设计识别各类单词的状态转换图。 描述无符号常数的确定、最小化状态转换图如图1所示。其中编号0，1，2，…，6代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。 图1 文法G[<无符号数>]的状态转换图 其中编号0，1，2，…，6代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。 在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。 四则运算算术符号的识别很简单，直接在状态图的0状态分别引出相应标记的矢 编译原理实验报告 实验名称NFA转换为DFA 实验时间2014-5-18 院系计算机科学与技术学院 班级 学号 姓名 1.试验目的 不确定有限状态自动机的确定化（Affirmation of the indefinitely finite automata） 2.实验原理 一个确定的有限自动机（DFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中： （1）K是一个有穷非空集，集合中的每个元素称为一个状态； （2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3）F是一个从K×∑→K的单值转换函数，即F（R，a）＝Q，（R，Q∈K）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态； （4）S∈K，是惟一的初态； （5）Z?K，是一个终态集。 由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。 对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。若M的初态结点同时又是终态结点，则称ε可为M所接受（或识别），DFA M所能接受的全部字符串（字）组成的集合记作L（M）。 一个不确定有限自动机（NFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中： （1）k是一个有穷非空集，集合中的每个元素称为一个状态； （2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3）F是一个从K×∑→K的子集的转换函数； （4）S?K，是一个非空的初态集； （5）Z?K，是一个终态集。 由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是： （1）NFA的初始状态S为一个状态集，即允许有多个初始状态； （2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。 因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。 对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（ε除外）连接形成的字符串可为M所接受。NFA M所能接受的全部字符串（字）组成的集合记作L（M）。 由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。 设M 1和M 2 是同一个字母集∑上的有限自动机，若L（M 1 ）＝L（M 2 ），则称有 限自动机M 1和M 2 等价。 由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等 价。DFA是NFA的特例，因此对于每一个NFA M 1总存在一个DFA M 2 ，使得L（M 1 ） ＝L（M 2 ）。即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有限自动机来接受该语言。编译原理实验报告
编译原理实验指导
编译原理实验报告《LL(1)语法分析器构造》
编译原理实验报告
编译原理实验 中间代码生成
编译原理实验词法解析总结器的设计及实现.doc
编译原理实验报告3-LL(1)文法构造
编译原理实验报告
编译原理实验题目及报告要求
编译原理实验报告一
编译原理实验报告1
编译原理实验报告
编译原理实验指导
编译原理实验1
编译原理实验报告-合肥工业大学版
编译原理实验报告2词法分析程序的设计
编译原理实验报告2
编译原理实验报告(手打)
编译原理实验四
相关主题
文本预览