消除文法的左递归

编译原理实验报告

实验名称消除文法的左递归

实验时间

院系计算机科学与技术学院

班级

学号

姓名

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

Q ?Rb ?Sab ?Qcab R ?Sa ?Qca ?Rbca

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

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

如果一个文法不含有回路，即形如P ?+

P 的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。

消除左递归算法： （1） 把文法G 的所有非终结符按任一顺序排列，例如，A 1，A 2，…，A n 。 （2） for （i ＝1；i<=n ；i++）

for （j ＝1；j<=i －1；j++）

{ 把形如A i →A j γ的产生式改写成A i →δ1γ /δ2γ /…/δk γ 其中A j →δ1 /δ2 /…/δk 是关于的A j 全部规则； 消除A i 规则中的直接左递归； }

（3） 化简由（2）所得到的文法，即去掉多余的规则。 利用此算法可以将上述文法进行改写，来消除左递归。

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

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

此时，S 存在直接左递归。在消除了S 的直接左递归后，得到整个文法为： S →abcS ’/ bcS'/ cS' S ’ →abcS'/ ε Q →Sab/ ab/ b R →Sa/ a

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

S →abcS'/ bcS ’/ cS' S' →abcS'/ ε

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

R' →bcaR'/ ε

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

3..实验内容

消除左递归算法：

把文法G 的所有非终结符按任一顺序排列，例如，A 1，A 2，…，A n 。 for （i ＝1；i<=n ；i++）

for （j＝1；j<=i－1；j++）

{ 把形如A

i →A

j

γ的产生式改写成A

i

→δ

1

γ/δ

2

γ/…/δ

k

γ

其中A

j →δ

1

/δ

2

/…/δ

k

是关于的A

j

全部规则；

消除A

i

规则中的直接左递归；

}

化简由（2）所得到的文法，即去掉多余的规则。

利用此算法可以将上述文法进行改写，来消除左递归。

4.实验心得

试验程序框图如下：

5.实验代码与结果

#include

#include

#define N 20

char P[N][N]; //规则集

char Q[N]; //规则集,存放间接左递归消除后的部分规则char R[N][N]; //用来存放规则的初始值

int r; //实际输入的规则的个数

int direct(char P[N][N]); //直接左递归函数

int indirect(char P[N][N]); //间接左递归函数

void directRemove(char P[N][N]); //消除直接左递归函数

void indirectRemove(char P[N][N]); //消除间接左递归函数

int direct(char P[N][N]) //定义直接左递归函数

{

int flag=0;

for(int i=0;i

{

if(P[i][3]==P[i][0]) //右部字符中有与左部相同的符号

{

flag++;

break;

}

}

if(flag>0)

{

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

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("经判断该文法含有间接左递归!\n");

return 2; //属于间接左递归

}

else

return 0; //不属于间接左递归

}

void directRemove(char P[N][N]) //定义消除直接左递归的函数{

int j=4;

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]='\'';

for(int k=0;k<4;k++) //包含空的一条规则

P[r][k]=P[i][k];

P[r][k]='*';

}

else

{

j=3;

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

j++;

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

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

}

}

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

printf("\n");

printf("(*代表ε)\n");

printf("\n");

for(int t=0;t

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

}

void indirectRemove(char P[N][N]) //定义消除间接左递归的函数

{

int flag,flag1=0,copy=r;

int e=0;

Q[e]=P[e][0]; //统计规则中不同的左部

for(int i=1;i

{

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];

}

}

int g=0;

for(int j=0;j

{

int number=0;

for(int z=0;z

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

number++; //统计相同左部的规则个数if(number>1)

copy++; //如果有相同左部则规则总数加一for(i=0;i

{

for(int 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-1-2

m++;

int t=m-3;

int n=4;

while(P[i+k][n]!=0) //统计被替换规则中非终结符的个数为n-4

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))

{

for(int y=0;R[g][y]!=0;y++)

P[copy-1][y]=R[g][y];

int m=3;

while(P[i][m]!=0) //统计替换字符的个数为m-1-2

m++;

int t=m-3;

int n=4;

while(P[copy-1][n]!=0) //统计被替换规则中非终结符的个数为n-4

n++;

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

P[copy-1][s+t-1]=P[copy-1][s];

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

P[copy-1][u]=P[i][u];

break;

}

}

}

flag1=0;

g++;

}

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

