实验4 递归下降子程序的编写
一、实验目的
通过本实验，了解递归下降预测分析的原理和过程以及可能存在的回溯问题，探讨解决方法，为预测分析表方法的学习奠定基础。分析递归下降子程序的优缺点。
二、实验准备
1．预习自上而下语法分析小节的内容；
2．学生自己考虑使用的开发环境，如VC++，熟悉开发环境。
三、实验内容
下列文法中选做一题：
1．针对算术表达式文法：E→TE’
E’→ +TE’|ε
T→FT’
T’→*FT’ |ε
F→(E) |i
为其编写递归下降子程序，判定某个算术表达式是否正确：如j+k*m，j*k+m
输入：其输入数据应该为词法分析器输出的记号形式：i+i*i，i*i+i
输出：分析结果：算术表达式结构正确或结构错误。
2．给定文法（PASCAL语言标识符定义文法）（选做）
type→simple|↑id|array[simple] of type
Simple→integer|char|num dotdot num
其中：dotdot表示.
编写递归下降子程序，判定一个句子结构是否正确：array [3..5]of integer 输入：其输入数据应该为词法分析器输出的单词序列：array[num dotdot num] of integer
输出：分析结果
四、实验要求
1．编写程序调试运行；考虑如果将你的程序改为识别其他的文法，你的递归下降子程序可否通用，考虑递归下降子程序方法的优缺点。
2．撰写实验报告：实验名称、实验目的、实验内容、实验结果、结果分析
五、实验结果
1、程序：
#include
int word=0; void E1(); void T(); void T1(); void F();
//编写E函数//E->TE
void E()
{
//因为是第一步，所以直接输出E->TE'
printf("E->TE'\n");
T();
E1();
}
//就是那个E'函数
//E'->+TE'|ε
void E1()
{ //如果匹配为+号的话输出E'->+TE if(EL[word]=='+')
{
printf("E'->+TE'\n");
word++;
T();
E1();
}
else
//如果不是加号、则输出空
printf("T'->ε\n");
}
//T->FT
void T()
{
printf("T->FT'\n");
F();
T1();
}
//如果匹配*则输出T'->*FT，否则输出空
//T'->*FT|ε
void T1()
{
if(EL[word]=='*')
{
printf("T'->*FT'\n");
word++;
F();
T1();
}
else
printf("T'->ε\n");
} //如果为i、则输出F->i\n，如果为（则指针下移、调用E函数、如果为）则输出F->(E)，否则说明括号不匹配。
//F->(E)|i
void F()
{
if(EL[word]=='i')
{
printf("F->i\n");
word++;
}
else if (EL[word]=='(')
{
word++;
E();
if(EL[word]==')'){
printf("F->(E)\n");
word++;
}
else{
printf("\n错误、括号不匹配（缺少右括号）\n");
exit (0);
} }
else{
printf("错误、请输入正确的算术表达式!\n");
exit(0);
}
}
//主函数
//输入算数表达式、为其编写递归下降子程序，判定算术表达式是否正确
int main()
{
while(1)
{
printf("请输入算数表达式：");
scanf("%s",EL);
E();
}
return 0;
}
2、截图：
（1）输入正确的算数表达式：
i+i*i
(2)输入有括号的算数表达式
: i+(i*i)
(3)输入缺少一半括号的算数表达式
: i+(i*i
(4) 输入缺少操作数的算数表达式
: i+i*
编译方法实验报告实验名称：简单的语法分析程序设计
实验要求 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及截图..................................... 错误!未定义书签。 代码清单................................................. 错误!未定义书签。
学号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
魏陈强 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 } ．．．．．．．
递归调用详解，分析递归调用的详细过程 2009年05月23日星期六 22:52 一、栈 在说函数递归的时候，顺便说一下栈的概念。 栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。 再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。 可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。 二、递归 递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级
实验三递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 程序比较复杂，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调 用的方法。 二、实验要求 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
} 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; } 三．实验步骤 调试程序的结果：
编译原理课程设计报告 2011 年 12 月 2 日 设计题目 递归下降分析程序的实现 学 号 专业班级 计算机科学与技术 学生姓名 指导教师
一、实验目的: （1）掌握自上而下语法分析的要求与特点。 (2）掌握递归下降语法分析的基本原理和方法。 （3)掌握相应数据结构的设计方法。 二、实验内容: 递归下降分析程序的实现 设计内容及要求： 对文法 G： E→E+T｜Ｔ构造出G的递归下降分析程序。程序显示输出T→T*F|Ｆ匹配过程（即自上而下生成语法分析树的步骤， F→（E）|i 输出各匹配产生式序号即可）。 三、设计思路： (１)语法分析: 语法分析是编译程序的核心部分，任务是分析一个文法的句子结构。递归下降分析程序的实现的功能:按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子（合式程序）。 （2)自上而下分析: 从文法的开始符号出发,向下推导,推出句子。可分为带“回溯”的和不带回溯的递归子程序(递归下降)分析方法。 它的主旨是对任何输入串，试图用一切可能的办法,从文法开始符号(根结点）出发，自上而下地为输入串建立一棵语法树。或者说,为输入串寻找一个最左推导。也即从文法的开始符号出发，反复使用各种产生式，寻找"匹配＂的推导。 (3)递归下降分析法： 对每一语法变量(非终结符)构造一个相应的子程序,每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 (４）分析过程中遇到的问题: a. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时,不得不“回溯”。 b．文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。 (5)构造不带回溯的自上而下分析算法： ａ.要消除文法的左递归性：一个文法可以消除左递归的条件是①不含以 为右部的产生式②不含回路。
魏陈强 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( )过程流程图
计算机硬件实验室实验报告 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （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();
学生课程实验报告书 2014--2015学年第1学期 实验项目：子程序设计（n!） 实验时间： 2014-10-30 实验原理： 在一个程序中如果其中有些内容完全相同或相似，为了简化程序，可以把这些重复的程序段单独列出，并按一定的格式编写成子程序。用递归方式求出n！。 实验仪器： Emu8086编译器 实验步骤（纸张不够写可另外加纸并应装订）： DATA SEGMENT NUM DW 5 FNUM DW ? DATA ENDS STACKS SEGMENT DW 100 DUP(?) STACKS ENDS CODE SEGMENT ASSUME CS:CODE,DS:DATA,SS:STACK BEGIN: MOV AX,DATA MOV DS,AX ;将数据段基值装入DS
MOV AX,NUM ;取N PUSH AX ;利用堆栈传递参数 CALL FAC ;调用递归子程序 POP FNUM ;送结果 MOV AX,4C00H ;返回DOS INT 21H FAC PROC PUSH AX ;保存调用参数 PUSH BP ;保存每帧的帧地址(偏移量) MOV BP,SP ;当前帧地址(栈顶地址)送BP寄存器 MOV AX,[BP+6];取参数N CMP AX,0 ;N = 0 ? JNZ FACSUB ;N≠0,继续递归调用 INC AX ;若N=0,则0!=1 JMP EXIT ;由递归调用过程转递次返回过程FACSUB: DEC AX ;N-1送AX PUSH AX ;保护各次调用参数 CALL FAC ;递归调用 POP AX ;从堆栈中弹出每次压入的参数 MUL WORD PTR [BP+6];计算各参数的乘积EXIT: MOV [BP+6],AX ;保存中间结果和最后结果 MOV DX,AX POP BP ;恢复BP内容 POP AX ;恢复AX内容 RET ;返回所调用程序 FAC ENDP CODE ENDS END BEGIN 指导教师评语： 实验成绩_______________ 指导教师_______________
集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算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
实验二递归下降分析器设计与实现 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) {
编译原理课程设计课程设计题目：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表示分析时每
课程设计 题目WHILE循环语句的翻译程序设计 （递归下降法、输出三地址表示）学院计算机科学与技术学院 专业计算机科学与技术 班级0806 姓名张方纪 指导教师郭羽成 2010 年 1 月7 日 课程设计任务书
学生姓名：张方纪专业班级：计算机0806班 指导教师：郭羽成工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件： 理论：学完编译课程，掌握一种计算机高级语言的使用。 实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） （1）写出符合给定的语法分析方法的文法及属性文法。 （2）完成题目要求的中间代码三地址表示的描述。 （3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 （4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 （5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括： 1 系统描述（问题域描述）； 2 文法及属性文法的描述； 3 语法分析方法描述及语法分析表设计； 4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计； 5 编译系统的概要设计； 6 详细的算法描述（流程图或伪代码）； 7 软件的测试方法和测试结果； 8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）； 9 参考文献（按公开发表的规范书写）。 时间安排： 设计安排一周：周1、周2：完成系统分析及设计。 周3、周4：完成程序调试及测试。 周5：撰写课程设计报告。 设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。 设计报告书收取时间：设计周的次周星期一上午10点。 指导教师签名： 2010年 11月 23日 系主任（或责任教师）签名： 2010年 11月 23日
一、实习题目：递归下降分析 二、实习目的 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。另：程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。 三、程序算法描述 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
编译原理实验 姓名：尹莉 学号：E31314022 专业：13级网络工程
语法分析器1 一、实现方法描述 所给文法为G【E】； E->TE’ E’->+TE’|空 T->FT’ T’->*FT’|空 F->i|(E) 递归子程序法： 首先计算出五个非终结符的first集合follow集，然后根据五个产生式定义了五个函数。定义字符数组vocabulary来存储输入的句子，字符指针ch指向vocabulary。从非终结符E函数出发，如果首字符属于E的first集，则依次进入T函数和E’函数，开始递归调用。在每个函数中，都要判断指针所指字符是否属于该非终结符的first集，属于则根据产生式进入下一个函数进行调用，若first集中有空字符，还要判断是否属于该非终结符的follow集。以分号作为结束符。 二、实现代码 头文件shiyan3.h #include
void judge_EE(); void judge_T(); void judge_TT(); void judge_F(); 源文件 #include"shiyan3.h" void judge_E() { if(*ch==';') { cout<<"该句子符合此文法！"<
递归下降语法分析设计原理与实现技术 实验报告 变更说明 日期版本变更位置变更说明作者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;
编译方法实验报告 令狐采学 实验名称：简单的语法分析程序设计 实验要求 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