Синтаксис языков программирования. Нисходящий синтаксический анализ, процедурная и автоматная реализации, страница 9

        treeLevel.add(i+j-1,si);  //и вставляем в текущий уровень дерева разбора

       }

      }

      rCnt+=1;   //увеличиваем количество применений правил

      back=false;break; //сбрасываем флажок отката и выходим из цикла поиска нетерминала, который можно заменить

     }

    }

   }

   if(!back){     //если флажок отката сброшен

//то проверим совпадение последовательности терминалов в текущем уровне дерева и во входном потоке

    i=0;ss=0;     //установим позицию начала остатка предложения на первый символ входного потока и сбросим в 0 счетчик количества нетерминалов в стеке разбора

    for(j=0;j<treeLevel.size();j+=1){ //просмотрим стек разбора

     if((k=(si=(stkItem)treeLevel.get(j)).sIndex)>=0){          //если очередной элемент - терминал, то в остатке предложения должен найтись такой же, иначе надо откатывать

      back=true;            //установим флажок отката на случай, если терминал не будет найден

      while(i<input.size()){      //просмотрим остаток входного потока

       if(((Integer)input.get(i++)).intValue()==k){     //если найден искомый терминал

        back=false;break;          //сбрасываем флажок и уходим из внутреннего цикла

       }

      }

      if(back)break;       //если флажок остался установленным - уходим из внешнего цикла, надо откатывать

     }else          //если очередной символ - нетерминал

      ss+=1;       //то увеличиваем счетчик их количества (вообще-то количество не важно, важно наличие)

    }

   }

   if(back){      //если нужно откатывать

    if(backUp.size()<=0)break;           //но откатывать нечего - уходим, предложение неверно

    ri=(stkItem)backUp.pop(); //возьмем верхний элемент спискаа откатов

    k=ri.pIndex;           //из элемента возьмем ту позицию в стеке разбора, из которой его удалили при применении правила

    treeLevel.add(k,ri);            //и вернем элемент на его место

    r=(Vector)rules.get(ri.rIndex);      //возьмем откатываемое правило

    for(k+=1,j=r.size();j>1;j-=1){       //все элементы, построенные ранее для символов правой части этого правила, переместим в стек свободных

     ri=(stkItem)treeLevel.get(k);       //возьмем элемент

     freeItems.push(ri); //занесем в стек свободных

     treeLevel.remove(k);        //и удалим его из стека разбора

    }

    for(j=k;j<treeLevel.size();j++)     //просмотрим остаток стека разбора

     if((si=(stkItem)treeLevel.get(j)).sIndex<0)         //и в элементах, соответствующих нетерминалам

      si.rIndex=-1;         //сбросим в -1 номер последнего применявшегося правила

    bCnt+=1;    //увеличиваем количество откатов

   }else //если откатывать не нужно

    if((ss==0)&&(treeLevel.size()==input.size()))    //если в стеке разбора нет нетерминалов и количество элементов в нем равно количеству слов во входном потоке

//то стек разбора полностью совпадает со входным потоком (иначе была бы обнаружена необходимость отката)

     return true; //возвращаем истину - предложение правильно

   if((cCnt+=1)>10000000)break;      //если количество попыток превысило установленный предел - выходим из основного цикла

  }

  return false;  //возвращаем ложь - предложение неверно (а может быть мы просто еще не нашли нужную последовательность применения правил)

 }

}

5.  Выводы

В ходе выполнения лабораторной работы была полностью определена грамматика языка, изучены основные идеи и понятия нисходящих методов синтаксического анализа, выявлены свойства формальных грамматик, необходимых для реализации нисходящего восстановления дерева грамматического разбора, приобретены навыки построения процедурной и различных автоматных реализаций нисходящего анализа, исследованы поведения нисходящих синтаксических акцепторов.