递归算法的优缺点

递归算法的优缺点：

○

1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

边界条件与递归方程是递归函数的二个要素

应用分治法的两个前提是问题的可分性和解的可归并性

以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。

回溯法以深度优先的方式搜索解空间树T ，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T 。

舍伍德算法设计的基本思想:

设A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x)。设Xn 是算法A 的输入规模为n 的实例的全体，则当问题的输入规模为n 时，算法A 所需的平均时间为

这显然不能排除存在x ∈Xn 使得 的可能性。希望获得一个随机化算法B ，使得对问题的输入规模为n 的每一个实例均有

拉斯维加斯( Las Vegas )算法的基本思想:

设p(x)是对输入x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x 均有p(x)>0。

设t(x)是算法obstinate 找到具体实例x 的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x 求解成功或求解失败所需的平均时间，则有： 解此方程可得：

蒙特卡罗(Monte Carlo)算法的基本思想:

设p 是一个实数，且1/2

线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。 单纯形算法的特点是：

（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加； （2）一般经过不大于m 或n 次迭代就可求得最优解。

单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问

∑∈=n X x n A A X x t n t |

|/)()()(

)(n t x t A A >>)()()(n s n t x t A B +=))()())((1()()()(x t x e x p x s x p x t +-+=)

()()

(1)()(x e x p x p x s x t -+=

题完全等价的标准线性规划问题。

图灵机由以下几部分组成：一条无限长的带（有无穷个格子）、一个读写头、一个有限状态控制器以及一个程序。

NPC形式化定义：

定义1：语言L是NP完全的当且仅当（1）L【NP；（2）对于所有L’【NP有L’ ～pL。

如果有一个语言L满足上述性质(2),但不一定满足性质（1），则称该语言是NP难的。

所有NP完全语言构成的语言类称为NP完全语言类，就是NPC。

定理1 设L是NP完全的，则（1）当且仅当P＝NP；（2）若，且，则L1是NP完全的。

团问题:

任给图G和整数k．试判定图G中是否存在具有k个顶点的团？

1)团问题。显然，验证G的一个子图是否成团只需多项式时间即可。

团问题。

任给表达式f．构造一个相应的图G如下：

①图G的每个顶点对应于f中的每个文字(多次出现的重复计算)。

②若G中两个顶点其原对应的文字不相互补且不出现于同一于句中，则将其连线。

设f有n个子句，则f可满足当且仅当f对应的图G中有n个顶点的团。

这是因为：

(a)若f可满足，即有某种赋值使得f取值为真，它等价于使得每个ci中都至少有一个文字为真，这n个文字(每个ci(1＜i

(b)若图G中有一n个顶点的团，则取给出使得这n个顶点对应的文字都为真的赋值，则f 的取值为真(这由图G的定义易证)。

显见，上述构造图G的方法是多项式界的，因此SA T 团问题。

由(a)、(b)有，团问题。证毕。

单源最短路径问题:

void shortestpaths(v)

{

MinHeap H[1000];

//定义最小堆MinHeapNode E;

E.i=v;

E.length=0;

Dist[v]=0;

//搜索问题界空间

while(true)

{ for(j=1;j<=n;j++)

if((c[E.i][j]

(E.length+c[E.i][j]

prev[j]=E.i;

//加入活结点优先队列MinHeapNode N;

N.i=j;

N.length=dist[j];

H.Insert(N);

}

//取下一个扩展结点

try { H.DeleteMin(E); }

//优先队列为空

catch (OutOfBounds) {break;} }

}

(1)数值随机化算法: 求解数值问题,得到近似解

(2)Monte Carlo算法:问题准确性,但却无法确定解正确性

(3)Las Vegas算法:获得正确解,但存在找不到解的可能性

(4)Sherwood算法:保证能获得正确解

旅行售货员问题:(优先队列式分支限界法)

Type Travding (int v[])

{ MinHeapNode H(1000)；

Type Minout[N+1]；

//计算Minout[i]=顶点i的最小出边费用

Type Minsurn=0；//最小出边费用和

for（i=1;i＜＝n；i++）{

Min=NoEdge；

for（j=1；j＜＝n；j++）

if（a[i][j]!=NoEdge＆＆(a[i][j]

if（Min==NoEdge）return(NoEdge)；//无回路

MinOut[i]= Min；

MinSum+=Min；

}

//初始化

MinHeapNode E；

for（i= 0；i＜n；i++）

E.x［i］= i+ 1；

E.s=0；

https://www.doczj.com/doc/fc3516808.html,=0；

E.rcost=MinSum；

Bestc=NoEdge；

while（E.s＜n-1) //非叶结点

if（E.s

if（a[E.x[n-2][E.x[n-1]]!=NoEdge ＆＆a[E.x[n-2][1]!=NoEdge&&（https://www.doczj.com/doc/fc3516808.html,+

a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]<

bestc || bestc==NoEdge）{

//费用更小的回路

bestc=Ecc+a[E.x[n-2]][E.x[n-1]]

+a[E.x[n-1]][1]；

E.c＝bestc；

E.lcost=bestc；

E.s++；

Insert（H,E）；}

else delete(E.x) ；} //舍弃扩展结点else { //产生当前扩展结点的儿子结点

for（i＝E.s+1；i＜n；i++＝

if（a[E.x[E.s]][E.x[i]]!=NoEdge）{ //可行儿子结点

Type cc＝https://www.doczj.com/doc/fc3516808.html,+a[E.x[E.s]][E.x[i]]；

Type rcost=E.rcost-MinOut[E.x[E.s]]；

Type b=cc+rcost；//下界

if（b＜bestc||bestc== NoEdge )

{ //子树可能含最优解

for（j= 0；j＜n；j++)

N.x[j]=E.x[j]；

N.x[E.s+1]=E.x[i]；

N.x[i]=E.x[E.s+1]；

https://www.doczj.com/doc/fc3516808.html,=cc；

N.s= E.s+1；

N.lcost=b；

N.rcost＝rcost；

Insert（H,N）；

}

}

delete(H,E.x)；

}//完成结点扩展

DeleteMin(H,E)；} //取下一扩展结点if (堆已空) break；//堆已空

}

if（bestc==NoEdge）return( NoEdge)；

//无回路

//将最优解复制到v[l：n]

for（i=0；i＜n；i++)

v[i+ 1]=E.x[i]；

while (true){ //释放最小堆中所有结点

delete(H, E. x)；

DeleteMin(H,E)；} //取下一扩展结点

if (堆已空) break；//堆已空

}

