一、实验目的：
利用C语言编制递归下降分析程序,并对简单语言进行语法分析。
编制一个递归下降分析程序,实现对词法分析程序所提供的单词序列的语法检查和结构分析。
二、实验原理
每个非终结符都对应一个子程序。
该子程序根据下一个输入符号(SELECT集)来确定按照哪一个产生式进行处理，再根据该产生式的右端:
- 每遇到一个终结符，则判断当前读入的单词是否与该终结符相匹配，若匹配，再读取下一个单词继续分析；不匹配，则进行出错处理
- 每遇到一个非终结符，则调用相应的子程序
三、实验要求说明
输入单词串，以“＃”结束，如果是文法正确的句子，则输出成功信息，打印“success”,否则输出“error”，并指出语法错误的类型及位置。
例如：
输入begin a:=9;x:=2*3;b:=a+x end #
输出success
#include <stdio.h> #include <string.h> #include <stdlib.h> char prog[]="begin a:=9;x:=2*3#",token[20],ch; int syn,p,m,n,sum; char *rwtab[6]={"begin","if","then","while","do","end"}; void scaner() { for(n=0;n<20;n++) token[n]=NULL; m=0; sum=0; ch=prog[p++]; while (ch==' ') {ch=prog[p++];} if (ch>='a'&&ch<='z') { while(ch>='a'&&ch<='z'||ch>='0'&&ch<='9') { token[m++]=ch; ch=prog[p++]; } syn=10;p--; for(n=0;n<6;n++) if(strcmp(token,rwtab[n])==0){ syn=n+1; break; } } else if(ch>='0'&&ch<='9') { while(ch>='0'&&ch<='9') { sum=sum*10+(ch-'0'); ch=prog[p++]; } syn=11;p--; } else switch(ch) { case '<':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=24; token[m++]=ch; } else{ syn=23;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=25;token[0]=ch;break; case ';':syn=26;token[0]=ch;break; case '(':syn=27;token[0]=ch;break; case ')':syn=28;token[0]=ch;break; case '#':syn=0; token[0]=ch;break; default:syn=-1;token[0]=ch; } } void E(); void T(); void E1(); void T1(); void T2(); void T3(); void F(); void G(); void G1(); void H(); void H1(); void I(); void I1(); void End(); void error(); void success(); void error(){ printf(" error！",token); } void success(){ printf(" success！",token); } main() { scaner(); E(); } void E(){ if (syn==1) { scaner(); /*读下一个单词符号*/ E1(); /*调用yucu()函数；*/ if(syn==6) { scaner(); if(syn==0) printf("success! "); } else { } } else if(syn==0||syn==28){ } else error(); } void E1(){ if(syn==10){ scaner(); T(); } else if(syn==0||syn==28){ } else error(); } void T(){ if(syn==17||syn==18){ scaner(); T1(); } else if(syn==0||syn==28){ } else error(); } void T1(){ if(syn==11){ scaner(); T2(); } else if(syn==0||syn==28){ } else error(); } void T2(){ if(syn==26){ scaner(); T3(); } else if(syn==0||syn==28){ } else error(); } void T3(){ if(syn==10){ scaner(); F(); } else if(syn==0||syn==28){ } else error(); } void F(){ if(syn==17||syn==18){ scaner(); G(); } else if(syn==0||syn==28){ } else error(); } void G(){ if(syn==11){ scaner(); G1(); } else if(syn==0||syn==28){ } else error(); } void G1(){ if(syn==15){ scaner(); H(); } else if(syn==0||syn==28){ } else error(); } void H(){ if(syn==11){ scaner(); H1(); } else if(syn==0||syn==28){ } else error(); } void H1(){ if(syn==0){ scaner(); I(); } else if(syn==0||syn==28){ } else error(); } void I(){ success(); return; }
输入x:=a+b*c end #
输出‘end' error
#include <stdio.h> #include <string.h> #include <stdlib.h> char prog[]="x:=a+b*c end #",token[20],ch; int syn,p,m,n,sum; int kk; char *rwtab[6]={"begin","if","then","while","do","end"}; void scaner() { for(n=0;n<20;n++) token[n]=NULL; m=0; sum=0; ch=prog[p++]; while (ch==' ') {ch=prog[p++];} if (ch>='a'&&ch<='z') { while(ch>='a'&&ch<='z'||ch>='0'&&ch<='9') { token[m++]=ch; ch=prog[p++]; } syn=10;p--; for(n=0;n<6;n++) if(strcmp(token,rwtab[n])==0){ syn=n+1; break; } } else if(ch>='0'&&ch<='9') { while(ch>='0'&&ch<='9') { sum=sum*10+(ch-'0'); ch=prog[p++]; } syn=11;p--; } else switch(ch) { case '<':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=24; token[m++]=ch; } else{ syn=23;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=25;token[0]=ch;break; case ';':syn=26;token[0]=ch;break; case '(':syn=27;token[0]=ch;break; case ')':syn=28;token[0]=ch;break; case '#':syn=0; token[0]=ch;break; default:syn=-1;token[0]=ch; } } void E(); void T(); void T1(); void T2(); void T3(); void F(); void G(); void H(); void I(); void error(); void success(); void error(){ printf(" (%s,error！)",token); } void success(){ printf(" success！",token); } main() { p=kk=0; scaner(); E(); } void F(){ if(syn==1) { scaner(); E(); if(syn==6) { scaner(); if((syn==0)&&(kk==0)) success(); } else { if(kk!=1) error(); kk=1; } } else { error(); } return; } void E(){ if (syn==10){ scaner(); T(); } else if(syn==0||syn==28){ } else error(); } void T(){ if(syn==17||syn==18){ scaner(); T1(); } else if(syn==0||syn==28){ } else error(); } void T1(){ if(syn==10){ scaner(); T2(); } else if(syn==0||syn==28){ } else error(); } void T2(){ if(syn==13){ scaner(); T3(); } else if(syn==0||syn==28){ } else error(); } void T3(){ if(syn==10){ scaner(); G(); } else if(syn==0||syn==28){ } else error(); } void G(){ if(syn==15){ scaner(); H(); } else if(syn==0||syn==28){ } else error(); } void H(){ if(syn==10){ scaner(); F(); } else if(syn==0||syn==28){ I(); } else error(); } void I(){ success(); return; }
四、实验步骤
1．待分析的语言的语法（参考P90）
2．将其改为文法表示，至少包含
–语句
–条件
–表达式
3. 消除其左递归
4. 提取公共左因子
5. SELECT集计算
6. LL(1)文法判断
7. 递归下降分析程序