赞
踩
Problem Description
若有文法G[S]:
S→pA | qB,
A→cAd | a
B→dB|b
编写递归下降法的语法分析程序,判断文法G所能接受的串。
Input 输入多行由终止符构成的符号串,输入EOF结束。
Output 判断每行输入的符号串在语法结构上是否合法,如果是合法的语法结构,输出"syntax correct";否则输出"syntax error"。
Sample Input
pccadd#
pccdda#
Sample Output
syntax correct
syntax error
C++代码实现
#include "iostream" using namespace std; string str; int flag=1; void S(string string1);//1.开始符S void A(string string1);//2.非终结符A void B(string string1);//3.非终结符B void S(string s){ str = s; if(str[0]=='p'){ str = s.substr(1,s.length()); A(str); } if (str[0]=='q'){ str = s.substr(1,s.length()); B(str); } } void A(string s){ str = s; if (str[0]=='c'){ str = s.substr(1,s.length()); A(str); if(str[0]=='d') str = str.substr(1,str.length()); //else flag = 0; } else if (s[0]=='a'){ str = str.substr(1,str.length()); } else flag=0; } void B(string s){ str = s; if (str[0]=='d'){ str = s.substr(1,s.length()); B(str); } else if (str[0]=='b'){ str = str.substr(1,str.length()); } else flag=0; } int main(){ while (cin>>str&&str!="EOF"){ S(str); if (str[0]=='#'&&flag==1)cout<<"syntax correct"<<endl; else cout<<"syntax error"<<endl; } return 0; }
//stack方式 #include <iostream> #include <stack> using namespace std; string S; int f(string s){ //cout<<s.length()<<endl; int i,j; if(s[0]=='p'){ if(s[1]=='a')return 1; else{ for(i=1;i<s.length();i++){ if(s[i]=='c')continue; if(s[i]=='a'){ for(j=i+1;j<i+i;j++){ if(s[j]=='d')continue; } if(j+1==s.length())return 1; else return -1; } else return -1; } } } else if(s[0]=='q'){ int i=0; if(s[1]=='b')return 1; else{ for(i = 1;i<=s.length()-3;i++){ if(s[i]=='d')continue; else return-1; } if(s[i]=='b'&&s[i+1]=='#')return 1; else return -1; } } else{ return -1; } } int main() { while(cin>>S&&S!="EOF"){ if(f(S)==1)cout<<"syntax correct"<<endl; else cout<<"syntax error"<<endl; } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。