赞
踩
- #include<iostream>
- #include<string>
- #include <cstdlib>
- #include <cstdio>
- #include <map>
- #include <vector>
- #include <cctype>
-
- using namespace std;
-
- typedef struct CSS
- {
- string left;
- string right;//定义产生式的右部
- }CSS;
- bool Zero (CSS *p, int n)
- {
- int i,j;
- for(i=0;i<n;i++)//循环n次,即遍历所有产生式
- {
- for(j=0;j<p[i].left.length();j++)//遍历产生式左部每一个字符
- {
- if(p[i].left[j]>='A'&&p[i].left[j]<='Z')//判断字符是否是非终结符
- break;
- }
- if(j==p[i].left.length())
- {
- cout<<"该文法不是0型文法"<<endl;
- return 0;
- break;
- }
- }
- if(i==n)
- return 1;//如果每个产生时都能找到非终结符
- }
- bool First(CSS *p , int n )//判断1型文法
- {
- int i;
- if(Zero(p,n)) //先判断是否是0型文法
- {
- for(i=0;i<n;i++)
- {
- if((p[i].left.length()>p[i].right.length())&&p[i].right.length()!=NULL)//判断产生式左部长度是否大于右部
- break;
- }
- if (i == n )
- return 1;
- else
- {
- cout<<"该文法是0型文法"<<endl;
- return 0;
- }
- }
- else
- return 0;
- }
- bool Second( CSS*p,int n)//判断2型文法
- {
- int i;
- if(First(p,n))//同上,先判断低级文法是否成立
- {
- for(i=0;i<n;i++)//同上,遍历所有文法产生式
- {
- if((p[i].left.length()!=1)||!(p[i].left[0]>='A'&&p[i].left[0]<='Z'))
- break;
- }
- if(i==n)
- return 1;
- else
- {
- cout<<"该文法是1型文法"<<endl;
- return 0;
- }
- }
- else
- return 0;
- }
-
- void Third(CSS *p,int n)//判断3型文法
- {
- int i;
- if(Second(p,n))//同上,先判断是否是2型文法
- {
- for(i=0;i<n;i++)//同上,遍历文法所有的产生式
- {
- if((p[i].right.length()==0)||(p[i].right.length()>=3)||(p[i].right[0]>='A'&&p[i].right[0]<='Z'))//判断产生式右部字符个数是否在12之间,判断右部第一个字符是否是非终结符
- break;
- }
- if(i==n)
- {
- for(i=0;i<n;i++)
- {
- if(p[i].right.length()==2)
- {
- if(!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))
- break;
- }
- }
- if(i==n)
- {
- cout<<"该文法属于3型文法"<<endl;
- }
- else
- cout<<"该文法属于2型文法"<<endl;
- }
- else
- cout<<"该文法属于2型文法"<<endl;
- }
- else
- cout<<"结束"<<endl;
- }
-
- int main ( )
- {
- CSS *p = new CSS[100];
- map<char,bool> dic;
- map<char,bool> dic2;
- vector<char> VN;
- vector<char> VT;
- string input1,input2,input3;
- cout <<"请输入文法:"<<endl;
- cin >> input1;
- cout << "请输入VN: "<<endl;
- cin >> input2;
- for ( int i = 0 ; i < input2.length() ; i++ )
- if ( isalnum ( input2[i] ) )
- {
- VN.push_back ( input2[i] );
- dic[input2[i]]=true;
- }
- cout <<"请输入产生式规则的个数:"<<endl;
- int n;
- cin >> n;
- cout <<"请输入产生式规则:"<<endl;
- int cnt = 0;
- for ( int i = 0 ; i < n ; i++ )
- {
- input3.erase ();
- cin >> input3;
- bool flag = false;
- for ( int j = 0 ; j < input3.length() ; j++ )
- if ( input3[j] =='|' ) flag = true;
- if ( flag )
- {
- string temp;
- int j;
- for ( j = 0 ; j < input3.length(); j++ )
- {
- if ( input3[j] ==':' )
- {
- temp = input3.substr(0,j);
- j = j+3;
- break;
- }
- }
- for ( int k =j ; k < input3.length() ; k++ )
- {
- if ( isalnum ( input3[k] ) )
- {
- p[cnt].left = temp;
- int tt = k;
- for ( ;tt < input3.length(); tt++ )
- if ( input3[tt]=='|' ) break;
- if ( input3[tt] == '|' ) tt--;
- p[cnt].right = input3.substr( k , tt-k+1 );
- if ( dic[input3[k]] == false )
- {
- VT.push_back ( input3[k] );
- dic[input3[k]] = true;
- }
- cnt++;
- k = tt;
- }
- }
- continue;
- }
- for ( int j = 0 ; j < input3.length() ; j++ )
- {
- if ( input3[j]== ':' )
- {
- p[cnt].left=input3.substr(0,j);
- p[cnt].right=input3.substr(j+3,input3.length());
- cnt++;
- break;
- }
- }
- for ( int j = 0 ; j < input3.length() ; j++ )
- {
- if ( isalnum( input3[j] ) )
- {
- if ( dic[input3[j]] ) continue;
- VT.push_back ( input3[j] );
- dic[input3[j]] = true;
- }
- }
- }
- cout << input1 << " = ( {";
- for ( int i = 0 ; i < VN.size()-1 ; i++ )
- cout << VN[i] << ",";
- cout << VN[VN.size()-1] <<"},{";
- for ( int i = 0 ; i < VT.size()-1 ; i++ )
- cout << VT[i] << ",";
- cout << VT[VT.size()-1] << "},";
- cout << "P," << input1[2] << " )"<<endl;
- cout << "P : " << endl;
- vector<string> output;
- vector<string> head[500];
- string pre[500];
- for ( int i = 0 ; i < cnt ; i++ )
- {
- int x = p[i].left[0];
- head[x].push_back ( p[i].right );
- pre[x] = p[i].left;
- }
- for ( int i = 0 ; i < 500 ; i++ )
- {
- if ( head[i].size() == 0 ) continue;
- string temp = pre[i]+" ::= ";
- for ( int j = 0 ; j < head[i].size() ; j++ )
- {
- temp += head[i][j];
- if ( j != head[i].size() - 1 ) temp += " | ";
- }
- output.push_back ( temp );
- }
- for ( int i = 0 ; i < output.size() ; i ++ )
- cout << output[i] << endl;
- Third ( p , cnt );
- }
-
-
-
-
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <cstring>
- #include <cctype>
-
- using namespace std;
- const int VSIZE= 300;
-
- class Principle
- {
- public:
- string left;
- string right;
- Principle ( const char* , const char* );
- };
- //只考虑不包含varepsilon的情况,且所有元素均只包含一个字母
- vector<char> VN;//非终结符集
- vector<char> VT;//终结符集
- vector<Principle> principle;//产生式的集合
- int type[VSIZE];//每个字符的类型
-
- void init();//清理工作
- int get_type(char);//1代表是非终结符,2代表是终结符
- bool set_type(char,int);//设置一个字符的类型
- int get_result ( );//获得输入的文法的类型
-
- int main ( )
- {
- char buf[1000];
- char ** elements;
- while ( true )
- {
- puts("输入VN:");
- gets( buf );
- for ( int i = 0 ; i < strlen(buf); i++ )
- {
- char ch = buf[i];
- if ( !isupper(ch) ) continue;
- if ( get_type(ch) ) continue;
- VN.push_back ( ch );
- set_type(ch,1);
- }
- puts("输入VT:");
- gets( buf );
- for ( int i = 0 ; i < strlen(buf); i++ )
- {
- char ch = buf[i];
- if ( !islower(ch) ) continue;
- if ( get_type(ch) ) continue;
- VT.push_back ( ch );
- set_type(ch,2);
- }
- puts("输入产生式:(格式为[A::=...a...]), 输入\"exit\"作为结束");
- while ( true )
- {
- gets ( buf );
- if ( !strcmp(buf , "exit" ) ) break;
- int i;
- for ( i = 0 ; i < strlen(buf) ; i++ )
- if ( buf[i] == ':' )
- {
- buf[i] = 0;
- i = i+3;
- break;
- }
- principle.push_back ( Principle( buf , buf+i ) );
- printf ( "%s|%s|\n" , buf , buf+i );
- }
- int flag = get_result();
- switch ( flag )
- {
- case -1:
- puts("产生式中出现未知字符");
- break;
- case 0:
- puts("该文法为0型文法");
- break;
- case 1:
- puts("该文法为1型文法");
- break;
- case 2:
- puts("该文法为2型文法");
- break;
- case 3:
- puts("该文法为左线性型文法");
- break;
- case 4:
- puts("该文法为右线性型文法");
- break;
- }
- }
- return 0;
- }
-
- Principle::Principle ( const char*l , const char* r )
- {
- left = l;
- right = r;
- }
-
- //判断字符串是否包含未知字符
- bool hasError ( const string& s )
- {
- for ( int i = 0 ; i < s.length() ; i++ )
- if ( !get_type(s[i]) ) return true;
- return false;
- }
-
- //判断是否为0型文法
- bool isZero ( )
- {
- for ( int i = 0 ; i < principle.size() ; i++ )
- if ( hasError(principle[i].left) ) return false;
- else if ( hasError(principle[i].right)) return false;
- return true;
- }
-
- //判断一个0型文法是否为1型文法
- bool isOne ( )
- {
- for ( int i = 0 ; i < principle.size(); i++ )
- if ( principle[i].left.length() > principle[i].right.length() )
- return false;
- return true;
- }
-
- //判断一个1型文法是否为2型文法
- bool isTwo ( )
- {
- for ( int i = 0 ; i < principle.size() ; i++ )
- {
- string left = principle[i].left;
- if ( left.size() != 1 ) return false;
- if ( get_type(left[0]) != 1 ) return false;
- }
- return true;
- }
-
- //判断一个2型文法是否为左线性文法
- bool isLeftThree ()
- {
- for ( int i = 0 ; i < principle.size() ; i++ )
- {
- string right = principle[i].right;
- for ( int j = 1; j < right.length() ; j++ )
- if ( get_type(right[j]) != 2 ) return false;
- }
- return true;
- }
-
- //判断一个2型文法是否为右线性文法
- bool isRightThree ()
- {
- for ( int i = 0 ; i < principle.size() ; i++ )
- {
- string right = principle[i].right;
- for ( int j = 0 ; j < right.length()-1; j++ )
- if ( get_type(right[j]) != 2 )
- return false;
- }
- return true;
- }
-
- int get_result ( )
- {
- if ( !isZero() ) return -1;
- if ( !isOne() ) return 0;
- if ( !isTwo() ) return 1;
- if ( isLeftThree() ) return 3;
- if ( isRightThree() ) return 4;
- return 2;
- }
-
- void init ( )
- {
- VN.clear();
- VT.clear();
- principle.clear();
- memset ( type , 0 , sizeof ( type ) );
- }
-
- int get_type ( char ch )
- {
- return type[ch];
- }
-
- bool set_type ( char ch , int x )
- {
- type[ch] = x;
- return true;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。