编译原理实验 递归下降分析器的设计含源代码和运行结果.docx
《编译原理实验 递归下降分析器的设计含源代码和运行结果.docx》由会员分享，可在线阅读，更多相关《编译原理实验 递归下降分析器的设计含源代码和运行结果.docx（17页珍藏版）》请在冰点文库上搜索。
编译原理实验递归下降分析器的设计含源代码和运行结果
《编译原理》实验报告
实验3递归下降分析器的设计
姓名学号班级计科1001班
时间：
2012/4/15地点:
文波
同组人：
无
指导教师：
***
实验目的
使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。
实验内容
a.运用所学知识，编程实现递归下降语法分析程序。
使用递归下降分析算法分析表达式是否符合下文法：
exp→expaddopterm|term
Addop→+|-
term→termmulopfactor|factor
mulop→*|/
factor→（exp）|id|number
其中number可以是多位的十进制数字串（整数即可），因此这里还需要一个小的词法分析器来得到id和number的值。
b.从数据文件中读出符号串，输出表达式并给出其正误评判。
实验数据文件中应该有多个表达式，可能有正确的也应该有错误的表达式；表达式有形式简单的也应该有复杂的。
每个表达式写在一行，以回车结束。
实验环境
软件：
VC++6.0
实验前准备
1、方案设计：
1准备模拟数据：
本实验中使用“work..cpp”
2程序思想：
为了使用递归向下的分析，为每个非终结符根据其产生式写一个分析程序，由于写入读出的操作频繁。
所以程序中还有一个match（chart）函数，该函数是将字符写入文件打印输出同时从文件中读取下一个字符，而由于id和number可能是多个字符构成，故写了number（）和id（）来分析数字和标识符，它们的功能仅仅是把整个number或id完整的读取出来并写入文件，打印输出。
由于分析的文件中可能出现非法字符，而一旦发现非法字符就无需再接着分析，所以在每次读取一个字符时调用islegal函数判断是否是合法字符，并返回0或1.
在main（）函数中，while（（lookahead=='\n'||lookahead==''）&&lookahead!
=EOF）fscanf（resource,"%c",&lookahead）;
是为了忽略分析文件中的换行或空格，之后进入分析阶段，根据返回值判断是否是合法的表达式。
在该程序中只有发现了非法字符才会返回0，否则就返回1，而对于合法的表达式，递归程序最后分析的字符就是换行符，不合法的表达式在未分析到换行符就会停止分析，所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。
实验步骤
首先将上述文法改写成LL
（1）文法
1消除左递归：
exp→termtexp
texp→addoptermtexp|ε
Addop→+|-
term→factortterm
tterm→mulopfactortterm|ε
mulop→*|/
factor→（exp）|id|number
2求出每个非终结符的FIRST集合和FOLLOW集合：
FIRST（exp）=FIRST（term）=FIRST（factor）={id,number,（}
FIRST（texp）={ε,+,-}
FIRST（Addop）={+,-}
FIRST（tterm）={ε,*,/}
FIRST（mulop）={*,/}
求出每个非终结符的FOLLOW集合：
FOLLOW（exp）=FOLLOW（texp）={#,）}
FOLLOW（Addop）=FOLLOW（mulop）={id,number,（}
FOLLOW（term）=FOLLOW（tterm）={+,-,#,）}
FOLLOW（factor）={*,/,+,-,#,）}
对于texp→addoptermtexp|ε：
FIRST（Addoptermtexp）∩FOLLOW（texp）=φ；
对于tterm→mulopfactortterm|ε：
FIRST（mulopfactortterm）∩FOLLOW（tterm）=φ；
而Addop→+|-mulop→*|/factor→（exp）|id|number显然也是符合LL
（1）文法要求的，所以改写后的文法符合LL
（1）文法，可以用自上而下的递归分析方法。
3为每个非终结符根据其产生式写一个分析子程序；
4编写数字和字母识别程序，以便分离数字和标识符。
；
5主函数调用递归程序进行分析，根据分析结果判断是否是合法表达式，并将所有识别到的表达式输出。
程序设计：
#include
#include
number（）;
id（）;
intexp（）;
inttexp（）;
intaddop（）;
intterm（）;
inttterm（）;
intmulop（）;
intfactor（）;
intislegal（）;
voidmatch（chart）;
FILE*resource;//测试文件
FILE*result;//结果文件
charlookahead;//全局变量
voidmatch（chart）//写入result文件,打印输出，并读取下一个
{
fprintf（result,"%c",lookahead）;//向result写入
printf（"%c",lookahead）;
fscanf（resource,"%c",&lookahead）;//读数据
}
number（）//识别数字，如果遇到数字就一直接着读直到不是数字
{
while（'0'<=lookahead&&lookahead<='9'）
{
fprintf（result,"%c",lookahead）;//写入
printf（"%c",lookahead）;
fscanf（resource,"%c",&lookahead）;//读出
}
}
id（）
{//识别标识符
while（（lookahead<='z'&&lookahead>='a'）||（lookahead>='A'&&lookahead<='Z'）||lookahead=='_'）
{
while（（lookahead<='z'&&lookahead>='a'）||（lookahead>='A'&&lookahead<='Z'）||lookahead=='_'
||lookahead>='0'&&lookahead<='9'）
{
fprintf（result,"%c",lookahead）;//写入
printf（"%c",lookahead）;
fscanf（resource,"%c",&lookahead）;//读
}
}
}
intaddop（）//Addop→+|-
{
//分析+，-
inti;
if（lookahead=='+'）//+
{
match（'+'）;
i=islegal（）;//判断下一个是否是合法字符，如果不是则返回0
if（i）
return1;
else
return0;
}
elseif（lookahead=='-'）//-
{
match（'-'）;
i=islegal（）;
if（i）
return1;
else
return0;
}
else
return0;
}
intmulop（）//mulop→*|/
{
//分析*，/
inti;
if（lookahead=='*'）
{
match（'*'）;
i=islegal（）;
if（i）
return1;
else
return0;
}
elseif（lookahead=='/'）
{
match（'/'）;
i=islegal（）;
if（i）
return1;
else
return0;
}
else
return0;
}
intexp（）//exp→termtexp
{
inti,j;
while（!
feof（resource））
{
if（lookahead=='（'||'0'<=lookahead&&lookahead<='9'||
（lookahead<='z'&&lookahead>='a'）||（lookahead>='A'&&lookahead<='Z'）||lookahead=='_'）
//FIRST（term）={id,number,（}
{
i=term（）;
if（i）
{
j=texp（）;
if（j）
{
return1;//当且仅当term和texp都返回1时才返回1
}
else
{
return0;
}
}
else
{
return0;
}
}
else
{
return0;;
}
}
}
intfactor（）//factor→（exp）|id|number
{
inti,m,n;
if（lookahead=='（'）
{
match（'（'）;
i=exp（）;//返回1则继续分析
if（lookahead=='）'&&i）
{
match（'）'）;
return1;
}
else
return0;
}
elseif（（lookahead<='z'&&lookahead>='a'）||（lookahead>='A'&&lookahead<='Z'）||lookahead=='_'）
{
id（）;
n=islegal（）;//判断读出的是否合法，不合法则不必接着分析
if（n）
return1;
else
return0;
}//id分析中自会匹配
elseif（'0'<=lookahead&&lookahead<='9'）
{
number（）;
m=islegal（）;//判断读出的是否合法，不合法则不必接着分析
if（m）
return1;
else
return0;
}
else
return0;
}
inttterm（）//tterm→mulopfactortterm|ε
{//mulop,factor都为空或mulop,factor都为真则返回1
inti,j,k;
i=mulop（）;
j=factor（）;
if（i&&j）
{
k=tterm（）;//调用自己继续分析直至mulop,factor都为空或仅其中之一返回真值，此时推出该函数
return1;
}
elseif（!
i&&!
j）//mulop,factor都为空
{
return1;
}
else
return0;
}
intterm（）//term→factortterm
{
//factor,tterm都为真则返回1
inti,j;
i=factor（）;
if（i）
{
j=tterm（）;
if（j）
return1;
else
return0;
}
else
return0;
}
inttexp（）//texp→addoptermtexp|ε
{
//addop,term为空或addop，term为真
inti,j,k;
i=addop（）;
j=term（）;
if（i&&j）
{
k=texp（）;//调用自己继续分析直至addop,term都为空或仅其中之一返回真值，此时推出该函数
return1;
}
elseif（!
i&&!
j）
{
return1;//没必要继续向下分析，否则死循环
}
else
return0;
}
intislegal（）//当为'（','）','+','-','*','/',换行，字母，数字，下划线才合法
{
if（lookahead=='（'||（lookahead<='9'&&lookahead>='0'）||lookahead=='）'||lookahead=='/'||lookahead=='*'||lookahead=='+'||lookahead=='-'
||（lookahead<='z'&&lookahead>='a'）||（lookahead>='A'&&lookahead<='Z'）||lookahead=='_'||lookahead=='\n'）
{
return1;
}
else
return0;
}
voidmain（）
{
inti;
resource=fopen（"work.cpp","r"）;
if（resource==NULL）
{
printf（"failtoopen!
"）;
}
result=fopen（"结果.txt","w"）;
fscanf（resource,"%c",&lookahead）;//读一个字符
while（lookahead!
=EOF）
{
while（（lookahead=='\n'||lookahead==''）&&lookahead!
=EOF）//空格或换行则接着读
fscanf（resource,"%c",&lookahead）;
if（lookahead!
=EOF）
{
i=exp（）;//判断
}
if（i）//返回1
{
if（lookahead!
='\n'）//若没有分析到换行，则说明表达式不正确
{
while（lookahead!
='\n'）//打印该行
{
fprintf（result,"%c",lookahead）;
printf（"%c",lookahead）;
fscanf（resource,"%c",&lookahead）;
}
fprintf（result,"error!
\n"）;
printf（"error!
\n"）;
}
else//表达式分析到换行符正确
{
fprintf（result,"right!
\n"）;
printf（"right!
\n"）;
}
}
else//返回0
{
while（lookahead!
='\n'）//打印该行
{
fprintf（result,"%c",lookahead）;
printf（"%c",lookahead）;
fscanf（resource,"%c",&lookahead）;
}
fprintf（result,"error!
\n"）;
printf（"error!
\n"）;
}
fscanf（resource,"%c",&lookahead）;//读取下一个字符
}
fclose（result）;
fclose（resource）;
}
实验结果及其分析：
结果：
被分析的文件work.cpp
#include"stdio.h"
#include"string.h"
#include
main（）
{
inti;
3+4
66/9
e/i
&&;
（666+op）*y;
（p+8+9+i）*l
printf（"%c",&i）
（（y+i）+p）*8
i=1
fgetc（fp）
6+re==1
y-6
_a1
}
输出到“结果.txt”中的内容：
#include"stdio.h"error!
#include"string.h"error!
#includeerror!
main（）error!
{error!
inti;error!
3+4right!
66/9right!
e/iright!
&&;error!
（666+op）*y;error!
（p+8+9+i）*lright!
printf（"%c",&i）error!
（（y+i）+p）*8right!
i=1error!
fgetc（fp）error!
6+re==1error!
y-6right!
_a1right!
}error!
分析：
这个实验是每行一个表达式，且每行以换行符终结，故需要按行分析并打印输出，且对于每个非终结符的子程序要有返回值以便确定是否继续向下分析。
还有一点就是对于被分析的文件最后一行不要忘了加上换行符，不然会导致程序死循环。
升级会员 