语法分析-递归下降分析法

一、实验目的

通过本实验，掌握自上而下语法分析的要求和特点，以及递归下降分析的原理和过程。调试一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。

二、实验内容

利用C语言完善递归下降分析程序，并对简单语言进行语法分析。

1、要点回顾

标识符ID=letter（letter| digit）* 整型常数NUM=digit digit * 单词符号及其种别码： 单词符号 种别码 begin 1 if 2 then 3 while 4 do 5 end 6 letter(letter| digit)* 10 digit digit * 11 - 13 + 14 * 15 / 16

单词符号 : := < <> <= > >= = ; ） （ # 种别码 17 18 20 21 22 23 24 25 26 27 28 0 2、待分析的简单语言的语法

用扩充的BNF表示如下： （1）<程序>：：=begin<语句串>end （2）<语句串>：：=<语句>{；<语句>} （3）<语句>：：=<赋值语句> （4）<赋值语句>：：=ID：=<表达式> （5）<表达式>：：=<项>{+<项>|-<项>} （6）<项>：：=<因子>{*<因子>|/<因子>} （7）<因子>：：=ID| NUM|(<表达式>)

3、实验要求说明

输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。

三、完整源程序代码

#include #include #include using namespace std;

char prog[80];//缓冲区

int p=0;//缓冲区prog的指针

char token[8];//单词

int m=0;//单词token的指针

char ch;//需要分析的字符

int syn=0;//单词的种别码

int sum=0;//计算整数

int n=0;//计数器 int kk=0;

char *rwtab[6]={\"begin\//关键字

void scaner();//扫描函数 void factor();//因子 void term();//项

void expression();//表达式 void statement();//语句 void yucu();//语句串

void lrparser();//语法分析

//扫描函数 void scaner() { 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; } }

//因子

void factor()

{//问题---补充程序代码 if(syn==11||syn==10)//当扫描的是数字或字母时，继续扫描 { scaner(); } else if(syn==28) //当扫描的'('时，继续扫描 { scaner(); expression(); if(syn==27) //当扫描的是')'时，继续扫描 scaner(); else { cout<<\"错误,表达式缺乏')'\"<void term()

{ factor(); //问题---补充判断条件 while(syn==15 || syn==16)//当开头扫描的是'*'或'/'时，继续扫描 { scaner(); factor(); } return; }

//表达式

void expression() { //问题---补充程序代码 term(); while(syn==14 || syn==13)//当开头扫描的是'+'或'-'时，继续扫描 { scaner(); term(); } return; }

//语句

void statement() { //问题---补充判断条件 if(syn==10) //当开头扫描的是字母时，继续扫描 { scaner(); if(syn==18)//赋值 { scaner();//问题---补充执行语句 expression(); } else { cout<<\"缺:=错误！\"<cout<<\"error!\"<//语句串 void yucu() { statement(); while(syn==26)//\";\" { scaner(); statement(); } }

//语法分析 void lrparser() { if(syn==1)//begin { scaner(); yucu(); if(syn==6)//end { scaner(); //问题---补充判断条件 if(syn==0 && kk==0)//当串最后扫描的是'#'，而且并无出错，分析成功 cout<<\"success!\"<int main() { //接收用户输入 p=0; cout<<\"please input string:(以#结束)\"<>ch; //不认识空格，当不存在 prog[p++]=ch; } while (ch!='#'); //当遇到'#'，结束输入 cout<四、结果验证

（1）输入：begin_a:=9; x:=2*3; b:=a+x end#

输出：success!

（2）输入：x:=9;if x>0 then x:=2*x+1/3;end# 输出：缺begin错误!

（3）输入：begin x:=10;x:=x-3;a:=a+x*7 # 输出：缺end错误!

（4）输入：begin x=x+1;m<>9;end# 输出：缺:=错误!

（5）输入：begin x:=x*7;m:=m+(x*7;end# 输出：错误，表达式缺乏‘)’

五、收获（体会）

由于已经有实验一的基础，看懂程序没有很大问题。在填写补充内容时，必须要注意细节问题，稍有不慎，在运行时便会出各种很奇怪的问题。这次的补充内容是环环相扣的，错了前面的一个，后面的一个也不会正确。必须要弄清楚什么是因子、项、表达式等。

通过这次实验，我加深了自己对语法组成的理解，对于递归下降分析方法更加的得心应手了。

吴雨霜 1108140222 计算机111班