Alter Code: LL1Parser

LL(k) Parser mit k=1 ist eins der einfachsten Parser für kontextfreie Grammatiken. Die Zahl k bedeutet die Symbole, die nach vorne geschaut werden, um zu entscheiden welche Regel zutrifft.

Die Grammatik wird dabei in der BNF beschrieben. Dabei gilt die Einschränkung, dass keine Linksrekursion erlaubt ist.

// written by André Betz 
// http://www.andrebetz.de

#include <stdio.h>
#include <stdlib.h>
#define  EPSILON '&'

/*
    LL(1)-Parser-Generator - keine Linksrekursion erlaubt
    A->AB; => 
    Umformen von EBNF -> BNF
    A->a(b)c => A->aBc,B->b
    A->a[b]c => A->aBc,B->b,B->&
    A->a{b}c => A->aBc,B->bB,B->&
    A->a|b   => A->a,A->b
    A->UV&   => A->UVX,X->&
*/

/* Baumstruktur */
typedef struct node
{
    struct node *suc;
    struct node *next;
    struct node *First;
    struct node *Follow;
    int            Nr;
    int            term;
    int            Epsfrei;
    char        sym;
    char        mark;
} *pnode;

/* erzeugt neuen Knoten */
pnode NewNode()
{
  pnode neu;
  char *point;
  int cnt;

  neu = (pnode)malloc(sizeof(struct node));
  point = (char*)neu;
  for(cnt=0;cnt<sizeof(struct node);cnt++)   {       point[cnt] = 0;   }   return neu; } /* schaut ob Zeichen im Baum schon vorhanden ist */ int isThere(pnode gram,char Sym) {     pnode HTrans = gram;     pnode Suc;     while(HTrans)     {         Suc = HTrans;         while(Suc)         {             if(Sym==Suc->sym) return 1;
            Suc = Suc->suc;
        }
        HTrans = HTrans->next;
    }
    return 0;
}

/* gibt Zeiger auf Element mit der Produktion zurück */
pnode getTransBegin(pnode gram,char Sym)
{
    pnode HTrans = gram;

    while(HTrans)
    {
        if(Sym==HTrans->sym) return HTrans;
        HTrans = HTrans->next;
    }
    return NULL;
}

/* gibt Zeiger auf Produktion in der sich das Symbol befindet */
pnode getTransInside(pnode suc,char Sym)
{
    pnode Suc = suc;

    while(Suc)
    {
        if(Sym==Suc->sym) return Suc;
        Suc = Suc->suc;
    }
    return NULL;
}

/* erzeugt aus der BNF-Grammatik einen Baum */
pnode Transform(char* Gram)
{
    pnode tree = NULL;
    pnode next;
    pnode help;
    pnode NTrans;
    int   GPtr = 0;
    int   NTr = 2;
    int      T = 0;
    int   NT = 0;
    char  Sym;

    while(Gram[GPtr]!=0)
    {
        Sym = Gram[GPtr];

        if(Sym!='=')
        {
            if(Sym!='.')
            {
                help = NewNode();

                if(Sym>='A'&&Sym<='Z')                 {                     help->Nr =NT;
                    if(!isThere(tree,Sym)) NT++;
                }
                else
                {
                    if(Sym!=EPSILON)
                    {
                          help->term = 1;
                        help->Nr = T;
                        if(!isThere(tree,Sym)) T++;
                    }
                    else 
                    {
                        help->term = 2;
                        Sym = 0;
                    }
                }
                help->sym     = Sym;

                switch(NTr) 
                {
                case 2:
                    tree   = help;
                    NTrans = help;
                    NTr = 0;
                    break;
                case 1:
                    NTrans->next = help;
                    NTrans = help;
                    NTr = 0;
                    break;
                default:
                    next->suc = help;
                    break;
                }
                next = help;
            }
            else NTr = 1;
        }
        GPtr++;
    }
    return tree;
}

