Свойства контекстно-свободных языков

СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ В предыдущих лекциях было показано, что не все языки регулярны. Так, например, применив лемму о накачке для регулярных языков, мы убедились, что язык L = {anbn | n 0} не является регулярным. В то же время легко распознать в нем так называемую правильную скобочную структуру, присущую синтаксису многих языков программирования. Например, строки (()), ((())) принадлежат языку L, а строка ((() – нет. Здесь мы используем соответствие между символами(  а и )  b. Этот и многие другие языки относятся к ранее введенному классу контекстно-свободных языков, порождаемых контекстно-свободными грамматиками. Для этого класса языков в этой лекции мы рассмотрим проблему грамматического разбора, или синтаксического анализа, заключающуюся в том, чтобы по данной строке определить, выводима ли она в данной грамматике. Изучение этой проблемы очень важно для разработки языков программирования и построения компиляторов. Контекстно-свободные грамматики В регулярной грамматике класс правил весьма ограничен: в левой части любой продукции А а правая часть ограничение, фигурирует один нетерминальный символ А, имеет специальный вид. Если ослабить это последнее разрешив быть любой строкой терминальных и нетерминальных символов (в том числе и пустой), то мы придем к классу контекстно-свободных грамматик в классификации Хомского. Напомним, что формальный язык L называется контекстно-свободным (или КС-языком), если существует контекстно-свободная грамматика G такая, что L = L(G). Очевидно, что любая регулярная грамматика контекстно-свободна, а любой регулярный язык является КС-языком. С другой стороны, язык L = {anbn | n 0} не регулярный, но является контекстно-свободным. Следовательно, класс регулярных языков есть собственное подмножество класса КС-языков. Термин «контекстно-свободные грамматики» возник в связи со следующим свойством их правил: замена нетерминального символа в левой части продукции на правую часть в процессе вывода может осуществляться в любой ситуации, когда этот нетерминальный символ появляется в сентенциальной форме, и независимо от его окружения (т.е. контекста). Это очевидное следствие того, что левая часть любого правила КС-грамматики состоит из единственного нетерминального символа. Пример 10.1. Грамматика G = ({S}, {a, b}, S, P), где Р есть множество правил S aSa S bSb S , является контекстно-свободной. Типичным выводом в этой грамматике является следующий вывод: S aSa abSba abbSbba Отсюда нетрудно видеть, что L(G) = { -1 abbbba. | {a, b}*}.Этот язык контекстно-свободный, но, как было показано ранее, не регулярный. В контекстно-свободных грамматиках при выводе могут возникать сентенциальные формы, содержащие более одного нетерминального символа. В силу этого появляется возможность выбора, поскольку любой из этих символов заменять раньше другого. В качестве примера рассмотрим КСграмматику G = ({E, T, F}, {a, +, *, (, )}, E, P) с продукциями 1) Е Е+Т, 2) E 3) Т Т * F, 4) Т 5) F (E) , 6) F Т, F, a. Рассмотрим два вывода в G строки а + а: 1 l) E 2 E+T 4 T+T 6 F+T 4 a+T 6 a+F a + a; 1 2) E 4 E+T 6 E+F 2 E+a 4 T+a 6 F+a a + a. В этих двух выводах над стрелками указаны номера примененных на соответствующем шаге правил из Р. Можно заметить, что в выводах l) и 2) использованы одни и те же продукции, но в разном порядке: в выводе l) на каждом шаге заменяется самый левый нетерминальный символ, а в выводе 2) – самый правый. Определение Вывод 10.2. в КС-грамматике называется левосторонним, если на каждом шаге замещается самое левое вхождение нетерминального символа. Если замещается всегда самый правый символ, то вывод называется правосторонним. Таким образом, в рассмотренном ранее примере вывод l) является левосторонним, а вывод 2) – правосторонним. Другой способ представления вывода вне зависимости от порядка применения правил - представление его в виде дерева вывода. Под деревом вывода понимается упорядоченное дерево, вершины которого помечены левыми частями продукций, а непосредственные потомки вершины в совокупности представляют собою правую часть соответствующей продукции. Таким образом, если на некотором шаге вывода в грамматике G = (N, T, S, P) была применена продукция X Y1Y2 ... Ym, а затем продукция Y2 Z1Z2 ... Zn, где Yi, Zj N T, 1 i m, 1 j n, Y2 N, то этой части вывода будет соответствовать фрагмент дерева вывода, изображенный на рис. 10.1. Рис. 10.1. Фрагмент дерева вывода - частичное дерево вывода Корень дерева вывода помечается начальным символом грамматики, а листья – терминальными символами. В целом, дерево вывода показывает, как в процессе вывода происходит замещение нетерминальных символов, и применяемые правила грамматики определяют «законы роста» ветвей дерева. Более точным образом сформулируем Определение 10.3. Пусть G = (N, T, S, P) – контекстно-свободная грамматика. Дерево вывода в грамматике G – это упорядоченное дерево, удовлетворяющее следующим условиям: 1) корень помечен начальным символом S; 2) каждый лист помечен символом из множества T { }; 3) каждая вершина, не являющаяся листом, помечена символом из N; 4) если вершина имеет метку А N, а ее потомки помечены (слева направо) символами X1, X2, ... , Xn, тогда продукция А X 1X2 ... Xn содержится в Р; 5) лист, помеченный , является единственной дочерней вершиной своей родительской вершины. Если в этом определении исключить условие 1, а условие 2 заменить на условие 2') каждый лист помечен символом из множества N T { }, то получим определение так называемого частичного дерева вывода. Кроной дерева вывода назовем строку, которая получится, если выписать слева направо все метки листьев-концевых вершин дерева (опуская при этом символы ): Пример 10.4. Рассмотрим грамматику G с продукциями S aSbS | bSaS | . Тогда следующим двум выводам в G строки abab: а) S aSbS abSaSbS б) S aSbS a bS ab a b ; a baSbS a ba b . будут соответствовать деревья выводов, изображенные на рис. 10.2. Дерево вывода предоставляет наглядное и легкое для понимания описание вывода. Как и для диаграмм переходов конечных автоматов, такая наглядность оказывается очень полезной при доказательстве различных свойств КС-грамматик. Но вначале установим строгую связь между выводами и деревьями выводов. Рис. 10.2. Деревья выводов Теорема 10.5. Пусть G = (N, T, S, P) – КС-грамматика. Тогда для любой строки L(G) существует дерево вывода, крона которого совпадает с . Обратно, крона любого дерева вывода в G определяет слово, принадлежащее языку L(G). Кроме того, крона любого частичного дерева вывода в G, корень которого помечен S, определяет сентенциальную форму в G. Доказательство. Сначала покажем, что каждой сентенциальной форме в G соответствует частичное дерево вывода. Сделаем это индукцией по длине вывода. В качестве базы индукции положим длину вывода равной 1. Тогда наличие вывода S влечет наличие продукции S в G, то утверждение немедленно следует из Определения 10.3. База индукции разобрана. Допустим теперь уже доказанным, что для каждой сентенциальной формы, выводимой за n шагов, отвечает соответствующее дерево вывода. Возьмем произвольную сентенциальную форму выводимую за (n + 1) шаг. Ее вывод можно разбить на две части: вывод длины n: и вывод длины 1: A , где , S A (N T)*, A X1X2 ... Xn = , где Xi N; N T. В силу предположения индукции существует частичное дерево вывода с кроной А . Поскольку грамматика содержит продукцию А Х1Х2 ... Хn, то, удлиняя это дерево в вершине А с помощью указанной продукции, получаем частичное дерево вывода с кроной Х1Х2 ... Хn = . Это завершает доказательство. Верно и обратное, т.е. что каждое частичное дерево вывода в G имеет в качестве кроны некоторую сентенциальную форму в той же грамматике. Это остается читателю в качестве задачи. Поскольку любое дерево вывода является и частичным деревом вывода, листья которого помечены терминальными символами, то из рассуждений выше следует, что каждая строка в L(G) является кроной некоторого дерева вывода в G. Далее, крона любого дерева вывода в G определяет слово из языка L(G). Итак, каждой строке L(G) отвечает дерево вывода, которое показывает, какие правила G участвуют в выводе этой строки, хотя без указания порядка их применения. Считая, что при построении дерева вывода наращивается самая левая вершина, помеченная нетерминальным символом, получим левый вывод: нетерминалы заменяются каждый раз независимо. Аналогичные рассуждения показывают существование у строки и правостороннего вывода. Следствие 10.6. В КС-грамматике G любая строка L(G) имеет левосторонний и правосторонний вывод. Контекстно-свободные языки. Грамматический разбор В предыдущих лекциях основным был вопрос о том, какое множество строк можно породить с помощью данной грамматики G. В приложениях приходится рассматривать и другой аспект. А именно: как по данной строке , состоящей из терминальных символов грамматики, определить, входит ли эта строка в язык L(G) или нет? Если входит, то как найти ее вывод в G? Ответом на первый вопрос служит алгоритм, распознающий принадлежность строки языку L(G). Построение вывода слова последовательностью правил, посредством которых строка можно описать выводится в G. Эта процедура называется грамматическим разбором. Для заданного слова из языка L(G) грамматический разбор можно провести следующим образом: строятся все возможные (например, левосторонние) выводы в G и далее из них отбираются те выводы, которые порождают . Точнее, начинаем с просмотра всех правил вида S и находим все строки , которые могут быть получены из S за один шаг. Если ни одна из них не совпадает с , то переходим к следующему этапу: используем все продукции из G, применимые к слову нетерминальному символу в строке и самому левому . Это приводит к множеству всех сентенциальных форм, некоторые из которых могут затем привести к выводу . Далее, на следующих промежуточных шагах, всякий раз будем выбирать самые левые нетерминалы в строках, полученных на предыдущем этапе. Применяем к ним все возможные продукции. Может случиться, что некоторые сентенциальные формы не ведут к . Они могут быть исключены из рассмотрения. Вообще говоря, на n-ом этапе мы получим множество всех сентенциальных форм, которые могут быть выведены в G применением n продукций. Если L(G), то эта строка должна иметь левосторонний вывод конечной длины. Следовательно, применяя описанную процедуру к , мы на некотором шаге получим левосторонний вывод для . Назовем эту процедуру грамматического разбора методом полного перебора. Она относится к группе методов, имеющих общее название – "нисходящий разбор", поскольку соответствует построению дерева вывода сверху вниз, начиная с корня. Рассмотрим следующий Пример 10.7. Возьмем грамматику 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 удовлетворяет указанным требованиям и порождает тот же язык, что и в примере 10.7, но без пустой строки. При этом для любой строки {a, b}+ грамматический разбор методом полного перебора всегда заканчивается не более чем за шагов. В результате мы получаем либо вывод строки либо информацию о том, что , не принадлежит языку, порождаемому данной грамматикой. Сказанное выше приводит к формулировке следующей теоремы о КСязыках. Теорема 10.8. Пусть G = (N, T, S, P) – контекстно-свободная грамматика, не содержащая продукций вида A или A B, где A, B N. Тогда грамматический разбор методом полного перебора определяет алгоритм, который для любой строки сообщает, что вывод для слова T* либо строит ее вывод, либо не существует. Доказательство. Рассмотрим слово S где 1 T* и произвольный вывод в G: … 2 n, – сентенциальные формы. Для каждой сентенциальной формы введем i две числовые характеристики: ее длину и количество терминальных символов в ней. Очевидно, при переходе от i к i+1 возрастает, по крайней мере, одна из этих характеристик. Если нас интересует вывод строки , то ни длина i, ни число терминальных символов не могут превышать . Следовательно, сам вывод не может иметь более чем 2 шагов. Просмотрев все такие выводы, мы либо найдем среди них вывод , либо заключим, что L(G). Относительно неэффективности метода полного перебора при грамматическом разборе следует отметить, что эта проблема эффективизации достаточно сложна. На первом шаге порождается P сентенциальных форм (если каждая из продукций применима к S), на втором шаге к каждой из полученных сентенциальных форм снова можно применить P продукций, т.е. получаем P 2 форм, и так далее. В итоге, применение полного перебора может привести к P сентенциальных форм. Если под строкой понимать текст программы в некотором языке программирования, то становится ясным, что полученная экспоненциальная оценка сложности процедуры грамматического разбора делает невозможным практическое применение такого метода. Более эффективные алгоритмы грамматического разбора относятся к частным видам КС-грамматик. Они требуют отдельного рассмотрения. Частично они изучены в практикуме [ 9 ]. Такие алгоритмы детально изучаются в дисциплинах, посвященных методам построения компиляторов или трансляторов. Практическое применение находят те методы грамматического разбора, для которых число шагов пропорционально длине рассматриваемой строки. Например, это так для КСграмматик типа 4 в классификации Хомского. Пример 10.9. Рассмотрим в качестве образца КС-грамматику, у которой все правила имеют вид A где A N, a T, a , N*, причем каждая пара символов (A, a) может входить не более чем в одно правило. Проверим, что для любой строки , выводимой в этой грамматике, грамматический разбор может быть произведен не более чем за шагов. Применим к произвольной строке = a1a2 … an метод полного перебора для построения ее вывода. Поскольку существует единственная пара (S, a1), входящая в правило, применимое на первом шаге, то единственным образом получаем: S a1A1A2 … Am. Заменив нетерминал A1 с учетом того, что существует лишь единственная продукция, соответствующая паре (A1, a2), получаем: S a1a2 B1… Bk A2 … Am. В этих условиях на каждом шаге в сентенциальную форму добавляется ровно один терминальный символ. Значит, через шагов алгоритм остановится. Данная грамматика относится к классу так называемых простых грамматик (или S-грамматик). Несмотря на простоту вида правил Sграмматик, с помощью них могут быть выражены ряд распространенных конструкции в описаниях синтаксиса языков программирования (см. Практикум [ 9 ]). Неоднозначность языков и грамматик Возможно, для произвольной строки L(G) грамматический разбор приводит к нескольким различным деревьям вывода. Тогда говорят, что КСграмматика имеет свойство неоднозначности вывода. Определение 10.10. Говорят, что контекстно-свободная грамматика G неоднозначна, если для некоторой строки L(G), имеется в G, по крайней мере, два различных дерева вывода. В противном случае КС-грамматика называется однозначной. Очевидно, что неоднозначность означает существование двух или более различных левосторонних (или правосторонних) выводов. Пример 10.11. Покажем, что грамматика S aSb SS неоднозначна. С этой целью возьмем строку = aabb и построим для нее два разных левых вывода в этой грамматике и отвечающие им деревья: В естественных языках неоднозначность некоторых предложений является одним из присущих им свойств, которое в ряде случаев эффективно используют как «игру слов». В языках программирования, где для каждого выражения требуется наличие единственной интерпретации, неоднозначностей следует избегать. Чтобы избавиться от нее, используются приемы перехода к эквивалентной грамматике, которая обладает свойством однозначности. Такое преобразование возможно для ряда частных типов КСграмматик. Тем не менее, проблема неоднозначности алгоритмически не разрешима в классе всех КС-грамматик. Пример 10.12. Рассмотрим грамматику G = (N, T, S, P), где N = {E, I}, T = {a, b, c, +, , (,)} и Р - множество следующих правил: E I, E E + E, E E E (E), I a b c. E, Эта грамматика порождает собственное подмножество множества арифметических выражений в некоторых языках программирования. Проанализируем эту грамматику на свойство неоднозначности. Возьмем строку a+b c, которая принадлежит языку L(G), и построим для нее два дерева вывода: Рис. 10.3. Два дерева вывода для a+b c Устранение неоднозначности в подобных случаях иногда достигается введением дополнительных правил, устанавливающих относительные приоритеты арифметических операций. Например, будем считать, что операция умножения вывода на связывает операнды сильнее, чем сложение +. Дерево рис. 10.3 а) может рассматриваться как правильное, соответствующее тому, что произведение b c является подформулой, значение которой должно быть вычислено раньше, чем будет произведено сложение. Однако эти требования не согласуются с грамматическими правилами, имеющими строго определенную форму. Можно ли так видоизменить данную грамматику, чтобы она стала однозначной? С этой целью в качестве множества нетерминаловN возьмем следующее множество метасимволов: {E, M, F, I} и новый набор продукций: E M, M F, F I, E E+M, M M F, F (E) , I a b c. В этой грамматике строке a+b c будет отвечать единственное дерево вывода, представленное на рис. 10.4 ниже. Кроме того, можно показать, что и для любой другой строки, выводимой в этой грамматике, соответствующее дерево вывода также единственно. Стало быть преобразованная грамматика однозначна. С учетом того, что она эквивалентна исходной грамматике (в чем можно убедиться), то естественно считать, что новая грамматика не имеет неоднозначности. Не всегда удается решить проблему неоднозначности в общем случае. Вопрос, однозначна грамматика или нет, весьма труден, как и вопрос, эквивалентности двух грамматик. На первый и на второй вопросы не существует универсальных алгоритмов, которые давали бы ответы для произвольной грамматики. Рис. 10.4. Единственное дерево вывода для a+b c В рассмотренном выше примере удалось избавиться от неоднозначности, выбрав другую форму записи правил грамматики для данного языка. Оказывается, что это не всегда возможно, так как иногда существуют КС-языки, которые существенно неоднозначны (см. Практикум[9]). Определение 10.13. однозначным, если Контекстно-свободный существует порождающая язык его L называется однозначная КС- грамматика. Если же любая грамматика, порождающая L, неоднозначна, то L называется существенно неоднозначным. Проблема существенной неоднозначности КС-языков является очень трудной. Ее анализу посвящены работы французского математика Ф. Флажоле, применившего в этой задаче методы комплексного анализа. Мы же обсудим только один характерный пример. Пример 10.14. Оказывается, язык L = {an bn cm n, m 0} {an bm cm n, m 0} является существенно неоднозначным контекстно-свободным языком. Сначала проверим, что язык L – КС-язык. Нетрудно проверить, что язык L = {anbncm n, m 0} порождается грамматикой G1: S1 C aS1bC , cC , а, во вторых, язык L2 = {anbmcm n, m 0} порождается грамматикой G2: Язык L = L1 S2 aS2 B, B bBc . L2 порождается грамматикой, правила которой состоят из всех правил грамматик G1 и G2 и двух дополнительных правил S S1 S2. Не приводя здесь технически сложное доказательство существенной неоднозначности языка L, на содержательном уровне отметим, что эта неоднозначность обусловлена тем, что невозможно выразить с помощью одного и того же множества правил два противоречащих требования на состав слов. Тогда в языке L1 количества символов a и b в строке должны совпадать между собой и почти всегда отличаться от количества символов с, тогда как в языке L2 количества символов b и c в строке совпадают между собой и почти всегда отличаются от количества символов a. Разумеется, вышесказанное – является только наводящим соображением, а не строгим доказательством.