目錄
- 内容：
-
- 示例：
- 具體實作：
-
- C++代碼：
- 運作結果：
内容：
實作以下文法的遞歸下降分析：
示例：
對于以下代碼給出其遞歸下降文法分析過程：
{
i=2;
while(i<=100)
{
sum=sum+i;
i=i+2;
}
}
具體實作：
- 首先對上下文無關文法進行檢查，消除左遞歸和左公共因子，從邏輯上檢測避免死循環和低效率處理。
- 采用每個産生式的左邊的文法符号對應一個函數或過程的形式，編寫程式實作一個遞歸下降分析器。
- 文法分析是在詞法分析的基礎上進行的（關于詞法分析的實作，具體參見我的上篇部落格->【編譯原理與技術】詞法分析器（C++實作））。
C++代碼：
#include<cstdio>
#include<cstring>
#include<ctype.h>
#include<iostream>
using namespace std;
char prog[1000],ch,ch1,token[1000],filename[30];
int p=0,sym=0,n,line=1;
FILE *fpin;
const char *keyword[22]={"if","else","while","do","main","int","float","for"
"double","return","const","void","continue","break","char",
"signed","enum","long","switch","case","auto","unsigned"};
char keywordtable[20][20]; //存放保留字
char digittable[20][20]; //存放數字
char otherchartable[20][20]; //存放其他字元
char 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 program();
void block();
void stmts();
void stmt();
void Bool();
void expr();
void expr1();
void term();
void term1();
void factor();
void YufaBegin();
void CifaBegin();
void GetToken();
void match(string str);
int digit_num=0,keyword_num=0,otherchar_num=0,id_num=0,note_num=0;
int final_num=0,finalnum=0;
int flag_error=0; //0表示沒有錯誤，1表示有錯誤
int flagerror=0;
int main()
{
cout<<"請輸入源檔案名:";
while(1)
{
cin>>filename;
if((fpin=fopen(filename,"r"))!=NULL)//隻讀
{
break;
}
else
cout<<"檔案輸入錯誤！請輸入源檔案名：";
}
//将檔案内容存儲到prog中
do
{
ch=fgetc(fpin);
prog[p++]=ch;
}while(ch!=EOF);
//調用詞法分析部分
printf("-----------------\n");
printf("詞法分析結果如下:\n");
rewind(fpin);
ch=fgetc(fpin);
CifaBegin();
//調用文法分析部分
rewind(fpin);
ch=fgetc(fpin);
initialize();
YufaBegin();
return 0;
}
void YufaBegin(){
p=0;
while(1)
{
ch=prog[p++];
if(ch==EOF) break;
if(isalpha(ch)||ch=='_')
//a-z或A-Z時傳回非零值(不一定是1)，否則傳回零
{
alpha();
initialize();
}
else if(isdigit(ch)) //用來判斷字元lookahead是否為數字
{
digit();
initialize();
}
else if(ch=='\t'||ch==' '||ch=='\n')
{
continue;
}
else if(ch=='/')
{
ch=prog[p++];
if(ch=='*'||ch=='/')
{
note();
initialize();
}
else
{
p--; //把一個字元退回到輸入流中
//lookahead是寫入的字元，stdin是檔案流指針
strcpy(finaltable[final_num],"/"); //将"/"放到終結符号表中
strcpy(otherchartable[otherchar_num++],"/"); //将"/"放到其他符号表中
finaltableint[final_num++]=2; //"/"的序号是2
initialize();
}
}
/*else if(ch=='#'){
break;
}*/
else
{
otherchar();
initialize();
}
}
if(flag_error==0)
{
finaltableint[final_num]='\0';
printf("--------------------");
printf("\n文法分析過程如下:\n");
program();
if(finalnum==final_num)
printf("文法分析完成！");
}
}
void alpha()
{
int i=0,flag;
word[i++]=ch;
ch=prog[p++];
while(isalpha(ch)||isdigit(ch)) //将辨別符放到word數組中
{
word[i++]=ch;
ch=prog[p++];
}
p--;
flag=0;
for(i=0;i<21;i++)
{
if(strcmp(word,keyword[i])==0){
flag=1;
break;
}
}
//在這裡我隻實作了部分保留字，大家可根據要求自行增删
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 initialize()
{
for(int i=0;i<20;i++)
{
word[i]='\0';
}
}
void digit()
{
int i=0,flag;
word[i++]=ch;
ch=prog[p++];
while(isdigit(ch))
{
word[i++]=ch;
ch=prog[p++];
}
p--;
strcpy(digittable[digit_num++],word);
strcpy(finaltable[final_num],"num");//數字數組，序号為99
finaltableint[final_num++]=99;
}
void note()
{
int i=0;
while(1)
{
if(ch=='*')
{
ch=prog[p++];
if(ch=='/')
break;
else
{
p--;
word[i++]=ch;
}
}
else if(ch=='\n'){
break;
}
else
{
word[i++]=ch;
}
ch=prog[p++];
}
strcpy(notetable[note_num++],word);//将注釋的内容放入注釋表
}
void otherchar()
{
switch(ch){
case '!':
{
ch=prog[p++];
if(ch=='=')
{
strcpy(otherchartable[otherchar_num++],"!=");
strcpy(finaltable[final_num],"!=");
finaltableint[final_num++]=3;
}
else
{
p--;
error();
}
}
break;
case '=':
{
ch=prog[p++];
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;
p--;
}
}
break;
case '(':
strcpy(otherchartable[otherchar_num++],"(");
strcpy(finaltable[final_num],"(");
finaltableint[final_num++]=6;
break;
case ')':
strcpy(otherchartable[otherchar_num++],")");
strcpy(finaltable[final_num],")");
finaltableint[final_num++]=7;
break;
case ';':
strcpy(otherchartable[otherchar_num++],";");
strcpy(finaltable[final_num],";");
finaltableint[final_num++]=8;
break;
case '{':
strcpy(otherchartable[otherchar_num++],"{");
strcpy(finaltable[final_num],"{");
finaltableint[final_num++]=9;
break;
case '}':
strcpy(otherchartable[otherchar_num++],"}");
strcpy(finaltable[final_num],"}");
finaltableint[final_num++]=10;
break;
case '|':
{
ch=prog[p++];
if(ch=='|')
{
strcpy(otherchartable[otherchar_num++],"||");
strcpy(finaltable[final_num],"||");
finaltableint[final_num++]=11;
}
else
{
p--;
error();
}
}
break;
case '&':
{
ch=prog[p++];
if(ch=='&')
{
strcpy(otherchartable[otherchar_num++],"&&");
strcpy(finaltable[final_num],"&&");
finaltableint[final_num++]=12;
}
else
{
p--;
error();
}
}
break;
case '+':
strcpy(otherchartable[otherchar_num++],"+");
strcpy(finaltable[final_num],"+");
finaltableint[final_num++]=13;
break;
case '-':
strcpy(otherchartable[otherchar_num++],"-");
strcpy(finaltable[final_num],"-");
finaltableint[final_num++]=19;
break;
case '>':
{
ch=prog[p++];
if(ch=='=')
{
strcpy(otherchartable[otherchar_num++],">=");
strcpy(finaltable[final_num],">=");
finaltableint[final_num++]=14;
}
else
{
strcpy(otherchartable[otherchar_num++],">");
strcpy(finaltable[final_num],">");
finaltableint[final_num++]=15;
p--;
}
}
break;
case '<':
{
ch=prog[p++];
if(ch=='=')
{
strcpy(otherchartable[otherchar_num++],"<=");
strcpy(finaltable[final_num],"<=");
finaltableint[final_num++]=16;
}
else
{
strcpy(otherchartable[otherchar_num++],"<");
strcpy(finaltable[final_num],"<");
finaltableint[final_num++]=17;
p--;
}
}
break;
case '*':
strcpy(otherchartable[otherchar_num++],"*");
strcpy(finaltable[final_num],"*");
finaltableint[final_num++]=18;
break;
default:
error();
break;
}
}
void error()
{
flag_error=1;
printf("出現錯誤，停止分析！\n");
}
void program()
{
printf("program-->block\n");
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;
}
//cout<<"stmts():"<<finaltableint[finalnum]<<endl;
if(finaltableint[finalnum]==10)
{
printf("stmts-->null\n");
return;
}
printf("stmts-->stmt stmts\n");
stmt();
stmts();
}
void stmt()
{
if(flagerror==1)
{
return;
}
//cout<<"stmt():"<<finaltableint[finalnum]<<endl;
switch(finaltableint[finalnum])
{
case 1:
printf("stmt-->id=expr;\n");
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 stmt\n");
match("else");
stmt();
break;
}
else
{
printf("stmt-->if(bool) stmt\n");
break;
}
case 400:
printf("stmt-->while(bool) stmt\n");
match("while");
match("(");
Bool();
match(")");
stmt();
break;
case 500:
printf("stmt-->do stmt while(bool)\n");
match("do");
stmt();
match("while");
match("(");
Bool();
match(")");
break;
case 800:
printf("stmt-->break\n");
match("break");
break;
default:
printf("stmt-->block\n");
block();
break;
}
}
void Bool()
{
if(flagerror==1)
{
return;
}
expr();
switch(finaltableint[finalnum])
{
case 17:
printf("bool-->expr < expr\n");
match("<");
expr();
break;
case 16:
printf("bool-->expr <= expr\n");
match("<=");
expr();
break;
case 15:
printf("bool-->expr > expr\n");
match(">");
expr();
break;
case 14:
printf("bool-->expr >= expr\n");
match(">=");
expr();
break;
default:
printf("bool-->expr\n");
expr();
break;
}
}
void expr()
{
if(flagerror==1)
{
return;
}
printf("expr-->term expr1\n");
term();
expr1();
}
void expr1()
{
if(flagerror==1)
{
return;
}
//cout<<"expr1():"<<finaltableint[finalnum]<<endl;
switch(finaltableint[finalnum])
{
case 13:
printf("expr1-->+term expr1\n");
match("+");
term();
expr1();
break;
case 19:
printf("expr1-->-term expr1\n");
match("-");
term();
expr1();
break;
default:
printf("expr1-->null\n");
return;
}
}
void term()
{
if(flagerror==1)
{
return;
}
printf("term-->factor term1\n");
factor();
term1();
}
void term1()
{
if(flagerror==1)
{
return;
}
//cout<<"term1():"<<finaltableint[finalnum]<<endl;
switch(finaltableint[finalnum])
{
case 18:
printf("term1-->*factor term1\n");
match("*");
factor();
term1();
break;
case 2:
printf("term1-->/factor term1\n");
match("/");
factor();
term1();
break;
default:
printf("term1-->null\n");
return;
}
}
void factor()
{
if(flagerror==1)
{
return;
}
//cout<<"factor():"<<finaltableint[finalnum]<<endl;
switch(finaltableint[finalnum])
{
case 6:
printf("factor-->(expr)\n");
match("(");
expr();
match(")");
break;
case 1:
printf("factor-->id\n");
match("id");
break;
case 99:
printf("factor-->num\n");
match("num");
break;
default:
flagerror=1;
break;
}
}
void match(string str)
{
char cha[20];
for(int i=0;i<20;i++){
cha[i]='\0';
}
for(int k=0;k<str.length();k++){
cha[k]=str[k];
}
//cout<<finaltable[finalnum]<<endl;
//cout<<cha<<endl;
if(strcmp(finaltable[finalnum],cha)==0){
//cout<<"1"<<endl;
}
else
{
flagerror=1;
return;
}
finalnum++;
}
//--------------
//詞法分析器部分
void CifaBegin()
{
p=0;
do
{
GetToken();//啟動字元識别函數
//if(ch==EOF) break;
switch(sym)//列印字元狀态
{
case 1:cout<<"("<<line<<" "<<token<<" "<<"辨別符"<<")"<<endl;break;
case 2:cout<<"("<<line<<" "<<token<<" "<<"保留字"<<")"<<endl;break;
case 3:cout<<"("<<line<<" "<<token<<" "<<"整型"<<")"<<endl;break;
case 31:cout<<"("<<line<<" "<<token<<" "<<"浮點型"<<")"<<endl;break;
case 32:cout<<"("<<line<<" "<<token<<"S"<<" "<<"短類型"<<")"<<endl;break;
case 33:cout<<"("<<line<<" "<<token<<"L"<<" "<<"長類型"<<")"<<endl;break;
case 34:cout<<"("<<line<<" "<<token<<"O"<<" "<<"八進制數"<<")"<<endl;break;
case 35:cout<<"("<<line<<" "<<token<<"H"<<" "<<"十六進制數"<<")"<<endl;break;
case 4:cout<<"("<<line<<" "<<token<<" "<<"特殊符号"<<")"<<endl;break;
case -1:cout<<"("<<line<<" "<<"錯誤！"<<")"<<endl;break;
default:break;
}
}while(ch!=EOF);
p=0;
}
void GetToken()
{
sym=0;
//先把token[]數組清空
for (n=0;n<1000;n++)
{
token[n]='\0';
}
n=0;
ch=prog[p++];
ch1=prog[p];
//跳過空格，回車，tab的識别
while(ch==' '||ch=='\t')
{
ch=prog[p++];
}
if(ch=='\n'){
line++;
return;
}
if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch=='_'))
{
//辨別符 狀态1
sym=1;
do{
token[n++]=ch;
ch=prog[p++];
}while ((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'));
//比較辨別符與keyword的關鍵字是否相同，若相同轉為狀态2
for(n=0;n<2;n++)
{
if(strcmp(token,keyword[n])==0){
sym=2;
break;
}
}
p--;
return;
}
else if (ch>='0'&&ch<='9')
{
//識别到數字，置狀态為3
sym=3;
do
{
token[n++]=ch;
ch=prog[p++];
if(ch=='.'){
sym=31;
token[n++]=ch;
ch=prog[p++];
}
if(ch=='S'){
sym=32;
ch=prog[p++];
}
if(ch=='L'){
sym=33;
ch=prog[p++];
}
if(ch=='O'){
sym=34;
ch=prog[p++];
}
if(ch=='H'){
sym=35;
ch=prog[p++];
}
}while(ch>='0'&&ch<='9');
p--;
return;
}
//跳過注釋的内容
else if(ch=='/' && ch1=='*')
{
p++;
do{
ch=prog[p++];
ch1=prog[p++];
if(ch=='\n'){
line++;
}
}while(ch!='*'||ch1!='/');
return;
}
else if(ch=='/'&& ch1=='/')
{
p++;
do{
ch=prog[p++];
}while(ch!='\n');
line++;
return;
}
else if(ch=='='&& ch1=='='){
p++;
sym=4;
token[0]='=';
token[1]='=';
return;
}
else if(ch=='<'&& ch1=='='){
p++;
sym=4;
token[0]='<';
token[1]='=';
return;
}
else if(ch=='>'&& ch1=='='){
p++;
sym=4;
token[0]='>';
token[1]='=';
return;
}
else if(ch=='!'&& ch1=='='){
p++;
sym=4;
token[0]='!';
token[1]='=';
return;
}
else if(ch=='&'&& ch1=='&'){
p++;
sym=4;
token[0]='&';
token[1]='&';
return;
}
else if(ch=='|'&& ch1=='|'){
p++;
sym=4;
token[0]='|';
token[1]='|';
return;
}
else
{
switch(ch)//識别關鍵符号
{
case '=':
case '<':
case '>':
case '/':
case '+':
case '-':
case '*':
case '{':
case '}':
case ';':
case '(':
case ')':
case ',':
case '\'':
case '\"':sym=4;token[0]=ch;break;
default:sym=-1;break;
}
}
return;
}
運作結果：