Регулярные выражения и языки (стр. 21 )

Пример 5.1. Правила определения палиндромов, выраженные в виде контекстно-свобод­ной грамматики, представлены на рис. 5.1. В разделе 5.1.2 мы рассмотрим их подробнее.

Первые три правила образуют базис. Они говорят, что класс палиндромов включает цепочки Е, 0 и 1. Эти правила образуют базис, поскольку ни одна из их правых частей (справа от стрелок) не содержит переменных.

Последние два правила образуют индуктивную часть определения. Например, прави­ло 4 гласит, что если взять произвольную цепочку w из класса Р, то OwO также будет в классе Р. Аналогично, по правилу 5 цепочка 1 w 1 также будет в классе Р. □

Р^Е 0 1 Р 0Р0 Р -> 1F1

Рис. 5.1. Контекстно-свободная грамматика для палиндромов

5.1.2. Определение контекстно-свободных грамматик

Описание языка с помощью грамматики состоит из следующих четырех важных компонентов.

Есть конечное множество символов, из которых состоят цепочки определяемого языка. В примере о палиндромах это было множество {0, 1}. Его символы называ­ются терминальными, или терминалами. Существует конечное множество переменных, называемых иногда также нетерми­налами, или синтаксическими категориями. Каждая переменная представляет язык, т. е. множество цепочек. В рассмотренном примере была только одна переменная, Р, которая использовалась для представления класса палиндромов в алфавите {0, 1}. Одна из переменных представляет определяемый язык; она называется стартовым символом. Другие переменные представляют дополнительные классы цепочек, кото­рые помогают определить язык, заданный стартовым символом. Имеется конечное множество продукций, или правил вывода, которые представляют рекурсивное определение языка. Каждая продукция состоит из следующих частей:

а)        переменная, (частично) определяемая продукцией. Эта переменная часто на­зывается головой продукции;

б)        символ продукции —

в)        конечная цепочка, состоящая из терминалов и переменных, возможно, пустая. Она называется телом продукции и представляет способ образования цепочек языка, обозначаемого переменной в голове. По этому способу мы оставляем тер­миналы неизменными и вместо каждой переменной в теле подставляем любую цепочку, про которую известно, что она принадлежит языку этой переменной.

Пример множества продукций приведен на рис. 5.1.

Описанные четыре компонента образуют контекстно-свободную грамматику, или КС-грамматику, или просто грамматику, или КСГ. Мы будем представлять КС - грамматику G ее четырьмя компонентами в виде G = (V, Т, Р, S), где V— множество пе­ременных, Т— терминалов, Р — множество продукций, S — стартовый символ. Пример 5.2. Грамматика Gpa/ для палиндромов имеет вид Gpal = ({P}, {0, 1 },А, Р), где А обозначает множество из пяти продукций (см. рис. 5.1). □

Пример 5.3. Рассмотрим более сложную КС-грамматику, которая представляет вы­ражения типичного языка программирования (в несколько упрощенном виде). Во - первых, ограничимся операторами + и *, представляющими сложение и умножение. Во - вторых, допустим, что аргументы могут быть идентификаторами, однако не произволь­ными, т. е. буквами, за которыми следует любая последовательность букв и цифр, в том числе пустая. Допустим только буквы аиАи цифры 0 и 1. Каждый идентификатор дол­жен начинаться с буквы а или Ь, за которой следует цепочка из {а, Ъ, 0, 1}*.

В нашей грамматике нужны две переменные. Одна обозначается Е и представляет выражения определяемого языка. Она является стартовым символом. Другая перемен­ная, /, представляет идентификаторы. Ее язык в действительности регулярен и задается регулярным выражением

(а + b)(a + b + 0 + 1)*.

В грамматиках, однако, регулярные выражения непосредственно не используются. Вместо этого будем обращаться к множеству продукций, задающих в точности то же са­мое, что и соответствующее регулярное выражение.

1.	Е -
2.	Е-^Е + Е
3.
4.
5.	I-	> а
6.	/-	>Ь
7.	I-	> 1а
8.	/-> lb
9.	/-	>/0
10.	/->/1

Рис. 5.2. Контекстно-свободная грамматика для простых выражений

Грамматика для выражений определяется формально как G - (\Е, /}, Т, Р, Е), где Т = {+, *, (, ), а, Ь, 0, 1}, а Р представляет собой множество продукций, показанное на рис. 5.2. Продукции интерпретируются следующим образом.

Правило 1 является базисным для выражений. Оно гласит, что выражение может быть одиночным идентификатором. Правила 2-4 описывают индуктивное образование выражений. Правила 2 и 3 говорят, что выражение может состоять из двух выражений, соединенных знаком сложения или умножения. Правило 4 — что если заключить произ­вольное выражение в скобки, то в результате получается также выражение.

