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

ЛЕКЦИЯ № 8 Нисходящий синтаксический анализ предложений. Анализ предложений заключается в том, что шаги порождения, которые формируют предложение, должны реконструироваться при чтении предложения, т.е. проходиться в обратном порядке. В принципе, это очень трудная, а иногда и невыполнимая задача. Её сложность сильно зависит от правил порождения, которые определяют язык. Алгоритм распознавания должен быть максимально простым и эффективным для практического применения. Это значит, что вычислительные затраты на анализ предложения должны находиться в пределах от линейной зависимости от длины предложения до величины n log n, где n – длина предложения. Простейший алгоритм для решения этой задачи заключается в простом переборе всех возможных предложений данного языка, однако неэффективность подобной схемы для сколь – нибудь содержательных грамматик очевидна. Задача построения алгоритма распознавания для любого языка не ставится. Поступают наоборот: строят некоторый эффективный алгоритм, а затем определяется, с каким классом языков он может работать. Из основного требования эффективности следует, что каждый очередной этап анализа должен выбираться лишь в зависимости от текущего состояния процесса и от одного следующего читаемого символа. Другое важное требование заключается в том, чтобы ни к какому этапу не было повторного обращения. Эти два требования в общем случае формулируются как просмотр на один символ вперёд без возврата. Одним из первых и часто используемых методов – это метод нисходящего грамматического разбора, поскольку его применение реконструирует этапы порождения предложения, которые в принципе образуют дерево, от начального символа к конечному предложению, т.е. сверху вниз. Пусть дано предложение «Корабли летят». Необходимо определить, принадлежит ли оно языку. По определению, предложение принадлежит языку только если оно может порождаться из начального символа <предложение>. Из грамматических правил следует, что предложение должно состоять из подлежащего, за которым следует сказуемое. Теперь задачу можно разделить на две части – подзадачи: вначале нужно определить, может ли какая-либо начальная часть предложения порождаться из символа <подлежащее>. Действительно, «Корабли» может порождаться непосредственно из этого символа, поэтому символ «Корабли» убирается из входного предложения, т.е. происходит сдвиг на один шаг и переход к следующей подзадаче: определить, может ли оставшаяся часть предложения порождаться из символа <сказуемое>. Поскольку ответ вновь положительный, результат анализа положительный. Процесс работы можно схематически изобразить так: Задача Непрочитанная часть входного предложения <предложение> Корабли летят <подлежащее> <сказуемое> Корабли летят Корабли <сказуемое> Корабли летят <сказуемое> летят летят летят - - Анализ предложения xyyz, принадлежащего праволинейной грамматике S∷ = xA A∷ = z / yA выполняется, как это показано ниже. S xyyz xA xyyz A yyz yA yyz A yz A yz A z z z - - Поскольку обратное прослеживание этапов порождения предложения называется грамматическим разбором, вышеприведённый алгоритм есть алгоритм грамматического разбора. Суть его заключается в последовательном просмотре входного предложения слева направо, заглядывая вперед только на один символ. Грамматики, позволяющие выполнять анализ такого типа, получили название LL(k) – грамматик по следующей причине. Нисходящий грамматический разбор в данном случае выполняется просмотром входной последовательности слева – направо (Left, первая буква L в названии) восстановлением так называемого левого канонического вывода предложения (вторая буква L в названии). Левый канонический вывод рассмотрен в пункте 3.3. Обозначение (k), в общем виде, говорит о том, что просмотр вперед происходит не более, чем на k входных символов. На практике в настоящее время используются алгоритмы с просмотром на один символ вперед, т. е., LL(1) – грамматики. В обоих вышеприведенных примерах отдельные подстановки можно производить однозначно при проверке одного очередного символа во входном предложении. К сожалению, это не всегда возможно, например: Пример 4 S:: = A/B A:: = xА/y B:: = хВ/z Очевидно, что данная грамматика является праволинейной. Пусть анализируется предложение xxxz, принадлежащее этой грамматике. Это предложение порождается в результате следующих подстановок: S → B → xB → xxB → xxxB → xxxz Однако анализ данного предложения в предположении первой подстановки S:: = A дает отрицательный результат: S xxxz A xxxz xA xxxz A xxz xA xxz A xz xA xz A z ? z Трудность возникает на самом первом шаге, так как решение о замене S на A или B нельзя принять на основе лишь первого прочитанного символа. Можно прослеживать один из возможных выборов, а затем возвращаться, если этот путь не даёт нужного решения. Такое действие называется возвратом. В данном случае, если вернуться к первому шагу и использовать подстановку S:: = B, то результат будет правильным: В языке примера 4 количество шагов, на которое иногда надо возвращаться, вообще говоря, неограниченно. Такая ситуация крайне нежелательна, поэтому нужно избежать особенностей языка, которые приводят к возврату при грамматическом разборе. Поэтому далее будут рассматриваться такие системы грамматик, которые не допускают возвратов при грамматическом разборе. Для этого на порождающие правила накладываются два ограничения. Ограничения на порождающие правила. Из рассмотренного примера видно, что для правильного выбора следующего шага анализа предложения начальные символы альтернативных правых частей порождающих правил должны быть обязательно различны. Это положение формализуется в виде Ограничения 1. Ограничение 1: Если дано порождающее правило вида: , то множества начальных символов всех предложений, которые могут порождаться из различных , не должны пересекаться, т.е. для . Множество есть множество всех терминальных символов, которые могут встречаться в начале предложений, полученных из . Это множество вычисляется согласно следующим правилам 1. Если первый символ аргумента терминальный, то 2. Если первый символ нетерминальный и стоит в левой части порождающего правила то В предыдущем примере first(A) = first(B) = {x}. Следовательно, в первом порождающем правиле нарушено Ограничение 1. На самом деле, можно найти другой синтаксис для языка этого примера, удовлетворяющий ограничению 1. Нужно отложить разделение на части до тех пор, пока не будут пройдены все X. Следующие порождающие правила эквивалентны вышеприведённым в том смысле, что они порождают то же множество предложений: (преобразование примера 4) S:: = C/хS; C:: = y/z S→xS→xxS→xxxS→xxxC→xxxz Для преобразованной таким образом грамматики Ограничение 1 выполнено, так как first(C) = {y,z}, а first(xS) = {x}. Однако выполнение одного Ограничения 1 может оказаться недостаточным. Пример 5. (Правосторонняя грамматика) S:: = Aх; А:: = х/ε, где ε - нулевая последовательность символов. Разбор предложения х, получающегося в результате следующих подстановок: S→Aх→εх→ х: Анализ данного предложения дал отрицательный результат. Проблема возникла из-за того, что при анализе нужно было следовать правилу А:: = ε, а не А:: = x: Эта ситуация называется проблемой пустой строки, она связана со случаем, когда нетерминальный символ может порождать пустую последовательность. Для недопущения подобной ситуации вводится ещё одно ограничение: Ограничение 2: Для ∀ символа A Є N, который порождает пустую последовательность (A ε), множество начальных символов не должно пересекаться с множеством символов, которые могут появляться в предложениях языка справа от какой-либо последовательности, порождаемой A (внешними символами A). Множество внешних символов A обозначается follow(A). Тогда Ограничение 2 формулируется следующим образом: Множество follow (A) определяются так: берутся все порождающие правила Pi вида: Х:: = , затем для каждой последовательности , стоящей справа от A, определяется её множество начальных символов . Множество follow (A) – объединение всех таких множеств Si. Если хотя бы одна η может породить пустую последовательность, то множество follow (X) также следует включить в follow (A). В примере 5 ограничение 2 нарушается для символа A, поскольку first (A) = follow (A) = {x} Таким образом, с учетом определения множеств начальных и внешних символов, можно дать формальное определение LL(1) – грамматики: Контекстно – свободная грамматика является LL(1) – грамматикой тогда и только тогда, когда множества начальных символов first правил с одинаковой левой частью не пересекаются между собой и с множеством follow ее внешних символов. Повторение последовательностей символов в предложениях обычно задаётся в порождающих правилах с помощью рекурсии. Например, порождающее правило A::=B/AB описывает множество предложений B, BB… Однако использование такого правила запрещает Ограничение 1, так как first(B) ∩ first(AB) = first(B) ≠ Ǿ Это правило можно модифицировать следующим образом: А:: = ε /AB, Оно будет порождать последовательности ε, B, BB, BBB, …, но в этом случае нарушится Ограничение 2, поскольку first(A) = first(B), и, следовательно, first(B) ∩ follow(AB) ≠ Ǿ Очевидно, что оба эти ограничения запрещают использование правил с «левой рекурсией». Простой способ избежать таких форм – это либо использовать правую рекурсию А:: = ε/BA, либо расширить БНФ-нотацию так, чтобы она допускала явное выражение повторений. Эквивалентность и однозначность грамматик Эти рассуждения, а также пример преобразования порождающих правил могут навести на мысль, что преобразования грамматик могут решить все проблемы синтаксического анализа. Однако структура предложений связана с их смыслом, а смысл синтаксических конструкций выражается через смысл их компонент. Пример: Грамматика G1, определяющая арифметические выражения: E ::= E + E | E – E | E * E | E / E | a | b | c | (E). Очевидно, что предложение a+b*c принадлежит этой грамматике. Однако, возможны два вывода этого предложения: 1. E → E * E→Е+Е*Е→ a+b*c. Этому выводу соответствует дерево разбора: 2. E → E + E→Е+Е*Е→ a+b*c. Этому выводу соответствует другое дерево разбора: Но два разных дерева дают две разные трактовки структуры этой последовательности. Дерево 1 объединяет a + b в одно подвыражение, которое затем участвует в роли операнда в операции умножения. Такая трактовка не соответствует общепринятому приоритету арифметических операций – умножение должно выполняться раньше сложения. Дерево 2 представляет структуру, соответствующую правильному порядку выполнения операций. Грамматика G называется однозначной, если любой сентенции x L(G) соответствует единственное дерево вывода. Грамматика G1 неоднозначна, что является ее серьезным недостатком, который не позволяет применить ее на практике для определения языка выражений, поскольку эта грамматика не позволяет однозначным образом выявить структуру выражения. Однако можно построить грамматику, которая будет определять арифметические выражения однозначно: Грамматика G2, определяющая арифметические выражения однозначно: E ::= T | E + T | E – T T ::= M | T * M | T / M M ::= a | b | c | (E) Дерево вывода последовательности a + b * c в грамматике G2 имеет вид: Эта грамматика однозначна и приписывает арифметическим выражениям структуру, соответствующую правильному порядку выполнения операций. Грамматики называются эквивалентными, если порождают один и тот же язык. Грамматики G1 и G2 эквиваленты, поскольку L(G1) = L(G2). При определении языка, обладающего смыслом, нужно всегда принимать во внимание его семантическую структуру, т.к. синтаксис должен её отражать. Ниже рассматривается пример проверки выполнения Ограничений 1 и 2 для контекстно – свободной грамматики типа 2. Пример 6. S:: = AbB / d; first (AbB) = {a, b, c, e} ; first (d) = {d} A:: = CAb / B; first (CAb) = {a, e} ; first (B) = {c} B:: = cSd / ε ; first (cSd) = {c} ; first(ε) = {ε} C:: = a / ed first (a) = {a} ; first(ed) = {e} Вычисление first для S:: = d; B:: = cSd; C:: = a; C:: = ed тривиально, поскольку их правые части начинаются с терминальных символов. Эти множества начальных символов содержат по одному элементу – первому терминальному символу правила. Множество first для правила B:: = ε также определяется тривиально: так как из пустой последовательности ε нельзя ничего вывести, то first(ε) не содержит ни одного символа. Для правила A:: = CAb множество first(CAb) состоит из терминальных символов, начинающих правила для нетерминального символа C:: = a и C:: = ed. Для правила A:: = B множество начальных символов состоит только из символа с, в соответствии с правилом B:: = cSd. Вычисление множества начальных символов для правила S:: = AbB : Нетерминальный символ A порождает последовательности, начинающиеся с C или B, которые, в свою очередь, начинаются с терминальных символов c, a и e, которые и включаются в множество начальных символов. Поскольку последовательностью, порождаемой первым A может быть и ε, следующий за A терминальный символ b может стать первым символом в порождаемой последовательности, и, следовательно, b тоже нужно включать в множество начальных символов AbB. То есть, в first(АbВ) т.к. последовательность АbВ порождает последовательность bВ следующим образом: АbВ → ВbВ → bВ Правило B:: = ε порождает пустую последовательность, поэтому необходимо определить follow(В). S → АbВ → ВbВ, S → АbВ → АbcSd → АbcAbBd, поэтому первый вывод показывет, что за В следует b, а второй вывод – это d, поэтому follow (В) = {b,d}, но first(B) = {c}, откуда следует выполнение Ограничения 2. В грамматике имеется ещё одно правило, с помощью которого можно породить ε, а именно: А:: = В, т.е. А → В → ε, поэтому, follow (А) = {b}, но first(A) = {a,e,c}, откуда следует выполнение Ограничения 2 и для этого правила. Таким образом, доказано, что Ограничения 1 и 2 для данной грамматики не нарушены.