Лекция 9 Контекстно-свободные языки

Грамматический разбор

В предыдущих лекциях мы интересовались в основном вопросом о том, какое множество строк можно породить с помощью данной грамматики G. В практических приложениях приходится рассматривать и аналитический аспект: как по данной строке , состоящей из терминальных символов грамматики, определить, входит ли эта строка в язык L(G) или нет, а если входит, то как найти ее вывод в G. Ответ на первый вопрос дает алгоритм, распознающий принадлежность строки  языку L(G). Процесс построения вывода  может быть описан в виде последовательности продукций, с помощью которых строка  выводится в G; этот процесс называется грамматическим разбором. Для данной строки  из L(G) можно провести грамматический разбор следующим образом: строим все возможные (например, левосторонние) выводы в G и смотрим, какие из них порождают . Начинаем с просмотра всех продукций вида

S  

и находим все строки , которые могут быть получены из S за один шаг. Если ни одна из них не совпадает с , то переходим к следующему этапу: применяем все продукции из G, применимые к , к самому левому нетерминальному символу в строке . Это дает нам множество всех сентенциальных форм, некоторые из которых могут вести нас к . Далее, на каждом промежуточном этапе мы каждый раз выбираем самые левые переменные в полученных на предыдущем этапе строках и применяем к ним все возможные продукции. Может случиться, что некоторые сентенциальные формы не ведут к , тогда они могут быть исключены из рассмотрения. Вообще говоря, на n-ом этапе мы получим множество всех сентенциальных форм, которые могут быть выведены в G применением n продукций. Если   L(G), то эта строка  должна иметь левосторонний вывод конечной длины. Следовательно, применяя описанную процедуру к , мы на некотором шаге n получим левосторонний вывод для . Будем называть эту процедуру грамматического разбора методом полного перебора, который относится к группе методов, имеющих общее название – "нисходящий разбор", который соответствует построению дерева вывода сверху вниз, начиная с корня.

Пример 9.1.

Рассмотрим грамматику S  SSaSbbSa и строку  = aabb.

Однократное применение продукций грамматики дает следующие выводы:

S  SS,

S  aSb,

S  bSa,

S  .

Имея в виду построение вывода строки , мы можем исключить из дальнейшего рассмотрения последние два вывода как заведомо не ведущие к цели. Рассмотрим теперь выводы длины 2 для первых двух случаев:

1) S  SS  SSS,

S  SS  aSbS,

S  SS  bSaS,

S  SS  S.

2) S  aSb  aSSb,

S  aSb  aaSbb,

S  aSb  abSab,

S  aSb  ab.

Как и на предыдущем шаге, некоторые выводы могут быть исключены из дальнейшего рассмотрения (третий вывод в группе 1 и два последних – в группе 2).

На следующем шаге строим продолжения оставшихся выводов из групп 1 и 2, применяя к каждой из заключительных сентенциальных форм последовательно все применимые продукции грамматики. В результате получим выводы длины 3, среди которых находим вывод

S  aSb  aaSbb  aabb.

Это означает, что данная строка  принадлежит языку, порождаемому рассматриваемой грамматикой.

Грамматический разбор методом полного перебора имеет серьезные недостатки. Во-первых, этот алгоритм недостаточно эффективен по времени работы и по объему используемой памяти, а во-вторых, он может расходиться на строке, не принадлежащей порождаемому языку. Так, в только что рассмотренном примере, если мы вместо строки  возьмем строку  = abb и запустим описанный выше алгоритм, то он будет без конца порождать все новые и новые сентенциальные формы, безуспешно пытаясь построить несуществующий вывод строки  в данной грамматике.

Заметим, что если грамматика не содержит продукций вида A и AB, то применение любой продукции такой грамматики либо увеличивает длину сентенциальной формы, либо добавляет в нее терминальный символ. А это дает нам эффективный критерий остановки алгоритма: как только длина сентенциальной формы становится больше длины данной строки, то работа алгоритма на данной ветке прекращается. Очевидно, что через конечное число шагов работа алгоритма на всех ветвях прекратится, даже если данная строка не принадлежит рассматриваемому языку. В следующих лекциях будет показано, что указанное ограничение на вид продукций грамматики не сужает класс языков, к которым может применяться рассмотренный алгоритм. Так, например, грамматика

