ll(1).cpp

学编译原理时写的一个语法分析程序

//学编译原理时写的一个语法分析程序 
//一．[目的要求]
//① 对输入文法，由程序自动构造FIRST FOLLOW集 
//② 对输入文法，由程序自动生成它的LL(1)分析表；
//③ 对于给定的输入串，应能判断识别该串是否为给定文法的句型。
//二．[题目分析]
//该程序可分为如下几步：
//（1）读入文法 
//（2）判断正误 
//（3）若无误，判断是否为LL(1)文法 
//（4）若是，构造分析表；
//（5）由总控算法判断输入符号串是否为该文法的句型。
//[源程序清单]
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int count=0;              /*分解的产生式的个数*/
int number;               /*所有终结符和非终结符的总数*/
char start;               /*开始符号*/
char termin[50];          /*终结符号*/
char non_ter[50];         /*非终结符号*/
char v[50];               /*所有符号*/
char left[50];            /*左部*/
char right[50][50];       /*右部*/
char first[50][50],follow[50][50];       /*各产生式右部的FIRST和左部的FOLLOW集合*/
char first1[50][50];      /*所有单个符号的FIRST集合*/
char select[50][50];      /*各单个产生式的SELECT集合*/
char f[50],F[50];         /*记录各符号的FIRST和FOLLOW是否已求过*/
char empty[20];           /*记录可直接推出^的符号*/
char TEMP[50];            /*求FOLLOW时存放某一符号串的FIRST集合*/
int validity=1;           /*表示输入文法是否有效*/
int ll=1;                 /*表示输入文法是否为LL(1)文法*/
int M[20][20];            /*分析表*/
char choose;              /*用户输入时使用*/
char empt[20];            /*求_emp()时使用*/
char fo[20];              /*求FOLLOW集合时使用*/

/*******************************************
 判断一个字符是否在指定字符串中
********************************************/
int in(char c,char *p)
{
 int i;
 if(strlen(p)==0)
	return(0);
 for(i=0;;i++)
 { 
	if(p[i]==c)
		return(1);       /*若在，返回1*/
    if(i==strlen(p))
		return(0);       /*若不在，返回0*/
 }
}
/*******************************************
 得到一个不是非终结符的符号
********************************************/
char c()
{
 char c='A';
 while(in(c,non_ter)==1)
  c++;
 return(c);
}
/*******************************************
 分解含有左递归的产生式
********************************************/

