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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Лабораторная работа №5

по  дисциплине «Системное программное обеспечение»

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

Вариант № 1343424

Факультет:  АВТ                                                  Преподаватель:  Малявко А.А.

Группа: АМ-610                                                   Дата сдачи: 17.12.09

Выполнил:  Ряшинцев А.С.                               

                                                                            

 

Новосибирск 2009

Содержание

1.Цель работы.. 3

2.Вариант задания. 3

3.Ход выполнения работы.. 4

4.Выводы………………………………………………………………………………………..11

1.Цель работы

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

2.Вариант задания

II.1  Идентификаторы и константы

II.2  Объявления примитивных типов (целое, вещественное, символьное, булево):

II.3  Объявления объектов и создание/уничтожение экземпляров

II.4  Оператор присваивания:

II.5  Условный оператор:

II.6  Переключатель

II.7  Оператор цикла:

3.Ход выполнения работы

     Используя пакет ВебТрансЛаб изучил и освоил проверку принадлежности грамматики к классу LL(1).

     Построил процедурную реализацию рекурсивного спуска, уяснил способы формирования функций этого акцептора.

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

    Ниже приведена программная реализация синтаксического акцептора(из шаблона), также показана таблица правил грамматики:

 

class parser{

int cCnt=0;

lexAnalyzer la;    //лексический анализатор

lexem currentLexem; //текущая лексема (терминал)/*^if(grammar.pertainToLL1)^*/

int curWordIndex;  //индекс текущего терминала

BitSet[] SelSet;   //массив множеств выбора правил/*^if(grammar.symbolSet.hasWords)^*/

//дальше идут слова, определенные в грамматике как строки литер

String words[]={/*^forEach(currentWord in grammar.symbolSet)^*/"/*^=currentWord.text^*/"/*^if(currentWord.hasNextWord)^*/,/*^endIf^*/

/*^endFor^*/};/*^endIf^*/

//Part_6_0 данные и методы из правил

/*^=parser.data^*/

//end of Part_6_0

//Part_6_1: конструктор СА

 public parser(String s){

  la=new lexAnalyzer(new textReader(s));     //создадим экземпляр лексического анализатора

  SelSet=new BitSet[/*^=grammar.rules.count^*/];    //создание массива множеств выбора правил грамматики

//далее для каждого правила образуется свое множество выбора и устанавливаются в 1 биты тех терминалов, которые входят в данное множество

//правила показаны в качестве комментария к оператору создания его множества выбора, имена терминалов в комментариях к оператору установки бита

/*^forEach(currentNonTerminal in grammar.symbolSet)^*//*^forEach(currentRule in currentNonTerminal.rules)^*/  SelSet[/*^=currentRule.index^*/]=new BitSet(); // /*^=currentNonTerminal.name^*/ :/*^forEach(CurrentSymbol in currentRule.rightPart)^*//*^if(currentSymbol.isAction)^*//*^else^*/ /*^=currentSymbol.name^*//*^endIf^*//*^endFor^*//*^forEach(symbolFromSS in currentRule.selectionSet)^*/

  SelSet[/*^=currentRule.index^*/].set(/*^=symbolFromSS.index^*/);      // /*^=symbolFromSS.name^*/

/*^endFor^*//*^endFor^*//*^endFor^*/

 }

//Part_6_2:  вызов лексического анализатора, получение лексемы и формирование индекса терминального символа

 private int getWordIndex(){

  int i;String w;

  currentLexem=la.getLexem();   //получим лексему/*^if(grammar.symbolSet.hasWords)^*/

  w=new String(currentLexem.textOfWord);

  for(i=0;i<words.length;i++)   //организуем просмотр слов, определенных в грамматике как строки литер

   if(w.compareToIgnoreCase(words[i])==0)return i+/*^=symbolSet.firstWord.index^*/;    //вернем индекс найденного слова/*^endIf^*/