ll(1)wenfa.cpp

LL! 文法。。功能有限。只能。只能测试非直接做递归的文法。

#include<iostream.h>
#include "conio.h"
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
char str[10][10],yjs[20];
int number,flag[10]={0,0,0,0,0,0,0,0,0,0};
int Fflag[10]={0,0,0,0,0,0,0,0,0,0};
int v=0,lenth=0;
//定义相关的结构
typedef struct node
{
char a[20];
struct node *next;
} node;

typedef struct hnode
{
char c;
struct node *next;
} hnode;

typedef struct fode
{
char a[20];
int len;
} fode;

typedef struct wode
{
char a[20];
int len;
} wode;

typedef struct lsstack
{
char ls[20];
int top;
} lsstack;

typedef struct H
{
char a[20];
int top;
} H;

typedef struct wlh
{
char a[20];
}  wlh;

typedef struct wo
{
char zjf[20];
int len;
} wo;

wlh graph[20][20];
wo E;
H stack;
lsstack B;
fode First[20];
wode Follow[20];
hnode head[20];

int f2(char c)
{
if((c>='a'&&c<='z')||c=='+'||c=='-'||c=='*'||c=='/'||c=='@'||c=='('||c==')'||c=='^'||c==',')
return 1;
else
return 0;
}

int f3(char *a,int t)
{
for(int i=0;i<t;i++)
if(a[i]=='@')
return 1;
return 0;
}

int f10(char c)
{
for(int i=0;i<number;i++)
if(c==head[i].c)
return i;
return(-1);
}
//
void insert1(int k1,int k2,int sum2)
{
int flag; 
 int sum1;
for(int j=0;j<sum2;j++)
{
flag=1; 
 sum1=Follow[k1].len;
for(int i=0;i<sum1;i++)
{
if(First[k2].a[j]==Follow[k1].a[i])
{
flag=0;
break;
}
}
if(flag==1)
{
if(First[k2].a[j]!='@')
{
Follow[k1].a[Follow[k1].len++]=First[k2].a[j];

}
}
}
}
//
void insert2(int k1,int k2,int sum2)
{
int sum1,flag;
for(int j=0;j<sum2;j++)
{
flag=1;
sum1=Follow[k1].len;
for(int i=0;i<sum1;i++)
{
if(Follow[k2].a[j]==Follow[k1].a[i])
{
flag=0;
break;
}
}
if(flag==1)
Follow[k1].a[Follow[k1].len++]=Follow[k2].a[j];
}
}

int f9(char c,int j)
{
char ch;
node *p;
ch=head[j].c;
for(int i=0;i<number;i++)
{
if(i!=j)
{
p=head[i].next;
while(p)
{  
int z=0;
while(p->a[z]!='\0')
{
if((p->a[z]==ch)&&p->a[z+1]=='\0')
{
if(head[i].c==c)
return 1;
else
p=p->next;
}
else
z++;
}//while
p=p->next;
}//out while
}//if
}//for
return 0;
}//f9