/* untersucht auf Epsilonfreiheit */
void EpsilonTable(pnode Gram)
{
    pnode HTrans = Gram;
    pnode Suc;
    pnode help;
    int cntEps;
    int cntT;
    int cntNT;
    int cntSum;
    int cntFrei1;
    int cntNFrei1;
    int cntUnent1;
    int cntFrei2;
    int cntNFrei2;
    int cntUnent2;
    int Unent = 0;

    while(HTrans)
    {
        Suc = HTrans->suc;
        cntEps = 0;
        cntT   = 0;
        cntNT  = 0;
        if(HTrans->Epsfrei==0)
        {
            while(Suc)
            {
                if(Suc->term==2)  cntEps++;
                if(Suc->term==1)  cntT++;
                if(Suc->term==0)  cntNT++;
                Suc = Suc->suc;
            }
            cntSum = cntEps + cntT + cntNT;
            if(cntT)           HTrans->Epsfrei = 2; /* Nein */ 
            if(cntSum==cntEps) HTrans->Epsfrei = 1; /* Ja */
            if(cntNT)          Unent = 1;
        }
        HTrans = HTrans->next;
    }

    while(Unent)
    {
        Unent = 0;
        HTrans = Gram;
    
        while(HTrans)
        {
            if(HTrans->Epsfrei==0)
            {
                Suc = HTrans->suc;

                cntFrei2   = 0; 
                cntNFrei2  = 0; 
                cntUnent2  = 0;

                while(Suc)
                {
                    help = Gram;
                    cntFrei1   = 0; 
                    cntNFrei1  = 0; 
                    cntUnent1  = 0; 
          
                    while(help)
                    {
                        help = getTransBegin(help,Suc->sym);

                        if(help!=NULL)
                        {
                               if(help->Epsfrei==0) cntUnent1++;
                            if(help->Epsfrei==1) cntNFrei1++;
                            if(help->Epsfrei==2) cntFrei1++;
                            help = help->next;
                        }
                    }
        
                    cntSum = cntUnent1 + cntFrei1 + cntNFrei1;
                    if(cntUnent1)         cntUnent2++;
                    if(cntSum==cntNFrei1) cntNFrei2++;
                    if(cntFrei1)          cntFrei2++;
                    Suc = Suc->suc;
                }

                cntSum = cntUnent2 + cntFrei2 + cntNFrei2;
                if(cntUnent2)         Unent = 1;
                if(cntSum==cntNFrei2) HTrans->Epsfrei = 1;
                if(cntFrei2)          HTrans->Epsfrei = 2;
          
            }
            HTrans = HTrans->next;
        }
    }

}

/* erzeugt First-Menge */
void FirstSet(pnode Gram)
{
    pnode HTrans = Gram;
    pnode Suc;
    pnode help;
    pnode help2;
    pnode HFst;
    int Unent = 1;
    int Epsfrei;
    int SchoHier;

    while(Unent)
    {
        HTrans = Gram;
        Unent = 0;
        while(HTrans)
        {
            Suc = HTrans->suc;
            Epsfrei = 1;    
      
            while((Epsfrei)&&(HTrans->Epsfrei==2)&&(Suc))
            {
                Epsfrei = 0;
                  help = Gram;

                if(Suc->term==0)
                {
                    while(help)
                    {
                         help = getTransBegin(help,Suc->sym);

                        if(help!=NULL)
                        {
                            if(help->Epsfrei==1) Epsfrei = 1;
                            help2 = help->First;

                            while(help2)
                            {
                                 HFst = HTrans;
                                 SchoHier = 1;
                                while((HFst->First)&&(SchoHier==1)) 
                                {
                                     HFst = HFst->First;
                                     if(help2->sym==HFst->sym) SchoHier = 0;
                                }

                                if(SchoHier==1)
                                {
                                    HFst->First = NewNode();
                                    HFst = HFst->First;
                                    HFst->sym = help2->sym;
                                    Unent = 1;
                                }
                                help2 = help2->First;
                            }
                              help = help->next;
                        }
                    }
                }
                else
                {
                    HFst = HTrans;
                    SchoHier = 1;
                    while((HFst->First)&&(SchoHier==1)) 
                    {
                        HFst = HFst->First;
                        if(Suc->sym==HFst->sym) SchoHier = 0;
                    }

                    if(SchoHier==1)
                    {
                        HFst->First = NewNode();
                        HFst = HFst->First;
                        HFst->sym = Suc->sym;
                        Unent = 1;
                    }
                }
                Suc = Suc->suc;
            }
            HTrans = HTrans->next;
        }
    }
}

