消除左递归实验报告

共享知识分享快乐

编译原理实验报告

实验名称消除文法左递归

实验时间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

就显现出其左递归性了，这就是间接左递归文法

消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。

如果一个文法不含有回路，即形如P P的推导，也不含有以&为右部的

产生式，那么就可以采用下述算法消除文法的所有左递归。

消除左递归算法：

(1)把文法G的所有非终结符按任一顺序排列，例如，A i, A,…，A。

(2)for (i = 1 ；i<=n ；i++ )

for (j = 1; j<=i —1; j++ )

{ 把形如A f A丫的产生式改写成A i 1丫/ S' 2丫/…/ S' k

Y

其中A fS 1 / S 2 /…/ S k是关于的A全部规则；消除A i 规则

中的直接左递归;

}

(3)化简由( 2)所得到的文法，即去掉多余的规则。利用此算法可以将

上述文法进行改写，来消除左递归。

首先，令非终结符的排序为R、Q S。对于R,不存在直接左递归。把R代入到Q中的相关规则中，贝U Q的规则变为Sab/ ab/ b。

代换后的Q不含有直接左递归，将其代入S,S的规则变为S f Sabc/ abc/ be/ c。

此时，S存在直接左递归。在消除了S的直接左递归后，得到整个文法为：S f abcS'/ bcS'/ cS'

S' f abeS'/ &

Q f Sab/ ab/ b

R f Sa/ a

可以看到从文法开始符号S出发，永远无法达到Q和R,所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法G[S]为：

S f abeS'/ beS ' / eS'

S' f abeS'/ ￡当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q R,那么最后得到的文法G[R]为：R f beaR'/ eaR'/ aR '

R' f beaR'/ ￡

容易证明上述两个文法是等价的。

实验内容：

指明是否存在左递归，以及左递归的类型。对于直接左递归，可将其改为直接右递归;对于间接左递归(也称文法左递归)，则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。(应该有n!种) 实验代码与结果：

#include

#include #include #define N 20 char P[N][N]; // 存放文法 char Q[N]; // 存放非终结符

char R[N][N]; // 存放含有间接左递归的产生式

char str[N][N], str1[N][N];

int sp[N]; // 标记无用的产生式

int r , count=0,count1=0;

int direct(char P[N][N]); int indirect(char P[N][N]);

void directRemove(char P[N][N]); void indirectRemove(char P[N][N]); void perm(char str[N][N], int i, int n); int main()

