А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 56
Текст из файла (страница 56)
Все идентификаторы представлены в их грамматиках токеном, таким как Ы. В компиляторах этих языков проверка 280 Глава 4. Синтаксический анализ того, что идентификаторы объявлены до их использования, производится на фазе семантического анализа. Пример 4.13. Не контекстно-свободный язык в этом примере абстрагирует проблему проверки соответствия количества фактических параметров при вызове функции количеству формальных параметров в ее объявлении. Язык состоит из строк вида а" 6'"с"с1™ (вспомните, что а" означает а, записанное и раз). Здесь а" и 1з могут представлять списки формальных параметров двух функций, объявленных с п, и т аргументами соответственно, в то время как с" и д™ представляют списки фактических параметров в вызовах этих двух функций.
Упомянутый абстрактный язык — 2,з = 1а"6™с"И ~ и > 1 и т ) 11, т.е. 2,з состоит из строк, генерируемых регулярным выражением а*Ь*с*с1*, причем количество а в строке равно количеству с, а количество б — количеству с1. Этот язык не является контекстно-свободным. Опять же, типичный синтаксис объявления и использования функции сам по себе не рассматривает количество ее параметров.
Например, вызов функции в С- подобном языке может быть определен как злпг — Ы (ехрг 1Ы1) ехрг 1и1 — ехрг 1и1, ехрг ехрг с соответствующими продукциями для ехрг. Проверка того, что число действительных параметров в вызове корректно, обычно выполняется во время семантического анализа. а 4.3.6 Упражнения к разделу 4.3 Упражнение 4.3.1. Ниже приведена грамматика для регулярных выражений над символами а и б (с использованием + вместо ~ для обозначения объединения, чтобы избежать конфликта с использованием вертикальной черты как метасимвола грамматики): гехрг — гехрг + ггегт ~ ггегт гГегт — гГегт г1асгог ( г/ас1ог ~ас1ог — ~ г)ас1ог * ~ грггтагу гритагу — ~ а ~ Ь а) Выполните левую факторизацию данной грамматики.
б) Делает ли левая факторизация данную грамматику пригодной для нисходящего синтаксического анализа? 2В! 4.4. Нисходящий синтаксический анализ в) В дополнение к левой факторизации устраните из исходной грамматики левую рекурсию. г) Является ли полученная грамматика пригодной для нисходящего синтаксического анализа? Упражнение 4.3.2. Повторите упражнение 4.3.1 для следующих грамматик. а) Грамматика из упражнения 4.2.1. б) Грамматика из упражнения 4.2.2, а. в) Грамматика из упражнения 4.2.2, в.
г) Грамматика из упражнения 4.2.2, д. д) Грамматика из упражнения 4.2.2, ж. згтг Ы ехрг !йеп зплг тагслеИЯплг тшслеЫгт~ — !1 ехрг 1пеп тагслейбгтг еае згтг обжег Покажите, что эта грамматика остается неоднозначной. 4.4 Нисходящий синтаксический анализ Нисходящий синтаксический анализ можно рассматривать как задачу построения дерева разбора для входной строки, начиная с корня и создавая узлы дерева разбора в прямом порядке обхода (обход в птубину, рассматривавшийся в разделе 2.3.4).
Или, что то же самое, нисходящий синтаксический анализ можно рассматривать как поиск левого порождения входной строки. Пример 4.14. На рис. 4.!2 приведена последовательность деревьев разбора для входной строки Ы + !д * Ы, представляющая собой нисходящий синтаксический анализ в соответствии с грамматикой (4.2), повторенной далее: Š— Т Е' Е' — + Т Е' ~ е Т вЂ” Р Т' Т' — + я Р Т') е Š— (Е)! и! (4.14) ! Упражнение 4.3.3.
Приведенная ниже грамматика предложена для устранения "неоднозначности висящего е!яе", рассматривавшегося в разделе 4.3.2: 282 Глава 4. Синтаксический анализ Е ~ Е ~ Е ~ Е 7т / ~ !т / ~ 7т / ', Т Е' Т Е' Т Е' / ) / 1 Е 7" Е Т' Ы 7а / ~ !т / Т Е' Т Е' /~ /! /!' Е Т Е Т + ТЕ' ! ! Ы е Ы / ' 7т /~ )'~ Е Т' + Т Е' / Ы е Е 7 ! !а / ', 7т т Е' /! / '~ Е Т' + Т Е' ! /'. Ы г Е T Е Т Е' /~ Е Т' + Т Е' ! ! /'~ Ы е Е 7 1 /!'~ Е > 7т ' 7а )~ Л~ Е Т' + Т Е' / '~ Ы е Е 7 /1" Ы ~ Е Т' 7т /1 Е Т' + Т Е' Ы е Е Т' Ы г / '~ )! )' Е 7" + Т Е' ! /', ! 16 е Е 7" е /! '. Ы ° Е Т' ! ! Ы г Рис. 4.12.
Нисходящий синтаксический анализ лля входной строки И+ И*И Эта последовательность деревьев соответствует левому порождению входной строки. и На каждом шаге нисходящего синтаксического анализа ключевой проблемой является определение продукции, применимой для нетерминала, скажем, А. Когда А-продукция выбрана, остальная часть процесса синтаксического анализа состоит из проверки "соответствий" терминальных символов в теле продукции входной строке. Этот раздел начинается с общего вида нисходящего разбора, называющегося синтаксическим анализом методом рекурсивного спуска, который может потребовать возврата (отката — Ьас)гтгасЫпй) для поиска корректной А-продукции, которая должна быть применена.
В разделе 2.4.2 рассказывалось о предиктивном синтаксическом анализе — частном случае синтаксического анализа методом рекурсивного спуска, не требующем возврата. Предиктивный синтаксический анализ выбирает корректную А-продукцию путем предпросмотра фиксированного количества символов входной строки; типичной является ситуация, когда достаточно просмотреть только один (очередной) входной символ. 4.4. Нисходящий синтаксический анализ Рассмотрим, например, нисходящий синтаксический анализ на рис. 4.12, который строит дерево с двумя узлами, помеченными Е'. В первом (в прямом порядке обхода) узле Е' выбирается продукция Е' — +Т Е', во втором узле Е' выбирается продукция Е' — е.
Предиктивный синтаксический анализатор может выбрать нужную Е'-продукцию, просматривая очередной входной символ. Класс грамматик, для которых можно построить предикгивный синтаксический анализатор, просматривающий к символов во входном потоке, иногда называется классом ЬЬ(к). Класс 1.Ь(1) будет рассматриваться в разделе 4.4.3, но некоторые необходимые при рассмотрении вычисления, НКЯТ и РОЬЬО%, будут рассмотрены в разделе 4.4.2. Из множеств НКЯТ и РОЬЬО% грамматики можно построить "таблицы предиктивного анализа", которые делают явным выбор продукции при нисходящем синтаксическом анализе.
Зги таблицы применяются также и при восходящем синтаксическом анализе. В разделе 4.4.4 будет приведен нерекурсивный алгоритм синтаксического анализа, использующий стек явно, а не посредством рекурсивных вызовов. Наконец, в разделе 4.4.5 будет рассмотрен вопрос восстановления после ошибок в процессе нисходящего разбора. 4.4.1 Синтаксический анализ методом рекурсивного спуска Программа синтаксического анализа методом рекурсивного спуска (гесшз!чедезсеп! рагз!пя) состоит из набора процедур, по одной для каждого нетерминала. Работа программы начинается с вызова процедуры для стартового символа и успешно заканчивается в случае сканирования всей входной строки. Псевдокод для типичного нетерминала показан на рис.
4.13. Обратите внимание на то, что этот псевдокод недетерминированный, поскольку он начинается с выбора А- продукции дпя применения не указанным способом. чоЫ А() ( 1) Выбираем А-продукцию А — Х!Хз... Хь, 2) Гог(тот!до/с)( 3) И ( Х, — нетерминал ) 4) Вызов процедуры Х, (); 5) е1яе И ( Х, равно текущему входному символу а ) 6) Переходим к следующему входному символу; 7) ене /* Обнаружена ошибка */; Рис.
4.! 3. Типичная процедура дпя нетерминапа в нисходящем анализаторе 284 Глава 4. Синтаксический анализ Пример 4.15. Рассмотрим грамматику Ь' — сАЫ А — аЬ)а Чтобы построить дерево разбора для входной строки ш = сад, начнем с дерева, состоящего из единственного узла с меткой Я, и указателя входного потока, указывающего на с, первый символ ш.
Я имеет единственную продукцию, так что мы используем ее для разворачивания Я и получения дерева, показанного на рис. 4.14, а. Крайний слева лист, помеченный с, соответствует первому символу входного потока ш, так что мы перемещаем указатель входного потока к а, второму символу и, и рассматриваем следующий лист, помеченный А. Г!" Л' /~ Г!' с А Н а Ь а) Рвс. 4.14.
Шаги нисходящего синтаксического анализа Теперь мы разворачиваем А с использованием первой альтернативы, А — а Ь, и получаем таким образом дерево, показанное на рис. 4.14, б. У нас имеется совпадение второго входного символа, а, так что мы переходим к третьему символу, Рекурсивный спуск в общем случае может потребовать выполнения возврата, т.е. повторения сканирования входного потока. Однако при анализе синтаксических конструкций языков программирования возврат требуется редко, так что встреча с синтаксическим анализатором с возвратом — явление не частое.
Даже в ситуациях наподобие синтаксического анализа естественного языка возврат не слишком эффективен, и предпочтительными являются табличные методы наподобие динамического программирования из упражнения 4.4.9 или метода Эрли (Еаг)еу) (см. список литературы к главе 4). Чтобы разрешить возврат, код на рис. 4.13 должен быть немного модифицирован.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