Сокращенное обозначение продукций

Продукцию удобно рассматривать как "принадлежащую" переменной в ее голове. Мы бу­дем часто пользоваться словами "продукции для А" или "А-продукции" для обозначения продукций, головой которых является переменная А. Продукции грамматики можно запи­сать, указав каждую переменную один раз и затем перечислив все тела продукций для этой переменной, разделяя их вертикальной чертой. Таким образом, продукции А —> ah А—>а2, ..., А —> а,, можно заменить записью А —» а, | а2 | ... | с^. Например, грамматику для палиндромов (см. рис. 5.1) можно записать в виде Р —> е | 0 | 110Р0 | 1Р1.

t        Правила 5-10 описывают идентификаторы I. Правила 5 и 6 образуют базис; они гла-

|        сят, что а и b — идентификаторы. Остальные четыре правила описывают индуктивный

i        переход: имея произвольный идентификатор, можно приписать к нему справа а, Ь, 0 или

*        1 и получить еще один идентификатор. □

5.1.3. Порождения с использованием грамматики

Для того чтобы убедиться, что данные цепочки принадлежат языку некоторой пере­менной, мы применяем продукции КС-грамматики. Есть два способа действий. Про­стейший подход состоит в применении правил "от тела к голове". Мы берем цепочки, про которые известно, что они принадлежат языкам каждой из переменных в теле прави­ла, записываем их в соответствующем порядке вместе с терминалами этого тела и убеж­даемся, что полученная цепочка принадлежит языку переменной в голове. Такая проце­дура называется рекурсивным выводом (recursive inference).

Есть еще один способ определения языка грамматики, по которому продукции при­меняются "от головы к телу". Мы разворачиваем стартовый символ, используя одну из его продукций, т. е. продукцию, головой которой является этот символ. Затем разворачи­ваем полученную цепочку, заменяя одну из переменных телом одной из ее продукций, и так далее, пока не получим цепочку, состоящую из одних терминалов. Язык грамматики— это все цепочки из терминалов, получаемые таким способом. Такое ис­пользование грамматики называется выведением, или порождением (derivation).

Начнем с примера применения первого подхода — рекурсивного вывода, хотя часто естественнее рассматривать грамматики в качестве применяемых для порождений, и да­лее мы разовьем систему записи таких порождений.

Пример 5.4. Рассмотрим некоторые из выводов, которые можно сделать, используя грамматику для выражений (см. рис. 5.2). Результаты этих выводов показаны на рис. 5.3. Например, строчка (/') говорит, что в соответствии с продукцией 5 цепочка а принадле­жит языку переменной /. Строчки (i/)—(iv) свидетельствуют, что цепочка 600 является идентификатором, полученным с помощью одного применения продукции 6 и затем двух применений продукции 9.

В строчках (v) и (vi) использована продукция 1 для того, чтобы прийти к заключению, что цепочки а и Ь00, которые выведены как идентификаторы в строчках (/') и (/V), при­надлежат также и языку переменной Е. В строчке (vii) применяется продукция 2 для вы­вода, что сумма этих идентификаторов является выражением, в строчке (viii) — продук­ция 4, и эта же сумма в скобках также представляет собой выражение. В строчке (ix) ис­пользуется продукция 3 для умножения идентификатора а на выражение, исследованное в строчке (viii). □

Процесс порождения цепочек путем применения продукций "от головы к телу" тре­бует определения нового символа отношения =>. Пусть G= (V, T,P, S)— КС-грам­матика. Пусть аА/З— цепочка из терминалов и переменных, где А — переменная. Таким

образом, а и (3— цепочки из (VU Т), А е V. Пусть А —> у— продукция из G. Тогда мы говорим, что аЛР => аур. Если грамматика G подразумевается, то это записывается

g

просто как аА/3=> ау/З. Заметим, что один шаг порождения заменяет любую переменную в цепочке телом одной из ее продукций.

Выведенная	Для языка	Использован­	Использо­
цепочка	переменной	ная продук­ция	ванные цепочки
(0	a	/	5	—
00	b	/	6	—
(Hi)	bO	/	9	(ii)
(iv)	bOO	/	9	(iii)
(V)	a	E	1	(0
(vi)	b№	E	1	(iv)
(vii)	a + bOO	E	2	(v), (vi)
(viii)	(a + bOO)	E	4	(vii)
(ix)	a* (a + bOO)	E	3	(v), (viii)

Рис. 5.3. Вывод цепочек с использованием грамматики, показанной на рис. 5.2 Для представления нуля, одного или нескольких шагов порождения можно расши­рить отношение => подобно тому, как функция переходов <5 расширялась до 5 . Для обо­значения нуля или нескольких шагов порождения используется символ *.