void f1(int i)
{
if(flag[i]==0)
{
node *p;
p=head[i].next;
while(p)
{
              if(f2(p->a[0]))
              {
                First[i].a[First[i].len++]=p->a[0];
                p=p->next;
              }
              else
              {
                 int z=0;
                 while(p->a[z]!='\0')
                {
                  for(int j=0;j<number;j++)
                  {
                     if(head[j].c==p->a[z])
                     break;
                 }
                 f1(j);
                 for(int t=0;t<First[j].len;t++)
                 if(First[j].a[t]!='@')
                 First[i].a[First[i].len++]=First[j].a[t];
                 if(f3(First[j].a,First[j].len))
                 {
                     if(p->a[z+1]=='\0')
                     First[i].a[First[i].len++]='@';
                     if(f2(p->a[z+1]))
                     {
                         First[i].a[First[i].len++]=p->a[z+1];
                         break;
                     }
                     z++;
                 }
                 else
                 break;
             }
             p=p->next;
        }//else
       }//while
       flag[i]=1;
}//if
}//f1
void f4(int i)
{
 if(Fflag[i]==0)
 {
        node *p;
        char c;
        c=head[i].c;
        if(i==0)
        Follow[i].a[Follow[i].len++]='#';
        for(int j=0;j<number;j++)
        {
         p=head[j].next;
         while(p)
         { int z=0;
             while(p->a[z]!='\0')
             {
                 if(p->a[z]!=c)
                 z++;
                 else
                 break;
             }
             if(p->a[z]=='\0') //not fine letter
p=p->next;
else//fine the letter
{
if(p->a[z+1]!='\0')
{
if(f2(p->a[z+1]))//later is zjf
{
Follow[i].a[Follow[i].len++]=p->a[z+1];
p=p->next;
}
else //later is fzjf
{
int k=0;
k=f10(p->a[z+1]);
insert1(i,k,First[k].len);

if(f3(First[k].a,First[k].len))
{
f4(j);
insert2(i,j,Follow[j].len);
}
p=p->next;
}
}
else //later have not a letter
{
if(c==head[j].c)
p=p->next;
else if(f9(c,j))
{
if(Fflag[j]==1)
{
insert2(i,j,Follow[j].len);
p=p->next;
}
else
p=p->next;
}
else
{
f4(j);
insert2(i,j,Follow[j].len);
p=p->next;
}
                 }//else
             }//out else
         }//while
        }//for
         Fflag[i]=1;
 }//if
}//f4
int f11(char c)//look for if have the same letter
{
       for(int i=0;i<E.len;i++)
       if(c==E.zjf[i])
       return 0;
       return 1;
}
void fs()//look for the zjfnode
{
       node *p;
       for(int i=0;i<number;i++)
       {
        p=head[i].next;
        while(p)
        {
            int z=0;
            while(p->a[z]!='\0')
            {
                if(f2(p->a[z])&&p->a[z]!='@')
{
if(f11(p->a[z]))
E.zjf[E.len++]=p->a[z];
}
z++;
}
p=p->next;
}
}
}
int f12(char c)
{
for(int i=0;i<E.len;i++)
if(c==E.zjf[i])
return i;
return (-1);
}
void kong ()
{
for(int i=0;i<number;i++)
{
for(int j=0;j<E.len;j++)
strcpy(graph[i][j].a,"0");
}
}
void f16()
{
int z;
z=v;
while(yjs[z]!='\0')
{
cout<<yjs[z];
z++;
}
cout<<"        ";
}
void f17()
{
int z=0;
while(z<=stack.top)
{
cout<<stack.a[z];
z++;
}
cout<<"    ";
}
void diandao(int m,int n)
{

int z=0;B.top=-1;
B.ls[++B.top]='#';
while(graph[m][n].a[z]!='\0') //error
{
B.ls[++B.top]=graph[m][n].a[z];
z++;
}
while(B.ls[B.top]!='#')
{
stack.a[++stack.top]=B.ls[B.top];
B.top--;
}
cout<<lenth++<<"   ";
f17();
f16();
cout<<head[m].c<<"->"<<graph[m][n].a<<endl;
}
void print()
{
char x;int m=-1,n=-1,flag11=1;
stack.top=-1;
stack.a[++stack.top]='#';
stack.a[++stack.top]=head[0].c;
while(flag11)
{
x=stack.a[stack.top];
stack.top--;
if(f2(x))
{
if(x==yjs[v])
{
v++;
cout<<lenth++<<"   ";
f17();
f16();
cout<<endl;
}
else
{
cout<<"error!"<<endl;
exit(-1);
}
}
else if(x=='#')
{
if(x==yjs[v])
{
flag11=0;
cout<<"success!"<<endl;
}
else
{
cout<<"error!"<<endl;
exit(-1);
}
}
else
{
m=f10(x);
n=f12(yjs[v]);
if(!strcmp(graph[m][n].a,"0\0"))
{
cout<<"error!"<<endl;
exit(-1);
}
else
{
if(strcmp(graph[m][n].a,"@\0")!=0)
{
diandao(m,n);
}
else
{
cout<<lenth++<<"    ";
f17();
f16();
cout<<x<<"->"<<'@'<<endl;
}
}
}
}
}
void print1()
{
for(int i=0;i<number;i++)
{
for(int j=0;j<First[i].len;j++)
{
cout<<First[i].a[j]<<"   ";
}
cout<<endl;
}
}
void print2()
{
for(int i=0;i<number;i++)
{
for(int j=0;j<Follow[i].len;j++)
{
cout<<Follow[i].a[j]<<"    ";
}
cout<<endl;
}
}
void print3()
{    cout<<"    ";
for(int t=0;t<E.len;t++)
cout<<E.zjf[t]<<"      ";
cout<<endl;
for(int i=0;i<number;i++)
{ cout<<head[i].c<<":"<<"  ";
for(int j=0;j<E.len;j++)
{
cout<<graph[i][j].a<<"      ";
}
cout<<endl;
}
}
void yw()
{
node *p;      char c;
for(int i=0;i<number;i++)
{
p=head[i].next;c=head[i].c;
while(p)
{
if(p->a[0]==c)
{
        cout<<"error!,please enter LL(1) wen fa!"<<endl;
        exit(-1);
       }
       p=p->next;
     }
 }
}
 