for(int t=0;t

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

printf("\n");

for(i=0;i

{

if(P[i][0]==Q[e])

{

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]='\'';

for(int k=0;k<4;k++) //包含空的一条规则

P[copy][k]=P[i][k];

P[copy][k]='*';

}

else

{

j=3;

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

j++;

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

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

}

}

}

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

printf("\n");

printf("(*代表ε)\n");

printf("\n");

for(t=0;t<=copy;t++)

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

}

void main()

{

printf("请输入上下文无关的文法规则P的个数: ");

scanf("%d/n",&r);

printf("\n");

printf("请输入各条规则，规则的左部跟右部用->连接，规则间用空格隔开");

printf("\n");

for(int k=0;k

scanf("%s",P[k]);

printf("\n");

printf("即输入的文法规则为:\n");

for(k=0;k

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

if(direct(P)==1)

directRemove(P);

else if(indirect(P)==2)

indirectRemove(P);

else

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

消除文法直接左递归实例如下：

消除文法简介左递归实例如下：

消除文法的左递归实验

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

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

递归与分治实验报告

递归与分治实验报告 班级：计科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坐标排序，然后取其中位数再计算各个油

消除左递归实验报告

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

编译原理第五章答案

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

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

《编译原理》期末试题（一） 一、是非题（请在括号内，正确的划√，错误的划×）（每个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) {

编译原理实验报告

院系：计算机科学学院 专业、年级： 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

编译原理实验报告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）运行界面 ①查找成功 ②查找失败

编译原理实验报告

学生学号0120810680316 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称《编译原理》 开课学院计算机科学与技术学院 指导老师姓名何九周 学生姓名刘洋 学生专业班级软件工程0803 2010 —2011 学年第二学期

实验课程名称：编译原理 实验项目名称单词的词法分析程序设计实验成绩实验者刘洋专业班级软件0803 组别 同组者实验日期 2011 年 5 月 17日 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 实验目的： 设计，编制并调试一个词法分析程序，加深对词法分析原理的理解。 实验要求： 在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写；上机时应随带有关的高级语言教材或参考书；要学会程序调试与纠错；每次实验后要交实验报告。 实验题目： 对于给定的源程序（如C语言或Pascal等），要求从组成源程序的字符行中寻找出单词，并给出它们的种别和属性——输出二元组序列。以便提供给语法分析的时候使用。要求能识别所有的关键字，标志符等，并且能够对出先的一些词法规则的错误进行必要的处理。 二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或 者算法描述） 实验原理： 由于这是一个用高级语言编写一个词法分析器,使之能识别输入串,并把分析结果(单词符号,标识符,关键字等等)输出.输入源程序,输入单词符号,本词法分析器可以辨别关键字,标识符,常数,运算符号和某些界符,运用了文件读入来获取源程序代码,再对该源程序代码进行词法分析,这就是词法分析器的基本功能.当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号.当缓冲区里的字符串被处理完之后,它又调用预处理子程序来处理新串. 编写的时候，使用了文件的输入和输出，以便于词法分析的通用型，同时在文件输出时，并保存在输出文件output文件中。 从左到右扫描程序，通过初始化：1为关键字；2为标志符； 3为常数；4为运算符或界符。 三、主要仪器设备及耗材 计算机

实验二语法设计(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负责找出较小重量值和较大重量值中的最小值和最大值，

编译原理语法分析实验报告

编译原理实验报告 实验名称：编写语法分析程序 实验类型：设计性实验 指导教师：蒋勇 专业班级：软件工程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。如果匹配，则读入下一

编译原理复习题2

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在基本块出口之后活跃，写出优化后的四元式序列。