语法分析递归下降分析法.docx
《语法分析递归下降分析法.docx》由会员分享，可在线阅读，更多相关《语法分析递归下降分析法.docx（16页珍藏版）》请在冰点文库上搜索。
语法分析递归下降分析法
实验2-1语法分析—递归下降法
一、实验目的
通过本实验，掌握自上而下语法分析的要求和特点，以及递归下降分析的原理和过程。
调试一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。
二、实验内容
利用C语言完善递归下降分析程序，并对简单语言进行语法分析。
1、要点回顾
标识符ID=letter（letter|digit）*
整型常数NUM=digitdigit*
单词符号及其种别码：
单词符号
种别码
单词符号
种别码
begin
1
:
17
if
2
:
=
18
then
3
<
20
while
4
<>
21
do
5
<=
22
end
6
>
23
letter（letter|digit）*
10
>=
24
digitdigit*
11
=
25
-
13
;
26
+
14
）
27
*
15
（
28
/
16
#
0
2、待分析的简单语言的语法
用扩充的BNF表示如下：
（1）<程序>：
：
=begin<语句串>end
（2）<语句串>：
：
=<语句>{；<语句>}
（3）<语句>：
：
=<赋值语句>
（4）<赋值语句>：
：
=ID：
=<表达式>
（5）<表达式>：
：
=<项>{+<项>|-<项>}
（6）<项>：
：
=<因子>{*<因子>|/<因子>}
（7）<因子>：
：
=ID|NUM|（<表达式>）
3、实验要求说明
输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。
三、完整源程序代码
#include
#include
#include
usingnamespacestd;
charprog[80];//缓冲区
intp=0;//缓冲区prog的指针
chartoken[8];//单词
intm=0;//单词token的指针
charch;//需要分析的字符
intsyn=0;//单词的种别码
intsum=0;//计算整数
intn=0;//计数器
intkk=0;
char*rwtab[6]={"begin","if","then","while","do","end"};//关键字
voidscaner（）;//扫描函数
voidfactor（）;//因子
voidterm（）;//项
voidexpression（）;//表达式
voidstatement（）;//语句
voidyucu（）;//语句串
voidlrparser（）;//语法分析
//扫描函数
voidscaner（）
{
for（n=0;n<8;n++）
{
token[n]=0;//初始化单词
}
ch=prog[p++];
while（ch==''）
{
ch=prog[p++];//过滤空格。
（也可用do……while）
}
if（（ch>='A'&&ch<='Z'）||（ch>='a'&&ch<='z'））
{
m=0;
while（（ch>='A'&&ch<='Z'）||（ch>='a'&&ch<='z'）||（ch>='0'&&ch<='9'））
{
token[m++]=ch;//将当前字符存入单词
ch=prog[p++];//取下一个
}
token[m++]='\0';//结束符
p--;//指针归位
syn=10;//假定是变量
for（n=0;n<6;n++）
{
if（strcmp（token,rwtab[n]）==0）
{
syn=n+1;//关键字！
break;
}
}
}
else
if（ch>='0'&&ch<='9'）
{
sum=0;
while（ch>='0'&&ch<='9'）
{
sum=sum*10+ch-'0';//计算数字
ch=prog[p++];
}
p--;//指针归位
syn=11;//是数字！
}
else
switch（ch）
{
case'>':
m=0;
token[m++]=ch;
ch=prog[p++];
if（ch=='='）
{
syn=24;//是">="
token[m++]=ch;//将"="存入单词
}
else
{
syn=23;//是">"
p--;//指针归位
}
break;
case'<':
m=0;
token[m++]=ch;
ch=prog[p++];
if（ch=='>'）
{
syn=21;//是"<>"
token[m++]=ch;//将">"存入单词
}
else
{
if（ch=='='）
{
syn=22;//是"<="
token[m++]=ch;//将"="存入单词
}
else
{
syn=20;//是"<"
p--;//指针归位
}
}
break;
case':
':
m=0;
token[m++]=ch;
ch=prog[p++];
if（ch=='='）
{
syn=18;
token[m++]=ch;
}
else
{
syn=17;
p--;
}
break;
case'-':
syn=13;
token[0]=ch;
break;
case'+':
syn=14;
token[0]=ch;
break;
case'*':
syn=15;
token[0]=ch;
break;
case'/':
syn=16;
token[0]=ch;
break;
case';':
syn=26;
token[0]=ch;
break;
case'（':
syn=28;
token[0]=ch;
break;
case'）':
syn=27;
token[0]=ch;
break;
case'#':
syn=0;
token[0]=ch;
break;
default:
syn=-1;
}
}
//因子
voidfactor（）
{//问题---补充程序代码
if（syn==11||syn==10）//当扫描的是数字或字母时，继续扫描
{
scaner（）;
}
elseif（syn==28）//当扫描的'（'时，继续扫描
{
scaner（）;
expression（）;
if（syn==27）//当扫描的是'）'时，继续扫描
scaner（）;
else
{
cout<<"错误,表达式缺乏'）'"<kk=1;
}
}
else
{
cout<<"表达式错误,表达式开头不是'（'"<kk=1;
}
return;
}
//项
voidterm（）
{
factor（）;
//问题---补充判断条件
while（syn==15||syn==16）//当开头扫描的是'*'或'/'时，继续扫描
{
scaner（）;
factor（）;
}
return;
}
//表达式
voidexpression（）
{
//问题---补充程序代码
term（）;
while（syn==14||syn==13）//当开头扫描的是'+'或'-'时，继续扫描
{
scaner（）;
term（）;
}
return;
}
//语句
voidstatement（）
{
//问题---补充判断条件
if（syn==10）//当开头扫描的是字母时，继续扫描
{
scaner（）;
if（syn==18）//赋值
{
scaner（）;//问题---补充执行语句
expression（）;
}
else
{
cout<<"缺:
=错误！
"<kk=1;
}
}
else
{
cout<<"error!
"<kk=1;
}
}
//语句串
voidyucu（）
{
statement（）;
while（syn==26）//";"
{
scaner（）;
statement（）;
}
}
//语法分析
voidlrparser（）
{
if（syn==1）//begin
{
scaner（）;
yucu（）;
if（syn==6）//end
{
scaner（）;
//问题---补充判断条件
if（syn==0&&kk==0）//当串最后扫描的是'#'，而且并无出错，分析成功
cout<<"success!
"<}
else
{
if（kk!
=1）
cout<<"缺end错误!
"<kk=1;
}
}
else
{
cout<<"缺begin错误！
"<kk=1;
}
}
intmain（）
{
//接收用户输入
p=0;
cout<<"pleaseinputstring:
（以#结束）"<do
{
scanf（"%c",&ch）;//识别空格
//cin>>ch;//不认识空格，当不存在
prog[p++]=ch;
}while（ch!
='#'）;//当遇到'#'，结束输入
cout<"<p=0;
scaner（）;
lrparser（）;
system（"pause"）;
return0;
}
四、结果验证
（1）输入：
begin_a:
=9;x:
=2*3;b:
=a+xend#
输出：
success!
（2）输入：
x:
=9;ifx>0thenx:
=2*x+1/3;end#
输出：
缺begin错误!
（3）输入：
beginx:
=10;x:
=x-3;a:
=a+x*7#
输出：
缺end错误!
（4）输入：
beginx=x+1;m<>9;end#
输出：
缺:
=错误!
（5）输入：
beginx:
=x*7;m:
=m+（x*7;end#
输出：
错误，表达式缺乏‘）’
五、收获（体会）
由于已经有实验一的基础，看懂程序没有很大问题。
在填写补充内容时，必须要注意细节问题，稍有不慎，在运行时便会出各种很奇怪的问题。
这次的补充内容是环环相扣的，错了前面的一个，后面的一个也不会正确。
必须要弄清楚什么是因子、项、表达式等。
通过这次实验，我加深了自己对语法组成的理解，对于递归下降分析方法更加的得心应手了。
吴雨霜
1108140222
计算机111班
升级会员 