return(bestc)；} 回溯算法解批处理作业调度(解空间：排列树):

void Flowshop::Backtrack(int i)

{

if (i > n) {

for (int j = 1; j <= n; j++)

bestx[j] = x[j];

bestf = f;

}

else

for (int j = i; j <= n; j++) {

f1+=M[x[j]][1];

f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];

f+=f2[i];

if (f < bestf) {

Swap(x[i], x[j]);

Backtrack(i+1);

Swap(x[i], x[j]);

}

f1- =M[x[j]][1];

f- =f2[i];

}

}

所以在最坏的情况下，整个算法的计算时间复杂性为O(n!)

回溯算法解0-1背包问题(解空间：子集树):

template

Typep Knap::Bound(int i) {// 计算上界

Typew cleft = c - cw; // 剩余容量

Typep b = cp;

// 以物品单位重量价值递减序装入物品while (i <= n && w[i] <= cleft) {

cleft -= w[i];

b += p[i];

i++;

}

// 装满背包

if (i <= n) b += p[i]/w[i] * cleft;

return b;

}

void backtrack(i)

{ if( i>n )

{ bestp=cp;

return; }

if(cw+w[i]<=c)//x[i]=1

{ cw+=w[i] ;cp+=p[i];

backtrack(i+1);

cw-=w[i] ;cp-=p[i]; }

if ( bound(i+1)>bestp )

backtrack(i+1); //x[i]=0

}

由于上界函数Bound()需要O(n)的时间，在最坏的情况下有O(2n)个右儿子结点需要计算上界函数，所以0-1背包问题的回溯算法Backtrack()所需要的时间是O(n2n)。

回溯算法解图的m着色问题:

void Color::Backtrack(int t) {

if (t>n) {

sum++;

for (int i=1; i<=n; i++)

cout << x[i] << ' ';

cout << endl;

}

else

for (int i=1;i<=m;i++) {

x[t]=i;

if (Ok(t)) Backtrack(t+1);

}

}

bool Color::Ok(int k)

{// 检查颜色可用性

for (int j=1;j<=n;j++)

if ((a[k][j]==1)&&(x[j]==x[k])) return false;

return true;

} 回溯法总的时间耗费是O(m^n *n) 回溯算法解最大团问题（解空间：子集树）：

void Clique::Backtrack(int i)

{// 计算最大团

if (i > n) {// 到达叶结点

for (int j = 1; j <= n; j++) bestx[j] = x[j];

bestn = cn; return;}

// 检查顶点i 与当前团的连接

int OK = 1;

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

if (x[j] && a[i][j] == 0) {

// i与j不相连

OK = 0; break;}

if (OK) {// 进入左子树

x[i] = 1; cn++;

Backtrack(i+1);

x[i] = 0; cn--;}

if (cn + n - i > bestn) {// 进入右子树x[i] = 0;

Backtrack(i+1);}

}

解最大团问题的回溯算法Backtrack所需的计算时间为O(n2n)。

