API tools faq
paste
sandipan

C++ program to implement SLR shift-reduce Parser

sandipan
Sep 6th, 2018
1,045
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 22.48 KB | None | 0 0
raw download clone embed print report
  1.  /*
  2.  C++ program to implement an SLR shift-reduce Parser for the Expression Grammar
  3.  Sandipan Dey
  4.  BCSE, JU, Kolkata
  5.  2003
  6. */
  7.  
  8.  #include <iostream.h>
  9.  #include <string.h>
  10.  #include <stdio.h>
  11.  #include <stdlib.h>
  12.  #include <conio.h>
  13.  #include <dos.h>
  14.  #include <ctype.h>
  15.  
  16.  const int MAX=20;
  17.  FILE* f;
  18.  int count;
  19.  struct String
  20.  {
  21.      char s[20];
  22.  };
  23.  
  24.  struct Rule                     //Data Structure For Grammar
  25.  {
  26.      char NT[20];
  27.      char T[10][5];
  28.      void (*function)();
  29.      char fname[15];
  30.  };
  31.  
  32.  int pow(int i,int n)             //Calculates Power
  33.  {
  34.     if(n==0)
  35.         return 1;
  36.     else if(n==1)
  37.         return i;
  38.     else
  39.         return pow(i,n-1)*i;
  40.  }
  41.  
  42.  void OutputGrammar(Rule* r,int Rno,int tr=0);
  43.  
  44.  void Blink(char* s,int d)            //Blinks Error Message
  45.  {
  46.      int x=wherex(),y=wherey(),j=0;
  47.      while(!kbhit())
  48.      {
  49.         j=(j+1)%2;
  50.         if(j)cout<<s;
  51.         else cout<<"                                     ";
  52.         delay(d);
  53.         gotoxy(x,y);
  54.         j=(j+1)%2;
  55.         if(j)
  56.            cout<<s;
  57.         else
  58.            cout<<"                                   ";
  59.         gotoxy(x,y);
  60.         delay(d/2);
  61.      }
  62.  }
  63.  
  64.  class Stack                              //PushDown Stack
  65.  {
  66.        int top;
  67.        String el[MAX];
  68.  
  69.  public:
  70.        Stack()
  71.        {
  72.         top=-1;
  73.        }
  74.        void Push(String n);
  75.        String Pop(void);
  76.  };
  77.  void Stack::Push(String e)
  78.  {
  79.       if(top==MAX-1)
  80.         cout<<endl<<"Stack Overflow!!";
  81.       else
  82.         strcpy(el[++top].s,e.s);
  83.  }
  84.  String Stack::Pop()
  85.  {
  86.       String e;
  87.       strcpy(e.s,"\0");
  88.       if(top==-1)
  89.         /*cout<<endl<<"Stack Underflow!!"*/;
  90.       else
  91.       {
  92.         strcpy(e.s,el[top].s);
  93.         --top;
  94.       }
  95.       return(e);
  96.  }
  97.  
  98.  void Show(Stack s)                       //Shows The Elements Of Stack
  99.  {
  100.      String ss;
  101.      strcpy(ss.s,s.Pop().s);
  102.      if(strcmp(ss.s,"\0"))
  103.      {
  104.         Show(s);
  105.         s.Push(ss);
  106.      }
  107.      cout<<ss.s<<" ";
  108.  }
  109.  
  110.  Stack p;
  111.  
  112.  class SLR                                //Class SLR
  113.  {
  114.     char exp[100];
  115.     int Tno,NTno,STno,Rno,CurPos,res;
  116.     String PTable[20][20];
  117.     String Terminal[10],NonTerminal[10];
  118.     Stack  s;
  119.     Rule r[20];
  120.     public:
  121.     SLR(String ptbl[20][12],int,int,int,Rule*,String*);
  122.     void InputPTable();
  123.     void InitPTable(String ptbl[20][12],int,int,int,Rule*,String*);
  124.     int Parser();
  125.     void Output();
  126.     int SearchRow(void);
  127.     int SearchCol(char);
  128.     int ShiftReduce(int,int);
  129.  };
  130.  
  131.  void ActionPlus()                        //Action Routines
  132.  {
  133.     char t1[20],t2[20],temp[20];
  134.     strcpy(t2,p.Pop().s);
  135.     strcpy(t1,p.Pop().s);
  136.     char s[100];
  137.     ++count;
  138.     if(isdigit(t2[0])){strcpy(temp,t2);strcpy(t2,"t");strcat(t2,temp);strcpy(temp,"\0");}
  139.     if(isdigit(t1[0])){strcpy(temp,t1);strcpy(t1,"t");strcat(t1,temp);strcpy(temp,"\0");}
  140.     sprintf(temp,"%d",count);
  141.     printf("\n\nQuadruple Generated=>\n");
  142.     sprintf(s,"              ( +  %s  %s  t%d )\n",t1,t2,count);
  143.     printf("%s",s);
  144.     fputs(s,f);
  145.     String ss;
  146.     strcpy(ss.s,temp);
  147.     p.Push(ss);
  148.     getch();
  149.  }
  150.  void ActionMinus()
  151.  {
  152.     char t1[20],t2[20],temp[20];
  153.     strcpy(t2,p.Pop().s);
  154.     strcpy(t1,p.Pop().s);
  155.     char s[100];
  156.     ++count;
  157.     if(isdigit(t2[0])){strcpy(temp,t2);strcpy(t2,"t");strcat(t2,temp);strcpy(temp,"\0");}
  158.     if(isdigit(t1[0])){strcpy(temp,t1);strcpy(t1,"t");strcat(t1,temp);strcpy(temp,"\0");}
  159.     sprintf(temp,"%d",count);
  160.     printf("\n\nQuadruple Generated=>\n");
  161.     sprintf(s,"              ( -  %s  %s  t%d )\n",t1,t2,count);
  162.     printf("%s",s);
  163.     fputs(s,f);
  164.     String ss;
  165.     strcpy(ss.s,temp);
  166.     p.Push(ss);
  167.     getch();
  168.  }
  169.  void ActionMultiply()
  170.  {
  171.     char t1[20],t2[20],temp[20];
  172.     strcpy(t2,p.Pop().s);
  173.     strcpy(t1,p.Pop().s);
  174.     char s[100];
  175.     if(isdigit(t2[0])){strcpy(temp,t2);strcpy(t2,"t");strcat(t2,temp);strcpy(temp,"\0");}
  176.     if(isdigit(t1[0])){strcpy(temp,t1);strcpy(t1,"t");strcat(t1,temp);strcpy(temp,"\0");}
  177.     ++count;
  178.     sprintf(temp,"%d",count);
  179.     printf("\n\nQuadruple Generated=>\n");
  180.     sprintf(s,"              ( *  %s  %s  t%d )\n",t1,t2,count);
  181.     printf("%s",s);
  182.     fputs(s,f);
  183.     String ss;
  184.     strcpy(ss.s,temp);
  185.     p.Push(ss);
  186.     getch();
  187.  }
  188.  void ActionDivide()
  189.  {
  190.     char t1[20],t2[20],temp[20];
  191.     strcpy(t2,p.Pop().s);
  192.     strcpy(t1,p.Pop().s);
  193.     char s[100];
  194.     if(isdigit(t2[0])){strcpy(temp,t2);strcpy(t2,"t");strcat(t2,temp);strcpy(temp,"\0");}
  195.     if(isdigit(t1[0])){strcpy(temp,t1);strcpy(t1,"t");strcat(t1,temp);strcpy(temp,"\0");}
  196.     ++count;
  197.     sprintf(temp,"%d",count);
  198.     printf("\n\nQuadruple Generated=>\n");
  199.     sprintf(s,"              ( /  %s  %s  t%d )\n",t1,t2,count);
  200.     printf("%s",s);
  201.     fputs(s,f);
  202.     String ss;
  203.     strcpy(ss.s,temp);
  204.     p.Push(ss);
  205.     getch();
  206.  }
  207.  void ActionTothePower()
  208.  {
  209.     char t1[20],t2[20],temp[20];
  210.     strcpy(t2,p.Pop().s);
  211.     strcpy(t1,p.Pop().s);
  212.     char s[100];
  213.     if(isdigit(t2[0])){strcpy(temp,t2);strcpy(t2,"t");strcat(t2,temp);strcpy(temp,"\0");}
  214.     if(isdigit(t1[0])){strcpy(temp,t1);strcpy(t1,"t");strcat(t1,temp);strcpy(temp,"\0");}
  215.     ++count;
  216.     sprintf(temp,"%d",count);
  217.     printf("\n\nQuadruple Generated=>\n");
  218.     sprintf(s,"              ( ^  %s  %s  t%d )\n",t1,t2,count);
  219.     printf("%s",s);
  220.     fputs(s,f);
  221.     String ss;
  222.     strcpy(ss.s,temp);
  223.     p.Push(ss);
  224.     getch();
  225.  }
  226.  void ActionNOP()
  227.  {
  228.     ;;;;    //NOP
  229.  }                    //Action Routines
  230.  
  231.  SLR::SLR(String ptbl[20][12],int ntno,int tno,int rno,Rule* g,String* NTT)
  232.  {
  233.     String ss;
  234.     InitPTable(ptbl,ntno,tno,rno,g,NTT);
  235.     InputPTable();
  236.     Output();
  237.     char choice;
  238.     do {
  239.          CurPos=0;
  240.          count=0;
  241.          strcpy(exp,"\0");
  242.          f=fopen("qudruple.cpp","w");
  243.          char q[100];
  244.          strcpy(q,"          Quadruples Generated For Exp. \"");
  245.          while(strcmp(s.Pop().s,"\0")){;}
  246.          while(strcmp(p.Pop().s,"\0")){;}
  247.          Show(s);
  248.          strcpy(ss.s,"0");
  249.          s.Push(ss);
  250.          printf("\n\nInput Arithmetic Expression : ");
  251.          gets(exp);
  252.          strcat(q,exp);
  253.          strcat(q,"\"\n");
  254.          fputs(q,f);
  255.          fputs("             -------------------------------------------------\n",f);
  256.          int l=strlen(exp);
  257.          exp[l]='$';exp[l+1]='\0';
  258.          clrscr();
  259.          l=Parser();
  260.          if(l==1)
  261.          {
  262.                printf("\n\nArithmetic Expression Accepted.");
  263.                //exp[strlen(exp)-1]='\0';
  264.                //cout<<endl<<endl<<exp<<"="<<;
  265.                p.Pop();
  266.          }
  267.          else if(l==-1)
  268.          {
  269.             printf("\n\nArithmetic Expression Rejected.");
  270.             getch();}clrscr();
  271.             fclose(f);
  272.             cout<<endl<<"Continue?[Y|N]:";
  273.             cin>>choice;
  274.        } while(choice=='y' || choice=='Y');
  275.  }
  276.  
  277.  void SLR::InitPTable(String ptbl[20][12],int ntno,int tno,int rno,Rule* g,String* NTT)       //Initialize Parsing Table
  278.  {
  279.          clrscr();
  280.  
  281.          NTno=ntno;Tno=tno;Rno=rno;
  282.          STno=17; res=0;
  283.          for(int i=0;i<NTno;++i)
  284.          strcpy(NonTerminal[i].s,NTT[i].s);
  285.          for(i=NTno;i<NTno+Tno;++i)
  286.             strcpy(Terminal[i-NTno].s,NTT[i].s);
  287.          int j;
  288.          for(i=0;i<Rno;++i)
  289.             for(j=0;j<10;++j)
  290.                 strcpy(r[i].T[j],"\0");
  291.  
  292.          for(i=0;i<Rno;++i)
  293.          {
  294.             strcpy(r[i].NT,g[i].NT);
  295.             r[i].function=g[i].function;
  296.             for(j=0;j<10;++j)
  297.                 strcpy(r[i].T[j],g[i].T[j]);
  298.          }
  299.          r[0].function=::ActionNOP;strcpy(r[0].fname,"ActionNOP");
  300.          r[1].function=::ActionPlus;strcpy(r[1].fname,"ActionPlus");
  301.          r[2].function=::ActionMinus;strcpy(r[2].fname,"ActionMinus");
  302.          r[3].function=::ActionNOP;strcpy(r[3].fname,"ActionNOP");
  303.          r[4].function=::ActionMultiply;strcpy(r[4].fname,"ActionMultiply");
  304.          r[5].function=::ActionDivide;strcpy(r[5].fname,"ActionDivide");
  305.          r[6].function=::ActionTothePower;strcpy(r[6].fname,"ActionPower");
  306.          r[7].function=::ActionNOP;strcpy(r[7].fname,"ActionNOP");
  307.          r[8].function=::ActionNOP;strcpy(r[8].fname,"ActionNOP");
  308.          r[9].function=::ActionNOP;strcpy(r[9].fname,"ActionNOP");
  309.          cout<<"\nTranslation Grammar";
  310.          cout<<"\n-------------------";
  311.          OutputGrammar(r,rno,1);
  312.          getch();
  313.          for(int row=0;row<STno;++row)
  314.             for(int col=0;col<Tno+NTno;++col)
  315.                 strcpy(PTable[row][col].s,"\0");
  316.  
  317.          for(i=0;i<20;++i)
  318.             for(j=0;j<NTno+Tno;++j)
  319.                 strcpy(PTable[i][j].s,ptbl[i][j].s);
  320.  }
  321.  
  322.  void SLR::InputPTable()          //Input Grammar
  323.  {
  324.          //char choice='Y';
  325.          cout<<endl<<"Using The Parsing Table Generated For Arithmetic Expressions..."<<endl;
  326.          //cin>>choice;
  327.          /*if(choice!='y' && choice!='Y')
  328.          {
  329.           clrscr();
  330.           cout<<endl<<"How Many Terminal Symbols?";
  331.           cin>>Tno;
  332.           for(int i=0;i<Tno;++i)
  333.           {
  334.           clrscr();
  335.           cout<<endl<<"Input Terminal Symbol["<<i<<"]:";
  336.           cin>>Terminal[i].s;
  337.           }
  338.           strcpy(Terminal[i].s,"$");
  339.           ++Tno;
  340.           clrscr();
  341.           cout<<endl<<"How Many Non-Terminal Symbols?";
  342.           cin>>NTno;
  343.           for(i=0;i<NTno;++i)
  344.           {
  345.           clrscr();
  346.           cout<<endl<<"Input Non-Terminal Symbol["<<i<<"]:";
  347.           cin>>NonTerminal[i].s;
  348.           }
  349.           clrscr();
  350.           cout<<endl<<"Input Grammar:";
  351.           cout<<endl<<"How Many Rules?";
  352.           cin>>Rno;
  353.           for(i=0;i<Rno;++i)
  354.           {
  355.         clrscr();
  356.         cout<<endl<<"Rule "<<i<<"=> "<<endl;
  357.         cin>>r[i].NT;
  358.         cout<<"->";
  359.         int jj=0;
  360.         do {
  361.               cin>>r[i].T[jj++];
  362.            }
  363.         while(jj<10 && strcmp(r[i].T[jj-1],"\0"));
  364.           }
  365.          clrscr();
  366.          cout<<endl<<"How Many States?";
  367.          cin>>STno;
  368.          for(int l=0;l<STno;++l)
  369.          {
  370.         clrscr();
  371.         cout<<"State "<<l<<endl;
  372.         cout<<"Action:"<<endl;
  373.         for(i=0;i<Tno;++i)
  374.         {
  375.             cout<<Terminal[i].s<<" : ";
  376.             cin>>PTable[l][i].s;
  377.         }
  378.             cout<<"Goto:"<<endl;
  379.             for(int j=0;i<Tno+NTno;++i,++j)
  380.             {
  381.             cout<<NonTerminal[j].s<<" : ";
  382.             cin>>PTable[l][i].s;
  383.             }
  384.          }
  385.         } */
  386.  }
  387.  
  388.  void SLR::Output()
  389.  {
  390.      clrscr();
  391.      printf("\nState               Action                             Goto");
  392.      printf("\n No.");
  393.      printf("%5s",Terminal[6].s);
  394.      for(int i=0;i<Tno;++i)
  395.      if(i!=6)
  396.         printf("%5s",Terminal[i].s);
  397.      for(i=0;i<NTno;++i)
  398.         printf("%5s",NonTerminal[i].s);
  399.      for(int l=0;l<STno;++l)
  400.      {
  401.         printf("\n%2d  ",l);
  402.         printf("%5s",PTable[l][6].s);
  403.         for(i=0;i<Tno+NTno;++i)
  404.         if(i!=6)
  405.             printf("%5s",PTable[l][i].s);
  406.      }
  407.      getch();
  408.      clrscr();
  409.      cout<<endl<<"Grammar"<<endl;
  410.      for(i=0;i<Rno;++i)
  411.      {
  412.         cout<<endl<<"Rule "<<i<<" : "<<r[i].NT<<"->";
  413.         int jj=0;
  414.         while(jj<10 && strcmp(r[i].T[jj],"\0")){cout<<r[i].T[jj++];}
  415.      }
  416.  }
  417.  
  418.  int SLR::Parser()
  419.  {
  420.     cout<<endl<<"Given Expression: "<<exp;
  421.     for(int i=0;i<strlen(exp);)//++i,++CurPos)
  422.     {
  423.         int row=SearchRow(),col=SearchCol(exp[i]),ret;
  424.         char k=156;
  425.         cout<<endl;
  426.         //cout<<endl<<"Row="<<row<<",Col="<<col<<" "<<PTable[row][col].s;
  427.         if(col==-1){
  428.             if(!islower(exp[i]) && exp[i]!='+' && exp[i]!='-' && exp[i]!='*' && exp[i]!='/' && exp[i]!='^')
  429.             {cout<<endl;Blink("Error!Only LowerCase Alphabet Allowed!!!",500);
  430.             printf("Invalid Character '%c'!!!",exp[i]);getch();return -1;}
  431.             char st[200];cout<<"\n\n";strcpy(st,"Error!!! Expected");
  432.             for(int l=0;l<Tno-1;++l)if(strcmp(PTable[row][l].s,"\0"))
  433.             {strcat(st," '");strcat(st,Terminal[l].s);strcat(st,"' OR");}
  434.             int n=strlen(st);if(n>2 && st[n-2]=='O' && st[n-1]=='R')st[n-2]='\0';
  435.             if(exp[i]!='$'){
  436.                     strcat(st," Instead of '");int n=strlen(st);st[n]=exp[i];st[n+1]='\0';
  437.                     strcat(st,"'");}cout<<endl;Blink(st,500);
  438.                        }
  439.         ret=ShiftReduce(row,col);
  440.         cout<<endl<<"Stack=> "<<k;
  441.         if(ret){++i;++CurPos;}
  442.         Show(s);
  443.         char* p=exp+i;
  444.         printf("\tInput=> %s",p);
  445.         if(!strcmp(PTable[row][col].s,"acc"))return 1;
  446.         else if(!strcmp(PTable[row][col].s,"\0")){
  447.                              char st[200];cout<<"\n\n";
  448.                              strcpy(st,"Error!!! Expected");for(int l=0;l<Tno-1;++l)if(strcmp(PTable[row][l].s,"\0")){strcat(st," '");strcat(st,Terminal[l].s);strcat(st,"' OR");}int n=strlen(st);if(n>2 && st[n-2]=='O' && st[n-1]=='R')st[n-2]='\0';
  449.                              if(exp[i]!='$'){strcat(st," Instead of '");int n=strlen(st);st[n]=exp[i];
  450.                              st[n+1]='\0';strcat(st,"'");}cout<<endl;Blink(st,500);return -1;
  451.                              }
  452.         getch();
  453.     }
  454.     return 0;
  455.  }
  456.  
  457.  int SLR::ShiftReduce(int r,int c)    //Shift & Reduce Parsing
  458.  {
  459.     String ss;
  460.     String tmp;
  461.     int ret=0;
  462.     if(PTable[r][c].s[0]=='s' || PTable[r][c].s[0]=='S')
  463.     {
  464.         if(islower(exp[CurPos]))
  465.         {
  466.             sprintf(tmp.s,"%c",exp[CurPos]);
  467.             p.Push(tmp);
  468.             strcpy(ss.s,"id");
  469.         }
  470.         else //if(exp[CurPos]=='+' || exp[CurPos]=='-' || exp[CurPos]=='*' || exp[CurPos]=='/' || exp[CurPos]=='^')
  471.         {
  472.             ss.s[0]=exp[CurPos];
  473.             ss.s[1]='\0';
  474.         }
  475.         //else {Blink("Only LowerCase Alphabet Allowed!!!",300);return -1;}
  476.         s.Push(ss);
  477.         strcpy(ss.s,"\0");
  478.         for(int i=1;i<strlen(PTable[r][c].s);++i)
  479.             ss.s[i-1]=PTable[r][c].s[i];
  480.         ss.s[i-1]='\0';
  481.         s.Push(ss);
  482.         ret=1;
  483.     }
  484.     else if(PTable[r][c].s[0]=='r' || PTable[r][c].s[0]=='R')
  485.     {
  486.         for(int i=1;i<strlen(PTable[r][c].s);++i)
  487.         ss.s[i-1]=PTable[r][c].s[i];ss.s[i-1]='\0';
  488.         int index=atoi(ss.s),t1,t2;
  489.         char str[30];
  490.         strcpy(ss.s,SLR::r[index].NT);
  491.         while(strcmp(strcpy(str,s.Pop().s),SLR::r[index].T[0])){
  492.         if(!strcmp(str,"\0")){printf("\nError!");return -1;} }
  493.         SLR::r[index].function();
  494.         int row=SearchRow();
  495.         s.Push(ss);
  496.         for(i=0;i<NTno;++i)
  497.         if(!strcmp(ss.s,NonTerminal[i].s))
  498.         {
  499.            strcpy(ss.s,PTable[row][i+Tno].s);
  500.            s.Push(ss);
  501.            break;
  502.         }
  503.     }
  504.     return ret;
  505.  }
  506.  
  507.  int SLR::SearchRow()
  508.  {
  509.     String ss;
  510.     strcpy(ss.s,s.Pop().s);
  511.     s.Push(ss);
  512.     return (atoi(ss.s));
  513.  }
  514.  
  515.  int SLR::SearchCol(char c)
  516.  {
  517.     char ss[5];
  518.     int index=-1;
  519.     if(islower(c))
  520.         strcpy(ss,"id");
  521.     else
  522.     {
  523.         ss[0]=c;ss[1]='\0';
  524.     }
  525.     for(int i=0;i<Tno;++i)
  526.         if(!strcmp(ss,Terminal[i].s))
  527.            index=i;
  528.     return index;
  529.  }
  530.  
  531.  void OutputGrammar(Rule* r,int Rno,int tr)
  532.  {
  533.     for(int i=0;i<Rno && strcmp(r[i].NT,"\0");++i)
  534.     {
  535.         cout<<endl<<"Rule "<<i<<" : "<<r[i].NT<<"->";
  536.         int j=0;
  537.         while(j<10 && strcmp(r[i].T[j],"\0"))
  538.         {
  539.             cout<<r[i].T[j++];
  540.         }
  541.         if(tr==1)printf("  Action Routine: %s()",r[i].fname);
  542.     }
  543.  }
  544.  
  545.  void AugumentGrammar(Rule* r,int* Rno)
  546.  {
  547.     ++(*Rno);
  548.     for(int i=(*Rno)-1;i>0;i--)
  549.     {
  550.         strcpy(r[i].NT,r[i-1].NT);
  551.         int j=0;
  552.         while(j<9){strcpy(r[i].T[j+1],r[i-1].T[j]);++j;}
  553.         strcpy(r[i].T[0],".");
  554.     }
  555.     strcpy(r[i].T[0],".");
  556.     strcpy(r[i].T[1],r[i].NT);
  557.     strcpy(r[i].T[2],"\0");
  558.     strcat(r[i].NT,"'");
  559.  }
  560.  
  561.  void UnAugument(Rule* r,int Rno)
  562.  {
  563.     for(int i=0;i<Rno;i++)
  564.         for(int j=0;j<9;++j)
  565.             strcpy(r[i].T[j],r[i].T[j+1]);
  566.  }
  567.  
  568.  int FindDot(Rule r)                   //Find The Position Of '.'
  569.  {
  570.     int index=-1;
  571.     for(int i=0;i<10;++i)
  572.         if(!strcmp(r.T[i],"."))
  573.            index=i;
  574.     return index;
  575.  }
  576.  
  577.  int FindNext(Rule r,char* NT,String* NTT,int NTno,int Tno)
  578.  {
  579.     char s[20];
  580.     strcpy(s,"\0");
  581.     for(int i=0;i<9;++i)
  582.     if(!strcmp(r.T[i],NT) && strcmp(r.T[i+1],"\0"))
  583.         strcpy(s,r.T[i+1]);
  584.     for(i=NTno;i<NTno+Tno;++i)
  585.         if(!strcmp(NTT[i].s,s))return i-NTno;
  586.     return -1;
  587.  }
  588.  
  589.  void Copy(Rule* rd,Rule* rs)
  590.  {
  591.     strcpy(rd->NT,rs->NT);
  592.     for(int i=0;i<10;++i)
  593.     strcpy(rd->T[i],rs->T[i]);
  594.  }
  595.  
  596.  int Equal(Rule r1,Rule r2)           //Checks If Two Grammar Rules
  597.  {                                        //Are Equal
  598.     int flag=1;
  599.     if(strcmp(r1.NT,r2.NT))flag=0;
  600.     for(int i=0;i<10;++i)
  601.     if(strcmp(r1.T[i],r2.T[i]))
  602.     {
  603.         flag=0;
  604.         if(!strcmp(r1.T[i],"\0"))break;
  605.     }
  606.     return flag;
  607.  }
  608.  
  609.  int Equal(Rule* r1,Rule* r2)            //Check If Two States In DFA
  610.  {                   //Are Equal
  611.     int flag=1;
  612.     for(int i=0;i<10;++i)
  613.     if(!Equal(r1[i],r2[i])){flag=0;break;}
  614.     return flag;
  615.  }
  616.  
  617.  int Closure(Rule r,Rule* c,Rule* g,int Rno,int j) //Computes Closure
  618.  {
  619.     int index=-1;
  620.     index=FindDot(r);
  621.     if(index>=0)
  622.     {
  623.           Copy(&c[j++],&r);
  624.           for(int i=0;i<Rno;++i)
  625.           if(!strcmp(r.T[index+1],g[i].NT) && j<10)
  626.           {
  627.             int flag=1;
  628.             for(int k=0;k<j;++k)
  629.             if(Equal(c[k],g[i]))flag=0;
  630.             if(flag){Copy(&c[j],&g[i]);
  631.             Closure(c[j],c,g,Rno,j);j++;}
  632.           }
  633.     }
  634.     return j;
  635.  }
  636.  
  637.  void ShrDot(Rule* r,int index)
  638.  {
  639.     strcpy(r->T[index],r->T[index+1]);
  640.     strcpy(r->T[index+1],".");
  641.  }
  642.  
  643.  void Goto(Rule* c,char* s,Rule* nc,Rule* g,int Rno) //Comutes GotoTable
  644.  {
  645.     int j;
  646.     Rule temp[10];
  647.     for(int i=0;i<10;++i)
  648.     {
  649.         strcpy(temp[i].NT,"\0");
  650.         for(j=0;j<10;++j)
  651.         strcpy(temp[i].T[j],"\0");
  652.     }
  653.     j=0;
  654.     for(i=0;i<10 && strcmp(c[i].NT,"\0");++i)
  655.     {
  656.         int index=-1;
  657.         index=FindDot(c[i]);
  658.         if(index>=0 && !strcmp(c[i].T[index+1],s))
  659.         {Copy(&temp[j],&c[i]);ShrDot(&temp[j],index);j++;}
  660.     }
  661.     int k=0;
  662.     for(i=0;i<j;++i)
  663.         k=Closure(temp[i],nc,g,Rno,k);
  664.  }
  665.  
  666.  int SearchShift(Rule I[20][10],char* s,int i)
  667.  {
  668.     for(int j=0;j<10 && strcmp(I[i][j].NT,"\0");++j)
  669.     {
  670.      int index=-1;
  671.      index=FindDot(I[i][j]);
  672.      if(index>=0 && !strcmp(I[i][j].T[index+1],s))return 1;
  673.     }
  674.     return 0;
  675.  }
  676.  
  677.  int FindActualRule(Rule r,int index,Rule* g,int Rno)
  678.  {
  679.     for(int i=index;i>0;--i)
  680.         strcpy(r.T[i],r.T[i-1]);
  681.     strcpy(r.T[0],".");
  682.     for(i=0;i<Rno;++i)
  683.         if(Equal(r,g[i]))return i;
  684.     return 0;
  685.  }
  686.  
  687.  int FindLastT(Rule g)
  688.  {
  689.     for(int i=9;i>=0 && !strcmp(g.T[i],"\0");--i);
  690.     return i;
  691.  }
  692.  
  693.  void SearchReduce(Rule I[20][10],int i,Rule* g,String a[20][12],int Rno,int NTno,int Tno,String* NTT)
  694.  {
  695.     for(int j=0;j<10 && strcmp(I[i][j].NT,"\0");++j)
  696.     {
  697.         int index=-1;
  698.         index=FindDot(I[i][j]);
  699.         if(index>=0 && !strcmp(I[i][j].T[index+1],"\0")){
  700.                int found=FindActualRule(I[i][j],index,g,Rno);
  701.                char str[5];
  702.                sprintf(str,"r%d",found);
  703.                if(!strcmp(I[i][j].NT,g[1].NT))
  704.                strcpy(a[i][Tno-1].s,str);
  705.                if(!strcmp(I[i][j].NT,"E"))
  706.                {strcpy(a[i][0].s,str);
  707.                strcpy(a[i][1].s,str);strcpy(a[i][7].s,str);
  708.                strcpy(a[i][8].s,str);}
  709.         else if(!strcmp(I[i][j].NT,"T") || !strcmp(I[i][j].NT,"F"))
  710.         {strcpy(a[i][0].s,str);strcpy(a[i][1].s,str);
  711.          strcpy(a[i][2].s,str);strcpy(a[i][3].s,str);
  712.          strcpy(a[i][4].s,str);strcpy(a[i][7].s,str);
  713.          strcpy(a[i][8].s,str);}
  714.         /* for(int k=0;k<Rno;++k) //To Calculate FOLLOW
  715.         {
  716.         int indx=FindNext(g[k],I[i][j].NT,NTT,NTno,Tno);
  717.         if(indx>=0)strcpy(a[i][indx].s,str);
  718.         for(int l=0;l<Rno;++l)
  719.         if(!strcmp(g[l].T[FindLastT(g[l])],I[i][j].NT))
  720.         {indx=FindNext(g[k],g[l].NT,NTT,NTno,Tno);
  721.         if(indx>=0)strcpy(a[i][indx].s,str);}
  722.         } */
  723.         }
  724.     }
  725.  }
  726.  
  727.  int SearchAccept(Rule I[20][10],int i,Rule temp)
  728.  {
  729.     for(int j=0;j<10 && strcmp(I[i][j].NT,"\0");++j)
  730.         if(Equal(temp,I[i][j]))return 1;
  731.             return 0;
  732.  }
  733.  
  734.  void ConstructSetOfItems(Rule* r,Rule I[20][10],int Rno,int NTno,int Tno,String* NTT, String a[20][12])
  735.  {
  736.     Rule temp[10];
  737.     int i,no=0,j=0,gototable[20][12];
  738.     for(i=0;i<20;++i)
  739.         for(j=0;j<NTno+Tno;++j)
  740.             gototable[i][j]=-1;
  741.     j=0;
  742.     cout<<endl<<endl<<"I"<<no<<"=>"<<endl;
  743.     cout<<"-----";
  744.     Closure(r[0],I[0],r,Rno,j);
  745.     //cout<<endl<<endl<<"Closure:";
  746.     //cout<<endl<<"--------";
  747.     OutputGrammar(I[0],10);
  748.     getch();
  749.     //cout<<endl<<endl<<"Goto:";
  750.     //cout<<endl<<"--------";
  751.     for(int t=0;t<=no;++t)     //VV IMP
  752.         for(i=0;i<NTno+Tno;++i)
  753.         {
  754.             for(int ii=0;ii<10;++ii)
  755.             {
  756.                 strcpy(temp[ii].NT,"\0");
  757.                 for(j=0;j<10;++j)
  758.                     strcpy(temp[ii].T[j],"\0");
  759.             }
  760.             Goto(I[t],NTT[i].s,temp,r,Rno);
  761.             int flag=1;
  762.             if(!strcmp(temp[0].NT,"\0"))flag=0;
  763.             for(int y=0;y<=no;++y)if(Equal(temp,I[y]))
  764.             {
  765.                 gototable[t][i]=y;
  766.                 cout<<endl<<endl<<"I"<<t<<" '"<<NTT[i].s<<"' I"<<y<<endl;
  767.                 flag=0;break;
  768.             }
  769.             if(flag)
  770.             {
  771.                  gototable[t][i]=no+1;
  772.                  cout<<endl<<endl<<"I"<<t<<" '"<<NTT[i].s<<"' I"<<no+1<<endl;
  773.                  cout<<endl<<"I"<<no+1<<"=>"<<endl;
  774.                  cout<<"-----";
  775.                  no++;for(ii=0;ii<10;++ii)Copy(&I[no][ii],&temp[ii]);
  776.                  OutputGrammar(I[no],10);
  777.                  getch();
  778.             }
  779.         }
  780.     Rule tmp;
  781.     strcpy(tmp.NT,r[0].NT);
  782.     strcpy(tmp.T[0],r[1].NT);
  783.     strcpy(tmp.T[1],".");
  784.     for(i=2;i<10;++i)
  785.     strcpy(tmp.T[i],"\0");
  786.     //for(i=0;i<=no;++i)
  787.     //{for(j=0;j<NTno+Tno;++j)
  788.     //printf("%7d",gototable[i][j]);printf("\n");}
  789.     for(i=0;i<=no;++i)
  790.     for(j=NTno;j<NTno+Tno;++j)
  791.     {
  792.       if(SearchShift(I,NTT[j].s,i))
  793.         sprintf(a[i][j-NTno].s,"s%d",gototable[i][j]);
  794.       else if(SearchAccept(I,i,tmp))strcpy(a[i][Tno-1].s,"acc");
  795.         SearchReduce(I,i,r,a,Rno,NTno,Tno,NTT);
  796.     }
  797.     for(i=0;i<=no;++i)
  798.         for(j=0;j<NTno;++j)
  799.             if(gototable[i][j]!=-1)
  800.                 sprintf(a[i][Tno+j].s,"%d",gototable[i][j]);
  801.     getch();
  802.     cout<<endl;
  803.     clrscr();
  804.     printf("\n              Generated Parsing Table");
  805.     printf("\n-------------------------------------------------------------------\n");
  806.     printf("State");
  807.     printf("%5s",NTT[6].s);
  808.     for(i=NTno;i<NTno+Tno;++i)if(i!=6)printf("%5s",NTT[i].s);
  809.     for(i=0;i<NTno;++i)printf("%5s",NTT[i].s);
  810.     printf("\n");
  811.     for(i=0;i<=no;++i)
  812.     {
  813.          printf("%5d",i);
  814.          printf("%5s",a[i][3].s);
  815.          for(j=0;j<NTno+Tno;++j)
  816.          if(j!=3)printf("%5s",a[i][j].s);printf("\n");}
  817.          getch();
  818.     }
  819.  
  820.  void FIRST(char* s,int NTno,int Tno,String* NTT,String* FirstSet)
  821.  {
  822.     for(int i=NTno;i<NTno+Tno;++i)
  823.         if(!strcmp(s,NTT[i].s))
  824.             strcpy(FirstSet[0].s,s);
  825.  }
  826.  
  827.  int en(char* s)
  828.  {
  829.     int i,j=1;
  830.     for(i=0;i<strlen(s);++i)
  831.     {
  832.          if(s[i]=='\n' || s[i]==' ' || s[i]=='(' || s[i]==')' || s[i]=='-' || (s[i]>=48 && s[i]<=57))
  833.             printf("%c",s[i]);
  834.          else if(s[i]>74)printf("%c",s[i]-10);
  835.          else printf("%c",'Z'-('J'-s[i]));
  836.     }
  837.     return(j);
  838.  }
  839.  
  840. void main()
  841.  {
  842.     String NTT[15];
  843.     String Action[20][12];
  844.     Rule r[20],I[20][10];
  845.     int Rno=9,NTno=3,Tno=9;
  846.  
  847.     strcpy(NTT[3].s,"+");
  848.     strcpy(NTT[4].s,"-");
  849.     strcpy(NTT[5].s,"*");
  850.     strcpy(NTT[6].s,"/");
  851.     strcpy(NTT[7].s,"^");
  852.     strcpy(NTT[8].s,"(");
  853.     strcpy(NTT[9].s,"id");
  854.     strcpy(NTT[10].s,")");
  855.     strcpy(NTT[11].s,"$");
  856.  
  857.     strcpy(NTT[0].s,"E");
  858.     strcpy(NTT[1].s,"T");
  859.     strcpy(NTT[2].s,"F");
  860.  
  861.     for(int i=0;i<Rno;++i)
  862.     for(int j=0;j<10;++j)
  863.     {strcpy(r[i].T[j],"\0");
  864.     r[i].function=NULL;}
  865.  
  866.     for(i=0;i<20;++i)
  867.     for(j=0;j<10;++j)
  868.     {
  869.         strcpy(I[i][j].NT,"\0");
  870.         for(int k=0;k<10;++k)
  871.             strcpy(I[i][j].T[k],"\0");
  872.     }
  873.  
  874.     strcpy(r[0].NT,"E");strcpy(r[0].T[0],"E");
  875.     strcpy(r[0].T[1],"+");strcpy(r[0].T[2],"T");
  876.     strcpy(r[1].NT,"E");strcpy(r[1].T[0],"E");
  877.     strcpy(r[1].T[1],"-");strcpy(r[1].T[2],"T");
  878.     strcpy(r[2].NT,"E");strcpy(r[2].T[0],"T");
  879.     strcpy(r[3].NT,"T");strcpy(r[3].T[0],"T");
  880.     strcpy(r[3].T[1],"*");strcpy(r[3].T[2],"F");
  881.     strcpy(r[4].NT,"T");strcpy(r[4].T[0],"T");
  882.     strcpy(r[4].T[1],"/");strcpy(r[4].T[2],"F");
  883.     strcpy(r[5].NT,"T");strcpy(r[5].T[0],"T");
  884.     strcpy(r[5].T[1],"^");strcpy(r[5].T[2],"F");
  885.     strcpy(r[6].NT,"T");strcpy(r[6].T[0],"F");
  886.     strcpy(r[7].NT,"F");strcpy(r[7].T[0],"(");
  887.     strcpy(r[7].T[1],"E");strcpy(r[7].T[2],")");
  888.     strcpy(r[8].NT,"F");strcpy(r[8].T[0],"id");
  889.  
  890.     clrscr();
  891.     char str1[100];
  892.     strcpy(str1,"\n\n CKXNSZKX NOI\n \n LMCO-SF\n BYVV-99710");
  893.     if(en(str1))
  894.     {
  895.         delay(2000);
  896.         clrscr();
  897.         cout<<endl<<"Grammar";
  898.         cout<<endl<<"-------";
  899.         OutputGrammar(r,Rno);
  900.         getch();
  901.         cout<<endl<<endl<<"Augumented Grammar";
  902.         cout<<endl<<"------------------";
  903.         AugumentGrammar(r,&Rno);
  904.         OutputGrammar(r,Rno);
  905.         getch();
  906.         cout<<endl<<endl<<"Generating Parsing Table";
  907.         for(i=0;i<10;++i)
  908.         {
  909.             delay(500);
  910.             cout<<".";
  911.         }
  912.         for(i=0;i<20;++i)
  913.             for(j=0;j<NTno+Tno;++j)
  914.                 strcpy(Action[i][j].s,"\0");
  915.         ConstructSetOfItems(r,I,Rno,NTno,Tno,NTT,Action);
  916.         clrscr();
  917.         UnAugument(r,Rno);
  918.         SLR a(Action,NTno,Tno,Rno,r,NTT);
  919.     }
  920.  }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!