/* erzeugt Follow-Menge */
void FollowSet(pnode Gram)
{
    pnode HTrans = Gram;
    pnode HTrans2;
    pnode HFlw;
    pnode HFst;
    pnode Suc;
    pnode help;
    int SchoHier;
    int Unent = 1;
    int Epsfrei;

    while(Unent)
    {
        Unent = 0;
        while(HTrans) /* HTrans entspricht dem A */ 
        {
            HTrans2 = Gram;
            while(HTrans2) /* sucht nach dem Zeichen von HTrans in den Produktionen */
            {
                help = HTrans2->suc; /* HTrans2 entspricht dem B */
                while(help)
                {
                    help = getTransInside(help,HTrans->sym);
                    if(help!=NULL)
                    {
                        help = help->suc; /* help entspricht dem Beta */
                        Epsfrei = 1;
                        while(Epsfrei)
                        {
                            Epsfrei = 0;
                            if(help==NULL)
                            {
                                Suc = HTrans2->Follow;

                                while(Suc)
                                {
                                    HFlw = HTrans;
                                    SchoHier = 1;

                                    while((HFlw->Follow)&&(SchoHier==1)) 
                                    {
                                        HFlw = HFlw->Follow;
                                        if(Suc->sym==HFlw->sym) SchoHier = 0;
                                    }
        
                                    if(SchoHier==1)
                                    {
                                        HFlw->Follow = NewNode();
                                        HFlw = HFlw->Follow;
                                        HFlw->sym = Suc->sym;
                                        Unent = 1;
                                    }

                                    Suc = Suc->Follow;
                                }
                            }
                            else
                            {
                                if(help->term==1)
                                {
                                    HFlw = HTrans;
                                    SchoHier = 1;
                                    while((HFlw->Follow)&&(SchoHier==1)) 
                                    {
                                        HFlw = HFlw->Follow;
                                        if(help->sym==HFlw->sym) SchoHier = 0;
                                    }

                                    if(SchoHier==1)
                                    {
                                        HFlw->Follow = NewNode();
                                        HFlw = HFlw->Follow;
                                        HFlw->sym = help->sym;
                                        Unent = 1;
                                    }
                                }
                                if(help->term==0)
                                {
                                    Suc = Gram;
        
                                    while(Suc)
                                    {
                                        Suc = getTransBegin(Suc,help->sym);
                                        if(Suc!=NULL)
                                        {
                                            HFst = Suc->First;
                                            while(HFst)
                                            {
                                                HFlw = HTrans;
                                                SchoHier = 1;
                        
                                                while((HFlw->Follow)&&(SchoHier==1)) 
                                                {
                                                    HFlw = HFlw->Follow;
                                                    if(HFst->sym==HFlw->sym) SchoHier = 0;
                                                }

                                                if(SchoHier==1)
                                                {
                                                    HFlw->Follow = NewNode();
                                                    HFlw = HFlw->Follow;
                                                    HFlw->sym = HFst->sym;
                                                    Unent = 1;
                                                }
                                                HFst = HFst->First;
                                            }
                                            if(Suc->Epsfrei==1)    Epsfrei = 1;
                                            Suc = Suc->next;
                                        }
                                    }
                                }
                            }
                            if(Epsfrei==1) help = help->suc;
                        }
                    }
                }
                HTrans2 = HTrans2->next;
            }
            HTrans = HTrans->next;
        }
    }
}

void ShowTables(pnode Gram)
{
    pnode HTrans = Gram;
    pnode Suc;
    pnode HFst;
    pnode HFlw;
    int count = 0;

    printf("Num\tTrans\tEps\tFirst\tFollow\n");
    while(HTrans)
    {
        printf("%d\t%c->",count,HTrans->sym);
        Suc  = HTrans->suc;
        HFst = HTrans->First;
        HFlw = HTrans->Follow;
        while(Suc)
        {
            printf("%c",Suc->sym);
            Suc = Suc->suc;
        }

        if(HTrans->Epsfrei==1)    printf("\tj");
        else                    printf("\tn");

        printf("\t{");
        while(HFst)
        {
            printf("%c",HFst->sym);
            HFst = HFst->First;
            if(HFst!=NULL) printf(",");
        }
        printf("}\t{");
        while(HFlw)
        {
            printf("%c",HFlw->sym);
            HFlw = HFlw->Follow;
            if(HFlw!=NULL) printf(",");
        }
        printf("}\n");
        count++;
        HTrans = HTrans->next;
    }
    printf("\n");
}