回溯法的基本思想是：不断用修改过的判定函数Pi只(x1,x2,…,xi)(亦称为限界函数)去测试正在构造中的n元组的部分向量(x1,x2,…,xn)．看其是否可能导致最优解。如果判定(x1，x2，…，xn)不可能导致最优解，那么就不再测试可能要测试的mi+1mi+2...mn个向量。

解符号三角形问题的回溯算法Backtrack所需的计算时间为O(n2n)。

贪心法解最优装载问题：

template

void Loading(int x[], Type w[], Type c, int n)

{

int *t = new int [n+1];

Sort(w, t, n);

for (int i = 1; i <= n; i++) x[i] = 0;

for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];}

}

算法所需的计算时间为O(nlogn)

算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入(2)输出(3)确定性(4)有限性：

(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。

1. 什么是动态规划法：将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。

2. 什么是贪心法：从问题某一初始或推测值出发，一步步的攀登给定目标，尽可能快的去逼近更好的解，当达到某一步不能继续时终止。

3.什么是分支定界法：对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可

行解空间不断地划分为越来越小的子集（分支），并为每一个子集的解计算一个上界和下界（定界）。

5、什么是NP类问题：

NP={L|L是一个能在多项式时间内被一台NDTM图灵机所接受的语言}，其中NDTM是非确定性图灵机。或者可说：NP是所有可在多项式时间内用不确定的算法求解的判定问题的集合。对于NP类，相当于要求验证模块在多项式时间内完成对应NDTM，有非确定性算法。

1. 算法的分类：1）(数值算法) 2）非数值算法

2. 算法的描述：1）自然语言描述2）(流程图描述) 3）程序语言描述

3. 算法的分析标准：1）时空观念2 ）(发展观念) 3）设计观点4）交流的观点

设计动态规划算法的步骤。

(1)找出最优解的性质，并刻划其结构特征。

(2)递归地定义最优值。

(3)以自底向上的方式计算出最优值。

(4)根据计算最优值时得到的信息，构造最优解。

动态规划法求矩阵连乘问题：

void MatrixChain(int *p，int n，int **m，int **s)

{for (int i = 1; i <= n; i++) m[i][i] = 0;

for (int r = 2; r <= n; r++)

for (int i = 1; i <= n - r+1; i++) {

int j=i+r-1;

m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];

s[i][j] = i;

for (int k = i+1; k < j; k++) {

int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}

}

}

}

因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。

1.简述算法的五个重要的特征。：①有穷性：一个算法必须保证执行有限步之后结束；②确切性：算法的每一步骤必须有确切的定义；③输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；⑤可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。备注：算法可以没有输入。因为有些算法中包含了输入，如随机产生输入。

2.简答贪心算法的基本元素：①贪心选择性质：所谓贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择达到。②最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。

3.简述动态规划算法的基本思想和基本步骤以及动态规划问题的特征。

动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。按以下几个步骤进行：

①分析最优解的性质，并刻划其结构特征。

②递归地定义最优值。

③以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。

④根据计算最优值时得到的信息，构造一个最优解。

动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。

1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

4.简述回溯算法的基本思想及解题步骤。

回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。（9分）运用回溯法解题通常包含以下三个步骤：

（1）针对所给问题，定义问题的解空间；（2分）

（2）确定易于搜索的解空间结构；（2分）

（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

5.简述分治算法的基本思想及基本步骤。

分治法的基本思想：对于一个输入规模为n的问题，若该问题容易的解决，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归求解这些子问题，然后将各个子问题的解合并，得到原问题的解。（9分）

分治法在每一层递归上由以下三个步骤组成：

①划分：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题；（2分）

②解决：若子问题规模较小，则直接解决；否则递归求解各个子问题。（2分）

③合并：将各个子问题的解合并为原问题的解。（2分）

6.分支限界法的基本思想：

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

7.贪心算法的基本思想如下：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地

求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止，得到问题的一个解。

贪心算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

8.动态规划与分治法的异同：

相同点：动态规划法与分治法类似，它们都是将问题划分为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。