S  SS aSbbSaabba

удовлетворяет указанным требованиям и порождает тот же язык, что и в примере 9.1, но не содержащий пустой строки. При этом для любой строки   {a, b}⁺ грамматический разбор методом полного перебора всегда заканчивается не более чем за  шагов. В результате мы получаем либо вывод строки , либо информацию о том, что  не принадлежит языку, порождаемому данной грамматикой.

Резюмируем сказанное в виде следующей теоремы для КС-языков.

Теорема 9.2.

Пусть G = (N, T, S, P) – контекстно-свободная грамматика, не содержащая продукций вида A   или A  B, где A, B  N. Тогда грамматический разбор методом полного перебора может быть трансформирован в алгоритм, который для любой строки   T* либо строит ее вывод, либо сообщает, что вывод для  не существует.

Доказательство.

Рассмотрим   T* и любой вывод в G:

S  ₁  ₂  …  _n,

где _i – сентенциальные формы. Для каждой сентенциальной формы введем две числовые характеристики: ее длину и количество терминальных символов в ней. Очевидно, при переходе от _i к _i+1 возрастает, по крайней мере, одна из этих характеристик. Если нас интересует вывод строки , то ни длина _i, ни число терминальных символов не могут превышать . Следовательно, сам вывод не может иметь более 2 шагов. Просмотрев все такие выводы, мы либо найдем среди них вывод , либо заключим, что   L(G).

Что касается неэффективности метода полного перебора при грамматическом разборе, то эта проблема намного сложнее. На первом шаге мы можем породить P сентенциальных форм (если каждая из продукций применима к S), на втором шаге к каждой из полученных сентенциальных форм мы снова можем применить P продукций, т.е. получаем P² форм, и так далее. В целом, применение полного перебора может дать P^ сентенциальных форм. Если под строкой  понимать текст программы в некотором языке программирования, то легко понять, что полученная экпоненциальная оценка сложности делает невозможным практическое применение данного метода. Существуют более эффективные алгоритмы грамматического разбора, но они не столь просты для понимания и их изучение выходит за рамки нашего курса. Такие алгоритмы рассматриваются в курсе, посвященном методам построения компиляторов. Мы здесь лишь отметим, что практически применимыми являются те методы грамматического разбора, для которых время работы пропорционально длине рассматриваемой строки. В общем случае нам не известны такие алгоритмы, применимые ко всем КС-языкам, но они существуют для целого ряда ограниченных, но практически важных специальных классов КС-языков.

Пример 9.3.

Рассмотрим такой тип контекстно-свободной грамматики, у которой все продукции имеют вид

A  a,

где A  N, a  T,   N*, причем каждая пара символов (A, a) может входить не более чем в одну продукцию. Покажем, что для любой строки , выводимой в этой грамматике, грамматический разбор может быть произведен не более чем за  шагов. Возьмем произвольную строку

 = a₁a₂ … a_n

и применим к ней метод полного перебора для построения ее вывода. Так как существует единственная пара (S, a₁), входящая в продукцию, применимую на первом шаге, то единственным образом получаем:

S  a₁A₁A₂ … A_m.

Затем, заменяя переменную A₁ и учитывая, что существует лишь единственная продукция, соответствующая паре (A₁, a₂), получаем:

S a₁a₂ B₁… B_k A₂ … A_m.

Ясно, что на каждом шаге в сентенциальную форму добавляется ровно один терминальный символ, следовательно, через  шагов алгоритм остановится.

Рассмотренная грамматика называется простой грамматикой (или S-грамматикой). Несмотря на кажущуюся простоту S-грам-матик, в них могут быть выражены многие распространенные конструкции языков программирования.