void main()
{
 int flag=1,i=0,k,m;
 node *p,*s=0;
 cout<<"enter chan shen shi:"<<endl;
       while(flag)
       {
        gets(str[i++]);
        if(!strcmp(str[i-1],"#\0"))
            flag=0;
       }
       number=i-1;
       cout<<"enter the string:"<<endl;
       gets(yjs);
       for(i=0;i<number;i++)
       {
        int j=0,t=0;
        flag=1;
        head[i].c=str[i][j];
        j+=3;
        while(str[i][j]!='\0')
        {
            p=new node;
            while(str[i][j]!='|'&&str[i][j]!='\0')
            {
                p->a[t]=str[i][j];
                t++;
                j++;
            }
            p->a[t]='\0';t=0;p->next=0;
            if(str[i][j]=='|')
            j++;
            if(flag==1)
            {
                head[i].next=p;
                s=p; flag=0;
            }
            else
            {
                s->next=p;
                s=p;
            }
        }//while
       }//for
       yw();
       for(i=0;i<number;i++)  //qiu first
        f1(i);
       for(i=0;i<number;i++)//qiu follow
       f4(i);
       fs();//look for the zjfnode
       E.zjf[E.len++]='#';
       kong();//let the graph is empty first
       for(int t=0;t<number;t++) //creat graph
       {
             p=head[t].next;
        while(p)
        {
 
            if(f2(p->a[0])&&p->a[0]!='@')
            {
                    k=f12(p->a[0]);
                    strcpy(graph[t][k].a,p->a);
            }
            else if(!f2(p->a[0]))
            {
                k=f10(p->a[0]);
                for(int b=0;b<First[k].len;b++)
                {
 
                     if(First[k].a[b]!='@')
                    {
                         m=f12(First[k].a[b]);
 
                         strcpy(graph[t][m].a,p->a);
                    }
                }
            }
            else if(p->a[0]=='@')
            {
                k=f10(head[t].c);
                for(int b=0;b<Follow[k].len;b++)
                {
                    m=f12(Follow[k].a[b]);
                    strcpy(graph[t][m].a,"@");
 
                }
            }
            p=p->next;
        }//while
}//for
       cout<<"FIRST:"<<endl;
       print1();
       getchar(); //control the stape
       cout<<"FOLLOW:"<<endl;
       print2();
       getchar();
       cout<<"THE GRAPH:"<<endl;
       print3();
       getchar();
       cout<<(lenth++)<<"   #"<<head[0].c<<"   "<<yjs<<"        "<<endl;
       print();
}