不同点：而分治法中的各个子问题是独立的(即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不同的是，如果各子问题是不是相互独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。

9.分支限界法与回溯法的异同：

分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。因此，回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

10.证明装载问题具有贪心选择性质.

证明:设集装箱已依其重量从小到大排序, (x1,x2, …,xn)是最优装载问题的一个最优解.

又设1.当k=1时, (x1,x2, …,xn)是一个满足贪心选择性质的最优解.

2.当k>1时,取y1=1;yk=0;yi=xi,1

因此,(y1,y2, …,yn)是所给最优装载问题的一个可行解

另一方面,由

(y1,y2, …,yn)是一个满足贪心选择性质的最优解

所以,最优装载问题具有贪心选择性质

Hanoi塔问题:

void hanoi(int n, int a, int b, int c) {

if (n > 0)

{

hanoi(n-1, a, c, b);

move(a,b);

hanoi(n-1, c, b, a);

}

}

递归下降语法分析程序设计

编译方法实验报告实验名称：简单的语法分析程序设计

实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下：

5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d-(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开) T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3-T4 (-,T3,T4,T5) x:=T5 (:=,T5,-,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计3-5个赋值语句测试实例，检验程序能否输出正确的四元式；当输入错误 的句子时，检验程序能够给出语法错误的相应提示信息。 7.报告内容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。

目录 1.语法分析递归下降分析算法............................... 错误!未定义书签。 背景知识............................................. 错误!未定义书签。 消除左递归........................................... 错误!未定义书签。 2.详细设计及流程图....................................... 错误!未定义书签。 函数void V( ) .|z ................................. 错误!未定义书签。 函数void A( ) 错误!未指定书签。错误!未指定书签。错误!未指定书签。错误!未指定书签。错误!未指定书签。试用例及截图........................ 错误!未定义书签。 测试用例1及截图..................................... 错误!未定义书签。 测试用例2及截图..................................... 错误!未定义书签。 测试用例3及截图..................................... 错误!未定义书签。 代码清单................................................. 错误!未定义书签。

编译原理-递归下降分析法的实现-内附源码

编 译 原 理 实 验 报 告 姓名：关海超 学号：200807010209 专业：计算机科学与技术 班级：08—02班

递归下降分析法的实现 实验要求 递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。它的基本思想是，对文法中的每个非终结符编写一个函数（或子程序），每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法通常是递归定义的，因此相应的这组函数（或子程序）必然一相互递归的方式进行调用，所以将此种分析方法称为递归下降分析法。 本实验要求构造下述文法的递归下降分析程序： 文法G[S]: S —> a | ^ | (T) T —> T,S | S 实验内容 首先，消去该文法左递归，得到文法G’[S]: S —> a | ^ | (T) T —> ST’ T’—> ,ST’ | 空串 然后，根据LL(1)文法的判断条件，对非终结符S和T’的不同产生式的SSELECT集进行考察，经验证改进后的文法已经是LL(1)文法。 最后构造递归下降分析程序。每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。 （1）当遇到终结符a时，则编写语句 if (当前读来的输入符号== a) 读下一个输入符号 （2）当遇到非终结符A时，则编写语句调用A（）。 （3）当遇到A —> 空串规则时，则编写语句 if (当前读来的输入字符不属于FOLLOW(A) ) error() （4）当某个非终结符的规则有很多个候选式是，按LL(1)文法的条件能唯一地选择一个候选式进行推导。 实验结果

实验总结 这次实验内容比较简单。由于有固定的模式来构造程序，因此即使对于其他LL(1)文法也很容易构造其相应的递归下降分析程序。 这次实验我学习了如何将递归下降分析思想具体转化为程序来实现，同时也加深了产生式的Follow集在递归下降分析法中的应用，练习了通过SELECT集判断文法是否为LL(1)文法。 附录（源代码） #include #include #include char token[20]; char sym; int p; void S(); void T(); void U(); void Scaner(); void Error();

编译原理-编写递归下降语法分析器

学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日

一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include #include char str[50]; int index=0; void E(); //E->TX; void X(); //X->+TX | e void T(); //T->FY void Y(); //Y->*FY | e void F(); //F->(E) | i int main() /*递归分析*/ { int len; int m;

实验三 递归下降分析程序实现

实验三递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 程序比较复杂，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调 用的方法。 二、实验要求 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 三、实验内容 程序输入/输出示例： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （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)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 引用也要改变）。 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。 四、实验学时 4学时 五、实验步骤 （一）准备：

1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序思路（仅供参考）： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将输入符号串输入到字符缓冲区中。 2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 六、实验预习提示 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 3、递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程,不妨命名为U。 U的产生式的右边指出这个过程的代码结构： (1)若是终结符号，则和向前看符号对照， 若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 具体为： （1）对于每个非终结符号U-u1|u2|…|un处理的方法如下： U( ) { ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; … else error() } （2）对于每个右部u1-x1x2…xn的处理架构如下： 处理x1的程序； 处理x2的程序； … 处理xn的程序； （3）如果右部为空，则不处理。

递归下降分析法

《编译原理》课程实验报告 实验名称：递归下降分析法 一．实验目的 1.理解递归下降语法分析方法的主要原理 2.理解递归下降分析法对文法的要求 3．熟练掌握Predict集合的求法 4.熟练掌握文法变换算法（消除左递归和消除公共前缀） 二．实验内容 #include char token[20]; char sym; int p; void S(); void T(); void U(); void Scanner(); void Error(); void S() { if (sym == 'a' || sym == '^') Scanner(); else if (sym == '(') { Scanner(); T(); if (sym == ')') Scanner(); else Error(); } else Error();

} void T() { S(); U(); } void U() { if (sym == ',') { Scanner(); S(); U(); } else if(sym != ')') Error(); } void Scanner() { sym = token[p++]; } void Error() { //exit(0); } int main() { printf("输入: "); gets(token); p = 0; Scanner(); S(); if (sym == '$') printf("Success!"); else printf("Fail!"); return 0; } 三．实验步骤 调试程序的结果：

实验三_递归下降法的语法分析器

魏陈强 23020092204168 实验3 递归下降法的语法分析器 一、实验目的 学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。 二、实验内容 用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。 这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录 A.1，p394） program→ block block→{stmts } stmts→stmt stmts | stmt→id=expr; | if(bool)stmt | if( bool)stmt else stmt | while(bool)stmt | do stmt while(bool ) ; | break ; | block bool →expr < expr | expr <= expr | expr > expr | expr >= expr | expr expr→ expr + term | expr - term | term

term→ term * factor | term / factor | factor factor→ ( e xpr ) | id| num 三、实验要求 １．个人完成，提交实验报告。 ２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。 测试程序片断： { i = 2; while (i <=100) { sum = sum + i; i = i + 2; } } 对应的推导过程为： program?block ?{stmts } ?{stmt stmts} ?{id=expr;stmts } ?{id=num;stmts } ?{id=num;stmt stmts } ?{id=num;while(bool)stmt stmts } ?{id=num;while(e xpr<= expr)stmt stmts } ?{id=num;while(id<= expr)stmt stmts } ?{id=num;while(id<= num)stmt stmts } ?{id=num;while(id<= num)block stmts } ?{id=num;while(id<= num){stmts }stmts } ?．．．．．．． 四、实验思路 之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable[100][20]，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable[0]=”id”，

递归下降分析法

编译原理课程实验报告 班级学号：姓名： 实验名称：递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （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)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 三、实验过程： 程序设计： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 程序编写： 1.定义部分：定义常量、变量、数据结构。 2.初始化：从文件将输入符号串输入到字符缓冲区中。 3.利用递归下降分析法，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 四、实验结果

