formal_languages_translation_theory (852748), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Можно попытаться поискать другую эквивалентную грамматику, к которой методприменим. Некоторые полезные для этого эквивалентные преобразования грамматик будут23)62Если бы в Gsequence последовательность терминалов, перечисляемых через запятую, завершалась отличнымот запятой символом (например, точкой с запятой), как это обычно и бывает в реальных языках программирования, то метод рекурсивного спуска был бы применим.Элементы теории трансляции / Синтаксический анализрассмотрены ниже. Однако, как следует из утверждения 12, успех в поиске эквивалентнойграмматики, для которой метод применим, не гарантирован.Преобразования грамматикЕсли грамматика не удовлетворяет требованиям применимости метода рекурсивногоспуска, то можно попытаться преобразовать ее, т.

е. получить эквивалентную грамматику,пригодную для анализа этим методом.(1) Если в грамматике есть нетерминалы, правила вывода которых непосредственнолеворекурсивны, т. е. имеют вид:A → A1 | ... | An | 1 | ... | m,+*где i  (T  N ) для i  1, 2, ..., n; j  (T  N ) для j  1, 2, ..., m, то в таком случае применять метод рекурсивного спуска нельзя, поскольку first(Ai)  first(Ak)   для некоторыхi  k, или j   для некоторого j и first (Аi)  follow (A)   для i  1, 2, ..., n.Левую рекурсию всегда можно заменить правой:A → 1 A′ | ... | m A′A′ → 1 A′ | ...

| n A′ | Будет получена грамматика, эквивалентная данной, т.к. из нетерминала A попрежнему выводятся цепочки вида j {i}, где i  1, 2, ..., n; j  1, 2, ..., m.(2) Если в грамматике есть нетерминал, у которого несколько правил вывода начинаются одинаковыми терминальными символами, т. е. имеют видA → a1 | a2 | ... | an | 1 | ... |m,*где a  T ; i, j  (T  N ) , j не начинается с a, i  1, 2,..., n, j  1, 2,..., m, то непосредственно применять метод рекурсивного спуска нельзя, т.

к. first(ai)  first(ak)   дляi  k. Можно преобразовать правила вывода данного нетерминала, объединив правила с общими началами в одно правило:A → aA′ | 1 | ... | mA′ → 1 | 2 | ... | nБудет получена грамматика, эквивалентная данной.(3) Если в грамматике есть нетерминал, у которого несколько правил вывода, и срединих есть правила, начинающиеся нетерминальными символами, т. е. имеют вид:A → B11 | ...

| Bnn | a11 | ... | ammB1 → 11 | ... | 1k…Bn → n1 | ... | np,*где Bi  N; aj  T; i, j, ij  ( T  N ) , то можно заменить вхождения нетерминаловBi их правилами вывода в надежде, что правила нетерминала A станут удовлетворять условиям применимости метода рекурсивного спуска:A → 111 | ... | 1k1 | ... | n1n | ... | npn | a11 | ... | amm63Элементы теории трансляции / Синтаксический анализ(4) Если есть правила с пустой альтернативой вида:A → 1 A | ...

| n A | 1 | ... | m| B → Aи first(A)  follow(A)   (из-за вхождения А в правила вывода для В), то можно построитьтакую грамматику:B → A′A′ → 1A′ | ... | n A′ | 1 | ... | m | Полученная грамматика будет эквивалентна исходной, т. к. из B по-прежнему выводятся цепочки вида  {i} j  либо  {i} .Однако правило вывода для нетерминального символа A′ будет иметь альтернативы,начинающиеся одинаковыми терминальными символами (т. к. first(A)  follow(A)  ); следовательно, потребуются дальнейшие преобразования, и успех не гарантирован.Пример.