void recur(char *point)
{                     /*完整的产生式在point[]中*/
 int j,m=0,n=3,k;
 char temp[20],ch;
 ch=c();           /*得到一个非终结符*/
 k=strlen(non_ter);
 non_ter[k]=ch;
 non_ter[k+1]='\0';
 for(j=0;j<=strlen(point)-1;j++)
 { 
  if(point[n]==point[0])
  {                          /*如果‘|’后的首符号和左部相同*/
   for(j=n+1;j<=strlen(point)-1;j++)
   {
    while(point[j]!='|'&&point[j]!='\0')
		temp[m++]=point[j++];
    left[count]=ch;
    memcpy(right[count],temp,m);
    right[count][m]=ch;
    right[count][m+1]='\0';
    m=0;
    count++;
    if(point[j]=='|')
    {
     n=j+1;
     break;
    }
   }
  }
  else
  {                          /*如果‘|’后的首符号和左部不同*/
   left[count]=ch;
   right[count][0]='^';
   right[count][1]='\0';
   count++;
   for(j=n;j<=strlen(point)-1;j++)
   {
       if(point[j]!='|')
           temp[m++]=point[j];
       else
    {
        left[count]=point[0];
        memcpy(right[count],temp,m);
        right[count][m]=ch;
        right[count][m+1]='\0';
     printf(" count=%d ",count);
     m=0;
        count++;
    }
   }
            left[count]=point[0];
      memcpy(right[count],temp,m);
      right[count][m]=ch;
        right[count][m+1]='\0';
   count++;
      m=0;
  }
 }
}
/*******************************************
 分解不含有左递归的产生式
********************************************/
void non_re(char *point)
{
 int m=0,j;
 char temp[20];
 for(j=3;j<=strlen(point)-1;j++)
 {
     if(point[j]!='|')
      temp[m++]=point[j];
	 else
	 {
		left[count]=point[0];
		memcpy(right[count],temp,m);
		right[count][m]='\0';
		m=0;
		count++;
	 }
 }
 left[count]=point[0];
 memcpy(right[count],temp,m);
 right[count][m]='\0';
 count++;
 m=0;
}
/*******************************************
 读入一个文法
********************************************/
char grammer(char *t,char *n,char *left,char right[50][50])
{
 char vn[50],vt[50];
 char s;
 char p[50][50];
 int i,j,k;
 printf("\n请输入文法的非终结符号串：");
    scanf("%s",vn);
 getchar();
    i=strlen(vn);
    memcpy(n,vn,i);
 n[i]='\0';
 printf("请输入文法的终结符号串：");
    scanf("%s",vt);
 getchar();
    i=strlen(vt);
    memcpy(t,vt,i);
 t[i]='\0';
    printf("请输入文法的开始符号：");
 scanf("%c",&s);
 getchar();
 printf("请输入文法产生式的条数：");
    scanf("%d",&i);
 getchar();
 for(j=1;j<=i;j++)
 {
  printf("请输入文法的第%d条（共%d条）产生式：",j,i);
  scanf("%s",p[j-1]);
  getchar();
 }
 for(j=0;j<=i-1;j++)
  if(p[j][1]!='-'||p[j][2]!='>')
  {
	  printf("\ninput error!");
      validity=0;
	  return('\0');
  }            /*检测输入错误*/
 for(k=0;k<=i-1;k++)
  {                        /*分解输入的各产生式*/
      //if(p[k][3]==p[k][0])
       // recur(p[k]);
	 // else
        non_re(p[k]);
 }
 return(s);
}
/*******************************************
 将单个符号或符号串并入另一符号串
********************************************/
void merge(char *d,char *s,int type)
{                 /*d是目标符号串，s是源串，type＝1，源串中的‘ ^ ’
				  一并并入目串；type＝2，源串中的‘ ^ ’不并入目串*/
 int i,j;
 for(i=0;i<=strlen(s)-1;i++)
 {
    if(type==2&&s[i]=='^')
      ;
    else
	{
      for(j=0;;j++)
	  {
        if(j<strlen(d)&&s[i]==d[j])
			break;
        if(j==strlen(d))
		{
			d[j]=s[i];
			d[j+1]='\0';
			break;
		}
	  }
	}
 }
}
/*******************************************
 求所有能直接推出^的符号
********************************************/
void emp(char c)
{                   /*即求所有由‘ ^ ’推出的符号*/
 char temp[10];
 int i;
 for(i=0;i<=count-1;i++)
 {
  if(right[i][0]==c&&strlen(right[i])==1)
  {
   temp[0]=left[i];
   temp[1]='\0';
   merge(empty,temp,1);
   emp(left[i]);
  }
 }
}
/*******************************************
 求某一符号能否推出‘ ^ ’
********************************************/
int _emp(char c)
{                  /*若能推出，返回1；否则，返回0*/
 int i,j,k,result=1,mark=0;
 char temp[20];
 temp[0]=c;
 temp[1]='\0';
 merge(empt,temp,1);
 if(in(c,empty)==1)
	return(1);
 for(i=0;;i++)
 {
	if(i==count)
		return(0);
	if(left[i]==c)         /*找一个左部为c的产生式*/
	{
        j=strlen(right[i]);    /*j为右部的长度*/
		if(j==1&&in(right[i][0],empty)==1)
			return(1);
		else if(j==1&&in(right[i][0],termin)==1)
			return(0);
		else 
		{
            for(k=0;k<=j-1;k++)
				if(in(right[i][k],empt)==1)
					mark=1;
				if(mark==1)
					continue;
				else
                {
					for(k=0;k<=j-1;k++)
					{
						result*=_emp(right[i][k]);
						temp[0]=right[i][k];
						temp[1]='\0';
						merge(empt,temp,1);
					}
				}
		}
		if(result==0&&i<count)
			continue;
		else if(result==1&&i<count)
			return(1);
		}
	}
}
/*******************************************
 判断读入的文法是否正确
********************************************/
int judge()
{
 int i,j;
 for(i=0;i<=count-1;i++)
 {
	if(in(left[i],non_ter)==0)
	{                    /*若左部不在非终结符中，报错*/
		printf("\nerror1!");
		validity=0;
		return(0);
	}
	for(j=0;j<=strlen(right[i])-1;j++)
	{
		if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='^')
		{               /*若右部某一符号不在非终结符、终结符中且不为‘ ^ ’，报错*/
			printf("\nerror2!");
			validity=0;
			return(0);
		}
	}
 }
 return(1);
}
/*******************************************
 求单个符号的FIRST
********************************************/
void first2(int i)
{                     /*i为符号在所有输入符号中的序号*/
 char c,temp[20];
 int j,k,m;
 c=v[i];
 char ch='^';
 emp(ch);
 if(in(c,termin)==1)       /*若为终结符*/
 {
     first1[i][0]=c;
     first1[i][1]='\0';
 }   
 else if(in(c,non_ter)==1)       /*若为非终结符*/
 {
	for(j=0;j<=count-1;j++)
	{
		if(left[j]==c)
		{
			if(in(right[j][0],termin)==1||right[j][0]=='^')
			{
				temp[0]=right[j][0];
				temp[1]='\0';
				merge(first1[i],temp,1);
			}
			else if(in(right[j][0],non_ter)==1)
			{
				if(right[j][0]==c)
					continue;
				for(k=0;;k++)
				if(v[k]==right[j][0])
					break;
				if(f[k]=='0')
				{   
					first2(k);
					f[k]='1';
				}
				merge(first1[i],first1[k],2);
                for(k=0;k<=strlen(right[j])-1;k++)
				{
					empt[0]='\0';
					if(_emp(right[j][k])==1&&k<strlen(right[j])-1)
					{
						for(m=0;;m++)
							if(v[m]==right[j][k+1])
								break;
							if(f[m]=='0')
							{
								first2(m);
								f[m]='1';
							}
						merge(first1[i],first1[m],2);
					}
					else if(_emp(right[j][k])==1&&k==strlen(right[j])-1)
					{
						temp[0]='^';
						temp[1]='\0';
						merge(first1[i],temp,1);
					}
					else 
					break;
				}
			}
		}
	}
 }
 f[i]='1';
}
/*******************************************
 求各产生式右部的FIRST
********************************************/
void FIRST(int i,char *p)
{
 int length;
 int j,k,m;
 char temp[20];