Parser Generator
Инструментарий для построения компиляторов.
   
Главная
О сайте
Документация
Download
Ссылки
Библиография
О нас

Структуры данных

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

Все ядро разрабатывалось на языке C++, с максимальным соблюдением стандартов, для последующего переноса на различные реализации языка. В библиотеке активно используется STL и оригинальная библиотека управления памятью с помощью автопоинтеров (autopointer). Благодаря этому библиотека является надежной, универсальной и производительной.

Библиотека классов ядра разрабатывалась в рамках идеологии MVC (model-view-controller)- модель- контроллер- вид. Таким образом существуют классы отвечающие исключительно за представление состояния объектов (модели), классы отвечающие за управлением состоянием моделей (контроллеры), и классы осуществляющие просмотр (вид).

Для работы с формальными грамматиками, автоматами, преобразователями и пр. разработаны специальные структуры данных- классы. Эти классы являются моделями соответствующих объектов. Они содержат минимальный набор необходимых операций такие как:

  • Копирование
  • Инициализация
  • Сравнение
  • Преобразование в строку
  • Итерирование по контейнеру (для таких классов как набор термов или правил).

    • Многие классы ядра содержат внутри себя определение типов данных, таких как:

  • Автопоинтер (auto_ptr) на объекты классы
  • STL контейнеры объектов классы (list, vector, map, stack, deque).
  • Итераторы по контейнерам.

    • Для выполнения различных операций над грамматиками, автоматами и т.д. разработаны специальные классы- алгоритмы или функционалы, с перегруженным оператором (). Эти классы осуществляют более сложные операции над объектами-моделями.

    Рассмотрим основные классы ядра библиотеки.

    Класс Term- терм

    Term
    void fromXML ( string p_XML ) // Конструирует терм из XML строки
    string getName ( ) // Возвращает имя терма
    termType  getType ( ) // Возвращает тип терма
    void setId ( int p_id ) // Задает Id терма.
    void setName ( string p_name ) // Задает имя терма
    void setType ( termType  p_type ) // Задает тип терма

    Этот класс описывает терминалы, нетерминалы и операционные символы грамматики. Тип терма определяется свойством type типа termType { tt_terminal, tt_notTerminal, tt_opSymbol }. Также терм содержит свойство name- имя терма. Внутри класса определены типы контейнеров для терма (list, map).

    Класс SetOfTerms- набор термов

    SetOfTerms
    void addTerm ( Term::ptr p_term ) // Добавляет терм в контейнер
    SetOfTerms::iterator begin ( ) // Возвращает итератор указывающий на начало контейнера
    void deleteTerm ( Term::ptr p_term ) // Удаляет терм
    SetOfTerms::iterator end ( ) // Возвращает итератор указывающий на конец контейнера
    void fromXML ( string p_XML ) // Конструирует набор термов из XML строки
    SetOfTerms::ptr intersection ( SetOfTerms::ptr p_st ) // Находит пересечение с другим набором термов
    BOOL isItTerm ( Term::ptr p_term ) // Есть ли такой терм
    int size ( ) // Возвращает размер контейнера

    Часто необходимо хранить целый набор термов для различных целей (словарь символов грамматики, множества ПЕРВ, СЛЕД...). Для этих целей был разработан этот контейнер. Внутри него все символы хранятся в ассоциативном массиве- map. Ключом для выборки является имя терма.

    Класс Rule- правило

    Rule
    Rule::iterator begin ( ) // Возвращает итератор указывающий на начало контейнера
    Rule::iterator end ( ) // Возвращает итератор указывающий на конец контейнера
    void fromXML ( string p_XML ) // Конструирует правило из XML строки
    int getCountTerms ( ) // Возвращает количество термов в правой части (размер правила)
    Term::ptr getFirstTerm ( ) // Возвращает первый терм в правиле
    int getId ( ) // Возвращает Id правила
    Term::ptr getLPart ( ) // Возвращает терм в правой части (определяемый терм)
    BOOL isChain ( ) // Признак цепного правила
    BOOL isEmpty ( ) // Признак пустого правила
    BOOL isRPartEquals ( Rule::ptr p_rule ) // Определяет равенство правых частей двух правил
    Rule::reverse_iterator rbegin ( ) // Возвращает обратный итератор указывающий на начало контейнера
    Rule::reverse_iterator rend ( ) // Возвращает обратный итератор указывающий на конец контейнера
    void setId ( int p_newId ) // Устанавливает Id правила
    void setLPart ( Term::ptr p_term ) // Устанавливает терм в правой части (определяемый терм)

    Представляет собой одно правило грамматики. Содержит в себе список термов в левой части правила по порядку. В качестве контейнера использует список.

    Класс SetOfRules- набор правил

    SetOfRules
    void  addRule ( Rule::ptr p_rule ) // Добавляет правило в контейнер.
    Rule::iterator begin ( ) // Возвращает итератор указывающий на начало контейнера
    SetOfRules::iterator delRule ( Rule::ptr p_rule ) // Удаляет правило из контейнера
    Rule::iterator end ( ) // Возвращает итератор указывающий на конец контейнера
    void fromXML ( string p_XML ) // Конструирует объект из XML строки
    Rule::ptr getRuleById ( int p_id ) // Возвращает правило из контейнера по его Id
    int size ( ) // Возвращает количество правил в наборе

    Класс является контейнером для правил вывода. Применяется для многих целей, например для хранения всех правил грамматики.

    Класс FormalGrammar- формальная грамматика

    FormalGrammar
    Rule::iterator begin_rules ( ) // Возвращает итератор указывающий на начало контейнера правил
    SetOfTerms::iterator begin_terms ( ) // Возвращает итератор указывающий на начало контейнера термов
    Rule::iterator end_rules ( ) // Возвращает итератор указывающий на конец контейнера правил
    SetOfTerms::iterator end_terms ( ) // Возвращает итератор указывающий на конец контейнера термов
    void fromXML ( string p_XML ) // Конструирует объект из XML строки
    SetOfRules getR ( ) // Возвращает набор правил вывода для грамматики
    Term::ptr getSTartSymbol ( ) // Возвращает начальный символ грамматики
    SetOfTerms::ptr getV ( ) // Возвращает список термов (терминалов, нетерминалов, операционных символов) грамматики.
    void  setR ( SetOfRules::ptr p_rules ) // Задает набор правил вывода для грамматики
    void  setStartSymbol ( Term::ptr p_ss ) // Задает начальный символ грамматики
    void  setV ( SetOfTerms::ptr p_v ) // Задает список термов (терминалов, нетерминалов, операционных символов) грамматики.

    Класс представляющий формальную грамматику. Основной класс ядра.

    Класс Token- токен

    Token
    int getLine ( ) // Возвращает номер строки, из которой взят токен.
    int getPos ( ) // Возвращает номер позиции в строке, из которой взят токен.
    void  getText (   ) // Возвращяет текст токена
    void  setLine ( int p_line ) // Задает номер строки, из которой взят токен.
    void  setPos ( int p_pos ) // Задает номер позиции в строке, из которой взят токен.

    Токен- основная единица анализируемой цепочки.

    Класс LL1Table- управляющая таблица для ЛЛ1 анализатора

    LL1Table
    void  clear ( ) // Очищает таблицу.
    void fromXML ( string p_XML ) // Конструирует объект из XML строки
    ll1_cell getCell ( Term::ptr p_t1 , Term::ptr p_t2 ) // Возвращает ячейку таблицы находящейся на пересечении строки и столбца соответствующей двум термам
    void  prepare ( ) // Подготавливает таблицу к заполнению, формируя ячейки, значения которых не зависят от правил грамматики (ВЫБРОС, ДОПУСК).
    void  setCell ( Term::ptr p_t1 , Term::ptr p_t2 , ll1_cell p_cell ) // Устанавливает ячейку.

    Класс- управляющая таблица для ЛЛ1 анализатора. Хранит необходимую информацию для работы парсера ЛЛ1 грамматик. Содержит внутри себя объявление перечислимого типа cell_type (тип ячейки) и класс ll1_cell (ячейка ЛЛ1 таблицы).

    Класс PrecedenceMatrix- матрица предшествования

    PrecedenceMatrix
    void  clearEqual ( Term::ptr p_t1 , Term::ptr p_t2 ) // Для двух термов удаляет отношение =
    void  clearLess ( Term::ptr p_t1 , Term::ptr p_t2 ) // Для двух термов удаляет отношение <
    void  clearMore ( Term::ptr p_t1 , Term::ptr p_t2 ) // Для двух термов удаляет отношение >
    void fromXML ( string p_XML ) // Конструирует объект из XML строки
    BOOL isEqual ( Term::ptr p_t1 , Term::ptr p_t2 ) // Возвращает TRUE, если p_t1 = p_t2, FALSE- иначе
    BOOL isLess ( Term::ptr p_t1 , Term::ptr p_t2 ) // Возвращает TRUE, если p_t1 < p_t2, FALSE- иначе
    BOOL isMore ( Term::ptr p_t1 , Term::ptr p_t2 ) // Возвращает TRUE, если p_t1 > p_t2, FALSE- иначе
    void  setEqual ( Term::ptr p_t1 , Term::ptr p_t2 , BOOL p_value = TRUE ) // Для двух термов устанавливает отношение =
    void  setLess ( Term::ptr p_t1 , Term::ptr p_t2 , BOOL p_value = TRUE ) // Для двух термов устанавливает отношение <
    void  setMore ( Term::ptr p_t1 , Term::ptr p_t2 , BOOL p_value = TRUE ) // Для двух термов устанавливает отношение >

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

     
       
    © С. Григорчук 2001, Содержание, дизайн
    ukman@yandex.ru
    Hosted by uCoz