实验二递归下降分析器设计与实现
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)
{
if(s[i]=='+')
{
++i;
T();
E1();
}
else if(s[i]!='#'&&s[i]!=')')
{
printf("语句有误！\n");
SIGN=1;
}
}
}
void T()
{
if(SIGN==0)
{
F();
T1();
}
}
void T1()
{
if(SIGN==0)
{
if(s[i]=='*')
{
++i;
F();
T1();
}
else if(s[i]!='#'&&s[i]!=')'&&s[i]!='+')
{
printf("语句有误！\n");
SIGN=1;
}
}
}
void F()
{
if(SIGN==0)
{
if(s[i]=='(')
{
++i;
E();
if(s[i]==')')
++i;
else if(s[i]== '#')
{
printf("语句有误！\n");
SIGN=1;
++i;
}
}
else if(s[i]=='i')
++i;
else
{
printf("语句有误！\n");
SIGN=1;
}
}
}
6、测试用例
（1）只含有一个字符的形式：
i
a
A
(2) 含有‘+’的形式：
i+i
i+i+i
i+
+++
(3) 含有‘*’的形式：
i*i
i*i*i
i*
**
(4) 含有‘（’‘）’的形式：
（i）
（）
（
（i））
(5) 综合形式：
（i+i）*i
(i+i)*(i+i) i+i*i
i++i*
(*i+
(i+
Iii
7、系统实施
系统实施环境为VC++6.0,在系统的实施过程中存在的问题主要是程序输入错误，没有大的技术问题，经过调试和修改，系统最终能够运行并实现上述所有功能。以下列出程序运行时的几个界面：
（1）系统运行初始界面：
(2)导入文法
选择要导入的文本
（3）生成非终结符集合，终结符集合，空串的非终结符集合，非终结符号的FIRST集合，非终结符号的FOLLOW集合，各产生式的SELECT集合，预测分析表：
8、实验总结
通过本次试验实践掌握了自上而下语法分析法的特点。掌握了递归下降语法分析的基本原理和方法。运用递归下降分析法完成了本试验的语法分析构造，并且成功的分析出每种正确的句子和错误的句子。函数的构造是根据文法分析的递归过程，所编写每个函数的功能，以文法的右部为函数名，对应的左部为相应分析过程。此分析法简单，直观，易构造分析程序，但是不适于文法过于复杂的，不易检查出错误。在试验的过程中，遇到了一些问题，都是粗心大意而造成，并非是对文法分析和编程的熟悉问题，说明了我再以后的试验中应该更细心的编写程序的每一步，对于本次试验所出现的马虎，应该牢记，以后不再犯同样的错误。
课程设计任务书 学生姓名：赵旭林专业班级：计算机0801班 指导教师：陈天煌工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件： 理论：学完编译课程，掌握一种计算机高级语言的使用。 实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） （1）写出符合给定的语法分析方法的文法及属性文法。 （2）完成题目要求的中间代码三地址表示的描述。 （3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 （4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 （5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括： 1 系统描述（问题域描述）； 2 文法及属性文法的描述； 3 语法分析方法描述及语法分析表设计； 4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计； 5 编译系统的概要设计； 6 详细的算法描述（流程图或伪代码）； 7 软件的测试方法和测试结果； 8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）； 9 参考文献（按公开发表的规范书写）。 时间安排： 设计安排一周：周1、周2：完成系统分析及设计。 周3、周4：完成程序调试及测试。 周5：撰写课程设计报告。 设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。 设计报告书收取时间：设计周的次周星期一上午10点。 指导教师签名： 2010年 11月 13日 系主任（或责任教师）签名： 2010年 11月 13日
学号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
1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。
编译方法实验报告实验名称：简单的语法分析程序设计
实验要求 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及截图..................................... 错误!未定义书签。 代码清单................................................. 错误!未定义书签。
魏陈强 204168 实验3 递归下降法的语法分析器 一、实验目的 学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。 二、实验内容 用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。 这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录，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 } ．．．．．．．
算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T
算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 实验三递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 程序比较复杂，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调 用的方法。 二、实验要求 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、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 n = 3 Backtrack(1) t=1 for i = 1 to 3 i=1 Swap(x[1], x[1]) t=1时，x[1]取了x[1]=1 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时，x[2]取了x[2]=2 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时，x[3]取了x[3]=3 Backtrack(4) ---> t = 4 > 3 输出(1,2,3) swap(x[3],x[3]) swap(x[2],x[2]) i=3 swap(x[2],x[3]) x[2]=3, x[3]=2 t=2时，x[2]取了3 Backtrack(3) -------> t=3 for i = 3 to 3 swap(x[3],x[3]) t=2时，x[3]取了x[3]=2 Backtrack(4) ---> t = 4 > 3 输出(1,3,2) swap(x[3],x[3]) swap(x[2],x[3]) x[2]=2, x[3]=3 Swap(x[1], x[1]) i=2 Swap(x[1], x[2]) x[1]=2, x[2]=1 t=1时，x[1]取了2 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时，x[2]取了x[2]=1 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时，x[3]取了x[3]=3 Backtrack(4) ---> 《编译原理》课程设计题目 设计题一：正规式r与正规文法G相互转换的程序设计 任意给定一个正规式，求出其对应的正规文法；任意给定一个正规文法，求出其对应的正规式。（参考教材P53～55） 设计题二：布尔表达式的递归下降翻译器 针对布尔表达式的文法： 〈布尔表达式〉∷＝〈布尔项〉{〈与运算符〉〈布尔项〉} 〈与运算符〉∷＝and 〈布尔项〉∷＝〈布尔因子〉{〈或运算符〉〈布尔因子〉} 〈或运算符〉∷＝or 〈布尔因子〉∷＝〈非运算符〉〈布尔因子〉｜〈布尔量〉 〈非运算符〉∷＝not 〈布尔量〉∷＝（〈布尔表达式〉）｜〈标识符〉〈关系运算符〉〈标识符〉｜ true｜false 〈关系运算符〉∷＝＞｜＜｜≥｜≤｜＝｜≠ 〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉} 利用递归下降分析法编制、调试其语法及语义分析程序，生成的中间代码为逆波兰式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P92～93） 设计题三：正规式r与有穷自动机FA相互转换的程序设计 任意给定一个正规式，求出其对应的有穷自动机；任意给定一个有穷自动机，求出其对应的正规式。（参考教材P61～64） 设计题四：赋值语句的LR翻译程序 对教材P180中的赋值语句文法，给出该文法的属性文法，同时实现赋值语句的翻译，生成的中间代码为逆波兰式。（参考教材P179～181） 设计题五：正规文法G与有穷自动机FA相互转换的程序设计 任意给定一个正规文法，求出其对应的有穷自动机；任意给定一个有穷自 动机，求出其对应的正规文法。（参考教材P65～66） 设计题六：条件语句的LR翻译程序 对教材P187中的条件语句文法，给出该文法的属性文法，同时实现条件语句的翻译，生成的中间代码为四元式。（参考教材P186～189） 设计题七：NFA确定化为DFA及化简的程序设计 任意给定一个NFA，将其确定化为DFA，然后化简为最小的DFA。（参考教材P57～61） 设计题八：布尔表达式的LR翻译器 针对布尔表达式的文法： B →B and T | T T→T or F | F F→not F|true｜false |（B）| i rop i 利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P181～182） 设计题九：生成预测分析表的算法实现 任意给定一个LL(1)文法，生成相应的LL(1)分析表。（参考教材P75第5章） 设计题十：while循环语句的LR翻译程序 对教材P187中的循环语句文法，给出该文法的属性文法，同时实现循环语句的翻译，生成的中间代码为四元式。（参考教材P186～189） 设计题十一：利用LEX自动生成词法分析程序 输入描述某种语言词法规则的正规式，利用LEX自动生成词法分析程序。（参考教材P66～68） 设计题十二：生成LR分析表的算法实现 任意给定一个LR文法，生成相应的LR分析表。（参考教材P123第7章） 设计题十三：布尔表达式翻译为逆波兰式的算法实现 针对布尔表达式的二义性文法： B → B and B | B or B | not B | ( B ) | true｜false| i rop i 将文法拓广为G’[B’]： (0) B’ → B 《编译原理》课程实验报告 实验名称：递归下降分析法 一．实验目的 1.理解递归下降语法分析方法的主要原理 2.理解递归下降分析法对文法的要求 3．熟练掌握Predict集合的求法 4.熟练掌握文法变换算法（消除左递归和消除公共前缀） 二．实验内容 #include } 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; } 三．实验步骤 调试程序的结果： 《算法设计与分析》习题 第一章算法引论 1、算法的定义 答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。 2、算法的特征 答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种 答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义 答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次， 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点 答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略 答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法： 递归法：汉诺塔问题兔子序列（上楼梯问题） 整数划分问题 蛮力法：百鸡百钱问题 倒推法：穿越沙漠问题 答：算法如下： （1） 递归法 汉诺塔问题 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); } } 兔子序列（fibonaci 数列 ） 递归实现： Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n 实验二递归下降分析器设计与实现 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 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) { 计算机硬件实验室实验报告 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （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(); 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败 编译原理课程设计课程设计题目：LL(1)递归下降分析器 姓名： 院（系）： 专业班级： 学号： 指导教师： 设计日期： 目录 1、需求分析 (1) 2、概要设计 (2) 3、详细设计 (3) 4、测试分析 (8) 5、用户手册 (9) 6、课程总结 (9) 7、参考文献 (10) 题目：LL （1）递归下降分析器 1、需求分析 语法分析是编译过程的核心部分。语法分析器的任务是识别和处理比单词更大的语法单位。如：程序设计语言中的表达式，各种说明和语句乃至全部源程序，指出其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。 我们知道，语言的语法结构是用上下文无关文法描述的。按照语法分析树的建立方法，我们可以粗略地把语法分析办法分成两类，一类是自上而下分析，另一类是自下而上分析法。而自上而下这种方法是带“回溯”的，且存在许多困难和缺点。 首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符P 且αP P + ?，含有左递归的文法使上述的自上而下的分析过程陷入无限循环。即，当试图用P 去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，有得重新要求P 去进行新的匹配。因此，使用自上而下分析法必须消除文法的左递归性。 其次，由于回溯，就碰到一大堆麻烦问题。如果我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作（指中间代码产生工作和各种表格的簿记工作）推倒重来。这些事情既麻烦又费时间，所以，最好应设法消除回溯。 第三，在自上而下分析过程中，当一个非终结符用某一候选匹配成功时，这种成功可能仅是暂时的。 第四，当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。 最后，由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此，效率很低，代价极高。严重的低效使得这种分析法只有理论意义，而在实践上价值不大。 由于上述原因，我们需要把原算术表达式改写为LL(1)文法，LL(1)文法的文法条件如下： 文法不含左递归。 对于文法中每一个非终结符A 的各个产生式的候选首集符两两不相交。即，若n A ααα|||21 →，则()()φαα=?j i FIRST FIRST ()j i ≠ 对文法中的每个非终结符A ，若它存在某个候选首符集包含ε，则()()φ=?A F O L L O W A F I R S T LL(1)中的第一个L 表示从左到右扫描输入串，第二个L 表示最左推导，1表示分析时每 集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算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 ′实验三 递归下降分析程序实现
计算机算法设计与分析期末考试复习题
算法设计与分析排列树递归推算
《编译原理》课程设计题目-2014
递归下降分析法
算法设计与分析习题
递归下降分析器设计与实现
编译原理-实验报告2-递归下降分析法
算法设计与分析期末试题答案解析
算法设计与分析：递归与分治法-实验报告
编译原理课程设计---LL(1)递归下降分析器
编译原理-实验二-递归下降分析程序构造
相关主题
文本预览