Нерекурсивный предиктивный анализ

Предиктивные анализаторы

Во многих случаях аккуратная разработка грамматики, устранение из нее левой рекурсии и ее левая факторизация позволяют получить грамматику, которая может быть проанализирована синтаксическим анализатором, работающим методом рекурсивно спуска и не требующим отката. Для построения предиктивного синтаксического анализатора необходимо знать, какая из альтернатив A → α₁|α₂|…|α_n данного анализируемого нетерми­нала A, порождает строку, начинающуюся с полученного входного символа а. То естьправильная альтернатива должна точно определяться по первому, порождаемому ею символу. Обычно в языках программирования управляющие конструкции отвечают этому правилу. Например, если есть продукции

stmt → if expr then stmt else stmt |while expr do stmt | begin stmt _list end

то ключевые слова if, while и begin однозначно определяют возможную альтернативу для рассматриваемой инструкции stmt.

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

Рис. 28. Модель нерекурсивного предиктивного синтаксического анализатора

Предиктивный синтаксический анализатор включает в себя:

управляющую программу, входной буфер, стек, таблицу разбора и выходной поток. Входной буфер содержит анализируемую строку с маркером ее правого конца — специальным символом. Стек содержит последовательность символов грамматики с символом $ на дне. Изначально стек содержит стартовый символ грамматики непосредственно над символом $. Таблица разбора представляет собой двухмерный массив М[А, а], где А — нетерминал, а а — терминал или символ $.

Синтаксический анализатор управляется программой, которая работает следующим образом. Программа рассматривает X — символ на вершине стека, и а, текущий входной символ. Эти два символа определяют действия синтаксического анализатора. Имеется три варианта:

1. Если Х=а=$, синтаксический анализатор прекращает работу и сообщает об успешном завершении разбора.

2. Если Х=а≠$, синтаксический анализатор снимает со стека X и перемещает указатель входного потока к следующему символу.

3. Если X представляет собой нетерминал, программа рассматривает запись M[Х, а] таблицы разбора М. Эта запись представляет собой либо X -продукцию грамматики, либо запись об ошибке. Если, например, М[ Х, а] = {X → UVW}, синтаксический анализатор замещает X на вершине стека на WVU (с U на вершине стека). В качестве выхода синтаксический анализатор просто выводит использованную продукцию. Если M[Х, а] = error, синтаксический анализатор вызывает программу восстановления после ошибки.

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

Дата добавления: 2014-12-27