Написание прораммы

1. Задание. 

В данной лабораторной работе необходимо:

      1.проверить,  обладает ли заданная грамматика  свойством LL(1), и при необходимости, выполнить ее преобразование к этому виду;

      2.построить  для полученной в п.1 грамматики  LL(1)-таблицу разбора;

      3.разработать программную реализацию синтаксического анализатора на основе полученной LL(1)-грамматики и соответствующей таблицы разбора. Результат анализа представить в виде последовательности номеров правил грамматики, примененных в процессе разбора. 
 
 
 

2. Заданная грамматика:

      S::=caA

      A::=(L)|L

  L::=e,L|e 

      S - аксиома     
 

3.Полученная  LL(1)-грамматика:

    1)S::=caA

    2)A::=(L)

    3)A::=L

  4)L::=eZ

  5)Z::=,L

    6)Z::=L 

4. Таблица  разбора:

 

 
 

5. Текст  программы:

 

# include <iostream>

# include <fstream>

# include <string>

using namespace std;

struct Symb

{

      char s1;

      char s2;

      string str;

      char out;

      struct Symb *next;

};

void add_to_list (struct Symb* &head, struct Symb t)

{

      struct Symb* ptr=new struct Symb;

      *(ptr)=t;

      if (head==NULL)

            ptr->next=NULL;

      else

            ptr->next=head;

      head=ptr;

}

void del_list (struct Symb* &head)

{

      struct Symb* ptr;

      while (head!=NULL)

      {

            if (head->next!=NULL)

            {

                   ptr=head;

                   head=head->next;

                   delete ptr;

            }

            else

            {

                  delete head;

                  head=NULL;

            }

      }

}

void read_file(struct Symb* &head)

{

      ifstream inFile ("table.txt", ios::in);

      char s;  struct Symb t;  string st;

      inFile>>s;

      while (!inFile.eof())

      {

                  t.s1=s;  inFile>>s;

                  t.s2=s;  inFile>>st;

                  t.str=st; inFile>>s;

                  if (t.str=="В"||t.str=="Д")

                  {

                        add_to_list(head,t);

                        continue;

                  }

                  t.out=s;

                  inFile>>s;

                  add_to_list(head,t);

      }

      inFile.close();

}

bool search (struct Symb* head,char inis,char sts,string& str,char& outs)

{

      struct Symb* ptr=head;

      while (ptr!=NULL)

      {

            if (inis==ptr->s1)

                  if (sts==ptr->s2)

                  {

                        str=ptr->str;

                        outs=ptr->out;

                        return true;

                  }

            ptr=ptr->next;

      }

      return false;

}

void pop_stack(string &stack,int &top)

{

      if (top>0)

      {

            stack.erase(top,1);

            top--;

      }

}

void replace_str(string &str)

{

      string str1="";

      for (int i=str.length()-1; i>=0; i--)

            str1+=str[i];

      str=str1;

}

void push_stack(string &stack,int &top,string str)

{

      replace_str(str);

      stack+=str;

      top+=str.length();

}

bool LL (struct Symb* head,string inistr,string &outstr)

{

      string stack,str;  int top=1,curs=0;

      stack="$S";

      char outs;

      while (inistr[curs]!='\0')

      {

            if(search(head,inistr[curs],stack[top],str,outs))

            {

                  switch (str[0])

                  {

                  case 'В':

                        {

                              pop_stack(stack,top);

                              curs++;

                              break;

                        }

                  case 'Д':

                              return true;

                  default:

                        {

                              pop_stack(stack,top);

                              if(str!="П")

                                    push_stack(stack,top,str);

                              outstr+=outs;

                              break;

                        }

                  }

            }

            else

                  return false;

      }

      return true;

}

int main()

{

      struct Symb* head=NULL;

      string inistr,outstr="";

      cout<<"Enter string: ";

      cin>>inistr;

      read_file(head);

      if(LL(head,inistr,outstr))

      {

            cout<<"The string is allowed"<<endl;

            cout<<"Resulting string: ";