{

printf(" 请输入文法 P 产生式的个数 : "); scanf("%d/n",&r);

printf(" 请输入各条产生式，产生式的左部跟右部用 -> 连接 :\n"); for(int k=0;k

{

scanf("%s",P[k]); if(strlen(P[k])==4) strcpy(str1[count1++],P[k]);

else strcpy(str[count++],P[k]);

}

if(direct(P)==1) directRemove(P);

else if(indirect(P)==2) perm(str , 0, count-1);

else

printf(" 经判断该文法不含有左递归 !\n");

return 0;

}

int direct(char P[N][N])

{

int flag=0;

// 判断直接左递归

// 判断间接左递归 // 消除直接左递归

// 消除间接左递归

// 实现全排列

{

{ if(P[i][3]==P[i][0])

{

flag++;

break;

}

}

if(flag>0)

{

printf(" 经判断该文法含有直接左递归 return 1; }

else

return 0;

}

int indirect(char P[N][N])

{ int flag=0;

for(int i=0;i

{

for(int k=1;k

{

if(P[i+k][0]==P[i][3])

{

flag++;

break;

}

}

if(flag>0)

break;

}

if(flag>0)

{

printf(" 经判断该文法含有间接左递归

return 2;

}

else

return 0;

}

void directRemove(char P[N][N])

int k,j=4;

memset(sp,0,sizeof(sp));

for(int i=0;i

{

if(P[i][3]==P[i][0])

{

P[i][3]=P[i][2]; P[i][2]=P[i][1];

P[i][1]='\'';

while(P[i][j]!=0)

j++;

P[i][j]=P[i][0];

P[i][j+1]='\'';

sp[i]=1; for(k=0;k<4;k++) P[r][k]=P[i][k];

!\n");

!\n");

sp[r]=1;

}

else

{

j=3;

while(P[i][j]!=0)

j++;

P[i][j]=P[i][0];

P[i][j+1]='\'';

sp[i]=1;

}

}

printf("\n 消除直接左递归后的文法为:\n");

for(int t=0;t

{

if(sp[t]==1)

printf("%s\n",P[t]);

}

}

void indirectRemove(char P[N][N])

{

int flag,flag1=0,r1=r;

int i,j,k,t,e=0,g=0;

Q[e]=P[e][0];

for(i=1;i

int flag=0;

for(int k=0;k<=e;k++)

if(P[i][0]!=Q[k])

flag++;

if(flag==(e+1))

{

e++;

Q[e]=P[i][0];

}

}

printf("\n 非终结符序列为：%s\n", Q);

for(j=0;j

{

int number=0;

for(int z=0;z

if(P[z][0]==Q[j])

number++;

if(number>1)

r1++;

for(i=0;i

{

for(k=1;k

{

if((P[i][0]==P[i+k][3])&&(flag1==0))

{

for(int y=0;P[i+k][y]!=0;y++) {

共享知识分享快乐

{

R[g][y]=P[i+k][y]; flag1=1; int m=3; while(P[i][m]!=0) m++;

int t=m-3;

int n=4;

while(P[i+k][n]!=0)

n++;

for(int s=n-1;s>=4;s--)

P[i+k][s+t-1]=P[i+k][s];

for(int u=3;u<3+t;u++)

P[i+k][u]=P[i][u];

break;

}

else if((P[i][0]==R[g][3])&&(flag1==1))

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

消除文法的左递归实验

编译原理实验报告 实验名称 _____________ 消除文法的左递归__________________________ 实验时间 _____________________________________________ 院系 _________________________________________ 班级 ______________________________________________ 学号 ____________________________________________ 姓名

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'/￡

c实现消除文法左递归

编译原理实验报告 实验名称消除文法的左递归 实验时间 2010.11.1 院系计算机科学与技术 班级 2008 学号 JB084193 姓名潘亚飞

1.试验目的 输入：任意的上下文无关文法。 输出：消除了左递归的等价文法。 2.实验原理 1．直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符P 的规则为 P →P α / β 其中，β是不以P 开头的符号串。那么，我们可以把P 的规则改写为如下的非直接左递归形式： P →βP ’ P ’→α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 α1 / P α2 /…/ P αn / β1 / β2 /…/βm 其中，αi （I ＝1，2，…，n ）都不为ε，而每个βj （j ＝1，2，…，m ）都不以P 开头，将上述规则改写为如下形式即可消除P 的直接左递归： P →β1 P ’ / β2 P ’ /…/βm P ’ P ’ →α1P ’ / α2 P ’ /…/ αn P ’ /ε 2．间接左递归的消除 直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法G[S]： S →Qc/ c Q →Rb/ b R →Sa/ a 虽不具有左递归，但S 、Q 、R 都是左递归的，因为经过若干次推导有 S ?Qc ?Rbc ?Sabc

实验报告 分治与递归

实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 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 #include #include using namespace std; int q(intn,int m); int main(){ int n; cout<<"请输入要划分的整数："<>n; int p=q(n,n); cout<<"正整数"<

return 0; } int q(intn,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

消除左递归实验报告

共享知识分享快乐 编译原理实验报告 实验名称消除文法左递归 实验时间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

算法设计与分析实验报告

本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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．代码设计：

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表

nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

编译原理第五章答案

第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

数据结构实验报告模板

2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

编译原理习题及答案(整理后)

第一章 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)

[高命中]编译原理期末试题及答案

《编译原理》期末试题（一） 一、是非题（请在括号内，正确的划√，错误的划×）（每个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．( )最左推导和最右推导对应的语法树必定相同

算法分析实验报告--分治策略

《算法设计与分析》实验报告 分治策略 姓名：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 #include #define MAX 10 using namespace std; void merge(int array[],int p,int q,int r) { int i,k; int begin1,end1,begin2,end2; int* temp = new int[r-p+1]; begin1 = p; end1 = q; begin2 = q+1; end2 = r; k = 0; while((begin1 <= end1)&&(begin2 <= end2)) { if(array[begin1] < array[begin2]) { temp[k] = array[begin1]; begin1++; } else { temp[k] = array[begin2]; begin2++; } k++; } while(begin1 <= end1) {

消除左递归

一个文法含有下列形式的产生式之一时： 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

编译原理实验报告3-LL(1)文法构造

实验3 LL（1）文法构造 一、实验目的 熟悉LL（1）文法的分析条件，了解LL（1）文法的构造方法。 二、实验内容 1、编制一个能够将一个非LL（1）文法转换为LL（1）文法； 2、消除左递归； 3、消除回溯。 三、实验要求 1、将一个可转换非LL（1）文法转换为LL（1）文法，要经过两个阶段，1）消除文 法左递归，2）提取左因子，消除回溯。 2、提取文法左因子算法： 1）对文法G的所有非终结符进行排序 2）按上述顺序对每一个非终结符Pi依次执行: for( j=1； j< i-1；j++) 将Pj代入Pi的产生式（若可代入的话）； 消除关于Pi的直接左递归： Pi -> Piα|β，其中β不以Pi开头，则修改产生式为： Pi —＞βPi′ Pi′—＞αPi′|ε 3）化简上述所得文法。 3、提取左因子的算法： A —＞δβ1|δβ2|…|δβn|γ1|γ2|…|γm (其中,每个γ不以δ开头) 那么,可以把这些产生式改写成 A —＞δA′|γ1| γ2…|γm A′—＞β1|β2|…|βn 4、利用上述算法，实现构造一个LL（1）文法： 1）从文本文件g.txt中读入文法，利用实验1的结果，存入实验1设计的数据结

构； 2） 设计函数remove_left_recursion （）和remove_left_gene （）实现消除左递归和 提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子； 3） 整理得到的新文法； 4） 在一个新的文本文件newg.txt 输出文法，文法输出按照一个非终结符号一行， 开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。 四、实验环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、学习LL （1）文法的分析条件； 2、学习构造LL （1）文法的算法； 3、结合实验1给出的数据结构，编程实现构造LL （1）文法的算法； 4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL （1）文法形式； 5、 把实验结果写入一个新建立的文本文件。 六、测试数据 输入数据： 编辑一个文本文文件g.txt ，在文件中输入如下内容： 正确结果： 本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或 选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果： 1、 P->P 之类的），也不含以ε为右部的产生式。 一个文法要能进行LL （1）分析，那么这个文法应该满足：无二义性，无左递归，

算法设计与分析：递归与分治法-实验报告

应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表

实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include #include using namespace std; int bin_search(int key[],int low, int high,int k) { int mid; if(low>high) return -1; else{ mid = (low+high) / 2; if(key[mid]==k) return mid; if(k>key[mid]) return bin_search(key,mid+1,high,k); else return bin_search(key,low,mid-1,k); } } int main() { int n , i , addr; int A[10] = {2,3,5,7,8,10,12,15,19,21}; cout << "在下面的10个整数中进行查找" << endl; for(i=0;i<10;i++){ cout << A[i] << " " ; } cout << endl << endl << "请输入一个要查找的整数" << endl; cin >> n; addr = bin_search(A,0,9,n);

if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败

数据结构实验报告及心得体会

2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨

实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。

三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

实验二语法设计(LL1文法)

实验二 LL（1）分析法 一、实验目的： 根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。 二、实验预习提示 1、LL（1）分析法的功能 LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。 2、LL（1）分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 3、LL（1）分析法实验设计思想及算法 三、实验过程和指导： （一）准备： 1.阅读课本有关章节，

2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序要求： 程序输入/输出示例： 对下列文法（要求每位同学文法不同），用LL（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 输出的格式如下： (1)LL（1 (2)输入一以#结束的符号串(包括+—*/（）i#) (3)输出过程如下： 步骤分析栈剩余输入串所用产生式 1 E i+i*i# E->TG

(或者为合法符号串) 备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。 (3)上述描述的输出过程只是其中一部分的。 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照； （四）程序思路（仅供参考）： 模块结构： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 （五）练习该实验的目的和思路：

算法实验报告

实验一分治与递归算法的应用 一、实验目的 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负责找出较小重量值和较大重量值中的最小值和最大值，