概述
实验3 递归下降法的语法分析器
一、实验目的
学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。
二、实验内容
用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。
这里只要求实现部分产生式，文法的开始符号为program。
program → block
block → { stmts }
stmts →stmt stmts |
stmt → id = expr ;
| if ( bool ) stmt
| if ( bool) stmt else stmt
| while (bool) stmt
| do stmt while (bool ) ;
| break ;
| block
bool → expr < expr
| expr <= expr
| expr > expr
| expr >= expr
| expr
expr → expr + term
| expr - term
| term
term → term * factor
| term / factor
| factor
factor → ( expr ) | id | num
三、实验要求
１．个人完成，提交实验报告。
２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。
测试程序片断：
{
i = 2;
while (i <=100)
{
sum = sum + i;
i = i + 2;
}
}
对应的推导过程为：
program block
{ stmts }
{ stmt stmts }
{ id = expr ; stmts }
{ id = num; stmts }
{ id = num; stmt stmts }
{ id = num; while (bool) stmt stmts }
{ id = num; while (expr<= expr) stmt stmts }
{ id = num; while (id <= expr) stmt stmts }
{ id = num; while (id <= num) stmt stmts }
{ id = num; while (id <= num) block stmts }
{ id = num; while (id <= num) { stmts }stmts }
．．．．．．．
四、实验思路
词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable[100][20]，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable[0]=”id”，finaltable[1]=”=”，finaltable[2]=”num”。并且，为了以后能够方便使用switch() case 语句，另外再定义一个一维整型数组finaltableint[100]，用于存放一个数字和finaltable[100][20]中的字符串对应。这里，我们定义if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800，< = 17，<= = 16，> = 15，>= = 14，+ = 13，&&=12，||=11，}=10，{=9，；=8；)=7，(=6，= = 5，== = 4，!= =3，/=2，id =1，keyword=0，num=99，*=18，- = 19.相比词法分析器，词法分析的时候，是以单个字符为一个单位，而语法分析，我们以字符串为单位，这些字符串即finaltable[100][20]中的字符串。编写的过程中涉及几个问题
，1、如何把每一步的迭代都显示出来？对于这个问题，可以在每个非终结符函数的开头输出对应的迭代即可。
2、在应用文法的时候，应该首先消除左递归，这是至关重要的，该实验我们只要消除expr()和term()的左递归即可。
3、if语句二义性处理。对于这个问题，我们只要再往后看一个字符串，看其是否是else，如果是，则匹配if ( bool) stmt else stmt，否则匹配if ( bool ) stmt。
4、对于空选择，如何处理？一开始的时候，我选择暂时忽略。
五、实验代码
#include<stdio.h>
#include<string.h>
#include <ctype.h>
/*
if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800，< = 17，<= = 16，> = 15，>= = 14，+ = 13，&&=12，||=11，}=10，{=9，；=8；)=7，(=6，= = 5，== = 4，!= =3，/=2，id =1，keyword=0，num=99，*=18，- = 19
*/
char *keyword[8]={"if","for","else","while","do","float","int","break"};
char keywordtable[20][20],re_keywordtable[20][20];
char digittable[20][20],re_digittable[20][20];
char otherchartable[20][20],re_otherchartable[20][20];
char idtable[20][20],re_idtable[20][20];
char notetable[20][20];
char finaltable[100][20];
int finaltableint[100];
char word[20];
void initialize();
void alpha();
void digit();
void error();
void otherchar();
void note();
void print();
void prin();
void check();
void program();
void block();
void stmts();
void stmt();
void Bool();
void expr();
void expr1();
void term();
void term1();
void factor();
void match(char *t);
int digit_num=0,keyword_num=0,otherchar_num=0,id_num=0,note_num=0;
int redigit_num=1,rekeyword_num=1,reotherchar_num=1,reid_num=1;
int final_num=0,finalnum=0;
int flag_error=0;
int flagerror=0;
char lookahead;
void main()
{
printf("请输入要分析的语句:n");
initialize();
lookahead=getchar();
while(1)
{
if(isalpha(lookahead))
{
alpha();
initialize();
}
else if(isdigit(lookahead))
{
digit();
initialize();
}
else if(lookahead=='t'||lookahead==' ')
{
;
}
else if(lookahead=='n')
break;
else if(lookahead=='/')
{
lookahead=getchar();
if(lookahead=='*')
{
note();
initialize();
}
else
{
ungetc(lookahead,stdin);
strcpy(finaltable[final_num],"/");
strcpy(otherchartable[otherchar_num++],"/");
finaltableint[final_num++]=2;
initialize();
}
}
else
{
otherchar();
initialize();
}
lookahead=getchar();
}
check();
if(flag_error==0)
{
printf("词法分析结果如下:n");
print();
prin();
program();
if(finalnum==final_num)
printf("语法分析完成!n");
}
}
void alpha()
{
int i=1,flag;
char ch;
ch=lookahead;
word[0]=ch;
ch=getchar();
while(isalpha(ch)||isdigit(ch))
{
word[i++]=ch;
ch=getchar();
}
ungetc(ch,stdin);
flag=0;
for(i=0;i<8;i++)
{
if(strcmp(word,keyword[i])==0)
flag=1;
}
if(flag==1)
{
strcpy(keywordtable[keyword_num++],word);
strcpy(finaltable[final_num],word);
if(strcmp(word,"if")==0)
finaltableint[final_num++]=100;
if(strcmp(word,"for")==0)
finaltableint[final_num++]=200;
if(strcmp(word,"else")==0)
finaltableint[final_num++]=300;
if(strcmp(word,"while")==0)
finaltableint[final_num++]=400;
if(strcmp(word,"do")==0)
finaltableint[final_num++]=500;
if(strcmp(word,"float")==0)
finaltableint[final_num++]=600;
if(strcmp(word,"int")==0)
finaltableint[final_num++]=700;
if(strcmp(word,"break")==0)
finaltableint[final_num++]=800;
}
else
{
strcpy(idtable[id_num++],word);
strcpy(finaltable[final_num],"id");
finaltableint[final_num++]=1;
}
}
void digit()
{
int i=1,flag;
char ch;
ch=lookahead;
word[0]=ch;
ch=getchar();
while(isalpha(ch)||isdigit(ch))
{
word[i++]=ch;
ch=getchar();
}
ungetc(ch,stdin);
flag=0;
for(i=0;word[i]!=' ';i++)
{
if(word[i]<'0'||word[i]>'9')
flag=1;
}
if(flag==1)
{
strcpy(idtable[id_num++],word);
strcpy(finaltable[final_num],"id");
finaltableint[final_num++]=1;
}
else
{
strcpy(digittable[digit_num++],word);
strcpy(finaltable[final_num],"num");
finaltableint[final_num++]=99;
}
}
void otherchar()
{
char ch;
ch=lookahead;
switch(ch){
case '!':
{
ch=getchar();
if(ch=='=')
{
strcpy(otherchartable[otherchar_num++],"!=");
strcpy(finaltable[final_num],"!=");
finaltableint[final_num++]=3;
}
else
{
ungetc(ch,stdin);
error();
}
}
break;
case '=':
{
ch=getchar();
if(ch=='=')
{
strcpy(otherchartable[otherchar_num++],"==");
strcpy(finaltable[final_num],"==");
finaltableint[final_num++]=4;
}
else
{
strcpy(otherchartable[otherchar_num++],"=");
strcpy(finaltable[final_num],"=");
finaltableint[final_num++]=5;
ungetc(ch,stdin);
}
}
break;
case '(':
strcpy(otherchartable[otherchar_num++],"(");
strcpy(finaltable[final_num],"(");
finaltableint[final_num++]=6; // ( 6
break;
case ')':
strcpy(otherchartable[otherchar_num++],")");
strcpy(finaltable[final_num],")");
finaltableint[final_num++]=7; // ) 7
break;
case ';':
strcpy(otherchartable[otherchar_num++],";");
strcpy(finaltable[final_num],";");
finaltableint[final_num++]=8; // ; 8
break;
case '{':
strcpy(otherchartable[otherchar_num++],"{");
strcpy(finaltable[final_num],"{");
finaltableint[final_num++]=9; // { 9
break;
case '}':
strcpy(otherchartable[otherchar_num++],"}");
strcpy(finaltable[final_num],"}");
finaltableint[final_num++]=10; // } 10
break;
case '||':
strcpy(otherchartable[otherchar_num++],"||");
strcpy(finaltable[final_num],"||");
finaltableint[final_num++]=11; // || 11
break;
case '&&':
strcpy(otherchartable[otherchar_num++],"&&");
strcpy(finaltable[final_num],"&&");
finaltableint[final_num++]=12; //&& 12
break;
case '+':
strcpy(otherchartable[otherchar_num++],"+");
strcpy(finaltable[final_num],"+");
finaltableint[final_num++]=13; // + 13
break;
case '-':
strcpy(otherchartable[otherchar_num++],"-");
strcpy(finaltable[final_num],"-");
finaltableint[final_num++]=19; // - 19
break;
case '>':
{
ch=getchar();
if(ch=='=')
{
strcpy(otherchartable[otherchar_num++],">=");
strcpy(finaltable[final_num],">=");
finaltableint[final_num++]=14;
} // >= 14
else
{
strcpy(otherchartable[otherchar_num++],">");
strcpy(finaltable[final_num],">");
finaltableint[final_num++]=15; // > 15
ungetc(ch,stdin);
}
}
break;
case '<':
{
ch=getchar();
if(ch=='=')
{
strcpy(otherchartable[otherchar_num++],"<=");
strcpy(finaltable[final_num],"<=");
finaltableint[final_num++]=16;
} // <= 16
else
{
strcpy(otherchartable[otherchar_num++],"<");
strcpy(finaltable[final_num++],"<");
finaltableint[final_num++]=17; //< 17
ungetc(ch,stdin);
}
}
break;
case '*':
strcpy(finaltable[final_num],"*");
finaltableint[final_num++]=18; // * 18
break;
default:
error();break;
}
}
void error()
{
flag_error=1;
printf("出现错误,中止分析!n");
}
void initialize()
{
int i;
for(i=0;i<20;i++)
{
word[i]=' ';
}
}
void check()
{
int i,j,flag;
strcpy(re_keywordtable[0],keywordtable[0]);
for(i=1;i<keyword_num;i++)
{
flag=0;
for(j=0;j<rekeyword_num;j++)
{
if(strcmp(keywordtable[i],re_keywordtable[j])==0)
{
flag=1;
break;
}
}
if(flag==0)
strcpy(re_keywordtable[rekeyword_num++],keywordtable[i]);
}
strcpy(re_digittable[0],digittable[0]);
for(i=1;i<digit_num;i++)
{
flag=0;
for(j=0;j<redigit_num;j++)
{
if(strcmp(digittable[i],re_digittable[j])==0)
{
flag=1;
break;
}
}
if(flag==0)
strcpy(re_digittable[redigit_num++],digittable[i]);
}
strcpy(re_otherchartable[0],otherchartable[0]);
for(i=1;i<otherchar_num;i++)
{
flag=0;
for(j=0;j<reotherchar_num;j++)
{
if(strcmp(otherchartable[i],re_otherchartable[j])==0)
{
flag=1;
break;
}
}
if(flag==0)
strcpy(re_otherchartable[reotherchar_num++],otherchartable[i]);
}
strcpy(re_idtable[0],idtable[0]);
for(i=1;i<id_num;i++)
{
flag=0;
for(j=0;j<reid_num;j++)
{
if(strcmp(idtable[i],re_idtable[j])==0)
{
flag=1;
break;
}
}
if(flag==0)
strcpy(re_idtable[reid_num++],idtable[i]);
}
}
void note()
{
char ch;
int i=0;
ch=getchar();
while(1)
{
if(ch=='*')
{
ch=getchar();
if(ch=='/')
break;
else
{
ungetc(ch,stdin);
word[i++]=ch;
}
}
else
{
word[i++]=ch;
}
ch=getchar();
}
strcpy(notetable[note_num++],word);
}
void print()
{
int i;
//printf("Keywords:n");
if(keyword_num!=0)
for(i=0;i<rekeyword_num;i++)
printf("< %s, >n",re_keywordtable[i]);
//printf("nDigits:n");
if(digit_num!=0)
for(i=0;i<redigit_num;i++)
printf("< number,%s >n",re_digittable[i]);
//printf("nOtherchars:n");
if(otherchar_num!=0)
for(i=0;i<reotherchar_num;i++)
printf("< comparison,%s >n",re_otherchartable[i]);
//printf("nId:n");
if(id_num!=0)
for(i=0;i<reid_num;i++)
printf("< id,%s >n",re_idtable[i]);
if(note_num!=0)
{
printf("注释:n");
for(i=0;i<note_num;i++)
printf("%sn",notetable[i]);
}
printf("词法分析完成!n");
}
void prin()
{
int i;
finaltableint[final_num]=' ';
printf("语法分析结果如下：n");
for(i=0;i<final_num;i++)
printf("%s",finaltable[i]);
printf("n语法分析过程如下:n");
}
void program()
{
printf("program-->blockn");
block();
if(flagerror==1)
{
error();
return;
}
}
void block()
{
if(flagerror==1)
{
return;
}
printf("block-->{stmts}n");
match("{");
stmts();
match("}");
}
void stmts()
{
if(flagerror==1)
{
return;
}
if(finaltableint[finalnum]==10)
{
printf("stmts-->nulln");
return;
}
printf("stmts-->{stmt stmts}n");
stmt();
stmts();
}
void stmt()
{
if(flagerror==1)
{
return;
}
switch(finaltableint[finalnum]){
case 1:
printf("stmt-->id=exprn");
match("id");
match("=");
expr();
match(";");
break;
case 100:
match("if");
match("(");
Bool();
match(")");
stmt();
if(strcmp(finaltable[finalnum],"else")==0)
{
printf("stmt-->if(bool) stmt else stmtn");
match("else");
stmt();
break;
}
else
{
printf("stmt-->{if(bool) stmtn");
break;
}
case 400:
printf("stmt-->while(bool) stmtn");
match("while");
match("(");
Bool();
match(")");
stmt();
break;
case 500:
printf("stmt-->do stmt while(bool)n");
match("do");
stmt();
match("while");
match("(");
Bool();
match(")");
match(";");
break;
case 800:
printf("stmt-->break;n");
match("break");
match(";");
break;
default:
printf("stmt-->blockn");
block();
break;
}
}
void Bool()
{
if(flagerror==1)
{
return;
}
expr();
switch(finaltableint[finalnum]){
case 17:
printf("bool-->expr<exprn");
match("<");
expr();
break;
case 16:
printf("bool-->expr<=exprn");
match("<=");
expr();
break;
case 15:
printf("bool-->expr>exprn");
match(">");
expr();
break;
case 14:
printf("bool-->expr>=exprn");
match(">=");
expr();
break;
default:
printf("bool-->exprn");
expr();
break;
}
}
void expr()
{
if(flagerror==1)
{
return;
}
printf("expr-->term expr1n");
term();
expr1();
}
void expr1()
{
if(flagerror==1)
{
return;
}
switch(finaltableint[finalnum]){
case 13:
printf("expr1-->+term expr1n");
match("+");
term();
expr1();
break;
case 19:
printf("expr1-->-term expr1n");
match("-");
term();
expr1();
break;
default:
printf("expr1-->nulln");
return;
}
}
void term()
{
if(flagerror==1)
{
return;
}
printf("term-->factor term1n");
factor();
term1();
}
void term1()
{
if(flagerror==1)
{
return;
}
switch(finaltableint[finalnum]){
case 18:
printf("term1-->*factor term1n");
match("*");
factor();
term1();
break;
case 2:
printf("term1-->/factor term1n");
match("/");
factor();
term1();
break;
default:
printf("term1-->nulln");
return;
}
}
void factor()
{
if(flagerror==1)
{
return;
}
switch(finaltableint[finalnum]){
case 6:
printf("fatcor-->(expr)n");
match("(");
expr();
match(")");
break;
case 1:
printf("factor-->idn");
match("id");
break;
case 99:
printf("factor-->numn");
match("num");
break;
default:
flagerror=1;
break;
}
}
void match(char *t)
{
if(strcmp(finaltable[finalnum],t)==0)
;
else
{
flagerror=1;
return;
}
finalnum++;
}
六、实验结果
正确的语法
｛i=6;sum=i+sum｝
对于不正确的语句
{i=4;while(i<=30){sum=sum+i;i=i+1}}/少了一个;
最后
以上就是忧郁曲奇为你收集整理的编译原理实验3 递归下降法的语法分析器的全部内容，希望文章能够帮你解决编译原理实验3 递归下降法的语法分析器所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复