实验二递归下降语法分析程序的设计与实现
一、实验目的：
加深对语法分析器工作过程的理解；加强对递归下降法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。
二、实验内容：
在实验1的基础上，用递归下降分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程工具。
三、实验要求：
1. 对语法规则有明确的定义；
2. 编写的分析程序能够进行正确的语法分析；
3. *对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；
4. 实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现*。
四、实验学时：4学时
五、实验步骤：
1. 定义目标语言的语法规则；
2. 根据语法规则输入语句段，用递归下降分析的方法进行语法分析，直到结束；
3. *对遇到的语法错误做出错误处理。
六、实验内容：
1.编程实现给定文法的递归下降分析程序。
E→T|E+T
T→F|T*F
F→(E)|i
2.（参考课本P74）对文法先进行消除左递归。
3.分析程序由一组递归过程组成，文法中每个非终结符对应一个过程几个全局过程和变量：
ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号
SYM，IP当前所指的输入符号
ERROR，出错处理子程序
每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。
4. 具体实现时：
（1）当遇到终结符，编写： if（当前读到的输入符号=i）
读入下一个输入符号
（2）当遇到非终结符E时，编写语句：调用E（）
（3）当遇到E--> 编写语句 if（当前读到的输入符号不属于Follow（E））
Error（）；
（4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一的选择一个候选式进行推导。
#include
using namespace std;
char a[80]; // 字符串的存入
char sym; // 单个的判断字符
int i=0; // 字符串下标
void E(); // 功能识别函数
void E2(); // 功能识别函数
void T(); // 功能识别函数
void T2(); // 功能识别函数
void F(); // 功能识别函数
void input(); // 输入函数
void advance(); // 字符串小标进一函数。。。。。。。。
5. 代码实现：
#include
#include
#include
#include
char a[50] ,b[50],d[200],e[10];
char ch;
int n1,i1=0,flag=1,n=5;
int total=0;/*步骤计数器*/
int E();
int E1();
int T();
int G();/*E’*/
int S();/*T’*/
int F();
void input();
void input1();
void output();
void main() /*递归分析*/
{
int f,p,j=0;
char x;
d[0]='E';
d[1]='=';
d[2]='>';
d[3]='T';
d[4]='G';
d[5]='#';
printf("请输入字符串(长度<50,以#号结束）\n");
do{
scanf("%c",&ch);
a[j]=ch;
j++;
}while(ch!='#');
n1=j;
ch=b[0]=a[0];
printf("步骤\t文法\t分析串\t\t分析字符\t剩余串\n"); f=E1();
if (f==0) return;
if (ch=='#')
{
printf("accept\n");
p=0;
x=d[p];
while(x!='#') {
printf("%c",x);p=p+1;x=d[p]; /*输出推导式*/
}
}else {
printf("error\n");
printf("回车返回\n");
getchar();
getchar();
return;
}
printf("\n");
printf("回车返回\n");
getchar();
getchar();
}
int E1()
{
int f,t;
printf("%d\tE-->TG\t",total);total++;
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
int E()
{
int f,t;
printf("%d\tE-->TG\t",total);total++;
e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5]='#'; output();
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
int T()
{
int f,t;
printf("%d\tT-->FS\t",total);total++;
e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#'; output();
flag=1;
input();
input1();
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);
}
int G()
{
int f;
if(ch=='+') {
b[i1]=ch;
printf("%d\tG-->+TG\t",total);total++;
e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#'; output();
flag=0;
input();input1();
ch=a[++i1];
f=T();
if (f==0) return(0);
G();
return(1);
}
printf("%d\tG-->^\t",total);total++;
e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';
output();
flag=1;
input();input1();
return(1);
}
int S()
{
int f,t;
if(ch=='*') {
b[i1]=ch;printf("%d\tS-->*FS\t",total);total++; e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#'; output();
flag=0;
input();input1();
ch=a[++i1];
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);}
printf("%d\tS-->^\t",total);total++;
e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#';
output();
flag=1;
a[i1]=ch;
input();input1();
return(1);
}
int F()
{
int f;
if(ch=='(') {
b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;
e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=E();
if (f==0) return(0);
if(ch==')') {
b[i1]=ch;printf("%d\tF-->(E)\t",total);total++; flag=0;input();input1();
ch=a[++i1];
}
else {
printf("error\n");
return(0);
}
}
else if(ch=='i') {
b[i1]=ch;printf("%d\tF-->i\t",total);total++;
e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';
output();
flag=0;input();input1();
ch=a[++i1];
}
else {printf("error\n");return(0);}
return(1);
}
void input()
{
int j=0;
for (;j<=i1-flag;j++)
printf("%c",b[j]); /*输出分析串*/
printf("\t\t");
printf("%c\t\t",ch); /*输出分析字符*/ }
void input1()
{
int j;
for (j=i1+1-flag;j printf("%c",a[j]); /*输出剩余字符*/ printf("\n"); } void output(){ /*推导式计算*/ int m,k,j,q; int i=0; m=0;k=0;q=0; i=n; d[n]='=';d[n+1]='>';d[n+2]='#';n=n+2;i=n; i=i-2; while(d[i]!='>'&&i!=0) i=i-1; i=i+1; while(d[i]!=e[0]) i=i+1; q=i; m=q;k=q; while(d[m]!='>') m=m-1; m=m+1; while(m!=q) { d[n]=d[m];m=m+1;n=n+1; } d[n]='#'; for(j=3;e[j]!='#';j++){ d[n]=e[j]; n=n+1; } k=k+1; while(d[k]!='=') { d[n]=d[k];n=n+1;k=k+1; } d[n]='#'; system("pause"); } 编译方法实验报告实验名称：简单的语法分析程序设计 实验要求 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及截图..................................... 错误!未定义书签。 代码清单................................................. 错误!未定义书签。 《编译原理》课程实验报告 实验名称：递归下降分析法 一．实验目的 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; } 三．实验步骤 调试程序的结果： 学号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）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.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 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）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(); 编译原理课程设计报告 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”， 递归下降分析算术表达式 计算机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.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 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 集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算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/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、实验目的： （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) { 实验报告 课程编译原理实验名称递归下降分析法 专业班级学号姓名 实验日期： 2015 年 5 月 20 日 一、实验目的 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验内容 1、递归下降分析法的功能：词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 三、实验环境 Visual c++ 6.0 四、实验步骤 代码： #include 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); } } 南京工程学院 实验报告 课程名称编译原理 实验名称递归下降分析技术班级 学号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 一、实习题目：递归下降分析 二、实习目的 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。另：程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。 三、程序算法描述 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 编 译 原 理 实 验 报 告 实验题目：递归子程序 姓名：柏顺顺 学号：540913100201 专业：软件工程JA V A技术班级：09——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)文法的条件能唯一地选择一个候选式进行推导。 实验结果 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、程序算法描述 这次的实习主要是根据以下文法实现一个递归下降分析器，依据文法如下：（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)。 程序主要的子函数模块流程图如下： 编译原理实验报告 题目： 递归下降语法分析器 学 院 计算机科学与技术 专 业 xxxxxxxxxxxxxxxx 学 号 xxxxxxxxxxxx 姓 名 宁剑 指导教师 xx 20xx 年xx 月xx 日 递归下降语法分析器 装 订 线 一、实验目的 了解语法分析器的内部工作原理，通过在本次实验中运用一定的编程技巧，掌握对表达式进行处理的一种方法。 二、实验原理 算术表达式的文法可以是（可以根据需要适当改变）： E→E+E|E-E|E*E|E/E|(E)|i 根据递归下降分析法或预测分析法，对表达式进行语法分析，判断一个表达式是否正确。 三、实验步骤 (1) 准备：1. 阅读课本有关章节，确定算术表达式的文法；（设计出预测分析表）；2. 考虑好设计方案；3. 设计出模块结构、测试数据，初步编制好程序。 (2) 上机调试，发现错误，分析错误，再修改完善。教师根据学生的设计方案与学生进行探讨，以修改方案和代码。 (3)改造后的文法：E→E+T|E-T|T T→T*F|T/F|F F→F^|P P→c |id| (E) 四、实验环境 计算机VC++软件 五、实验程序 #include递归下降语法分析程序设计
递归下降分析法
编译原理-编写递归下降语法分析器
递归下降分析法
实验三 递归下降分析程序实现
编译原理-实验报告2-递归下降分析法
编译原理-递归下降子程序-课程设计报告
实验三_递归下降法的语法分析器
递归下降分析算术表达式
递归下降语法分析程序设计
编译原理-实验二-递归下降分析程序构造
递归下降语法分析设计原理与实现技术实验报告
递归下降分析器设计与实现
递归下降分析法
递归下降
c++实现递归下降法的语法分析器
编译原理 递归下降分析法C语言
递归下降分析程序
递归下降分析器
递归下降语法分析器实验报告
相关主题
文本预览