spoPresentation2

Детерминированные МП - автоматы

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

Функция переходов ДМПА G может иметь

один из трех видов:

G ( q, a, z) содержит 1 элемент G ( q, a, z ) = { ( q’, J ) }, J Z*, G ( q, O, z ) =

G ( q, a, z) = , G ( q, O, z ) содержит 1 элемент

G ( q, O, z) = { ( q’, J ) }, J Z*

G ( q, a, z) = , G ( q, O, z ) =

241

Детерминированные МП - автоматы

Класс ДМПА и соответствующих им языков

значительно уже, чем весь класс МПА и КСязыков

В отличие от КА, для которого всегда можно

построить эквивалентный ему ДКА, не для каждого МПА можно построить эквивалентный ему ДМПА

ДМПА определяют очень важный подкласс

КС-языков – детерминированные КС-языки

Все языки этого подкласса, могут быть

построены с помощью однозначных КСграмматик

242

Детерминированные МП - автоматы

Не всякий язык, задаваемый однозначной КСграмматикой, является детерминированным

Большинство практически используемых распознавателей, относятся к классу детерминированных КС-языков

243

Нисходящий и восходящий разбор

Все распознаватели для КС-языков можно разделить на 2 большие группы

нисходящиевосходящие

Нисходящие просматривают входную цепочку символов слева направо и порождают левосторонний вывод

Дерево вывода таким распознавателем строится от корня к листьям (сверху вниз)

Для таких распознавателей используется алгоритм с подбором альтернатив

244

Нисходящий и восходящий разбор

Восходящие также просматривают входную цепочку слева направо, но порождают правосторонний вывод

Дерево вывода при этом строится от листьев к корню (снизу вверх)

Для таких распознавателей используется алгоритм “сдвиг-свертка”

Для ЯП в большинстве случаев легче построить правосторонний восходящий распознаватель

245

Нисходящий и восходящий разбор

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

На практике используются оба варианта

Конкретный выбор зависит от реализации конкретного компилятора и сложности грамматики входного языка

246

Нисходящий синтаксический анализ

В основе лежит левосторонний разбор

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

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

247

Нисходящий синтаксический анализ

И так до тех пор, пока очередные подцели не приведут к сравнению символов цепочки с терминалами, что и позволит сделать вывод о принадлежности цепочки языку

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

248

Нисходящий синтаксический анализ

В общем случае при нисходящем анализе возникают следующие проблемы:

Наличие леворекурсивных правил

Пусть цель – А, и первое же правило для А имеет вид АoАJ. Раз так, то будет

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

249

Нисходящий синтаксический анализ

В общем случае при нисходящем анализе возникают следующие проблемы:

Пусть при нисходящем анализе необходимо заменить самый левый нетерминал,

определяемый правилом вида: АoD1 | D2 |…| Dn. Какую из подстановок выбрать?

Общего подхода не существует. Есть следующие варианты:

250