递归与分治实验报告
班级：计科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
#include
using namespace std ;
int jihehuafen( int n , int m )
{
if( m == 1 || n == m )
return 1 ;
else
return jihehuafen( n - 1 , m - 1 ) + m*jihehuafen( n - 1 , m ) ;
}
int main()
{
ifstream fin("C:/input.txt") ;
ofstream fout("C:/output.txt") ;
int N , M , num ;
fin >> N >> M ;
num = jihehuafen( N , M) ;
fout << num << endl ;
return 0 ;
}
问题2：输油管道
算法思想：由于主管道由东向西铺设。故主管道的铺设位置只和各油井的y坐标有关。要使主管道的y坐标最小，主管道的位置y坐标应是各个油井y坐标的中位数。先用快速排序法把各个油井的y坐标排序，然后取其中位数再计算各个油
井y坐标与中位数差值的绝对值之和。
实验代码：
#include
#include
#include
using namespace std ;
struct point//定义坐标结构体
{
int x ;
int y ;
};
//快速排序
void sort( point a[] , int size )
{
int i = 0 , j = size - 1 ;
int temp ;//用来保存作为基准的数
if( size >= 1 )
{
temp = a[0].y ;//用区间的第一个元素作为基准
while( i != j )//区间两端交替向中间扫描，知道i = j
{
while( i < j && a[j].y > temp )
j-- ; //从右向左扫描，找到第一个小于temp的a[j] if( i < j )//表示找到a[j] ，把a[j] 赋给a[i]
{
a[i].y = a[j].y ;
i++ ;
}
while( i < j && a[i].y < temp )
i++ ;//从左向右扫描，找到第一个大于temp 的a[i] if( i < j )//表示找到a[i]，把a[i]赋给a[j]
{
a[j].y = a[i].y ;
j-- ;
}
}
a[i].y = temp ;
sort( a , i ) ;//对左递归
sort( a + i + 1 , size - i - 1 ) ;//对右递归
}
}
//取中位数
int madian( point *a , int size )
{
int num = size + 1 ;
return a[num/2 - 1].y ;
//return size%2 ? a[size>>1].y :( a[size>>1].y + a[ (size>>1) +1 ].y)>>1 ; }
//计算最短路程
int lucheng( point *a , int size )
{
int mid = madian( a , size ) ;
int i , sum = 0 ;
for( i = 0 ; i < size ; i ++ )
{
sum +=abs( a[i].y - mid ) ;
}
return sum ;
}
int main()
{
ifstream fin( "C:/input.txt") ;
ofstream fout( "C:/output.txt") ;
int n ;
fin >> n ;
point *p = new point[n] ;
for( int i = 0 ; i < n ; i ++)
fin >> p[i].x >> p[i].y ;
sort( p , n ) ;
int minlen = lucheng( p , n) ;
fout << minlen << endl ;
return 0 ;
}
问题3：邮局选址问题
算法思想：同问题2
实验代码：
#include
#include
#include
using namespace std ;
struct point
{
int x ;
int y ;
} ;
void sort_x( point *a , int size )
{
int temp ;
int i = 0 , j = size - 1 ;
if( size >= 1 )
{
temp = a[0].x ;//
while( i != j )
{
while( i < j && a[j].x > temp )
j-- ;
if( i < j )
{
a[i].x = a[j].x ;
i++ ;
}
while( i < j && a[i].x < temp )
i++ ;
if( i < j )
{
a[j].x = a[i].x ;
j-- ;
}
}
a[i].x = temp;
sort_x( a , i ) ;//
sort_x( a + i +1 , size - i - 1 ) ;// }
}
void sort_y( point *a , int size )
{
int temp ;
int i = 0 , j = size - 1 ;
if( size >= 1 )
{
temp = a[0].y ;//
while( i < j )
{
while( i < j && a[j].y > temp )
j-- ;
if( i < j )
{
a[i].y = a[j].y ;
i++ ;
}
while( i < j && a[i].y < temp )
i++ ;
if( i < j )
{
a[j].y = a[i].y ;
j-- ;
}
}
a[i].y = temp;
sort_y( a , i ) ;//
sort_y( a + i +1 , size - i - 1 ) ;//
}
}
int madian_x( point *a , int size )
{
//int num = size + 1 ;
//return a[num/2 - 1].x ;
return size%2 ? a[size>>1].x :( a[size>>1].x + a[ (size>>1) +1 ].x)>>1 ; }
int madian_y( point *a , int size )
{
int num = size + 1 ;
return a[num/2 - 1].y ;
//return size%2 ? a[size>>1].y :( a[size>>1].y + a[ (size>>1) +1 ].y)>>1 ; }
int lucheng( point *a , int size )
{
int mid_x = madian_x( a , size ) ;
int mid_y = madian_y( a , size ) ;
int i , sum = 0 ;
for( i = 0 ; i < size ; i ++ )
{
sum += abs( a[i].y - mid_y ) + abs(a[i].x - mid_x ) ;
}
return sum ;
}
int main()
{
ifstream fin("C:/input.txt") ;
ofstream fout("C:/output.txt") ;
if( !fin )
{
cout<<"the file can't open!"< return - 1 ; } int n ; fin >> n ; point *p = new point[n] ; for( int i = 0 ; i < n ; i++ ) { fin >> p[i].x >> p[i].y ; } sort_x( p , n ) ; sort_y( p , n ) ; int minlen = lucheng( p , n ) ; fout << minlen << endl ; delete []p ; return 0 ; } 问题4：整数因子分解问题 算法思想：采用递归的算法思想 实验代码： #include #include using namespace std ; int count = 0 ; void yinzifenjie( int x ) if( x == 1 ) { count++; } else { for( int i = 2 ; i <= x ; i++ ) { if( x % i == 0 ) { yinzifenjie(x/i); } } } } int main() { ifstream fin("C:/input.txt") ; ofstream fout("C:/output.txt") ; if( !fin ) { cout<<"the file can't open!"< return - 1 ; } int x ; fin >> x ; yinzifenjie(x) ; fout << count << endl ; return 0 ; } 问题5：众数问题 算法思想：首先利用快速排序将其数组排序，利用写的求中位数函数及其返回中位数起始点函数编写求众数。求众数函数思想是：找到中位数及其起始结束点，将众数初始化为中位数。判断起点左边的元素数是否大于中位数的重数，如果大于则向左递归找众数，再判断终点右边的元素数是否大于中位数的重数，如果大于则向右递归找众数。 实验代码： #include #include using namespace std ; //结构体用来保存众数的元素与重数 typedef struct { int element; //元素 int sum; //重数 }zhongshu; //记录中位数的起始下标 typedef struct { int low; int high; }node; //快排 zhongshu x ; void sort( int a[] , int s , int t )//对a[s]到a[t]的元素排序 { int i = s , j = t ; int temp ; if( s < t ) //区间里至少存在一个元素的情况 { temp = a[s] ; //用区间的第一个元素做基准 while( i != j ) //区间两端交替向中间扫描，直到I=J { while( j > i && a[j] > temp ) j-- ; //从右向左扫描，找到第一个小于temp的a[j] if( i < j ) //表示找到a[j],则a[i],a[j]交换 { a[i] = a[j] ; i++ ; } while( i < j && a[i] < temp ) i++ ; //从左向右扫描，找到第一个大于temp的a[i] if( i < j ) //表示找到a[i],则a[i],a[j]交换 { a[j] = a[i] ; j-- ; } } a[i] = temp ; sort( a , s , i - 1 ) ; //对左递归 sort( a , i + 1 , t ) ; //对右递归} } //中位数 int madian( int *a , int L , int R ) { int num = L + R + 1 ; return a[num/2] ; } //返回中位数的起始点终点 node spalit(int *a , int med , int L , int R ) { node m ; m.low = L ; m.high = R ; for( int i = 0 ; i <= R ; i++ ) { if( med == a[i] ) { m.low = i ; break ; } } for( int j = R ; j >= 0 ; j-- ) { if( med == a[j] ) { m.high = j ; break ; } } return m ; } //众数的重数求取 void mode( int *a , int L , int R ) { if( L >= R ) return;//x.sum=0; else { node n; int temp = 0 ; int med ; med = madian( a , L , R ) ; n = spalit( a , med , L , R ); temp = n.high - n.low + 1 ; if( x.sum < temp ) { x.element = med ; x.sum = temp ; } if( n.low - L > temp )// { if( x.sum < temp ) { x.element = med ; x.sum = temp ; } mode(a , L , n.low - 1 ) ; } if( R - n.high > temp ) { if( x.sum < temp ) { x.element = med ; x.sum=temp; } mode( a , n.high + 1 , R ) ; } } } int main() { x.sum = 0 ; int n ; int *a ; ifstream fin("C:/input.txt"); ofstream fout("C:/output.tex"); if( !fin ) { cout<<"the file can't open!"< return - 1 ; } fin >> n ; a = new int[n]; for( int i = 0 ; i < n ; i++) { fin >> a[i] ; } sort(a,0,n-1); mode(a,0,n-1); fout << x.element << endl << x.sum; delete []a; return 0 ; } 实验心得：要用好一种算法，首先要理解它的思想，就这次实验而言，要理解分治的算法思想，分治要用递归来实现。清楚算法思想后问题就迎刃而解了。还有就是多练习用分治来解决一些实际问题对于更好地掌握分治是有很大帮助的。要掌握它，我还要多练习写这方面的程序。 编译原理实验报告 实验名称 _____________ 消除文法的左递归__________________________ 实验时间 _____________________________________________ 院系 _________________________________________ 班级 ______________________________________________ 学号 ____________________________________________ 姓名 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'/￡ 《算法设计与分析》实验报告 分治策略 姓名：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 共享知识分享快乐 编译原理实验报告 实验名称消除文法左递归 实验时间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 实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 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 第5章自顶向下语法分析方法 第1题 对文法G[S] S→a||(T)∧ T→T,S|S (1) 给出(a,(a,a))和(((a,a),,(a)),a)∧的最左推导。 (2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。 (4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 答案： 也可由预测分析表中无多重入口判定文法是LL(1)的。 可见输入串（a,a）#是文法的句子。 第3题 已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM 判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 第7题 对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。 (１)A→baB|ε B→Abb|a (2) A→aABe|a B→Bb|d (3) S→Aa|b A→SB B→ab 答案： (１)先改写文法为： 0) A→baB 1) A→ε 2) B→baBbb 3) B→bb 4) B→a 再改写文法为： 0) A→baB 1) A→ε 2) B→bN 3) B→a 4) N→aBbb 5) N→b （2）文法：A→aABe|a B→Bb|d 提取左公共因子和消除左递归后文法变为： 0) A→a N 1) N→A B e 2) N→ε 3) B→d N1 4) N1→b N1 5) N1→ε （3）文法：S→Aa|b A→SB B→ab 第1种改写： 用A的产生式右部代替S的产生式右部的A得：S→SBa|b B→ab 消除左递归后文法变为： 0) S→b N 1) N→B a N 2) N→ε 3) B→a b 集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算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 ′ 第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。 一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a) 宁波工程学院电信学院计算机系 实验报告 课程名称：算法设计与分析实验项目：用分治法算法解 最接近点对问题 指导教师：崔迪 实验位置：软件工程实验室姓名： 班级： 学号： 日期： 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/1011493452.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 《编译原理》期末试题（一） 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．编译程序是对高级语言程序的解释执行。(× ) 2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 4．语法分析时必须先消除文法中的左递归。(×) 5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 6．逆波兰表示法表示表达式时无须使用括号。(√ ) 7．静态数组的存储空间可以在编译时确定。(×) 8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。(× ) 10．一个语义子程序描述了一个文法所对应的翻译工作。(×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值D．( ) 单词自身值 2．正规式M 1 和M 2 等价是指_____。 A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。 A．( )最左推导和最右推导对应的语法树必定相同 西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告 题目：分治法循环赛日程表 学号 姓名 专业班级 指导教师 实践日期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。 一个文法含有下列形式的产生式之一时： 1)A→Aβ，A∈VN，β∈V* 2)A→Bβ，B→Aα，A、B∈VN，α、β∈V* 则称该文法是左递归的。 然而，一个文法是左递归时，不能采取自顶向下分析法。 消除左递归方法有： a)把直接左递归改写为右递归： 设有文法产生式：A→Aβ|γ。其中β非空，γ不以A打头。 可写为：A→γA' A'→βA'|ε 一般情况下，假定关于A的产生式是： A→Aα1| Aα2 |…|Aαm|β1|β2 |…|βn 其中，αi(1≤i≤m)均不为空，βj(1≤j≤n)均不以A打头。 则消除直接左递归后改写为： A→ β1A'| β2 A' |…| βn A' A'→ α1A' | α2A' |…| αm A' |ε 例4.12：有文法G(E)： E→E +T |T T→T*F | F F→i| (E) 消除该文法的直接左递归。 解：按转换规则,可得: E→TE' E'→+TE'|ε T→FT ' T'→*FT'|ε F→i| (E) b)消除间接左递归： 对于间接左递归的消除需要先将间接左递归变为直接左递归，然后再按a)清除左递归。例4.13：以文法G6为例消除左递归： (1)A→aB (2)A→Bb (3)B→Ac (4)B→d 解：用产生式(1)，(2)的右部代替产生式(3)中的非终结A得到左部为B的产生式： (1)B→aBc (2)B→Bbc (3)B→d 消除左递归后得到： B→aBcB' |dB' B'→bcB' |ε 再把原来其余的产生式A→aB,A→Bb加入，最终得到等价文法为: (1) A→aB (2) A→Bb (3) B→(aBc|d)B' (4) B'→bcB'|ε c)消除文法中一切左递归的算法 设非终结符按某种规则排序为A1，A2，…，A n。 For i﹕=1 to n do begin For j﹕=1 to i-1 do begin 若A j的所有产生式为： A j→δ1| δ2| … | δn 替换形如A i→A jγ的产生式为： A i→δ1γ|δ2γ | … |δnγ end 消除A i中的一切直接左递归 end 分治策略 姓名：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为运算符或界符。 三、主要仪器设备及耗材 计算机 编译原理实验报告 实验名称：编写语法分析程序 实验类型：设计性实验 指导教师：蒋勇 专业班级：软件工程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、（10分）下面的文法G[S]是否是LL（1）文法，说明理由，构造LL（1） 分析表 S→aBc|bAB A→aAb|Bb B→cB| 2、（5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文 法。 S→SaB|bB A→S|a B→Ac 3、（5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法 S→A[] A→[ A→aA A→B] B→a 4、（10分）将表达式A+B*(C-D)-E/F↑G分别表示为三元式、四元式、逆 波兰式序列 5、（10分）现有文法如下： S→aS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。 1、已知文法G A::=aABe|a B::=Bb|d （1）给出与上述文法等价的LL（1）文法G’。 （2）构造预测分析表并给出输入串aade#分析过程。（10分） 2、设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=P↑F F::=P P::=(E) P::=i 构造此文法的算符优先矩阵。（10分） 3、有正规式b*abb*(abb*)* （1）构造该正规式所对应的NFA（画出状态转换图）。 （2）将所求的NFA确定化。（画出确定化的状态转换图）。 （3）将所求的NFA最小化。（画出最小化后的状态转换图）。（10分） 4、若有文法G（S）的产生式如下：S::=L=R S::=R L::=*R L::=i R::=L,构造 识别所有项目集规范族的DFA。（15分） （1）判断该文法是否是LR（0）文法，说明理由。 （2）判断该文法是否是SLR（1）文法，说明理由。 （3）判断该文法是否是LR（1）文法，说明理由。 （4）判断该文法是否是LALR（1）文法，说明理由 1、（10分）将表达式（（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列 2、（10分）对基本块P画出DAG图 B:=3 D:=A+C E::=A*C F:=E+D G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L 假定只有L在基本块出口之后活跃，写出优化后的四元式序列。 实验一分治与递归算法的应用一、实验目的 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。 二、算法问题要求 老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三、算法设计 在n个元素的集合中寻找最大和最小值元素。(1)将集合一分为二，变为两个集合，目的是在较小的两个集合中分别找最大、最小元素。(2)递归分解较小集合，直到每个集合中的元素个数≤2，然后找出小集合的最大、最小元素。（3）合并（回溯）：自低向上把子问题的解合并，大元素中取最大者，小元素中取最小者，最后得到元问题的解。 四、验证分析实验结果 图1.1 运行界面 图1.2 运行结果五、程序 #include fmax=a[i]; fmin=a[i]; } else if (i==(j-1)){ if (a[i] 编译原理 2014—2015学年第二学期第四单元测试试卷（闭卷考试）时间：45分钟满分：100分 姓名班级出题人刘兵班级 2 一、选择题（5*2分）（每题1分，共10分） 1．编译过程中语法分析器的任务就是__________。 (1) 分析单词是怎样构成的（2）分析单词串是如何构成语句和说明的 （3）分析语句和说明是如何构成程序的（4)分析程序的结构 A （2）（3） B（2）（3）（4） C （1）（2）（3） D（1）（2）（3）（4） 2．给定文法G[S]及其非终结符A，FIRST(A)定义为：从A 出发能推导出的终结符号的集合（S 是文法的起始符号，为非终结符）。对于文法G[S]： S→[L] | a L→L, S| S 其中，G[S]包含的四个终结符号分别为：a , [ ] 则FIRST(S)的成员包括。 A. a B. a、[ C. a、[和] D. a、[、]和， 3．若一个文法是递归的，则它产生的句子个数是( ) A．无穷个 B．不确定 C．有限个 D.根据具体情况而定 4．语法分析器则可以发现源程序中的__D___。 A．语义错误 B．语法和语义错误 C．错误并校正 D．语法错误 5．若文法 G 定义的语言是无限集，则文法必然是( ) 。 A．递归的 B．前后文无关的 C．二义性的 D．无二义性的 二、简答题（2*10分）（每题10分，共20分） 1．自上而下分析的前提？ 2.若有文法A→(A)A|ε，说明该文法是LL(1)的文法。 三、分析题（4题共70分） 1．设有文法G[E]: E→Aa|Bb A→cA|eB B→bd 试按照递归子程序法为该文法构造语法分析程序。 2．设有文法G[S]： S→AB A→bB|Aa B→Sb|a 试消除该文法的左递归。消除文法的左递归实验
算法分析实验报告--分治策略
递归与分治实验报告
消除左递归实验报告
实验报告 分治与递归
编译原理第五章答案
编译原理-实验二-递归下降分析程序构造
编译原理习题及答案(整理后)
分治法实验报告一
[高命中]编译原理期末试题及答案
(完整word版)分治法循环赛日程表实验报告
算法设计与分析：递归与分治法-实验报告
编译原理实验报告
消除左递归
算法分析实验报告--分治策略
编译原理实验报告
编译原理语法分析实验报告
编译原理复习题2
实验一分治与递归算法报告
《编译原理》第四章试题
相关主题
文本预览