void ShowStack(pnode FrstEl)
{
    pnode help = FrstEl;
    while(help)
    {
        printf("%c",help->sym);
        help = help->next;
    }
    printf("\n");
}

void ParseLL1(pnode Gram,char* Text)
{
    pnode FrstEl  = NULL;
    pnode help   = NULL;
    pnode FSym;
    pnode HTrans;
    pnode Ersetz;
    pnode Next;
    int   count = 0;
    char  Sym;

    FrstEl = NewNode();
    Sym = Text[count];
    FrstEl->sym  = Gram->sym;
    FrstEl->term = Gram->term;

    while((Sym!=0)&&(FrstEl!=NULL))
    {

        printf("%c\t",Sym);
        ShowStack(FrstEl);

        if(FrstEl->term==1)
        {
            FSym = FrstEl->next;
            free(FrstEl);
            FrstEl = FSym;
            count++;
            Sym = Text[count];
        }
        else
        {
            HTrans = Gram;
            Ersetz = NULL;
            while(HTrans) /* sucht nach der zu ersetzenden Regel */
            {
                HTrans = getTransBegin(HTrans,FrstEl->sym); /* Geht dei Regeln durch */
                if(HTrans!=NULL)
                {
                    /* FSym enthält die zu vergleichenden Zeichen */
                    if(HTrans->Epsfrei==1)    FSym = HTrans->Follow;
                    else                    FSym = HTrans->First;

                    while(FSym!=NULL) /* sucht nach dem Zeichen */
                    {
                        if(FSym->sym==Sym)        Ersetz = HTrans;
                        if(HTrans->Epsfrei==1)    FSym = FSym->Follow;
                        else                    FSym = FSym->First;
                    }
                    HTrans = HTrans->next;
                }
            }
    
            Ersetz = Ersetz->suc;
            FSym = FrstEl->next;
            free(FrstEl);
            FrstEl = NULL;

            if(Ersetz->term==2)
            {
                FrstEl = FSym;
            }
            else
            {
                while(Ersetz!=NULL)
                {
                    help = NewNode();
                    help->sym  = Ersetz->sym;
                    help->term = Ersetz->term;
                    Ersetz = Ersetz->suc;

                    if(FrstEl==NULL)    FrstEl = help;
                    else                Next->next = help;
                    Next = help;
                }
                Next->next = FSym;
            }
        }
    }
}

void DeleteTables(pnode Gram)
{
    pnode HTrans = Gram;
    pnode Suc;
    pnode HFst;
    pnode HFlw;
    pnode help;

    while(HTrans)
    {
        Suc  = HTrans->suc;
        HFst = HTrans->First;
        HFlw = HTrans->Follow;
        while(Suc)
        {
            help = Suc;
            Suc = Suc->suc;
            free(help);
        }
        while(HFst)
        {
            help = HFst;
            HFst = HFst->First;
            free(help);
        }
        while(HFlw)
        {
            help = HFlw;
            HFlw = HFlw->Follow;
            free(help);
        }
        help = HTrans;
        HTrans = HTrans->next;
        free(help);
    }
}

pnode LL0Table(pnode Gram)
{
    return NULL;
}

int LL1Analyse(char* BNF,char* Text)
{
    pnode Gram = Transform(BNF);
    EpsilonTable(Gram);
    FirstSet(Gram);
    FollowSet(Gram);
    ShowTables(Gram);
    ParseLL1(Gram,Text);
    DeleteTables(Gram);
    return 0;
}

int SLR1Analyse(char* BNF,char* Text)
{
    pnode Gram = Transform(BNF);
    EpsilonTable(Gram);
    FirstSet(Gram);
    FollowSet(Gram);
    ShowTables(Gram);
    LL0Table(Gram);
    DeleteTables(Gram);
    return 0;
}

int main(int argc,char **argv)
{
    char BspBNF[] = "S=E#.E=TU.U=+TU.U=&.T=FV.V=*FV.V=&.F=z.F=(E).";
    char BspText[] = "z+(z+z)*z#";
    if(argc!=3)
    {
        printf("Aufruf: %s '%s' '%s'\n",argv[0],BspBNF,BspText);
        LL1Analyse(BspBNF,BspText);
    }
    else
    {
        LL1Analyse(argv[1],argv[2]);
    }
    return 0;
}

Werbung