2024年5月25日发(作者：)
编译原理语法分析递归下降子程序实验
报告
编译课程设计-递归下降语法分析
课程名称编译原理
设计题目 递归下降语法分析
一、 设计目的
通过设计、编制、调试一个具体的
语法分析程序，加深对
语法分析原理的理解，加深对语法
及语义分析原理的理解，并实现对文法
的判断，是算符优先文法的对其进行
FirstVT集及LastVT集的分析，并对输入
的字符串进行规约输出规约结果成功或
失败。
二、 设计内容及步骤
内容：在C++ 6.0中编写程序代码实
现语法分析功能，调试得到相应文法的
判断结果：是算符优先或不是。若是，
则输出各非终结符的FirstVT与LastVT集
的结果，还可进行字符串的规约，输出
详细的规约步骤，程序自动判别规约成
功与失败。
步骤:1.看书，找资料，了解语法分
析器的工作过程与原理
2.分析题目，列出基本的设计思路
1定义栈，进栈，出栈函数 ○
2栈为空时的处理 ○
3构造函数判断文法是否是算符文
法，算符优先文法 ○
4构造FirstVT和LastVT函数对文法
的非终结符进行分析 ○
5是算符优先文法时，构造函数对其
可以进行输入待规约 ○
串，输出规约结果
○6构造主函数，对过程进行分析
3.上机实践编码，将设计的思路转换
成C++语言编码，编译运
行
4.测试，输入不同的文法，观察运行
结果
详细的算法描述
详细设计伪代码如下：
首先要声明变量，然后定义各个函
数
Initstack(charstack &s)
{//定义栈
=new charLode[20];
=-1; }
2. void push(charstack
&s,charLode w)
{//字符进栈
++;
[].E=w.E;
[].e=w.e;
}
3. void pop(charstack
&s,charLode &w)
{//字符出栈
w.E=[].E; 三、
w.e=[].e;
--;
}
4. int IsEmpty(charstack s)
{//判断栈是否为空
if(==-1)
return 1;
else return 0;
}
IsLetter(char ch)
{//判断是否为非终结符
if(ch='A'&&ch=
'Z')
return 1;
else return 0;
}
judge1(int n)
{ //judge1是判断是否是算符文法：
若产生式中含有两个相继的
非终结符则不是算符文法
}
7. void judge2(int n)
{//judge2是判断文法G是否为算符
优先文法：若不是算符文法或
若文法中含空字或终结符的优先级
不唯一则不是算符优先文法
search1(char r[],int kk,char a)
{ //search1是查看存放终结符的数
组r中是否含有重复的终结符}
createF(int n)
{ //createF函数是用F数组存放每个
终结符与非终结符和组合，
并且值每队的标志位为0;F数组是
一个结构体}
search(charLode w)
{ //search函数是将在F数组中寻找
到的终结符与非终结符对的
标志位值为1 }
分情况讨论：//产生式的后选式的第
一个字符就是终结符的情况
//产生式的后选式的第一个字符是
非终结符的情况
LastVT(int n)
{//求LastVT
}
FirstVT(int n)
{//求FirstVT
}
createYXB(int n)
{//构造优先表
分情况讨论：//优先级等于的情况，
用1值表示等于}
//优先级小于的情况，用2值表示小
于
//优先级大于的情况，用3值表示大
于
}
judge3(char s,char a)
{//judge3是用来返回在归约过程中
两个非终结符相比较的值
}
print(char s[],char
STR[][20],int q,int u,int ii,int k)
{//打印归约的过程}
16. void process(char STR[][20],int ii)
{//对输入的字符串进行归约的过程
}
四、 设计结果
分两大类，四种不同的情况
第一类情况：产生式的候选式以终
结符开始候选式以终结符开始经过存在
递归式的非终结符后再以终结符结束
篇二：编译原理递归下降子程序
北华航天工业学院
《编译原理》课程实验报告
课程实验题目： 递归下降子程序
实验
作者所在系部： 计算机科学与工
程系
作者所在专业： 计算机科学与技
术
作者所在班级：xxxx
作 者 学 号： xxxxx_
作 者 姓 名 ：
xxxx
指导教师姓名：xxxxx
完 成 时 间 ：2011年3月28日
一、实验目的
通过本实验，了解递归下降预测分
析的原理和过程以及可能存在的回溯问
题，探讨解决方法，为预测分析表方法
的学习奠定基础。分析递归下降子程序
的优缺点。
二、实验内容及要求
1．针对算术表达式文法：E→TE’
E’ → +TE’|ε
T→FT’
T’ →*FT’ |ε
F→(E) |i
为其编写递归下降子程序，判定某
个算术表达式是否正确：如j+k*m，j*k+m
输入：其输入数据应该为词法分析器输
出的记号形式：i+i*i，i*i+i 输出：分析
结果：算术表达式结构正确或结构错误。
三、实验程序设计说明
1．实验方案设计
各个函数之间的调用关系如下图所
示：
2．程序源代码
源代码如下：
#includestdio.h
#includeiostream
#includefstream
#includestring
char a[10];
int lookahead=0;
void E1();
void T();
void T1();
void F();
void E()
{
printf(E-TE'n);
T();
E1();
}
void E1()
{
if(a[lookahead]=='+')
{
printf(E'-+TE'n);
lookahead++;
T();
E1();
}
else
printf(T'-εn);
}
void T()
{
printf(T-FT'n);
F();
T1();
}
void T1()
{
if(a[lookahead]=='*')
{
printf(T'-*FT'n);
lookahead++;
F();
T1();
}
else
printf(T'-εn);
}
void F()
{
if(a[lookahead]=='i')
{
printf(F-in);
lookahead++;
}
else if (a[lookahead]=='(')
束)：
{
lookahead++;
E();
if(a[lookahead]==')'){
printf(F-(E)n);
lookahead++;
}
else{
printf(n
exit (0);
括号不匹配分析失败!n);
}
}
else{
printf(
exit(0);
括号不匹配,分析失败!n);
}
}
int main()
{
while(1)
{
printf(
);
请输入算数表达式(以#键结
scanf(%s,a);
E();
if((a[lookahead]=='#'))
printf(句子结构正确n);
else
printf(无结束标志，分析失败n);
}
return 0;
}
3．程序的执行结果
程序运行结果如下所示：
四、实验中出现的问题及解决方法
1.错误处理：最初程序只是将所有的
错误都简单的显示为句子结构错误，并
没有进行具体详细的说明和解释，最后
通过修改程序，细化错误类型，使用了
对if语句的嵌套，将错误分为三种类型。
2.句子结构分析：最初程序只能分析
结构比较简单的句子类型，比如输入的
字符不匹配等问题，输入类似i+i*+等缺
少操作数结构类型的句子则不能做出正
确的判断，通过修改 F（）等相关函数
解决了这个问题；但此程序只能分析此
类文法的句子结构，如果文法改变则需
要修改程序，才能进一步分析对应的句
子结构。
尽管，在实验过程中遇到的问题得
到了解决，但是仍然有很多缺陷。尤其
是在进行错误处理时只有三种，并不完
善，并没有对错误进行详细的分析和说
明的功能。
五、体会、意见或建议
通过本次实验基本掌握了语法分析
的原理和递归下降子程序分析方法，通
过编写程序进一步复习巩固了c语言的
相关知识，由于对c语言的掌握不扎实，
在编程过程中遇到了很多基础性问题，
通过不断的查阅课本，最终解决了问题，
但程序仍然存在很多值得改进和完善的
地方，这就提醒我们在以后的学习过程
当中应该及时复习巩固以前学过的相关
知识。
篇三：编译原理 实验二 递归下降
分析程序构造
集美大学计算机工程学院实验报告
课程名称：编译原理
实验编号： 实验二
班级：计算12
上机实践日期：2014.11
一、实验目的
通过设计、编制、调试一个递归下
降语法分析程序，实现对词法分析程序
所提供的单词序列进行语法检查和结构
分析，掌握常用的语法分析方法。通过
本实验，应达到以下目标：
(1) 掌握从源程序文件中读取有效
字符的方法和产生源程序内部表示文件
的方法；
(2)掌握语法分析的实现方法；
(3)上机调试编出的语法分析程序。
二、实验环境
Windows7 x64、VC6.0
三、实验原理
递归下降法是语法分析中最易懂的
一种方法。它的主要原理是，对每个非
终结符按其产生式结构构造相应语法分
析子程序，其中终结符产生匹配命令，
而非终结符则产生过程调用命令。因为
文法递归相应子程序也递归，所以称这
种方法为递归子程序下降法或递归下降
法。其中子程序的结构与产生式结构几
乎是一致的。
递归下降分析程序的实现思想是：
识别程序由一组子程序组成。每个子程
序对应于一个非终结符号。每一个子程
序的功能是：选择正确的右部，扫描完
相应的字。在右部中有非终结符号时，
调用该非终结符号对应的子程序来完
成。
自上向下分析过程中，如果带回溯，
则分析过程是穷举所有可能的推导，看
是否能推导出待检查的符号串。分析速
度慢。而无回溯的自上向下分析技术，
可根据输入串的当前符号以及各产生式
右部首符，选择某非终结符的产生式，
效率高，且不易出错。 无回溯的自上
向下分析技术可用的先决条件是：无左
递归和无回溯。即：假设A的全部产生
式为A?α1|α2|……|αn ，则必须满足
如下条件才能保证可以唯一的选择合适
的产生式
First(A?αi)∩First(A?αj)=Φ,当i≠j.
无左递归：既没有直接左递归，也
没有间接左递归。
无回溯：对于人以非中介符号U的
产生式右部x1|x2|...|xn，其对应的字的
首终结符号两两不相交。
如果一个文法不含回路（形如P??P
的推导），也不含以?为右部的产生式，
那么可以通过执行消除左递归的算法消
除文法的一切左递归。
四、实验内容
完成以下描述算术表达式的LL(1)文
法的递归下降分析程序构造
G[E]:
E→TE′
E′→+TE′|ε
T→FT′ 指导教师：付永钢 姓名：
上机实践时间： 4学时 实验成绩： 学
号： 实验名称：递归下降分析程序构
造
T′→*FT′|ε
F→(E)|i
说明：终结符号i为用户定义的简单
变量,即标识符的定义。
要求具有如下功能：
1) 从文件读入算术表达式/或者从
终端输入
2) 总控函数分析算术表达式；
3) 根据分析结果正误，分别给出不
同信息
五、实验步骤
1、分析文法，该文法无左递归，无
回溯。
2、设计程序，采用递归下降分析法
形象描述递归子程序。程序中将要用到
的几个重要数据如下：全局变量ch，存
放由文件输入得到的字符。五个子函数：
E( )、E1( )、T( )、T1( )、F( )；
3、在VC6.0环境下编写程序（程序
见附录） （1）输入文本：
六、实验结果
测试结果：
（2）输入文本：
测试结果：
（3）输入文本：
测试结果：
六、实验小结
1、在本次实验中，通过设计、编制、
调试一个递归下降语法分析程序，实现
对词法分析程序所提供的单词序列进行
语法检查和结构分析，掌握了常用的语
法分析方法；
2、通过本次实验，对递归下降分析
程序的构造和设计有了更为全面的认
识，对LL(1)文法分析程序的实现有了进
一步了解；
3、实验开始，由于没有读懂题意，
把主要精力放在词法错误的分析上，对
语法错误的分析不够全面，通过调试和
改进，最终实现了LL(1)文法语法错误的
判别；
4、通过本次实验发现，本次实验中
LL(1)文法分析程序还是不够完善的，比
如识别到‘（’时，必须找到‘）’，无法
判别多输入‘（’产生的错误，将所有输
入的‘（’认为是合法的。
附录：程序代码：
#includestdio.h
#includestdlib.h
#includestring.h
FILE *fp;
char ch;
#define N 20
char string[N];
char *p;
int re;
int n=1;
void E();
void T();
void E1();
void F();
void T1();
void F(){
if(ch=='i'){
printf(F---i%cn,ch);
*p=ch;
p++;
n++;
ch=fgetc(fp);
}
else if (ch=='('){
printf(F---(E) %cn,ch);
*p=ch;
p++;
ch=fgetc(fp);
n++;
E();
while(ch==EOF||ch!=')'){
printf((%d)error:never find
')'n,n); if(ch==EOF)
break;
ch=fgetc(fp);
n++;
re=0;
}
发布评论