Рассмотрим грамматику Gorigin:GoriginS → fASd | A → Aa | Ab | dB | fB → bcB | first(Aa)  first(Ab)  {d, f }first(bcB)  {b}, follow(B)  {a, b, d, f }Условия применимости метода рекурсивного спуска не выполняются для Gorigin. Спомощью преобразований приведем эту грамматику к каноническому виду для рекурсивногоспуска. Будем подчеркивать не удовлетворяющие каноническому виду правила и припереходе к новой грамматике указывать номер примененного преобразования (i) , 1  i  4 :Gorigin:SAB→ fASd | → Aa | Ab | dB | f→ bcB | (1)Gtransform1:SAA'B→ fASd | → dBA' | fA'→ aA' | bA' | → bcB | (4)first(S)  { f }, follow( S )  { d },first (S)  follow(S)  ;first(A')  {a, b}, follow(A') { f, d }, first (A')  follow(A')  ;first(B) {b}, follow(B) {a, b, f, d }, first(B)  follow(B) {b} .(4)64Gtransform2:SAB'A'→ fASd | → dB' | fA'→bcB' | A'→ aA' | bA' | (3)Gtransform3:SAB'A'→ fASd | → dB' | fA'→ bcB' | aA' | bA' | → aA' | bA' | Элементы теории трансляции / Синтаксический анализ(2)Gtransform4:SAB'CA'Gobject:→ fASd | → dB' | fA'→ bC | aA' | → cB' | A'→ aA' | bA' | (3)SAB'CA'→ fASd | → dB' | fA'→ bC | aA' | → cB' | aA' | bA' | → aA' | bA' | first(B') {a, b}, follow(B') {f, d}; first(B')  follow(B')  ;first(A') {a, b}, follow(A')  {f, d}; first(A')  follow(A')  ;first(C) {a, b, c}, follow(C) {f, d}; first(C)  follow(C)  .Т.

е. получили эквивалентную грамматику Gobject, к которой применим метод рекурсивногоспуска. Gobject удобна для построения системы рекурсивных процедур, так как ее правилаимеют канонический вид.Задача разбора для неоднозначных грамматикДля неоднозначных грамматик задача синтаксического анализа (задача разбора) может быть поставлена двумя основными способами.(1) Даны КС-грамматика G и цепочка x.

Требуется проверить: x  L(G)? Если да, топостроить все деревья вывода для x (или все левые выводы для x, или все правые выводы дляx) 24).Для решения этой задачи можно обобщить метод рекурсивного спуска, чтобы он работал с возвратами, пробуя различные подходящие альтернативы.(2) Даны КС-грамматика G и цепочка x. Требуется проверить: x  L(G)? Если да, топостроить одно дерево вывода для x (возможно, наиболее подходящее в некотором смысле).При такой постановке для некоторых неоднозначных грамматик удается модифицировать обычный РС-метод без возвратов так, что получаемый анализатор корректен, и строит наиболее подходящее в некотором смысле дерево.Неприменимость метода рекурсивного спуска в «чистом» виде для неоднозначныхграмматик обусловлена невозможностью однозначно спрогнозировать выбор альтернативыпри разборе цепочки (прогноз может состоять из нескольких подходящих альтернатив).

Модификация метода состоит в следущем: одна из альтернатив объявляется «наиболее подходящей», и процедура анализа всегда выбирает эту альтернативу, игнорируя другие.Рассмотрим пример, иллюстрирующий ситуацию с условными (полным и сокращенным) операторами в языке Паскаль.Gif-then   {if, then, else, a, b}, {S }, P, S, S′ ,где P  { S → if b then S S′ | a ; S′ → else S |  }. В этой грамматике прогноз для S′ по elseнеоднозначен, так как first(else S)  follow(S′) {else} . Для цепочки if b then if b then aelse a можно построить два различных дерева вывода, показанных на рис. 101 (а, б).Если при построении анализатора отдать предпочтение непустой альтернативе для S′,то такой анализатор построит дерево, изображенное на рис. 101 (а), в котором else соотносится с ближайшим (на его уровне вложенности) if, что соответствует правилам, принятым в24)Цепочка в неоднозначной грамматике может иметь и бесконечно много деревьев вывода.

