Контекстно-свободные грамматики

Врегулярной грамматике класс продукций очень ограничен: в левой части любой продукции А → α фигурирует один нетерминальный символ А, а правая часть α имеет специальный вид. Можно попытаться ослабить это последнее ограничение, разрешив α быть любой строкой терминальных и нетерминальных символов (в том числе и пустой). Это расширение

и приводит нас к контекстно-свободной грамматике.

Определение 8.1.

Грамматика G = (N, T, S, P) называется контекстно-свободной (или КС-грамматикой), если любая ее продукция имеет вид А → α,

где А N, α (N T)*.

Язык L называется контекстно-свободным (или КС-языком), если существует контекстно-свободная грамматика G такая, что

L = L(G).

Так как, очевидно, любая регулярная грамматика контекстносвободна, то и любой регулярный язык является КС-языком. С другой стороны, язык L = {anbn | n ≥ 0} не регулярный, но, как это видно из примера 1.7, является контекстно-свободным. Следовательно, класс регулярных языков есть собственное подмножество класса КС-языков.

Свое название контекстно-свободные грамматики получили за следующее свойство: замена нетерминального символа в левой части продукции на правую часть в процессе вывода может осуществляться в любой момент, когда этот нетерминальный символ появляется в сентенциальной форме, и независимо от его окружения (т.е. контекста). Это является следствием того, что левая часть продукции представляет собою один-единственный нетерминальный символ.

Пример 8.2.

Грамматика G = ({S}, {a, b}, S, P), где Р есть множество продукций

S → aSa

S → bSb

S → ε,

является контекстно-свободной. Типичным выводом в этой грамматике является следующий:

S aSa abSba abbSbba abbbba.

Отсюда нетрудно видеть, что L(G) = {αα-1 | α {a, b}*}. Этот язык контекстно-свободный, но, как было показано ранее, не регулярный.

В контекстно-свободных грамматиках вывод может включать сентенциальные формы, содержащие более одного нетерминального символа. В этом случае появляется возможность выбора, какой из этих символов заменять раньше другого. В качестве примера рассмотрим КС-грамматику G = ({E, T, F}, {a, +, *, (, )}, E, P) с продукциями

В этих двух выводах над стрелками указаны номера примененных на соответствующем шаге продукций из Р. Можно заметить, что в выводах l) и r) использованы одни и те же продукции, но в разном порядке: в выводе l) на каждом шаге

заменяется самый левый нетерминальный символ, а в выводе r) – самый правый.

Определение 8.3.

Вывод в КС-грамматике называется левосторонним, если на каждом шаге замещается самый левый нетерминальный символ. Если замещается всегда самый правый символ, то вывод называется

правосторонним.

Таким образом, в рассмотренном ранее примере вывод l) является левосторонним, а вывод r) – правосторонним.

Другой способ представления вывода вне зависимости от порядка применения продукций - представление его в виде дерева вывода. Это упорядоченное дерево, вершины которого помечены левыми частями продукций, а непосредственные потомки вершины в совокупности представляют собою правую часть соответствующей продукции. Так, если на некотором шаге вывода в грамматике G = (N, T, S, P) была применена продукция X → Y1Y2 ... Ym, а затем продукция Y2 → Z1Z2 ... Zn, где

Yi, Zi N T, 1 ≤ i ≤ m, 1 ≤ j ≤ n, Y2 N,

то этой части вывода будет соответствовать фрагмент дерева вывода, представленный на рис. 8.1.

X

Y1 Y2 Y3 K Ym

Z1 Z2 K Zn

Рис. 8.1. Фрагмент дерева вывода Корень дерева вывода помечается начальным символом

грамматики, а листья – терминальными символами. В целом, дерево

вывода показывает, как в процессе вывода происходит замещение нетерминальных символов.

Определение 8.4.

Пусть G = (N, T, S, P) – контекстно-свободная грамматика. Дерево вывода в грамматике G – это упорядоченное дерево, удовлетворяющее следующим условиям:

1)корень помечен начальным символом S;

2)каждый лист помечен символом из множества T {ε};

3)каждая вершина, не являющаяся листом, помечена символом из N;

4)если вершина имеет метку А N, а ее потомки помечены (слева направо) символами X1, X2, ... , Xn, тогда продукция

А→X1X2 ... Xn содержится в Р;

5) лист, помеченный ε, является единственной дочерней вершиной своей родительской вершины.

Если в этом определении исключить условие 1, а условие 2 заменить на условие

2') каждый лист помечен символом из множества N T {ε},

то получим определение так называемого частичного дерева вывода.

Кроной дерева вывода назовем строку, которая получится, если выписать слева направо все метки листьев (опуская при этом символы ε):

Пример 8.5.

Рассмотрим грамматику G с продукциями

S → aSbS | bSaS | ε.

Тогда следующим двум выводам в G строки abab:

а) S aSbS abSaSbS abεaεbε ;

б) S aSbS aεbS aεbaSbS aεbaεbε

будут соответствовать деревья выводов, изображенные на рис.8.2.

Дерево вывода представляет собой очень наглядное и легкое для понимания описание вывода. Как и для диаграмм переходов конечных автоматов, такая наглядность оказывается очень полезной при доказательстве различных свойств КС-грамматик. Но вначале установим строгую связь между выводами и деревьями выводов.

Рис. 8.2. Деревья выводов

Теорема 8.6.

Пусть G = (N, T, S, P) – КС-грамматика. Тогда для любой строки α L(G) существует дерево вывода, крона которого совпадает с α. И обратно, крона любого дерева в G принадлежит L(G). Кроме того, крона любого частичного дерева вывода в G, корень которого помечен S, является сентенциальной формой в G.

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

Покажем вначале, что каждой сентенциальной форме в G соответствует частичное дерево вывода. Используем для этого индукцию по длине вывода. Пусть длина вывода равна 1. Так как вывод S α влечет наличие продукции S → α в G, то требуемое утверждение немедленно следует из Определения 8.4.

Предположим теперь, что для каждой сентенциальной формы, выводимой за n шагов, существует соответствующее дерево вывода.

Пусть произвольная сентенциальная форма ϕ выводима за (n + 1) шаг, тогда вывод можно разбить на две части:

вывод длины n: S αSβ, где α, β (N T)*, A N;

и вывод длины 1: αAβ αX1X2 ... Xnβ = ϕ, где Xi N T.

Так как по предположению индукции существует частичное дерево вывода с кроной αАβ и так как грамматика содержит продукцию А → Х1Х2 ... Хn, то, наращивая это дерево в вершине А с помощью указанной продукции, мы получим частичное дерево вывода с кроной αХ1Х2 ... Хnβ = ϕ, что и требовалось.

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

Так как любое дерево вывода является в то же время и частичным деревом вывода, листья которого помечены терминальными символами, то из предыдущих рассуждений следует, что каждая строка в L(G) является кроной некоторого дерева вывода в G, а крона любого дерева вывода в G принадлежит

L(G).

Итак, для каждой строки α L(G) существует соответствующее дерево вывода, которое показывает, какие продукции участвуют в выводе этой строки, но без указания их строгого порядка применения. Но можно представить себе, что при построении дерева вывода наращивается самая левая вершина,

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

Следствие 8.7.

В КС-грамматике G любая строка α L(G) имеет левосторонний и правосторонний вывод.