信息商务学院实验报告
课程:编译原理
实验名称:递归下降分析
学号: 201101014103
姓名:崔玲玲
指导老师:王春霞
日期:2014年5月13日
实验二递归下降分析法
一、实验目的和要求
1. 根据某一文法编制递归下降分析程序,以便对任意输入的符号串进行分
析。
2. 本次实验的目的是加深对递归下降分析法的理解。
二、实验内容
(1)功能描述
对下列文法,用递归下降分析法对任意输入的符号串进行分析,看是否能匹配成功:
(1)E→TG
(2)G→+TG|-TG
(3)G→ε
(4)T→FS
(5)S→*FS|/FS
(6)S→ε
(7)F→(E)
(8)F→i
(2)程序结构描述
本程序的实现方法主要就是函数的递归调用,在程序前面先对文法中所涉及到的非终结符对应的函数进行声明,以免在用到的时候提示函数无声明的错误提示,程序从开始符E开始,根据文法,E可以推出T和G,就在函数E()中调用T()和G(),其他的也是类似,这属于文法中只涉及到非终结符;遇到有终结符的情况则不同,想函数G(),因为G可以推出+TG或者-TG,所以在函数G()中,要分两种情况,先判断当前的字符是否是+,是则调用T()和G(),如果当前字符为-,就调用T()和G(),否则就是ε字符;按照这种方法,把文法所涉及到的非终结符都写成对应的函数,并正确调用其他函数。等所有的函数都描述之后就在mian()里判断当前字符是否分析到结束符#,是则说明此字符串是合法字符,否则说明此字符串为不合法字符。
(3)程序部分代码
#include
#include
#include
FILE *fp;
char ch;
#define N 20
char string[N];
char *p;
void E();
void T();
void G();
void F();
void S();
void E()
{
printf("E-->TG...%c\n",ch);
T();
G();
}
void F()
{
if(ch=='i')
{
printf("F-->i...%c\n",ch);
*p=ch;
p++;
ch=fgetc(fp);
}
else if(ch=='(')
{
printf("F-->(E)...%c\n",ch);
*p=ch;
p++;
ch=fgetc(fp);
E();
if(ch==')')
{
*p=ch;
p++;
ch=fgetc(fp);
}
else
{
printf("没有右括号“)”匹配不成功!\n");
exit(0);
}
}
else
{
printf("算式匹配不成功!\n");
exit(0);
}
}
void G()
{
if(ch=='+')
{
printf("G-->+TG...%c\n",ch);
*p=ch;
p++;
ch=fgetc(fp);
T();
G();
}
else if(ch=='-')
{
printf("G-->+TG...%c\n",ch);
*p=ch;
p++;
ch=fgetc(fp);
T();
G();
}
else
printf("G-->空...%c\n",ch); }
void T()
{
printf("T-->FS...%c\n",ch);
F();
S();
}
void S()
{
if(ch=='*')
{
printf("S-->*FS...%c\n",ch);
*p=ch;
p++;
ch=fgetc(fp);
F();
S();
}
else if(ch=='/')
{
printf("S-->/FS...%c\n",ch);
*p=ch;
p++;
ch=fgetc(fp);
F();
S();
}
else
printf("S-->空...%c\n",ch);
}
void main()
{
if((fp=fopen("D:\\3.txt","r"))==NULL)
{ //读取文件内容,并返回文件指针,该指针指向文件的第一个字符
fprintf(stderr,"error opening.\n");
exit(1);
}
ch=fgetc(fp);
p=string;
printf("调用分析程序所用产生式:\n");
E();
if(ch=='#')
{
*p=ch;
printf("算法匹配成功!\n算法结果:%s\n",string);
}
else
{
printf("算法匹配不成功!\n");
}
fclose(fp);
}三、实验结果
测试数据一:D盘的一个名为ceshi.txt的文本文件里文件里输入字符串:(*i)+i#,运行结果如图1所示。
测试数据二:D盘的一个名为ceshi.txt的文本文件里输入字符串:(*i)+i,运行结果如图2所示。
图1 匹配失败
图2 匹配成功
四、实验总结
本实验是为了完成字符串的分析,判断字符串能否通过一个固定的文法推导出来,正好是对课程里学到的理论进行实践的一个机会。本程序的实现代码在书本里以及给出了一部分,他的原理也不难理解,老师在实验要求里也给出了一部分代码,所以,此程序做起来还是很容易的,下面就来说说现实方法。
本程序的关键在于函数的递归调用,所以,在程序前面需要对文法中所涉及到的非终结符对应的函数进行声明,以免在用到的时候提示函数无声明的错误提示,程序从开始符E开始,根据文法,E可以推出T和G,就在函数E()中调用T()和G(),其他的也是类似。这属于文法中只涉及到非终结符,遇到有终结符的情况则不同,想函数G(),因为G可以推出+TG或者-TG,所以在函数G()中,要分两种情况,先判断当前的字符是否是+,是则调用T()和G(),如果当前字符为-,就调用T()和G(),否则就是ε字符。除了这两种情况,还有一种情况,像语法F→(E),他不仅在非终结符前有终结符,在非终结符后面也有终结符,所以F()写起来就比较复杂,在判断“(”之后条用E(),再写判断如果当前字符不是“)”就输出提示信息说明字符串不合法。按照这种方法,把文法所涉及到的非终结符都写成对应的函数,并正确调用其他函数。等所有的函数都描述之后就在mian()里判断当前字符是否分析到结束符#,是则说明此字符串是合法字符,否则说明此字符串为不合法字符。Mian()函数里除了这些还要有文件的打开和关
闭以及对开始符E的函数E()的调用,以及对文件中字符串的字符流的处理,要保证判断一个字符之后要把指针指向下一个字符,所以在每个函数调用里也需要一一重复这样功能的代码,以保证程序的正确运行。
总的来时程序比较简单,代码写完调试了几下就达到了要求,中间也没出现大的错误,所以本报告里没有写调试错误这一部分。做完实现觉得这种程序还挺有意思的,希望在以后的学习中能有更多的这样的机会,以培养我的兴趣爱好。
编译原理实验报告 实验名称 _____________ 消除文法的左递归__________________________ 实验时间 _____________________________________________ 院系 _________________________________________ 班级 ______________________________________________ 学号 ____________________________________________ 姓名
1. 试验目的 ?掌握和理解消除左递归(包括直接左递归和间接左递归)在构建 LL(1)文法的作用和目的 ?掌握消除左递归(包括直接左递归和间接左递归)的方法和步骤。 ?写出对于输入任意的上下文无关文法可以输出消除了左递归的等 价文法。 2. 实验原理 ?直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符 P的规则为 P—P a/ B 其中,B是不以P开头的符号串。那么,我们可以把P的规则改写为 如下的非直接左递归形式:P—尸’ P'—P'£ 考虑更一般的情况,假定关于非终结符P的规则为 P—P a / P o2 / …/ P a n / [31 / [32 / …/ p m 其中,a (I = 1, 2,…,n)都不为£而每个p j (j = 1, 2,…,m) 都不以P开头,将上述规则改写为如下形式即可消除P的直接左递归: P— p l P'/ 32 P'/…/p m P' P' — 01P' / a P'/…/ a n P'/£
实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境; 2、通过本实验加深对递归过程的理解 二、实验内容: 掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数,输出结果能够用递归方法实现整数的划分。 四、算法思想 对于数据n,递归计算最大加数等于x 的划分个数+最大加数不大于x-1的划分个数。最大加数x 从n 开始,逐步变小为n-1, (1) 考虑增加一个自变量:对于数据n,最大加数n1不大于m 的划分个数记作),(m n q 。则有: ???????>>=<==-+--+=1 1,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q 五、代码实现 #include "stdafx.h" #include return 0; } int q(intn,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n 《算法设计与分析》实验报告 分治策略 姓名:XXX 专业班级:XXX 学号:XXX 指导教师:XXX 完成日期:XXX 一、试验名称:分治策略 (1)写出源程序,并编译运行 (2)详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序,实现归并排序。 (2)编写一段程序,实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其它n-1个选手各赛一次(2)每个选手一天只能赛一场(3)循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序,实现归并排序。 将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行 排序,最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序,实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有 数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数 据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略,将所有的选手分为两组,n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割, 直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序,实现归并排序。 #include 递归与分治实验报告 班级:计科1102 姓名:赵春晓学号:2011310200631 实验目的:进一步掌握递归与分治算法的设计思想,通过实际问题来应用递归与分治设计算法。 实际问题:1集合划分问题,2输油管道问题,3邮局选址问题,4整数因子分解问题,5众数问题。 问题1:集合划分 算法思想:对于n个元素的集合,可以划分为由m个子集构成的集合,例如{{1,2}{3,4}}就是由2个子集构成的非空子集。假设f(n,m)表示将n个元素划分成由m个子集构成的集合的个数。那么1)若m == 1 ,则f(n,m)= 1 ;2)若n == m ,则f(n,m)= 1 ;3)若不是上面两种情况则有下面两种情况构成:3.1)向n-1个元素划分成的m个集合里面添加一个新的元素,则有m*f(n-1,m)种方法;3.2)向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合,则有f(n-1,m-1)种方法。 实验代码: #include 本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼110 专业班级:物联网1601 学号:2016002105 学生姓名:俞梦真 指导教师:郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1.进一步熟悉C/C++语言的集成开发环境; 2.通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治(Divide-and-Conquer)的思想:一个规模为n的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。 需要注意的是,分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。 1.4 实验题目 1.上机题目:格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素,每个元素都是长度为n的串,相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可)。 对于给定的正整数n,格雷码为满足如下条件的一个编码序列。 (1)序列由2n个编码组成,每个编码都是长度为n的二进制位串。 (2)序列中无相同的编码。 (3)序列中位置相邻的两个编码恰有一位不同。 2.设计思想: 根据格雷码的性质,找到他的规律,可发现,1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计: 共享知识分享快乐 编译原理实验报告 实验名称消除文法左递归 实验时间2014年12月12日 院系软件工程 ______________ 班级软件工程(2)班 学号E01214215 __________ 姓名刘翼________________ 实验目的: 输入:任意的上下文无关文法。输出:消除了左递归的等价文法。 实验原理: 1.直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符P 的规则为 P—P a / B 其中,B是不以P开头的符号串。那么,我们可以把P的规则改写为如下的非直接左递归形式:P —B P' P'—a P' / £ 这两条规则和原来的规则是等价的,即两种形式从P推出的符号串是相同的。 设有简单表达式文法G[E] : E —E+T/ T T —T*F/ F F —(E)/ I 经消除直接左递归后得到如下文法: E —TE' E ' —+TE' / £ T —FT' T' —*FT' / £ F —(E)/ I 考虑更一般的情况,假定关于非终结符P的规则为 P—P a 1 / P a 2 / …/ P a n / B 1 / B 2 / …/ B m 其中,a i (I = 1,2,…,n)都不为£,而每个B j (j = 1,2,…,m都不以P开头,将上述规则改写为如下形式即可消除P的直接左递归: P—B 1 P' / B 2 P' / …/ B m P' P' —a 1P' / a 2 P' / …/ a n P' / £ 2.间接左递归的消除 直接左递归见诸于表面,利用以上的方法可以很容易将其消除,即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归,但却隐藏着左递归。例如,设有文法G[S] : S—Qc/ c Q—Rb/ b R—Sa/ a 虽不具有左递归,但S、Q R都是左递归的,因为经过若干次推导有 S Qc Rbc Sabc Q Rb Sab Qcab R Sa Qca Rbca 集美大学计算机工程学院实验报告 课程名称:编译原理 指导教师:付永钢 实验成绩: 实验编号: 实验二 实验名称:递归下降分析程序构造 班级:计算12 姓名: 学号: 上机实践日期:2014.11 上机实践时间: 4学时 一、实验目的 通过设计、编制、调试一个递归下降语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,掌握常用的语法分析方法。通过本实验,应达到以下目标: (1) 掌握从源程序文件中读取有效字符的方法和产生源程序内部表示文件的方法; (2)掌握语法分析的实现方法; (3)上机调试编出的语法分析程序。 二、实验环境 Windows7 x64、VC6.0 三、实验原理 递归下降法是语法分析中最易懂的一种方法。它的主要原理是,对每个非终结符按其产生式结构构造相应语法分析子程序,其中终结符产生匹配命令,而非终结符则产生过程调用命令。因为文法递归相应子程序也递归,所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 递归下降分析程序的实现思想是:识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是:选择正确的右部,扫描完相应的字。在右部中有非终结符号时,调用该非终结符号对应的子程序来完成。 自上向下分析过程中,如果带回溯,则分析过程是穷举所有可能的推导,看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术,可根据输入串的当前符号以及各产生式右部首符,选择某非终结符的产生式,效率高,且不易出错。 无回溯的自上向下分析技术可用的先决条件是:无左递归和无回溯。即:假设A 的全部产生式为A →α1|α2|……|αn ,则必须满足如下条件才能保证可以唯一的选择合适的产生式 First(A →αi )∩First (A →αj )=Φ,当i≠j. 无左递归:既没有直接左递归,也没有间接左递归。 无回溯:对于人以非中介符号U 的产生式右部n x x x |...||21,其对应的字的首终结符号两两不相交。 如果一个文法不含回路(形如P P +?的推导),也不含以ε为右部的产生式,那么可以通过执行消除左递归的算法消除文法的一切左递归。 四、实验内容 完成以下描述算术表达式的LL(1)文法的递归下降分析程序构造 G[E]: E →TE ′ E ′→+TE ′|ε T →FT ′ 宁波工程学院电信学院计算机系 实验报告 课程名称:算法设计与分析实验项目:用分治法算法解 最接近点对问题 指导教师:崔迪 实验位置:软件工程实验室姓名: 班级: 学号: 日期: 2016/10/12 一、实验目的 通过上机实验,要求掌握分治法算法的问题描述、算法设计思想、程序设 计和算法复杂性分析等。 二、实验环境: Eclipse 三、实验内容:用分治法解最接近点对问题 (1)问题描述 给定平面S上n个点,找其中的一对点,使得在n(n-1)/2 个点对中,该 点对的距离最小。 (2)算法设计思想 1. n较小时直接求 (n=2). 2.将S上的n个点分成大致相等的2个子集S1和S2 3.分别求S1和S2中的最接近点对 4.求一点在S1、另一点在S2中的最近点对 5.从上述三对点中找距离最近的一对. (3)程序设计(程序清单及说明) package closestpair; import java.util.Arrays; import https://www.doczj.com/doc/0214693650.html,parator; import java.util.Random; import java.util.Scanner; //定义坐标点 class Point { double x; double y; public Point(double x, double y) { this.x = x; this.y = y; } } // 根据x坐标排序 class MyComparatorX implements Comparator 西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告 题目:分治法循环赛日程表 学号 姓名 专业班级 指导教师 实践日期2011年5月16日-5月20日 目录 一、综合训练目的与要求 (1) 二、综合训练任务描述 (1) 三、算法设计 (1) 四、详细设计及说明 (3) 五、调试与测试 (4) 六、实习日志 (6) 七、实习总结 (6) 八、附录:核心代码清单 (6) 一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一,是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务: (1)巩固和加深学生对算法分析课程基本知识的理解和掌握; (2)培养利用算法知识解决实际问题的能力; (3)掌握利用程序设计语言进行算法程序的开发、调试、测试的能力; (4)掌握书写算法设计说明文档的能力; (5)提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表:(1)每个选手必须与其他n-1个选手各赛一次 (2)每个选手一天只能赛一次 (3)循环赛一共进行n-1天 利用Java语言开发一个界面,输入运动员的个数,输出比赛日程表。对于输入运动员数目不满足n=2k时,弹出信息提示用户。 三、算法设计 (1) 文字描述 假设n位选手顺序编号为1,2,3……n,比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手,根据分治法,要求n个选手的比赛日程,只要知道其中一半的比赛日程,所以使用递归最终可以分到计算两位选手的比赛日程,然后逐级合并,得出结果。 (2) 框图 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 (1)源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } (2)运行界面 ①查找成功 ②查找失败 院系:计算机科学学院 专业、年级: 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。 分治策略 姓名:XXX 专业班级:XXX 学号:XXX 指导教师:XXX 完成日期:XXX 一、试验名称:分治策略 (1)写出源程序,并编译运行 (2)详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序,实现归并排序。 (2)编写一段程序,实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其它n-1个选手各赛一次(2)每个选手一天只能赛一场(3)循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序,实现归并排序。 将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行 排序,最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序,实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有 数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数 据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略,将所有的选手分为两组,n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割, 直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序,实现归并排序。 #include 学生学号0120810680316 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称《编译原理》 开课学院计算机科学与技术学院 指导老师姓名何九周 学生姓名刘洋 学生专业班级软件工程0803 2010 —2011 学年第二学期 实验课程名称:编译原理 实验项目名称单词的词法分析程序设计实验成绩实验者刘洋专业班级软件0803 组别 同组者实验日期 2011 年 5 月 17日 第一部分:实验分析与设计(可加页) 一、实验内容描述(问题域描述) 实验目的: 设计,编制并调试一个词法分析程序,加深对词法分析原理的理解。 实验要求: 在上机前应认真做好各种准备工作,熟悉机器的操作系统和语言的集成环境,独立完成算法编制和程序代码的编写;上机时应随带有关的高级语言教材或参考书;要学会程序调试与纠错;每次实验后要交实验报告。 实验题目: 对于给定的源程序(如C语言或Pascal等),要求从组成源程序的字符行中寻找出单词,并给出它们的种别和属性——输出二元组序列。以便提供给语法分析的时候使用。要求能识别所有的关键字,标志符等,并且能够对出先的一些词法规则的错误进行必要的处理。 二、实验基本原理与设计(包括实验方案设计,实验手段的确定,试验步骤等,用硬件逻辑或 者算法描述) 实验原理: 由于这是一个用高级语言编写一个词法分析器,使之能识别输入串,并把分析结果(单词符号,标识符,关键字等等)输出.输入源程序,输入单词符号,本词法分析器可以辨别关键字,标识符,常数,运算符号和某些界符,运用了文件读入来获取源程序代码,再对该源程序代码进行词法分析,这就是词法分析器的基本功能.当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号.当缓冲区里的字符串被处理完之后,它又调用预处理子程序来处理新串. 编写的时候,使用了文件的输入和输出,以便于词法分析的通用型,同时在文件输出时,并保存在输出文件output文件中。 从左到右扫描程序,通过初始化:1为关键字;2为标志符; 3为常数;4为运算符或界符。 三、主要仪器设备及耗材 计算机 实验一分治与递归算法的应用 一、实验目的 1.掌握分治算法的基本思想(分-治-合)、技巧和效率分析方法。 2.熟练掌握用递归设计分治算法的基本步骤(基准与递归方程)。 3.学会利用分治算法解决实际问题。 二 . 实验内容 金块问题 老板有一袋金块(共n块,n是2的幂(n≥2)),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三.问题分析: 一般思路:假设袋中有n 个金块。可以用函数M a x(程序 1 - 3 1)通过n-1次比较找到最重的金块。找到最重的金块后, 可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。这样,比较的总次数为2n-3。 分治法:当n很小时,比如说,n≤2,识别出最重和最轻的金块,一次比较就足够了。当n 较大时(n>2),第一步,把这袋金块平分成两个小袋A和B。第二步,分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA,以此类推,B中最重和最轻的金块分别为HB 和LB。第三步,通过比较HA 和HB,可以找到所有金块中最重的;通过比较LA 和LB,可以找到所有金块中最轻的。在第二步中,若n>2,则递归地应用分而治之方法 程序设计 据上述步骤,可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数,若n < 1,则程序返回f a l s e,否则返回t r u e。 当n≥1时,程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量,w [ M a x ]为最大的重量。 首先处理n≤1的情况。若n>1且为奇数,第一个重量w [ 0 ]将成为最小值和最大值的候选值,因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时,首先将两个重量值放在for 循环外进行比较,较小和较大的重量值分别置为Min和Max,因此也有偶数个重量值w[2:n-1]参与for循环。 在for 循环中,外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应,而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值, 编译原理实验报告 实验名称:编写语法分析程序 实验类型:设计性实验 指导教师:蒋勇 专业班级:软件工程1401 姓名:**** 学号:********** 实验地点:东六E座301 实验成绩:_________________ 日期:2016年5月17日 实验一 编写词法分析程序 一、实验目的: 1.设计、编写、调试一个递归下降分析程序,实现对词法分析程序提供的 单词序列进行语法检查和结构分析。 2.掌握递归下降语法分析方法。 3.巩固理论知识。 二、实验设计: 1.设计原理: 1)对于文法的每一个非终结符U的文法规则是一个识别U的过程定义, 为每一个非终结符构造子程序。 2)如果U的右部符号串只有一个候选式则从左到右依次构造U的识别 代码。 3)如果U的右部符号串有终结符号,则判断输入的符号是否匹配终结 符号,如果相等,则读入下一个符号;如果不相等,则有语法错误, 应当报错。 4)如果是非终结符号,则调用非终结符号的子程序即可。 5)如果U的右部有多个候选式,应该根据每个候选式的第一个符号来 确定该分支。 6)对于含有ε表达式的文法规则需要判断输入的符号是否在U的 FOLLOW集里面。 2.设计方法: (1)文法改造,消除二义性; (2)对含有左递归或者左公因子的文法消除左递归,提取左公因子; (3)求每一个右部符号串的FIRST集合,如果右部含有ε,则需要求出其 产生式左部非终结符的FOLLOW集。判断文法是否是LL(1)文法, 若不是LL(1)文法,说明文法的复杂性超过自顶向下方法的分析能力。 (4)根据改写后的文法设计程序,依据设计原理构造每一个非终结符的子 程序。 3.设计过程: (1)改写文法、消除左递归(将左递归改为右递归)、提取左公因子; (2)求出相应的First集和Follow集; (3)设计程序流程图,设计程序; (4)编写程序; 4.框架思路,错误信息输出: 对每一个非终结符构造其子程序,设定一个返回值。如果语法分析有错 则返回1,没有错误就返回0;对于错误,在程序的相应行数报错。各 个非终结符之间依据文法规则调用。每次遇到终结符函数都判断是否匹 配当前终结符号,如果不匹配则报错,返回1。如果匹配,则读入下一 实验一分治与递归算法的应用一、实验目的 1.掌握分治算法的基本思想(分-治-合)、技巧和效率分析方法。 2.熟练掌握用递归设计分治算法的基本步骤(基准与递归方程)。 3.学会利用分治算法解决实际问题。 二、算法问题要求 老板有一袋金块(共n块,n是2的幂(n≥2)),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三、算法设计 在n个元素的集合中寻找最大和最小值元素。(1)将集合一分为二,变为两个集合,目的是在较小的两个集合中分别找最大、最小元素。(2)递归分解较小集合,直到每个集合中的元素个数≤2,然后找出小集合的最大、最小元素。(3)合并(回溯):自低向上把子问题的解合并,大元素中取最大者,小元素中取最小者,最后得到元问题的解。 四、验证分析实验结果 图1.1 运行界面 图1.2 运行结果五、程序 #include 算法分析实验报告--分治策略
递归与分治实验报告
算法设计与分析实验报告
消除左递归实验报告
编译原理-实验二-递归下降分析程序构造
分治法实验报告一
(完整word版)分治法循环赛日程表实验报告
算法设计与分析:递归与分治法-实验报告
编译原理实验报告
算法分析实验报告--分治策略
编译原理实验报告
算法实验报告
编译原理语法分析实验报告
实验一分治与递归算法报告