panduan.txt

判断文法类型

#include<iostream>
#include<string>

using namespace std;

struct WF       //定义一个产生式结构体
{
string left; //定义产生式的左部
string right; //定义产生式的右部
};

bool Zero(WF *p,int n)   //判断0型文法
{
int flag=0,count=0; //定义一个零时计数器，来判断某些情况可曾发生
for(int i=0;i<n;i++) //循环n次，即遍历所有产生式
{
   for(int j=0;j < int (p[i].left.length());j++) //遍历产生式左部每一个字符
   {
    if(p[i].left[j]>='A'&&p[i].left[j]<='Z')   //判断字符是否是非终结符
    flag++;
   }
   if(flag>0)
   {
    flag=0;
    count++; //计数器加一
   }
   else  
    break; //如果flag为0，即找不到非终结符，跳出循环，结束

}

if(count==n) //如果每个产生时都能找到非终结符
   return 1;
else
{
   cout<<"该文法不是0型文法！\n";
   return 0;
}
}


bool First(WF *p,int n)    //判断1型文法
{
int flag=0;
if(Zero(p,n))         //先判断是否是0型文法
{
   for(int i=0;i<n;i++) //同上
   {
    if(p[i].left.length()>p[i].right.length()) //判断产生式左部长度是否大于右部
     flag++;
   }
}
else
   flag--;

if(flag>0)
{
   cout<<"该文法是0型文法！\n";
   return 0;
}
else if(flag==0)
     return 1;
else
   return 0;

}

bool Second(WF *p,int n)     //判断2型文法
{
int flag=0;
if(First(p,n))     //同上，先判断低级文法是否成立
{
   for(int i=0;i<n;i++)   //同上，遍历所有文法产生式
    if( (p[i].left.length()!=1) || !(p[i].left[0]>='A'&&p[i].left[0]<='Z') ) //判断产生式左部长度是否为一，左部第一个是否是非终结符
    {
     flag++;
     break;
    }
}
else
   flag--;

if(flag>0)
{
   cout<<"该文法是1型文法！\n";
   return 0;
}
else if(flag==0)
{
   return 1;
}
else
   return 0;
}


bool Third(WF *p,int n)    //判断3型文法
{
int flag=0;
if(Second(p,n))   //同上，先判断是否是2型文法
{
   for(int 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之间，判断右部第一个字符是否是终结符
    {
     //cout<<"********";调试用的
     flag++;
     break;
    }
    else if(p[i].right.length()==2)   //如果右部字符个数为2
            if(!(p[i].right[1]>='A'&&p[i].right[1]<='Z')) //右部第二个字符是否是非终结符
      {
             flag++;
       break;
      }
}
else
   flag--;

if(flag>0)
{
   cout<<"该文法是2型文法！\n";
   return 0;
}
else if(flag==0)
{
   cout<<"该文法是3型文法！\n";
   return 1;
}
else
{
   cout<<"结束！\n";
   return 0;
}
}


void Chang(WF *p,string input,int i)    //改变文法产生式的形式
{
for(int j=0;j < int (input.size());j++)
   if( input[j] == '-' )
   {
    p[i].left=input.substr(0,j);
    p[i].right=input.substr(j+2,int (input.size()));
   }
}


int main()
{
int i,n;
string input;
cout<<"请输入文法产生式个数N：";
cin>>n;
    WF *p=new WF[n];   // 初始化产生式数组
for(i=0;i<n;i++)   //输入产生式数组
{
   input.erase(); //清除
   cin>>input;   //输入
   Chang(p,input,i); //改变输入数据的形式
}


Third(p,n);     //调用文法类型判断，自顶向下

return 0;
}