（1）程序流程图 主函数main( )流程图 E( )过程流程图 T( )过程流程图

G( )过程流程图 F( )过程流程图

编译原理-实验报告2-递归下降分析法

计算机硬件实验室实验报告 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （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)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 三、实验过程：

程序设计： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 程序编写： 1.定义部分：定义常量、变量、数据结构。 2.初始化：从文件将输入符号串输入到字符缓冲区中。 3.利用递归下降分析法，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 四、实验结果 （1）程序流程图 （2）运行结果 示例程序： #include <> #include<> #include<> #include<> char a[50] ,b[50],d[500],e[10]; char ch; int n1,i1=0,flag=1,n=5; int E(); int E1(); int T(); int G();

编译原理-实验二-递归下降分析程序构造

集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算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 ′

递归下降分析算术表达式

递归下降分析算术表达式 计算机092—07 邹芬芬 ●实验目的： （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 ●实验内容： 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下：E→E+T | T T→T*F | F F→(E) | i ●设计分析 题目所给的文法不为LL(1)文法，应改写成如下文法： E →TE2 E2→+TE2 |∑ T →FT2 T2→*FT2 | ∑ F →(E) | i 采用递归下降分析法时，需要求出E2和T2 的FOLLOW集： FOLLOW(E2)={），#} FOLLOW(T2)={+,),#} 递归下降分析法是确定的自上而下分析法，基本思想是，对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。因此需要分别构造E,E2,T,T2,F函数来执行自己的识别功能，根据文法的内容顺序决定函数的识别功能。advance函数用于字符串的推进，input函数用于字符串的输入。 ●程序代码 #include using namespace std; char a[80]; // 字符串的存入 char sym; // 单个的判断字符 int i=0; // 字符串下标 void E(); // 功能识别函数 void E2(); // 功能识别函数 void T(); // 功能识别函数 void T2(); // 功能识别函数 void F(); // 功能识别函数 void input(); // 输入函数

递归下降分析器设计与实现

实验二递归下降分析器设计与实现 1、实验目的： （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 2、实验内容： 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下： E-->E+T|T T-->T*F|F F-->(E)|i 3、设计说明： 首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。4、设计分析 这个题目属于比较典型的递归下降语法分析。需要先将原算术表达式方法改写为LL(1)文法为： E-->TE' E'-->+TE'|ε T-->FT' T'-->*FT'|ε F-->(E)|i 然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而实现递归下降语法分析的功能。具体方法为： （1）当遇到终结符a时，则编写语句 If(当前读到的输入符号==a)读入下一个输入符号 （2）当遇到非终结符A时，则编写语句调用A()。 （3）当遇到A-->ε规则时，则编写语句 If(当前读到的输入符号不属于Follow(A))error() （4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导. 5、程序代码 #include void E(); void T(); void E1(); void T1(); void F();

char s[100]; int i, SIGN; int main() { printf("请输入一个语句，以#号结束语句（直接输入#号推出）\n"); while( 1 ) { SIGN = 0; i=0; scanf("%s",&s); if( s[0] == '#') return 0; E(); if(s[i]=='#') printf("正确语句！\n"); printf("请输入一个语句，以#号结束语句\n"); } return 1; } void E() { if(SIGN==0) { T(); E1(); } } void E1() { if(SIGN==0) {

递归下降

南京工程学院 实验报告 课程名称编译原理 实验名称递归下降分析技术班级 学号0105 学生姓名 成绩 指导教师 20年12月

一．实验目的： 应用递归下降分析技术，关于各非终结符号构造相应子程序来识别相对于它的短语。 二．实验内容： 递归下降识别程序的例1： 对于文法G[E]： E::=E+T|T T::=T*F|F F::=(E)|i 经消去左递归同时也就消去了回溯性后的等价文法G’[E]： E::=TE’E’::=+TE’|εT::=FT’ T’::=*FT’|εF=(E)|i 递归下降识别程序的例2： 对于文法G[S]： S::=S;T S::=T T::=if e then S else S T::=if e then S T::=a 经消去左递归同时也就消去了回溯性后的等价文法G’[S]： S::=TS’S’::=;TS’|εT::= if e then ST’|a T’::=else S |ε+ 三.流程图: 递归下降例１的流程图

递归下降例2的流程图四.实验方法: 1．用C语言写出递归下降识别程序1如下: #include #include void T(); // 声明函数 void F(); // 声明函数 void E1(); // 声明函数 void T1(); // 声明函数 char sym; char str[10]; //存放输入的字符串 int i=0; char GetSymbol(){ //取字符 sym=str[i]; i++; return sym; } void Error(){ //出错判断 cout<<"error!"<

c++实现递归下降法的语法分析器

一、实习题目：递归下降分析 二、实习目的 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。另：程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。 三、程序算法描述 1.递归下降分析法功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2.递归下降分析法前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法。 3.递归下降分析法算法 (1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 4.对下列文法,用递归下降分析法对任意输入的符号串进行分析: (1)E->TG (2)G->+TG|-TG|ε (3)T->FS (4)S->*F S|/FS|ε (5)F->(E)|i 四、核心程序代码 #include #include #include using namespace std; char str[10]; int index = 0; int flag = 0; void E(); //E->TX; void E1(); //X->+TX | e void T(); //T->FY void T1(); //Y->*FY | e void F(); //F->(E) | i void E() { T(); E1(); } void E1()

递归下降语法分析程序设计

编译方法实验报告 令狐采学 实验名称：简单的语法分析程序设计 实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下： 5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开)

T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3T4 (,T3,T4,T5) x:=T5 (:=,T5,,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计35个赋值语句测试实例，检验程序能否输出正确的四 元式；当输入错误的句子时，检验程序能够给出语法错误的相应提示信息。 7.报告内容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，35个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。

目录 1.语法分析递归下降分析算法5 1.1背景知识5 1.2消除左递归6 2.详细设计及流程图6 2.1 函数void V( ) // V > a|b|c|d|e...|z6 2.2 函数void A( ) // A > V:=E7 2.3 函数void E() //E > TE'7 2.4函数void T( ) // T > FT'8 2.5函数void E1( ) //E'> +TE'|TE'|null8 2.6函数void T1() // T'> *FT'|/FT'|null9 3.测试用例及截图9 3.1测试用例1及截图9 3.2测试用例2及截图10 3.3测试用例3及截图11 代码清单11

递归下降语法分析设计原理与实现技术实验报告

递归下降语法分析设计原理与实现技术 实验报告 变更说明 日期版本变更位置变更说明作者2014/4/16 1、0 初稿生成房皓

一、实验目的: 本实验的目的在于在教师的引导下以问题回朔与思维启发的方式,使学生在不断的探究过程中掌握编译程序设计与构造的基本原理与实现技术,启迪学生的抽象思维、激发学生的学习兴趣、培养学生的探究精神与专业素养,从而提高学生发现问题、分析问题与解决问题的能力。 二、实验内容: [实验项目] 完成以下描述算术表达式的LL(1)文法的递归下降分析程序 G[E]: E→TE′ E′→ATE′|ε T→FT′ T′→MFT′|ε F→ (E)|i A→+|- M→*|/ [设计说明] 终结符号i 为用户定义的简单变量,即标识符的定义。 [设计要求] (1)输入串应就是词法分析的输出二元式序列,即某算术表达式“实验项目一”的输出结果,输出为输入串就是否为该文法定义的算术表达式的判断结果; (2)递归下降分析程序应能发现输入串出错; (3)设计两个测试用例(尽可能完备,正确与出错),并给出测试结果。 三、实验环境: 操作系统:Windows 7 软件: VC++6、0 四、程序功能描述: ●提供了两种输入方式:键盘与文件,有文件输入时需为二元式序列; ●能够对输入的字符串做出正确的递归下降分析判断,并给出判断结果; ●能发现输入串中的错误,包含非法字符,输入不匹配等; ●能够处理一些可预见性的错误,如文件不存在,用户输入非法等。

五、数据结构设计: 全局: 局部(main()中): 六、程序结构描述: ●设计方法: 本程序采用从键盘输入或文件读取两种输入方式,其中文件的内容需为二元式序列,然后按照递归下降分析的方法对输入的字符串进行分析判断,并输出判断结果,程序通过对输入串的检查能够发现输入串中的错误。程序规定的单词符号及其种别码见下表: 单词符号种别码单词符号种别码 ( 1 * 5 ) 2 / 6 + 3 i 7 - 4 # 8 ● advance():将下一个字符送入current;

递归下降分析法

实验报告 课程编译原理实验名称递归下降分析法 专业班级学号姓名 实验日期： 2015 年 5 月 20 日 一、实验目的 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验内容 1、递归下降分析法的功能：词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 三、实验环境 Visual c++ 6.0 四、实验步骤 代码： #include #include char t[20]; char sym; int p; void T(); void E(); void G() { if(sym=='+') { printf("G->+TG…………%c\n",sym); sym=t[p]; p++; T(); G(); } else if(sym=='-') {

printf("G->-TG…………%c\n",sym); sym=t[p]; p++; T(); G(); } else printf("S->ε…………%c\n",sym); } void F() { if(sym=='i') { printf("F->i…………%c\n",sym); sym=t[p]; p++; } else if(sym=='(') { printf("F->(E)…………%c\n",sym); sym=t[p]; p++; E(); if(sym==')') { sym=t[p]; p++; } else { printf("匹配不成功\n"); exit(0); } } else { printf("匹配不成功\n"); exit(0); } }

递归下降分析程序

一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、程序算法描述 这次的实习主要是根据以下文法实现一个递归下降分析器，依据文法如下：（1）E->TG （2）G->+TG|－TG|ε （3）T->FS （4）S->*FS|/FS|ε （5）F->(E)|i 在这个递归下降分析器程序中每一个非终结符E、G、T、S和F构造相应的递归函数，函数的名字表示文法左部的非终结符，函数中就是按文法中每个非终结符右部的候选式依次进行匹配，根据对输入串的分析如果非终结符可以用其中的一个候选式替代就返回1，否则返回0。因为该文法中有五个非终结符，所以定义了五个函数，分别为E（），G（），T()，S()和F（）。当输入一串字符串后，就对该字符串进行分析，首先从开始符号分析，所以首先调用E()函数，在E（）函数中会调用T（）和G(),就是每个非终结符的候选式中出现了哪个非终结符就调用哪个函数。所以，将字符串的第一个字符和E中的每个候选式匹配，如果成功就匹配输入字符串的下一个字符，当最后剩下的字符为’#’时，匹配成功。其实这个工程就是构造一个语法树。 程序总流程图如下： 图1 程序总流程图 三、关键性代码

这个工程的主要工作用五个非终结符生成的句子是否和输入字符串匹配，所以主要的工作是函数E（），G（），T()，S()和F（）的编写。 1. 对非终结符E处理的函数E() 这个函数主要是根据文法中的E->TG，在E（）中调用了T（）和G（）来进行递归分析，这个就是构造生成树的一个分支。 int E() { int f,t;//变量 printf("E-->TG\t");//输出根据的文法 flag=1; outDeduce ();//输出字符串 outputRemain ();//输出剩余字符 f=T(); if (f==0) return(0);//表示当前分析字符可由非终结符T推导出 t=G(); if (t==0) return(0);//表示当前分析字符可由非终结符G推导出 else return(1); } 2. 对非终结符G处理的函数G() 这个函数主要是根据文法中G->+TG|-TG|ε，在函数中调用了T()和G()函数。将当前字符和候选式的第一个字符进行匹配，如果匹配成功，就调用该候选式中涉及到得第一个非终结符对应的函数，一次递归嵌套调用。如果不是由第一个候选式推出然后依次匹配剩下的候选式。 int G() { int f; if(ch=='+') {//当前字符式‘+’ b[i1]=ch; printf("G-->+TG\t");//说明用的是第一个候选式 e[0]='G'; e[1]='='; e[2]='>'; e[3]='+'; e[4]='T'; e[5]='G'; e[6]='#'; Compute ();//计算推导式 flag=0; outDeduce ();//输出字符串 outputRemain ();//输出剩余字符 ch=a[++i1];//读取当前字符的下一个字符 if (f==0) return(0);//表示当前分析字符可由非终结符T推导出 t=G(); if (t==0) return(0); //表示当前分析字符可由非终结符G推导出 if(ch=='-') {//当前字符是‘-’ b[i1]=ch;

递归下降分析器

题目：编程识别由下列文法所定义的表达式的递归下降语法分析器。 E→E+T | E-T | T T→T*F | T/F |F F→(E) | i 输入：每行含一个表达式的文本文件。 输出：分析成功或不成功信息。 解答: （1）分析 a) ∵E=>E+T=>E+T*F=>E+T*(E)即有E=>E+T*(E)存在左递归。用直接改写法消除左递归，得到如下： E →TE’ E’ →+TE’ | ?TE’|ε T →FT’ T’ →*FT’ | /FT’|ε F → (E) | i b) 对于以上改进的方法。可得： 对于E’:FIRST( E’ )=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，?，ε} 对于T’:FIRST( T’ )=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε} 而且：FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST((E))∪ FIRST(i)={(，i } 由此我们容易得出各非终结符的FOLLOW集合如下： FOLLOW( E )= { )，#} FOLLOW(E’)= FOLLOW(E)={ )，#} FOLLOW( T )= FIRST(E’)\ε∪FOLLOW(E’)={+，?，)，#} FOLLOW( T’ ) = FOLLOW( T ) ={+，?，)，#} FOLLOW( F )=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，?，)，#}由以上FOLLOW集可以我们可以得出SELECT集如下：

对E SELECT（E→TE’）=FIRST(TE’)=FIRST(T)={ (，i } 对E’ SELECT（E’ →+TE’）={ + } SELECT（E’ →?TE’）={ ? } SELECT（E’ →ε）={ε，)，#} 对T SELECT（T→FT’）={(，i} 对T’ SELECT（T’ →*FT’）={ * } SELECT（T’ →∕FT’）={ ∕ } SELECT（T’ →ε）={ε，+，?，)，#} 对F SELECT（F→(E) ）={ ( } SELECT（F→i）={ i } ∴SELECT(E’ →+TE’)∩SELECT（E’ →?TE’）∩SELECT（E’ →ε）=ΦSELECT(T’ →*FT’)∩SELECT（T’ →∕FT’）∩SELECT（T’ →ε）=Φ SELECT（F→(E) ）∩SELECT（F→i）= Φ 由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL （1）文法。因此，转化后的文法可以用递归下降分析法作语法分析。 （2）设计 这里采用递归下降分析法形象描述递归子程序。程序中将要用到的几个重要数据如下： 一个全局变量ch，存放由文件输入得到的字符。 一个函数宏READ(ch)，实现读取文件中的字符。 五个子函数：P(E)、P(E’)、P(T)、P(T’)、P(F)。 程序主要的子函数模块流程图如下：

编译原理——递归下降语法分析之欧阳家百创编

《编译原理》课程实验报告 欧阳家百（2021.03.07） 实验名称：递归下降分析法 姓名：彭国保 学号：540907010130 院系：计算机与通信工程学院 专业：计算机科学与技术 班级：09-1班 教师：韩丽 2012年4月22日 一．实验目的 根据某一文法编制调试递归下降分析程序，以便对任意输入 的符号串进行分析。本次实验的目的主要是加深对递归下降分析 法的理解。程序开始变得复杂起来，需要利用到程序设计语言的 知识和大量编程技巧，递归下降分析法是一种较实用的分析法， 通过这个练习可大大提高软件开发能力。通过练习，掌握函数间 相互调用的方法。 二．实验内容 递归下降分析法是确定的自上而下分析法，它要求文法是LL(1)文法。它的基本思想是：对文法中的每个非终结符编写一个函数

或子程序，每个函数或子程序的功能是识别由该非终结符所表示的语法成分。 2.1程序算法描述 2.1.1递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2.1.2递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 2.1.3递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程。U的产生式的右边指出这个过程的代码结构： (1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 最后编写程序以实现上述功能。 三．实验步骤 根据上述算法描述，编写程序以实现相应的功能，该程序由C 语言编写，然后在VC运行环境下进行调试，并不断完善，直到能正确的实现递归下降分析功能，判断输入的字符串是否是一个文法的句子。 源程序代码如下：