В таком случаеможно ограничиться построением всех деревьев, высота которых не превосходит некоторой константы.65Элементы теории трансляции / Синтаксический анализязыке Паскаль при разрешении подобных неоднозначностей в комбинациях условных операторов.Итак, мы модифицировали РС-метод для данного примера неоднозначной грамматики, отдав предпочтение одной из альтернатив (и получив тем самым подходящее для семантики языка Паскаль дерево разбора).Нетрудно убедиться, что получаемый для грамматики Gif-then анализатор корректен:он не зацикливается, распознает правильные цепочки и отвергает неправильные.Отметим, что подобная модификация РС-метода не всегда приводит к построениюкорректного анализатора.

Корректность необходимо дополнительно проверять.SS′bifSthenbifthenS′SaSelse(a)aSS′ifbSthenelseifbthenSSS′a(б)aРис. 10. Деревья вывода для цепочки if b then if b then a else a.О других методах распознавания КС-языковМетод рекурсивного спуска применим к достаточно узкому подклассу КС-грамматик.Известны более широкие подклассы КС-грамматик, для которых существуют эффективныеанализаторы, обладающие тем же свойством, что и анализатор, построенный методом рекурсивного спуска, — входная цепочка считывается один раз слева направо и процесс разбораполностью детерминирован, в результате на обработку цепочки длины n расходуется времяcn. К таким грамматикам относятся LL(k)-грамматики, по которым, как правило, реализуетсяанализ сверху-вниз — нисходящий; LR(k)-грамматики, грамматики предшествования, по которым, как правило, реализуется анализ снизу-вверх — восходящий; и некоторые другие(см., например, [2], [3]).66Элементы теории трансляции / Синтаксический анализАнализатор для LL(k)-грамматик просматривает входную цепочку слева направо иосуществляет детерминированный левый вывод, принимая во внимание k входных символов,расположенных справа от текущей позиции.

Выбор альтернативы осуществляется на основезаранее составленной таблицы прогнозов.Анализатор для LR(k)-грамматик просматривает входную цепочку слева направо иосуществляет детерминированный правый вывод, принимая во внимание k входных символов, расположенных справа от текущей позиции. Вывод строится методом сверток, как приразборе по леволинейной автоматной грамматике. Предварительно по LR(k)-грамматикестроится таблица, которая на каждом шаге вывода позволяет анализатору однозначно выбрать нужную свертку.Анализатор для грамматик предшествования просматривает входную цепочку слеванаправо и осуществляет детерминированный правый вывод, учитывая только некоторые отношения между парами смежных символов выводимой цепочки.Часто одна и та же КС-грамматика может быть отнесена не к одному, а сразу к нескольким классам грамматик (например, любая LL-грамматика является LR-грамматикой,обратное неверно), допускающих построение линейных по временнóй сложности распознавателей.

Но, на вопрос, какой лучше распознаватель выбрать, нисходящий или восходящий,нет однозначного ответа.Нисходящий синтаксический анализ предпочтителен с точки зрения процесса трансляции, поскольку на его основе легче организовать процесс порождения цепочек результирующего языка. Восходящий синтаксический анализ привлекательнее тем, что часто дляданного языка программирования легче построить LR-грамматику, поскольку ограниченияна правила слабее, чем для LL-грамматик.Конкретный выбор зависит от конкретного компилятора, от сложности грамматикивходного языка программирования и от того, как будут использованы результаты работыраспознавателя.Синтаксический анализатор для М-языкаБудем считать, что синтаксический и лексический анализаторы взаимодействуют следующим образом: анализ исходной программы идет под управлением синтаксического анализатора; если для продолжения анализа ему нужна очередная лексема, то он запрашивает ееу лексического анализатора; тот выдает одну лексему и «замирает» до тех пор, пока синтаксический анализатор не запросит следующую лексему.Соглашения: наш лексический анализатор — это функция-член get_lex( ) класса Scanner, котораяв качестве результата выдает лексемы типа (class) Lex; в переменной curr_lex типа Lex будем хранить текущую лексему, выданную лексическим анализатором, а в переменной c_val — ее значение.Анализатор методом рекурсивного спуска для М-языка реализуем в виде на Си   ввиде класса Parser .

Характеристики

Список файлов книги