А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 58
Текст из файла (страница 58)
Грамматика С принадлежит классу 1Д.(1) тогда и только тогда, когда для любых двух различных продукций С А — гт ~ (3 выполняются следующие условия. 1. Не существует такого терминала а,, для которого и о, и (3 порождают строку, начинающуюся с в. 2. Пустую строку может порождать не более чем одна из продукций а или (3. 3. Если 13 =~ е, то о не порождает ни одну строку, начинающуюся с терминала из ГОП.0%(А). Аналогично, если а ~ е, то 13 не порождает ни одну строку, начинающуюся с терминала из ГОББЛ.0% (А). Первые два условия эквивалентны утверждению, что НКБТ (а) и НКЯТ (Д) представляют собой непересекающиеся множества.
Третье условие эквивалентно утверждению, что если е е ГИНУТ(13), то НКЯТ(а) и ЕОЫ.0%(А) — непересекающиеся множества; аналогичное утверждение справедливо и в случае, если е Е НК8Т (я). Для ЕЕ(1)-грамматик могут быть построены предиктивные синтаксические анализаторы, поскольку коррекгная продукция для применения к нетерминалу может быть выбрана путем просмотра только текущего входного символа.
Конструкции управления потоком с нх определяющими ключевыми словами обычно удовлетворяют ограничениям Е!.(1). Например, пусть имеются продукции к!пп — и (ехрг) зпиг е!яе згвп' и'Ы!е (ехрг) зппг (яппг Йгг) Тогда ключевые слова 1г, и Ьйе и символ ( говорят, какая из альтернатив должна быть выбрана, когда мы встречаемся с инструкцией. Приведенный далее алгоритм собирает информацию из множеств НКБТ и ГОП.0% в таблицу прсдиктивного синтаксического анализа М(А,а) (представляющую собой двумерный массив), где А — нетерминал, а а — терминал или 289 4А.
Нисходящий синтаксический анализ Диаграммы переходов для предиктивных синтаксических анализаторов Диаграммы переходов полезны для визуализации предиктивных синтаксических анализаторов. Например, на рис. 4.16, а показаны диаграммы для нетерминалов Е и Е' грамматики (4.14). Для построения диаграммы переходов на основе грамматики сначала требуется удалить из нее левую рекурсию, а затем выполнить левую факторизацию грамматики.
Затем необходимо для каждого нетерминала А 1) создать начальное и конечное состояния; 2) для каждой продукции А — ХзХз... Хь создать путь из начального в конечное состояние с дугами, помеченными Хы Хщ..., Хь, если А — е, путь представляет собой ребро, помеченное г.
Диаграммы переходов для предикгивных синтаксических анализаторов отличаются от диаграмм переходов для лексических анализаторов. Синтаксические анализаторы имеют по диаграмме для каждого нетерминала. Метки ребер могут быть токенами или нетермнналами. Переход для токсна (или терминала) означает; что этот переход будет выполнен, если этот токен будет очередным входным символом. Переход для нетерминала А представляет собой вызов процедуры для А.
В случае Щ1)-грамматики неоднозначность, связанная с решением о том, использовать ли е-переход, может быть разрешена, если считать епереход выбором по умолчанию. Диаграммы переходов могут быть упрощены при сохранении грамматических символов вдоль путей. Можно также вместо дуг для нетерминалов подставить диаграммы переходов для этих нетерминалов. Диаграммы на рис. 4.16, а и б эквивалентны: если мы проследим путь от Е до принимающего состояния и выполним подстановку для Е', то заметим, что в обоих множествах диаграмм символы вдоль путей образуют строки вида Т+ Т + + .. + Т.
Диаграмма на рис. 4.16, б может быть получена из диаграммы а путем преобразований, подобных описанным в разделе 2.5.4, где использовались устранение оконечной рекурсии и подстановка тел процедур для оптимизации процедуры нетерминала. символ 3 (маркер конца входного потока). Алгоритм основан на следующей идее: если очередной входной символ а находится в множестве Е(КБТ (о), выбирается продукция А — а. Единственная сложность возникает при а = с или, в общем 290 Глава 4.
Синтаксический анализ Е: б) а) Рнс. 4.16. Диаграммы переходов лля нетерминалов Е и Е' грамматики (4.14) случае, когда гг =~ г. В этом случае мы снова должны выбрать А — о, если текущий входной символ имеется в РО?Л 0%(А) или если из входного потока получен 3, который при этом входит в Р01Л.0% (А). Алгоритм 4.17. Построение таблицы предиктивного синтаксического анализа Вход: грамматика С. Выход: таблица синтаксического анализа М. Митод: для каждой продукции грамматики А — а выполняем следующие действия.
1. Для каждого терминала а из НКВТ (о) добавляем А — а в ячейку М [А, а]. 2. Если гЕ НКЯТ(а), то для каждого терминала 6 из Р01Л.0% (А) добавляем А — гг в М [А, 6]. Если е Е ЯКУТ(а) и 3 Е Р01Л 0%(А), то добавляем А — а также и в М [А, 3]. Если после выполнения этих действий ячейка М [А, а] осталась без продукции, устанавливаем ее значение равным еггог (это значение обычно представляется пустой записью таблицы). и Пример 4.18. Для грамматики выражений (4.14) алгоритм 4.17 дает таблицу синтаксического анализа, приведенную на рис. 4.17. Пустые места в таблице означают записи ошибок; непустые указывают продукции, при помощи которых выполняется разворачивание нетерминала.
Рассмотрим продукцию Š— Т Е'. Поскольку Р)КВТ (т Е') = Р1КВТ(т) = ((, и), эта продукция добавляется к М [Е, (] и М [Е, И]. Продукция Е' — +Т Е' добавляется к М [Е', +], поскольку ЯКУТ (+Т Е') = (+). Так как Р01Л.0%(Е') = = (), 3), продукция Е' — е добавляется к М [Е', )] и М [Е', 3]. Алгоритм 4.17 может быть применен для получения таблицы М к любой грамматике С.
Для любой Щ1)-грамматики каждая запись в таблице синтаксического 291 4.4. Нисходящий синтаксический анализ Рис. 4.17. Таблица синтаксического анализа М к примеру 4.18 анализа единственным образом определяет продукцию либо сообщает об ошибке. Однако для некоторых грамматик таблица М может иметь записи с несколькими продукциями.
Например, если С вЂ” леворекурсивная или неоднозначная грамматика, таблица М будет содержать как минимум одну запись с несколькими продукциями. Хотя устранение левой рекурсии и левая факторизация — легко выполняемые задачи, существуют такие грамматики, никакие изменения которых не приведут к Щ1)-грамматике. Язык в следующем примере не является Щ1)-грамматикой.
Пример 4.19. Следующая грамматика, абстрагирующая проблему "висящего е!зе", взята из примера 4.11: Š— г Е1Е У ~ а 5' — е Е ( г Š— 6 Таблица синтаксического анализа для этой грамматики показана на рис. 4.!8. Запись М (У, е) в ней содержит как У вЂ” е Е, так и У— Рис. 4.18. Таблица синтаксического анализа М к примеру 4.!9 Грамматика неоднозначна, и эта неоднозначность проявляется в выборе используемой продукции при встрече во входном потоке е (е!яе). Эту неоднознач- 292 Глава 4. Синтаксический анализ ность можно разрешить путем выбора продукции У вЂ” е Я. Данный выбор соответствует связыванию еие с ближайшим предыдущим Феп. Заметим, что выбор У вЂ” е приводит к тому, что е не помещается в стек и не удаляется из входного потока, что, очевидно, неверно.
и 4.4.4 Нерекурсивный предиктивный синтаксический анализ Нерекурсивный предикгивный синтаксический анализатор можно построить с помощью явного использования стека (вместо неявного при рекурсивных вызовах). Синтаксический анализатор имитирует левое порождение. Если в — входная строка, соответствие которой проверено до текущего момента, то в стеке хранится последовательность грамматических символов тт, такая, что Синтаксический анализатор на рис.
4.19, управляемый таблицей синтаксического анализа, имеет входной буфер, стек, содержащий последовательность грамматических символов, таблицу синтаксического анализа, построенную при помощи алгоритма 4.17, и выходной поток. Входной буфер содержит анализируемую строку, за которой следует маркер конца строки 3. Мы также используем символ 3 для указания дна стека, который изначально содержит над символом 3 стартовый символ грамматики. Входной Стек Выходной поток Рис. 4.19. Модель синтаксического анализатора, управляемого таблицей синтаксического анализа Синтаксический анализатор управляется программой, которая рассматривает символ на вершине стека Х и текущий входной символ а. Если Х является нетерминалом, синтаксический анализатор выбирает Х-продукцию в соответствии с записью ЛХ [Х, а~ таблицы синтаксического анализа М.
(Здесь может выполняться 293 4.4. Нисходящий синтаксический анализ дополнительный код, например, для построения узла дерева разбора.) В противном случае проверяется соответствие между терминалом Х и влекущим входным символом о. Поведение синтаксического анализатора может быть описано в терминах его конфигураций (сопбнигаг!оп), которые дают содержимое стека и оставшийся входной поток. Приведенный далее алгоритм описывает работу с конфигурациями. Алгоритм 420. Предиктивный синтаксический анализ, управляемый таблицей Вход: строка ю и таблица синтаксического анализа М для грамматики С.
Выход: если и е 7, (С) — левое порождение гс; в противном случае — сообщение об ошибке. Метод: изначально синтаксический анализатор находится в конфигурации с иб во входном буфере и стартовым символом Я грамматики С на вершине стека, над 3. Программа на рис. 4.20 использует таблицу предиктивного синтаксического анализа М для анализа входной строки. о Устанавливаем указатель входного потока !р так, чтобы он указывал на первый символ строки в; Устанавливаем Х равным символу на вершине стека; ттЫ!е ( Х ф 3 ) 1 !* Стек не пуст */ Устанавливаем а равным символу, на который в настоящий момент указывает !р !!'( Х равен а ) ( Снимаем символ со стека и перемещаем 1р к следующему символу строки; е!яе !!' ( Х -- терминал ) еггого; е!яе !!' ( М [Х, а] — запись об ошибке ) еггогО; е!яе !!' ( М [Х, а] = Х вЂ” У~ Уз...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
