А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 21
Текст из файла (страница 21)
2.18, а. Цель заключается в построении оставшегося дерева разбора таким способом, чтобы строка, сгенерированная деревом разбора, соответствовала входной строке. Для получения соответствия нетерминал згтг на рис. 2.18, а должен порождать строку, которая начинается с предсимвола 1ог. В грамматике на рис. 2.16 имеется только одна продукция для кппб которая может породить такую строку, так что мы выбираем ее и строим дочерние узлы корня, помеченные символами из тела зтой продукции. Соответствующий рост дерева разбора показан на рис.
2.18, б. На каждом из трех "снимков" дерева на рис. 2.18 стрелки указывают сканируемый символ входной строки и рассматриваемый узел дерева разбора. Как только у узла дерева создаются дочерние узлы, следует рассмотреть крайний слева узел. На рис. 2.18, б только что были созданы дочерние по отношению к корню узлы и рассматривается крайний слева узел, помеченный как 1ог. Если рассматриваемый узел дерева разбора представляет терминал и зтот терминал соответствует сканируемому символу, мы перемещаемся как по дереву разбора, так и по входной строке.
На рис. 2.18, в стрелка в дереве разбора перемешается к следующему дочернему узлу корня, а во входном потоке — к следующему терминалу, который в данном случае представляет собой (. Дальнейшее перемещение стрелки в дереве разбора приведет ее в дочерний узел, помеченный нетерминалом оргекрг, а во входной строке — к терминалу; . Дословно — "предвиденный символ'*. — Прим. лер. 2.4. Разбор Дерево разбора зонт а) Гог (; ехрг; ехрг ) ожег Входная строка Дерево разбора -Ю г~ б) Гог (; ехрг; ехрг ) о(аег Входная строка Дерево разбора Г! '~ Гог ( ортехрг; ортехрг; ортехрг ) зтгят в) Гог (; ехрг; ехрг ) ответ Входная строка Рис. 2.18. Нисходящий разбор прн сканировании слева направо В нетерминальном узле, помеченном ор(ехр», мы повторяем процесс выбора продукции для нетерминала.
Продукция, в теле которой находится е ("е-продукция'*) требует специального рассмотрения. В настоящее время мы используем ее по умолчанию, если ни одна другая продукция не может быть использована; мы вернемся к этому вопросу в разделе 2.4.3. При нетерминале ор(ехрг и сканируемом символе; используется е-продукция, поскольку; не соответствует единственной другой продукции для ор(ехрг, в теле которой имеется терминал ехрг. В общем случае выбор продукции для нетерминала может включать метод проб и ошибок, т.е. следует испытывать продукции, возвращаться и пробовать другие, если испытанная оказалась неподходящей.
Продукция является неподходящей, если после ее использования не получается завершить дерево, соответствующее входной строке. Однако возврат оказывается излишним в важном частном случае предикгивного анализа, который будет рассматриваться в следующем разделе.
104 Глава 2. Простой синтаксически управляемый транслятор 2.4.2 Предиктивный анализ Анализ методом рекурсивного спуска (геспгяче-дезсеп( рагяпя) представляет собой способ нисходящего синтаксического анализа, при котором для обработки входной строки используется множество рекурсивных процедур (с каждым нетерминалом грамматики связана своя процедура). Здесь будет рассмотрен простой вид анализа методом рекурсивного спуска, именуемый предиктивным (нли предсказываюи(им) анализом (ргед(с((ие рагяпя), при котором сканируемый символ однозначно определяет поток управления в теле процедуры для каждого нетерминала.
Последовательность вызовов процедур при обработке входной строки неявно определяет его дерево разбора и при необходимости может использоваться для его явного построения. Предиктивный анализатор на рис. 2.19 состоит из процедур для нетерминалов вгт~ и ор(ехр» грамматики на рис. 2.16 и дополнительной процедуры тагсп, использующейся для упрощения кода для ятг и оргехр».
Процедура тагсй (1) сравнивает свой аргумент 1 со сканируемым символом и переходит к следующему символу в случае соответствия. Она изменяет значение глобальной переменной (оо1апеад, которая хранит сканируемый входной терминал. Анализ начинается с вызова процедуры для стартового нетерминала згтп Для той же входной строки, что и на рис. 2.18, переменная 1оо1апеад изначально представляет собой первый терминал Гог. Процедура згтг выполняет код, соответствующий продукции згтг — (ог ( оргехр»; ор1ехр»; ор(ехр» ) вгт~ В коде для тела продукции — т.е.
для 1ог в процедуре ятг — каждый терминал проверяется на соответствие сканируемому символу, а каждый нетерминал приводит к вызову соответствующей процедуры путем следующей последовательности вызовов: таге((ог); тагсд(~ ( ); оргехр»()' та(сл( г ); оргехр»()' тагсп('; ~); оргехр»() тагсл( ) ); ят~О; Предиктивный анализ основан на информации о первых символах, которые могут быть сгенерированы телом продукции. Говоря более строго, пусть о — строка символов грамматики (терминалов и/или нетерминалов).
Определим Р1КЯТ (о) как множество терминалов, которые могут появиться в качестве первого символа одной или нескольких строк, сгенерированных из а. Если а представляет собой е или может порождать е, то е также входит в Е(КИТ (о). Детальное вычисление Е)В5Т (а) приведено в разделе 4.4.2. Здесь же мы воспользуемся рассуждениями для вывода символов в Р1 КИТ (о) для частного случая.
!05 2А. Разбор чо!д в«т«() ( язч)«сЬ ( «ооха!«еа««) ( саяе ехрг: та«с!«(ехрг)' та«с!«(; ); Ьгеа1«; саве !й та«с!«(!!); та«с!«('('); та«с!«(ехрг)' та«с!«(') '); в«т«() Ьгеа)«; саяе Тот: та«с!«(аког); та«с!«(' ('); ор«ехрг()' та«с)«( 1'); ор«ехрг()' та«с!«( 1 ); ор«ехрг()' та«с!«(') '); в«т«()' Ьгеа)с; саяе о«Ьег; та«с!«(о«Ьег); Ьгеа1«; «)еГац!1: герог«("вупсах еггог"); чоЫ ор«ехргО ( !( ( !ио!«а««еа«! == ехрг ) та«с!«(ехрг); чоЫ та«с!«(!епп)па! «) ( !1 ( «ооха!«еа«! == 1 ) «оо!«а!«еа«« = пех«Тептппа1; е!ве «ерог«(" вупсах еггог"'); Рнс. 2.19.
Псевдокод преднктивного анализатора Обычно о начинается либо с терминала, который, таким образом, является единственным символом в НК5Т (о), либо с нетерминала, тела продукций которого начинаются с терминалов (и в данном случае в НКБТ (о) входят только эти терминалы). Например, что касается грамматики на рис. 2.16, то вот примеры корректных вычислений Р!КоТ (о): р!ККТ(х«т«) = (ехрг, !Г, !ог, отйег) НКЯТ(ехрг 1) = (ехрг) Множества НКБТ должны рассматриваться, если существуют две продукции А — о и А — Ц.
Игнорируя пока что е-продукции, предиктивный анализатор 106 Глава 2. Простой синтаксически управляемый транслятор требует, чтобы множества НКЯТ (о) и НКЯТ ф) были непересекающимися. Тогда текущий сканируемый символ может использоваться для принятия решения, какую из продукций следует применить. Если сканируемый символ принадлежит множеству НКБТ (о), используется продукция а; в противном случае, если сканируемый символ принадлежит множеству НКЯТ (11), применяется продукция 11. 2.4.3 Использование пустых продукций Наш предиктивный анализатор использует е-продукцию в качестве продукции по умолчанию, когда не могут быть использованы никакие другие продукции. Для входной строки, приведенной на рис. 2.18, после соответствия терминалов 1ог и ( сканируемым символом становится;. В этот момент вызывается процедура арГехр», а в ее теле выполняется код 1Г( 1оо1галеаг1 = — ехрг ) тагсй(ехрг); Нетерминал оргехр» имеет две продукции, с телами ехрг и е.
Сканируемый символ; не соответствует терминалу ехрг, так что продукция с телом ехрг неприменима. Реально происходит возврат из процедуры без изменения текущего сканируемого символа или выполняются какие-то иные действия. Случай, когда процедура ничего не делает, соответствует применению е-продукции. Рассмотрим более общий случай продукции на рис. 2.1б, где аргехр» генерирует нетерминальное выражение вместо терминала ехрг: ор1ехр» — ~ ехр» Таким образом, оргехр» генерирует либо выражение с использованием нетерминала ехр», либо е.
При анализе аргехр», если сканируемый символ не принадлежит ЯКУТ (ехрг), используется е-продукция. Дополнительную информацию о том, когда применяются е-продукции, можно почерпнуть из раздела 4.4.3, посвященного Щ1)-грамматикам.
2.4.4 Разработка предиктивного анализатора Можно обобщить неформально описанные в разделе 2.4.2 методы для применения к любой грамматике, которая обладает непересекающимися множествами НКЯТ для тел продукций, принадлежащих нетерминалам. Мы также увидим, что если имеется схема трансляции — т.е. грамматика с внедренными действиями,— то этн действия можно выполнять как часть процедур, разработанных для анализатора.
Вспомним, что предиктивный анализатор представляет собой программу, состоящую из процедур для каждого нетерминала. Каждая такая процедура для нетерминала А решает две задачи. 2.4. Разбор 1. Принимает решение, какая А-продукция будет использоваться, исходя из текущего сканируемого символа. Если сканируемый символ принадлежит множеству ЕИБТ (а), применяется продукция с телом а (где а не является пустой строкой г).
В случае конфликта двух непустых тел для некоторого сканируемого символа этот метод анализа для рассматриваемой грамматики неприменим. Кроме того, е-продукция для А, если таковая существует, используется в случае, когда сканируемый символ отсутствует в множестве Р1ВВТ для всех остальных тел продукций для А. 2. Процедура имитирует тело выбранной продукции, т.е.
символы тела "выполняются" по очереди, слева направо. Нетерминал "выполняется" путем вызова процедуры, соответствующей этому нетерминалу, а терминал, соответствующий текущему сканируемому символу, — путем чтения следующего входного сканируемого символа. Если в какой-то момент терминал продукции не соответствует сканируемому символу, сообщается о наличии синтаксической ошибки. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
