遞歸下降分析
程式輸入輸出示例:
( 1 ) E→TG
( 2 ) G→ + TG |- TG | ε
( 3 ) T→FS
( 4 ) S → * FS |/ FS | ε
( 5 ) F→(E) | i
輸出的格式如下:
(1)輸出一個以#結束的符号串(包括+ - * / i #):
(2)輸出結果:i+i*i#為合法符号串
備注:輸入一符号串如i+i*#,要求輸出為"非法的符号串"
// //
// //
// E→TG //
// G→+TG|-TG|ε //
// T→FS //
// S→*FS|/FS|ε //
// F→(E)|i //
// //
#include < iostream >
using namespace std;
char A[ 100 ]; // 用于存放符号串,不能多于100個字元
int i = 0 ; // 記錄目前要判斷的字元位置
void E(); // E()
void G(); // G()
void T(); // 為每個非終節符構造一個子程式
void S(); // S()
void F(); // F()
void match( int & k); // 此程式隻是此執行加1操作,為了取到後一個終結符
void main( )
... {
cout<<"+++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
cout<<"+ 遞歸下降分析 +"<<endl;
cout<<"+ 作者:楊浩 +"<<endl;
cout<<"+ 日期:2008年4月 +"<<endl;
cout<<"+++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
cout<<"請輸入一個有待判斷的符号串(以#結尾): ";
cout<<"輸入的符号串： ";
cin>>A;
cout<<"輸出的符号串： "<<A<<endl<<endl;
cout<<"比對的結果： ";
E();
if(A[i]!='#')
...{
cout<<"此輸入串不合法"<<endl;
cout<<"不合法的原因： 不比對開始于在第"<<i+1<<"個終結符處，沒有發現與"<<A[i]<<"相比對的文法"<<endl;
}
}
void E() // E->TG
... {
T();
G();
}
void G() // G->+TG|-TG|ε
... {
// 這裡分了三個情況，“+”“-”以及“ε”三種情況。
// 如果是前兩種，則很好，本步驟比對 。如果沒有比對，則預設取到“ε”
if(A[i]=='+') //比對“+”
...{
match(i);
T();
G();
}
else if(A[i]=='-') //比對“-”
...{
match(i);
T();
G();
}
else return; //沒有與之比對，則預設為空
}
void T() // T->FS
... {
F();
S();
}
void S() // S->*FS|/FS|ε
... {
// 這裡分了三個情況，“*”“/”以及“ε”三種情況。
// 如果是前兩種，則很好，本步驟比對 。如果沒有比對，則預設取到“ε”
// 情況雷同G()
if(A[i]=='*')
...{
match(i);
F();
S();
}
else if(A[i]=='/')
...{
match(i);
F();
S();
}
else return;
}
void F() // F->(E)|i
... {
if(A[i]=='(')
...{
match(i);
if(A[i]=='#') //如果是“#”則說明已經搜尋比對完畢了，肯定合法
...{
cout<<"此輸入串不合法"<<endl;
cout<<"不合法的原因： 沒有與'('相配對的')'"<<endl;
exit(0);
}
E();
if(A[i]==')')
...{
match(i);
if(A[i]=='#') //如果是“#”則說明已經搜尋比對完畢了，肯定合法
...{
if(A[i-2]=='i')
...{
cout<<" 此輸入串合法 ";
exit(0);
}
else
...{
cout<<"此輸入串不合法"<<endl;
cout<<"不合法的原因： 前面沒有與'('相配對的'i'"<<endl;
exit(0);
}
}
}
}
else if(A[i]=='i')
...{
match(i); //比對後繼續判斷有沒有到結束
if(A[i]=='#') //如果是“#”則說明已經搜尋比對完畢了，肯定合法
...{
if(A[i-2]=='(')
...{ cout<<"此輸入串不合法"<<endl;
cout<<"不合法的原因： 沒有與'('相配對的')'"<<endl;
exit(0);
}
else
...{
cout<<" 此輸入串合法 ";
exit(0);
}
}
return ;
}
else if (A[i]=='#')
...{
cout<<"此輸入串不合法"<<endl;
cout<<"不合法的原因： 不比對開始于在第"<<i<<"個終結符處，沒有發現與"<<A[i-1]<<"相比對的文法"<<endl;
exit(0);
}
else
...{
cout<<"此輸入串不合法"<<endl;
cout<<"不合法的原因： 不比對開始于在第"<<i+1<<"個終結符處，沒有發現與"<<A[i]<<"相比對的文法"<<endl;
exit(0);
}
}
void match( int & k) // 如果比對的話,取下一個終結符
... {
k++;
}
輸出正确的還行，錯誤方面的分析有些被動，因為情況太多了，我隻把我想到的各種情況都寫上了，至于其他的，還請各位大哥幫小弟偵查一下。嘿嘿，謝謝啦！~~~