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

Синтаксический анализ.

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

Этот радел посвящен в основном вопросам практической реализации синтаксических анализаторов (парсеров).

Почти все парсеры используют схожие структуры данных для анализа. Почти все они используют магазин (стек). Работой многих управляет специальная управляющая таблица. Для реализации стека использовался класс stack из STL. Управляющая таблица во многих случаях может быть реализована на основе ассоциативного массива map.

Библиотека содержит реализацию некоторых, широко используемых алгоритмов анализа.

Алгоритм анализа ЛЛ1 грамматик.

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

Анализатор реализован в классе LL1Parser. Этот класс осуществляет разбор цепочек целиком и по шагам, позволяет отслеживать свое состояние на каждом шаге своей работы. Для своей работы он требует формальную грамматику (FormalGrammar), управляющую таблицу (LL1Table), сканер (ITokenizer).

LL1Parser
string getXMLCfg ( int p_sp ) // Возвращает строку в формате XML, описывающую текущее состояние автомата.
int next (   ) // Осуществляет один шаг работы парсера. Возвращает -1, если произошла ошибка, 0, если анализ не закончен, 1, если парсер закончил свою работу.
int parse (   ) // Осуществляет полный цикл анализа цепочки. Возвращает 1, если не было обнаружено ошибок, -1, если встретились ошибки.
void  setFG ( FormalGrammar::ptr p_fg ) // Задает парсеру грамматику разбора.
void  setTable ( LL1Table::ptr p_t ) // Задает парсеру управляющую таблицу, для разбора.
void  setTokenizer ( ITokenizer::ptr p_tokenizer ) // Задает сканер, поставляющий лексемы для парсера.

Управляющая таблица ЛЛ1 анализатора

Управляющая таблица полностью определяет работу синтаксического анализатора. Ее построение берет на себя класс-алгоритм isLL1. Эта таблица реализована с помощью ассоциативного массива map.

Просмотр разбора входной цепочки по шагам.

Класс LL1Parser предоставляет метод next, который переводит автомат в следующее состояние. Для того, чтобы получить информацию о его состоянии необходимо получить XML строку методом getXMLCfg. Эта строка описывает состояние алгоритма и имеет следующий формат:

<ll1_parser_cfg>
  <stack>
    <stack_item term="E"/>
    <stack_item term="^"/>
  </stack>
  <cur_symbol term="e" text="e"/>
</ll1_parser_cfg>

Внутри тега ll1_parser_cfg находятся два тега- stack, который содержит все символы стека начиная с верхнего и тег cur_symbol, описывающий текущий символ на ленте.

Используя эту XML строку можно визуально отобразить состояние алгоритма в любой момент времени.

Алгоритм анализа грамматик предшествования.

Алгоритм разбора для грамматик предшествования работает по принципу "перенос-свертка" и относится к восходящим методам разбора. Этот алгоритм использует стек и входную ленту. В каждый момент времени автомат обозревая очередной символ на входной цепочке и зная состояние магазина выполняет одно из следующих действий:

  • закончить разбор в состоянии ОШИБКА
  • закончить разбор в состоянии ДОПУСК
  • перенести обозреваемый символ в стек (ПЕРЕНОС)
  • свернуть верхушку стека к определенному нетерминалу (СВЕРТКА)

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

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

    Алгоритм разбора реализован в классе carryRollParser. Для работы необходимо проинициализировать объект этого класса: задать формальную грамматику для разбора (FormalGrammar, лексический анализатор, поставляющий лексемы (ITokenizer), матрицу предшествования (PrecedenceMatrix). Для анализа можно использовать пошаговый режим работы (с возможностью контролировать состояние алгоритма на каждом шаге) и режим полной проверки, цепочки.

    carryRollParser
    string getCfg ( int p_sp ) // Возвращает в виде строки XML полную информацию о текущем состоянии алгоритма.
    action_type next (   ) // В пошаговом режиме переводит алгоритм на следующий шаг.
    BOOL parse (   ) // Запускает анализатор в режиме полной проверки входной цепочки.
    void  setFG ( FormalGrammar::ptr p_fg ) // Задает формальную грамматику для разбора.
    void  setPM ( PrecedenceMatrix::ptr p_pm ) // Задает матрицу предшествования для разбора.
    void  setTokenizer ( ITokenizer::ptr p_tokenizer ) // Задает лексический анализатор, поставляющий лексемы.

    Отношение предшествования. Матрица предшествования.

    Матрица предшествования практически является управляющей таблицей для работы алгоритма. Описанные выше отношения предшествования четко определяют каждое действие алгоритма. Для описания работы алгоритма введем две специальнные функции: f (функция переноса) и g (функция свертки).

    Функция f определена на множестве (V+^)x(Vt+e) следующим образом:

  • f(X,a) = ПЕРЕНОС, если X<a или X=a
  • f(X,a) = СВЕРТКА, если X>a
  • f(^S,e) = ДОПУСК
  • f(X,a) = ОШИБКА в остальных случаях

    • Функция g зависит от верхней части магазина, т.е. определена на множестве (X+^)*:

  • g(X(k+1),X(k),...X(1))=i, если X(k+1)<X(k)=X(k-1)=...=X(1) и A::=X(k)X(k-1)...X(1)- правило грамматики с номером i
  • g(v)= ОШИБКА в остальных случаях.

    • Просмотр разбора входной цепочки по шагам.

    В режиме пошаговой работы алгоритма анализа входной цепочки существует возможность просматривать состояние алгоритма. Для этого необходимо получить XML строку вызвав метод getCFG(). Состояние алгоритма полностью определяется текущим входным символом и состоянием стека, поэтому формат XML строки такой же как в ЛЛ1 парсере (см. "Просмотр разбора входной цепочки по шагам" для ЛЛ1-грамматик).

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