Введение в теорию автоматов, языков и вычислений. Глава 5. |

ГЛАВА 5 Контекстно-свободные грамматики и языки

Перейдем от рассмотрения регулярных языков к более широкому классу языков, которые называются контекстно-свободными. Они имеют естественное рекурсивное описание в виде контекстно-свободных грамматик. Эти грамматики играют главную роль в технологии компиляции с начала 1960-х годов; они превратили непростую задачу реализации синтаксических анализаторов, распознающих структуру программы, из неформальной в рутинную, которую можно решить за один вечер. Позже контекстно-свободные грамматики стали использоваться для описания форматов документов в виде так называемых определений типа документов (document-type definition — DTD), которые применяются в языке XML (extensible markup language) для обмена информацией в Internet.

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

Контекстно-свободные языки также описываются с помощью магазинных автоматов, рассматриваемых в главе 6. Эти автоматы не столь важны, как конечные, однако в качестве средства определения языков они эквивалентны контекстно-свободным грамматикам и особенно полезны при изучении свойств замкнутости и разрешимости контекстно- свободных языков (глава 7).

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

Начнем с неформального представления контекстно-свободных грамматик, затем рассмотрим их некоторые важные свойства. Далее определим их формально и представим процесс «вывода», с помощью которого грамматика задает цепочки языка.

5.1.1. Неформальный пример

Рассмотрим язык палиндромов. Палиндром — это цепочка, читаемая одинаково слева направо и наоборот, например, otto или madamimadam («Madam, I’m Adam» — по преданию, первая фраза, услышанная Евой в Райском саду). Другими словами, цепочка w является палиндромом тогда и только тогда, когда w = мЛ Для упрощения рассмотрим описание палиндромов только в алфавите {0, 1}. Этот язык включает цепочки вроде 0110, 11011, е, но не включаетОП или0101.

Нетрудно проверить, что язык L_pa/ палиндромов из символов 0 и 1 не является регулярным. Используем для этого лемму о накачке. Если язык L_pat регулярен, то пусть п — соответствующая константа из леммы. Рассмотрим палиндром w = 0^П10″. Если L_pa/ регулярен, то w можно разбить на w = xyz так, что у состоит из одного или нескольких нулей из их первой группы. Тогда в слове xz, которое также должно быть в L_pai, если L_pai регулярен, слева от единицы будет меньше нулей, чем справа. Следовательно, xz не может быть палиндромом, что противоречит предположению о регулярности L_pa_/.

Существует следующее естественное рекурсивное определение того, что цепочка из символов 0 и 1 принадлежит языку L_pa_/. Оно начинается с базиса, утверждающего, что несколько очевидных цепочек принадлежат L_pah а затем использует идею того, что если цепочка является палиндромом, то она должна начинаться и заканчиваться одним и тем же символом. Кроме того, после удаления первого и последнего символа остаток цепочки также должен быть палиндромом.

Базис, е, 0 и 1 являются палиндромами.

Индукция. Если w— палиндром, то OwO и 1 w 1 — также палиндромы. Ни одна цепочка не является палиндромом, если не определяется этими базисом и индукцией.

Контекстно-свободная грамматика представляет собой формальную запись подобных рекурсивных определений языков. Грамматика состоит из одной или нескольких переменных, которые представляют классы цепочек, или языки. В данном примере нужна только одна переменная, представляющая множество палиндромов, т.е. класс цепочек, образующих язык Lpai. Имеются правила построения цепочек каждого класса. При построении используются символы алфавита и уже построенные цепочки из различных классов.

Пример 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. Грамматика G_pa/ для палиндромов имеет вид G_pal = ({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 — что если заключить произвольное выражение в скобки, то в результате получается также выражение.

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

Продукцию удобно рассматривать как «принадлежащую» переменной в ее голове. Мы будем часто пользоваться словами «продукции для А» или «А-продукции» для обозначения продукций, головой которых является переменная А. Продукции грамматики можно записать, указав каждую переменную один раз и затем перечислив все тела продукций для этой переменной, разделяя их вертикальной чертой. Таким образом, продукции А —> a_h А—>а₂, …, А —> а,, можно заменить записью А —» а, | а₂ | … | с^. Например, грамматику для палиндромов (см. рис. 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 подразумевается, то это записывается

просто как аА/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 . Для обозначения нуля или нескольких шагов порождения используется символ *.

Базис. Для произвольной цепочки а терминалов и переменных считаем, что а => а.

Таким образом, любая цепочка порождает саму себя.

Индукция. Если а => f3 и /3 => у, то а => у. Таким образом, если а может породить

g g g

13 за нуль или несколько шагов, и из /3 еще за один шаг порождается у, то а может породить у. Иными словами, а => /3 означает, что для некоторого п> 1 существует последовательность цепочек y_h у₂, …, у„, удовлетворяющая следующим условиям. 1. а=у,. 2- 13=у„.

Для i = 1,2, …, п-1 имеет место отношение у, => y_f₄.

* •

Если грамматика G подразумевается, то вместо => используется обозначение =>.

Пример 5.5. Вывод о том, что а*(а + 600) принадлежит языку переменной £, можно отразить в порождении этой цепочки, начиная с Е. Запишем одно из таких порождений. £=> Е* £=> /* £=> а* £=> а * (£) =>а*(Е + Е)=>а*(1 + Е)=>а* (а+ Е)=> а*(а + Г)=$а*(а + Ю)=$а*(а + /00) => а * (а + 600) На первом шаге £ заменяется телом продукции 3 (см. рис. 5.2). На втором шаге применяется продукция 1 для изменения £ на / и т.д. Заметим, что мы систематически придерживались тактики замены крайней слева переменной в цепочке. На каждом шаге, однако, мы можем произвольно выбирать переменную для замены и использовать любую из продукций для этой переменной. Например, на втором шаге мы могли бы изменить второе £ на (£), используя продукцию 4. В этом случае £*£=>£* (£). Мы могли бы также выбрать замену, не приводящую к той же самой цепочке терминалов. Простым примером было бы использование продукции 2 на первом же шаге, в результате чего Е=> Е + Е, но теперь никакая замена переменных £ не превратит цепочку Е + Ева* (а + 600).

Мы можем использовать отношение => для сокращения порождения. На основании

базиса нам известно, что £ => £ Несколько использований индукции дают нам утвер- * * *

ждения £=> £*£,£=> I* Е и так далее до заключительного £ => а* (а + 600).

Две точки зрения — рекурсивный вывод и порождение — являются эквивалентными. Таким образом, можно заключить, что цепочка терминалов w принадлежит языку некоторой переменной А тогда и только тогда, когда А => w. Доказательство этого факта, однако, требует некоторых усилий, и мы отложим его до раздела 5.2.

5.1.4. Левые и правые порождения

Для ограничения числа выборов в процессе порождения цепочки полезно потребо¬вать, чтобы на каждом шаге мы заменяли крайнюю слева переменную одним из тел ее продукций. Такое порождение называется левым (leftmost), и для его указания использу¬ются отношения => и =>. Если используемая грамматика G не очевидна из контекста, то

lm 1т

ее имя G также добавляется внизу.

Аналогично можно потребовать, чтобы на каждом шаге заменялась крайняя справа

переменная на одно из тел. В таком случае порождение называется правым (rightmost), и

для его обозначения используются символы => и =>. Имя используемой грамматики

rm гт

также при необходимости записывается внизу.

Пример 5.6. Порождение из примера 5.5 в действительности было левым, и его мож¬но представить следующим образом.

£=>£*£=>1*Е=>а*Е=>

lm lm lm 1т

а * (£) => а *(£ + £) => а* (1 + Е) => а * (а + £) =>

Im Im Im 1т

а * (а + I) => а * (а + /0) а* (а + /00) => а * (а + Ь00)

Im 1т /т

Обозначения для порождений, заданных КС-грамматиками

Существует немало соглашений, напоминающих о роли тех или иных символов, ис¬пользуемых в КС-грамматиках. Будем использовать следующие соглашения.

Строчные буквы из начала алфавита (а, Ъ и т.д.) являются терминальными симво¬лами. Будем предполагать, что цифры и другие символы типа знака + или круглых скобок — также терминалы.
Прописные начальные буквы (А, В и т.д.) являются переменными.
Строчные буквы из конца алфавита, такие как w или z, обозначают цепочки тер¬миналов. Это соглашение напоминает, что терминалы аналогичны входным сим¬волам конечного автомата.
Прописные буквы из конца алфавита, вроде X или У, могут обозначать как терми¬налы, так и переменные.
Строчные греческие буквы (а, (5 и т.д.) обозначают цепочки, состоящие из терми¬налов и/или переменных.

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

Можно резюмировать левое порождение в виде Е => а * (а + 300) или записать несколь-

1т

ко его шагов в виде выражений типа Е* Е => а* (Е).

1т

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

£=> Е* Е => Е*(Е) => £ * (£ + Е) =>

rm rm гт гт

£*(£ + /) => £*(£ +10) => £ * (£ + /00) £ * (£ + 600)

гт гт гт гт

£*(/+М)0) => Е*(а + Ь00) => I*(a + b00) => а*(а + 600)

гт гт гт

Данное порождение также позволяет заключить, что £ => а* (а + 600).

гт

Любое порождение имеет эквивалентные левое и правое порождения. Это означает, что если w — терминальная цепочка, а А — переменная, то А => w тогда и только тогда, когда А => w, а также А => w тогда и только тогда, когда А => w. Эти утверждения дока-

1п! гт

зываются также в разделе 5.2.

5.1.5. Язык, задаваемый грамматикой

Если G = (V, T,P,S)— КС-грамматика, то язык, задаваемый грамматикой G, или язык грамматики G, обозначается L(G) и представляет собой множество терминальных цепочек, порождаемых из стартового символа. Таким образом,

L(G)={we f\S=>w}.

Если язык L задается некоторой КС-грамматикой, то он называется контекстно- свободным, или КС-языком. Например, мы утверждали, что грамматика, представленная на рис. 5.1, определяет множество палиндромов в алфавите {0, 1}. Таким образом, множество палиндромов является КС-языком. Можем доказать это утверждение следующим образом.

Теорема 5.7. Язык L(Gpal), где Gpai— грамматика из примера 5.1, является множест¬вом палиндромов над {0, 1}.

Доказательство. Докажем, что цепочка w в {0, 1}* принадлежит L(Gpa,) тогда и толь¬ко тогда, когда она является палиндромом, т.е. w = wR.

(Достаточность) Пусть w — палиндром. Докажем индукцией по |w|, что w е L(Gpai).

Базис. Если |w| = 0 или |w| = 1, то w представляет собой е, 0 или 1. Поскольку в грам-

♦

матике есть продукции Р —> £, Р —> О, Р —> 1, то во всех случаях Р => w.

Индукция. Пусть |w| > 2. Так как w = wR, она должна начинаться и заканчиваться од¬ним и тем же символом, т.е. w = 0x0 или w = 1×1. Кроме того, х является палиндромом, т.е. х = xR. Заметим, что нам необходим факт w > 2, чтобы обеспечить наличие двух раз¬личных нулей или единиц на обоих концах w.

Если w = 0x0, то по предположению индукции Р => х. Тогда существует порождение

w из Р: Р 0Р0 => 0x0 = w. Если w = 1×1, то рассуждения аналогичны, но с использова¬нием продукции Р —> \Р\ на первом шаге. В обоих случаях заключаем, что we L(Gpai), тем самым завершая доказательство.

(Необходимость) Предположим, что we L(Gpai), т.е. Р => w. Докажем, что w— па¬линдром. Проведем доказательство индукцией по числу шагов в порождении w из Р.

Базис. Если порождение имеет один шаг, то он использует одну из трех продукций, не имеющих Р в теле, т.е. порождение представляет собой Р => £, Р => 0 или Р => \. Так как £, 0 и 1 — палиндромы, то базис доказан.

Индукция. Предположим, что порождение состоит из п+ 1 шагов, где п> 1, и что утверждение индукции верно для всех порождений из п шагов. Таким образом, если

Р =ф х за п шагов, то х является палиндромом.

Рассмотрим (п + 1)-шаговое порождение, которое должно иметь вид

Р 0Л) =» 0x0 = w

или Р => lPl => lxl = w, поскольку п + 1 шаг— это как минимум два шага, и только ис¬пользование продукций Р —> Of0 или Р —» 1Р1 делает возможными дополнительные ша-

ги порождения. Заметим, что в обоих случаях Р => х за п шагов.

По предположению индукции х является палиндромом, т.е. x=xR. Но тогда и 0x0, и 1×1 — палиндромы. Например, (0x0)R = 0xR0 = 0x0. Делаем вывод, что w— палиндром и завершаем доказательство. □

5.1.6. Выводимые цепочки

Порождения из стартового символа грамматики приводят к цепочкам, имеющим осо¬бое значение. Они называются «выводимыми цепочками» («sentential form»). Итак, если

G = (У, Т, Р, S) — КС-грамматика, то любая цепочка а из (FU Т), для которой S ==> а, называется выводимой цепочкой. Если S => а, то а является левовыводимой цепочкой, a

если S => а, то — правовыводимой. Заметим, что язык L(G) образуют выводимые це-

тт

почки из Т*, состоящие исключительно из терминалов.

Пример 5.8. Рассмотрим грамматику выражений (см. рис. 5.2). Например, Е* (1+ Е) является выводимой цепочкой, поскольку существует следующее порождение.

£=>£*£=>£*(£) £*(£ + £) =>£*(/ + £) Однако это порождение не является ни левым, ни правым, так как на последнем шаге за¬меняется среднее £.

Примером левовыводимой цепочки может служить а * £ со следующим левым поро¬ждением.

£=>£*£=> /*£=> а*£

hn Im Im

Аналогично, порождение

rm rm rm

показывает, что £*(£ + £) является правовыводимой цепочкой. □

Способ доказательства теорем о грамматиках

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

Доказывается достаточность: если цепочка w удовлетворяет неформальным утвер¬ждениям о цепочках переменной А, то А => w. В нашем примере, поскольку Р явля-

ется стартовым символом, мы утверждали «Р => w», говоря, что w принадлежит язы¬ку грамматики. Обычно достаточность доказывается индукцией по длине слова w. Если в грамматике к переменных, то индуктивное утверждение имеет к частей, кото¬рые доказываются с помощью взаимной индукции.

Нужно доказать также необходимость, т.е. что если А => w, то w удовлетворяет не¬формальным утверждениям о цепочках, порождаемых из переменной А. Поскольку в

нашем примере был только стартовый символ Р, предположение о том, что

w б L(Gpai), было равносильно Р => w. Для доказательства этой части типична индук¬ция по числу шагов порождения. Если в грамматике есть продукции, позволяющие нескольким переменным появляться в порождаемых цепочках, то «-шаговое порож¬дение нужно разбить на несколько частей, по одному порождению из каждой пере¬менной. Эти порождения могут иметь менее п шагов, поэтому следует предполагать утверждение индукции верным для всех значений, которые не больше п, как это об¬суждалось в разделе 1.4.2.

5.1.7. Упражнения к разделу 5.1

5.1.1. Построить КС-грамматики для следующих языков:

а) (*) множество {0″1п|/7> 1} всех цепочек из одного и более символов 0, за которыми следуют символы 1 в таком же количестве;

б) (*!) множество {аУск | i или j # к) всех цепочек из символов а, за кото¬рыми следуют символы Ъ и затем с так, что количества символов а и Ъ или количества Ьис различны;

в) (!) множество всех цепочек из символов а и Ь, не имеющих вида тс, т.е. не равных ни одной цепочке-повторению;

г) (!!) множество всех цепочек, у которых символов 0 вдвое больше, чем сим¬волов 1.

5.1.2. Следующая грамматика порождает язык регулярного выражения 0*1(0 + 1)*.

S-M1B

А—>0А\е

В->0В\ \В\е

Запишите левое и правое порождения следующих цепочек:

а) 00101;

б) 1001; в) 00011.

5.1.3. Докажите, что каждый регулярный язык является КС-языком. Указание. По¬стройте КС-грамматику с помощью индукции по числу операторов в регуляр¬ном выражении.

5.1.4. КС-грамматика называется праволинейной, если тело каждой продукции имеет не более одной переменной, причем она находится на правом краю тела. Таким образом, продукции праволинейной грамматики имеют вид А —> wB или A —>w, где А и В — переменные, aw — терминальная цепочка, возможно, пустая:

а) докажите, что каждая праволинейная грамматика порождает регулярный язык. Указание. Постройте е-НКА, который имитирует левые порождения, представляя своим состоянием единственную переменную в текущей лево- выводимой цепочке;

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

5.1.5. (*!) Пусть Т= {0, 1, (,),+,*, 0, е}. Т можно рассматривать как множество символов, используемых в регулярных выражениях над алфавитом {0, 1}. Единственная разница состоит в том, что во избежание возможной путаницы вместо символа е используется символ е. Постройте КС-грамматику со мно¬жеством терминалов Т, которая порождает в точности регулярные выражения в алфавите {0, 1}.

5.1.6. Отношение => было определено с базисом «а=>а» и индукцией, утверждав-

* * ♦

шей: «из а => Р и /3 => /следует а => Есть несколько других способов опре¬деления отношения =>, также равнозначных фразе: «=> есть нуль или несколь¬ко шагов отношения =>». Докажите следующие утверждения:

а) а Р тогда и только тогда, когда существует последовательность из одной или нескольких цепочек у,, у2, …, у„ где а= yh /3 = у„ и для /’= 1, 2, …, п- 1 имеет место у, => уьГ,

б) если а => Р и /3 у, то а => у. Указание. Воспользуйтесь индукцией по

числу шагов в порождении Р => у.

5.1.7. (!) Рассмотрим КС-грамматику G, определяемую следующими продукциями: S->aS|S6|a|6

а) докажите индукцией по длине цепочки, что ни одна цепочка в 1(G) не со¬держит Ьа как подцепочку;

б) дайте неформальное описание L(G). Уточните ответ, используя часть (а). 5.1.8. (!!) Рассмотрим КС-грамматику G, определяемую следующими продукциями.

S-> aSbS | bSaS \ e

Докажите, что L(G) представляет собой множество всех цепочек, в которых по¬ровну символов а и Ь.

5.2. Деревья разбора

Для порождений существует чрезвычайно полезное представление в виде дерева. Это дерево наглядно показывает, каким образом символы цепочки группируются в подце¬почки, каждая из которых принадлежит языку одной из переменных грамматики. Воз¬можно, более важно то, что дерево, известное в компиляции как «дерево разбора», явля¬ется основной структурой данных для представления исходной программы. В компиля¬торе древовидная структура исходной программы облегчает ее трансляцию в исполняе¬мый код за счет того, что допускает естественные рекурсивные функции для выполнения этой трансляции.

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

5.2.1. Построение деревьев разбора

Будем рассматривать грамматику G = (V, Т, Р, S). Деревья разбора для G — это дере¬вья со следующими свойствами.

Каждый внутренний узел отмечен переменной из V.
Каждый лист отмечен либо переменной, либо терминалом, либо е. При этом, если лист отмечен £, он должен быть единственным сыном своего родителя.
Если внутренний узел отмечен А, и его сыновья отмечены слева направо Xh Х2, …, Хк, соответственно, то А —>Х,Х2 — Хк является продукцией в Р. Отметим, что Смо¬жет быть £ лишь в одном случае— если он отмечает единственного сына, и А £ — продукция грамматики G.

Обзор терминов, связанных с деревьями

Мы предполагаем, что читатель знаком с понятием дерева и основными определе¬ниями для деревьев. Тем не менее, напомним их вкратце.

Деревья представляют собой множества узлов с отношением родитель-сын. Узел имеет не более одного родителя, изображаемого над узлом, и нуль или несколько сыновей, изображаемых под ним. Родителей и их сыновей соединяют линии. Примеры деревьев представлены на рис. 5.4-5.6.
Один узел, корень, не имеет родителя; он появляется на вершине дерева. Узлы без сыновей называются листьями. Узлы, не являющиеся листьями, называются внутренними узлами.
Сын сына и так далее узла называется его потомком’, соответственно, роди¬тель родителя и так далее — предком. Узлы считаются потомками и предками самих себя.
Сыновья узла упорядочиваются слева направо и изображаются в этом порядке. Если узел N находится слева от узла М, то считается, что все потомки узла N на¬ходятся слева от всех потомков М.

Пример 5.9. На рис. 5.4 показано дерево разбора, которое использует грамматику выражений (см. рис. 5.2). Корень отменен переменной £. В корне применена продук¬ция £—»£ + £, поскольку три сына корня отмечены слева направо как £, +, £. В левом сыне корня применена продукция £ —» /, так как у этого узла один сын, отмеченный переменной /. □

Пример 5.10. На рис. 5.5 показано дерево разбора для грамматики палиндромов (см. рис. 5.1). В корне применена продукция Р —» 0/>0, а в среднем сыне корня — Р —> \Р\. Отметим, что внизу использована продукция Р —> е. Это использование, при котором у узла есть сын с отметкой е, является единственным случаем, когда в дереве может быть узел, отмеченный е. □

Рис. 5.4. Дерево разбора, показы- Рис. 5.5. Дерево разбора, показы¬вающее порождение 1 + ЕизЕ .

‘ ‘ Ч/У/У М Ч III III

вающее порождение Р => 0110

5.2.2. Крона дерева разбора

Если мы посмотрим на листья любого дерева разбора и выпишем их отметки слева направо, то получим цепочку, которая называется кроной дерева и всегда является це¬почкой, выводимой из переменной, отмечающей корень. Утверждение о том, что крона выводима из отметки корня, будет доказано далее. Особый интерес представляют дере¬вья разбора со следующими свойствами.

Крона является терминальной цепочкой, т.е. все листья отмечены терминалами или е.
Корень отмечен стартовым символом.

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

Пример 5.11. На рис. 5.6 представлен пример дерева с терминальной цепочкой в ка¬честве кроны и стартовым символом в корне. Оно основано на грамматике для выраже¬ний (см. рис. 5.2). Крона этого дерева образует цепочку а * (а + 600), выведенную в при¬мере 5.6. В действительности, как мы увидим далее, это дерево разбора представляет по¬рождение данной цепочки. □

Рис. 5.6. Дерево разбора для а * (a + b00) в языке для грамматики выражений

5.2.3. Вывод, порождение и деревья разбора

Каждый из способов, определенных ранее для описания работы грамматики, приво¬дит по существу к одним и тем же утверждениям о цепочках. Итак, покажем, что при любой грамматике G = (V, T,P,S) следующие утверждения равносильны.

Процедура рекурсивного вывода определяет, что цепочка w принадлежит языку пе¬ременной/!.

=> w. А => w.

Правое порождение

Порождение

Рекурсивный вывод

Рис. 5.7. Доказательство равносильности утверждений о грамматиках

Отметим, что две стрелки весьма просты и не будут обоснованы формально. Если це¬почка w имеет левое порождение из А, то она безусловно порождается из А, поскольку левое порождение является порождением. Аналогично, если цепочка w имеет правое по¬рождение, то она имеет и порождение. Приступим к доказательству более трудных ша¬гов описанной равносильности.

1т

А
Существует дерево разбора с корнем А и кроной w.

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

Указанные равносильности доказываются в соответствии с планом, приведенным на рис. 5.7. Для каждой стрелки в этой диаграмме доказывается теорема, которая утвержда¬ет, что если w удовлетворяет условию в начале стрелки, то удовлетворяет и условию в ее конце. Например, мы покажем в теореме 5.12, что если w принадлежит языку А в соот¬ветствии с рекурсивным выводом, то существует дерево разбора с корнем А и кроной w.

Дерево ^^^^ разбора

Левое порождение

5.2.4. От выводов к деревьям разбора

Теорема 5.12. Пусть G = (V, Т, P,S) — КС-грамматика. Если рекурсивный вывод ут¬верждает, что терминальная цепочка w принадлежит языку переменной А, то существует дерево разбора с корнем А и кроной w.

Доказательство. Проведем доказательство индукцией по числу шагов, используемых в выводе того, что w принадлежит языку А.

Базис. Вывод содержит один шаг. В этом случае использован только базис процеду¬ры вывода, и в грамматике должна быть продукция A—>w. В дереве на рис. 5.8 сущест¬вует лист для каждого символа цепочки w, оно удовлетворяет условиям, налагаемым на дерево разбора для грамматики G, и, очевидно, имеет корень А и крону w. В особом слу¬чае, когда w = £, дерево имеет только один лист, отмеченный е, и является допустимым деревом разбора с корнем А и кроной w.

Индукция. Предположим, что факт принадлежности w языку переменной А выводит¬ся за п + 1 шаг, и что утверждение теоремы справедливо для всех цепочек х и перемен¬ных В, для которых принадлежность х языку В была выведена с использованием п или менее шагов вывода. Рассмотрим последний шаг вывода того, что w принадлежит языку А. Этот вывод использует некоторую продукцию для А, например А —> XtX2…Xb где ка¬ждый X, есть либо переменная, либо терминал.

Цепочку w можно разбить на подцепочки w,w2. ..Wk, для которых справедливо следующее.

Если Xj является терминалом, то w, = X,, т.е. w, представляет собой один- единственный терминал из продукции.

Если X) — переменная, то w, представляет собой цепочку, о которой уже сделан вы¬вод, что она принадлежит языку переменной Xt. Таким образом, этот вывод относи¬тельно и>; содержит не более п из п + 1 шагов вывода, что w принадлежит языку А. Этот вывод не может содержать все п+ 1 шагов, поскольку заключительный шаг, использующий продукцию А —>X^-.-Xh, безусловно, не является частью вывода относительно w,. Следовательно, мы можем применить предположение индукции к w, и заключить, что существует дерево разбора с кроной w, и корнем X,.

Рис. 5.8. Дерево, построенное для базиса Рис. 5.9. Дерево, использованное в индуктив- теоремы 5.12 ной части доказательства теоремы 5.12

Далее мы построим дерево с корнем А и кроной w в соответствии с рис. 5.9. Там по¬казан корень с отметкой А и сыновьями X), Х2, …, Хк. Такой выбор отметок возможен, поскольку Л —> Х,Х2.. .Хк является продукцией грамматики G.

Узел для каждого X, становится корнем поддерева с кроной w,. В ситуации 1, где X, — терминал, это поддерево состоит из одного листа, отмеченного X,. Так как в данной си¬туации w,=Xi, условия того, что кроной поддерева является w,, выполнены.

Во второй ситуации X, является переменной. Тогда по предположению индукции су¬ществует дерево с корнем X, и кроной w,. Оно присоединяется к узлу для X, (см. рис. 5.9).

Построенное таким образом дерево имеет корень А. Его крона состоит из крон под¬деревьев, приписанных друг к другу слева направо, т.е. w = wtw2…wk. □

5.2.5. От деревьев к порождениям

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

Пример 5.13. Рассмотрим еще раз грамматику выражений (см. рис. 5.2). Нетрудно убедиться, что существует следующее порождение.

£=>/=> lb ab

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

аЕ(3 аф=> alb/3 => aab/3 Доказательством служит то, что головы продукций можно заменять их телами в контек¬сте а и /3 точно так же, как и вне его.

Например, если порождение начинается заменами £=>£ + £=>£ + (£), то можно было бы применить порождение цепочки ab из второго £, рассматривая «£+(» в качестве а и «)» — Д Указанное порождение затем продолжалось бы следующим образом. £+(£)=>£ + (/)=>£ + (lb) => £ + (ab)

□

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

Например, высота дерева, изображенного на рис. 5.6, равна 7. Самый длинный из путей от корня к листьям ведет к листу, отмеченному Ь. Заметим, что длины путей обычно учиты¬вают ребра, а не узлы, поэтому путь, состоящий из единственного узла, имеет длину 0.

Теорема 5.14. Пусть G = (V, Т, P,S) — КС-грамматика. Предположим, что существу¬ет дерево разбора с корнем, отмеченным А, и кроной w, где we 7*. Тогда в грамматике G

существует левое порождение А => w.

Доказательство. Используем индукцию по высоте дерева.

Базис. Базисом является высота 1, наименьшая из возможных для дерева разбора с терминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным А, и сыновьями, образующими цепочку w. Поскольку это дерево является деревом раз¬бора, А —> w должно быть продукцией. Таким образом, А => w есть одношаговое левое

порождение w из А.

Индукция. Если высота дерева равна п, где п> 1, то оно должно иметь вид, как на рис. 5.9. Таким образом, существует корень с отметкой А и сыновьями, отмеченными слева направоХ/Х2…Хк. Символы Смогут быть как терминалами, так и переменными.

Если X] — терминал, то определим w, как цепочку, состоящую из одного X,.
Если X, — переменная, то она должна быть корнем некоторого поддерева с терми¬нальной кроной, которую обозначим w,. Заметим, что в этом случае высота поддере¬ва меньше п, поэтому к нему применимо предположение индукции. Следовательно,

существует левое порождение X, => w,.

Заметим, что w = и>/и^…и>/;..

Построим левое порождение цепочки w следующим образом. Начнем с шага А => Х,Х2. ■ Хк. Затем для / = 1,2,…, к покажем, что имеет место следующее порождение.

А => w,w2…wiX^1Xi+2…Xk

Данное доказательство использует в действительности еще одну индукцию, на этот раз по (. Для базиса /’= 0 мы уже знаем, что А => XjX2.. .Х^ Для индукции предположим, что

существует следующее порождение. А WjW2…w./XX,■!■■ Хк

Если X,— терминал, то не делаем ничего, но в дальнейшем рассматриваем X, как терминальную цепочку W/. Таким образом, приходим к существованию следующего порождения. .

А w/w2…wjXi4XM…Xk

Если Xi является переменной, то продолжаем порождением vv, из X, в контексте уже построенного порождения. Таким образом, если этим порождением является

Xi => а; =» а2… wh

Im 1т 1т

то продолжаем следующими порождениями. Wiw2…wl4XlXi+,…Xk =>

w,w2…wi-, a,Xi4…Xk =»

W,W2… Wi уСЫС- ,…Xk =>

Wixv2…WiXi4X^2…Xk

Результатом является порождение A => wlw2…wX^iX^2…Xk.

Когда i = к, результат представляет собой левое порождение w из А. □

Пример 5.15. Рассмотрим левое порождение для дерева, изображенного на рис. 5.6. Продемонстрируем лишь заключительный шаг, на котором строится порождение по целому дереву из порождений, соответствующих поддеревьям корня. Итак, предполо¬жим, что с помощью рекурсивного применения техники из теоремы 5.14 мы убеди¬лись, что поддерево, корнем которого является левый сын корня дерева, имеет левое порождение £=>/=> а, а поддерево с корнем в третьем сыне корня имеет следующее

1т 1т

левое порождение.

£=>(£)=>(£ + £)=>(/ + £)=> (а + Е) =>

Im im Im Im Im

(a +1) => (a + /0) => (a + /00) => (a + 600)

lm lm Im

Чтобы построить левое порождение для целого дерева, начинаем с шага в корне: А => Е * Е. Затем заменяем первую переменную £ и в соответствии с ее порождением

1т

приписываем на каждом шаге *£, чтобы учесть контекст, в котором это порождение ис¬пользуется. Левое порождение на текущий момент представляет собой следующее.

£=» £*£=> / *£=> а * Е

lm Im 1т

Символ * в продукции, использованной в корне, не требует порождения, поэтому ука¬занное левое порождение также учитывает первые два сына корня. Дополним левое по¬рождение, используя порождение £ => (а + 600), левый контекст которого образован це¬ли

почкой а*, а правый пуст. Это порождение в действительности появлялось в примере 5.6 и имело следующий вид.

£* £ /* £ а * £

/m lm lm lm

a * (£) a * (£+£)=> a *(/+£) a * (a + £)

/я? /m lm lm

a * (a +1) a * (a +10) => a * (a + /00) => a * (a + 600)

lm lm lm

Аналогичная теорема позволяет нам преобразовать дерево в правое порождение. По¬строение правого порождения по дереву почти такое же, как и построение левого. Здесь, однако, после первого шага А => Х,Х2…Хк мы заменяем сначала Хк, используя правое

гт

порождение, затем Хки так далее до X,. Таким образом, примем без доказательства следующее утверждение.

Теорема 5.16. Пусть G = (V, Т, P,S) — КС-грамматика. Предположим, что существу¬ет дерево разбора с корнем, отмеченным А, и кроной w, где we f. Тогда в грамматике G

существует правое порождение А => w.

5.2.6. От порождений к рекурсивным выводам

Теперь завершим цикл, представленный на рис. 5.7, доказав, что если существует по- *

рождение А => w для некоторой КС-грамматики, то факт принадлежности w языку А до¬казывается путем процедуры рекурсивного вывода. Перед тем как приводить теорему и ее доказательство, сделаем важные замечания о порождениях.

Предположим, у нас есть порождение А =>XiX2…Xk => w. Тогда w можно разбить на

подцепочки w = w;w2…wk, где X, => w,. Заметим, что если X, является терминалом, то w, = Х„ и порождение имеет 0 шагов. Доказать это замечание несложно. Вы можете дока¬зать индукцией по числу шагов порождения, что еслиXjX2…Xk => а, то все позиции в а, происходящие от расширения X,, находятся слева от всех позиций, происходящих от расширения Xj, если i < j.

Если Xj является переменной, то можно получить порождение X, => w„ начав с поро- *

жденияЛ => w и отбрасывая следующее:

а) все шаги, не относящиеся к порождению w, из X,;

б) все позиции выводимой цепочки, которые находятся либо справа, либо слева от позиций, порождаемых из X,.

Этот процесс поясняется примером.

Пример 5.17. Используем грамматику выражений и рассмотрим следующее поро¬ждение.

Е=$Е*Е=>Е*Е + Е=э1*Е+Е=>1*1+Е=* l*l+l=$a*I + I=>a*b + I=$a*b + a

Рассмотрим третью выводимую цепочку, £*£ + £, и среднее £ в ней.2

Начав с £*£ + £, можно пройти по шагам указанного выше порождения, выбрасы¬вая позиции, порожденные из £* слева от центрального £ и из +£ справа от него. Шага¬ми порождения тогда становятся £, £, /, /, /, Ь, Ь. Таким образом, следующий шаг не ме¬няет центральное £, следующий за ним меняет его на /, два шага за ними сохраняют /, следующий меняет его на Ь, и заключительный шаг не изменяет того, что порождено из центрального £.

Если мы рассмотрим только шаги, которые изменяют то, что порождается из цен¬трального £, то последовательность £, £, /, /, /, b, Ь превращается в порождение £ => / => Ь. Оно корректно описывает, как центральное £ эволюционирует в полном по¬рождении. □

Теорема 5.18. Пусть G = (V, Т, Р, S) — КС-грамматика, и пусть существует порожде- ниеА =* w, где we Т. Тогда процедура рекурсивного вывода, примененная к G, опреде-

ляет, что w принадлежит языку переменной А.

Доказательство. Доказательство проведем индукцией по длине порождения А => w.

Базис. Если порождение состоит из одного шага, то А —» w должно быть продукцией. Так как w состоит только из терминалов, то факт принадлежности w языку А устанавли¬вается на основе базисной части процедуры рекурсивного вывода.

Индукция. Пусть порождение состоит из п + 1 шагов и пусть для любого порожде¬ния из и и менее шагов утверждение выполняется. Запишем порождение в виде А => *

Х,Х2…Хк => w. Тогда, как обсуждалось перед теоремой, можно представить w как w = w,w2…wk, где:

а) если X, — терминал, то w, = Хп

* *

б) если X, — переменная, то X, => w,. Так как первый шаг порождения А => w

действительно не является частью порождения X/ => w„ нам известно, что это порождение состоит из п или менее шагов. Таким образом, к нему при¬менимо предположение индукции, и можно сделать вывод, что w принадле¬жит языку Х:.

Теперь у нас есть продукция А —> Х/Х2. ■ .Хк, и нам известно, что w, или равно Х„ или принадлежит языку Хг На следующем шаге процедуры рекурсивного вывода мы обна¬ружим, что w/w2…wk принадлежит языку/!. Так как w/w2…wk = w, выводимость того, что w е ЦА), доказана. □

5.2.7. Упражнения к разделу 5.2

5.2.1. Приведите деревья разбора для грамматики и каждой из цепочек в упражнении 5.1.2.

5.2.2. Пусть G — КС-грамматика без продукций сев правой части. Доказать, что если w е L(G), длина w равна п, и w порождается за т шагов, то для w существует де¬рево разбора с п + т узлами.

5.2.3. Пусть действуют все предположения упражнения 5.2.2, но G может иметь не¬сколько продукций с е справа. Доказать, что дерево разбора для w может иметь до п + 2т — 1 узлов, но не более.

5.2.4. В разделе 5.2.6 мы заметили, что если Х,Х2. . -Хк => а, то все позиции в а, проис¬ходящие от расширения Xt, находятся слева от всех позиций, происходящих от расширения Xj, если / < j. Доказать этот факт. Указание. Провести индукцию по числу шагов в порождении.

5.3. Приложения контекстно-свободных грамматик

Контекстно-свободные грамматики были придуманы Н. Хомским (N. Chomsky) как способ описания естественных языков, но их оказалось недостаточно. Однако по мере того, как множились примеры использования рекурсивно определяемых понятий, воз¬растала и потребность в КС-грамматиках как в способе описания примеров таких поня¬тий. Мы рассмотрим вкратце два применения КС-грамматик, одно старое и одно новое.

Грамматики используются для описания языков программирования. Более важно здесь то, что существует механический способ превращения описания языка, вроде КС-грамматики, в синтаксический анализатор — часть компилятора, которая изуча¬ет структуру исходной программы и представляет ее с помощью дерева разбора. Это приложение является одним из самых ранних использований КС-грамматик; в дей¬ствительности, это один из первых путей, по которым теоретические идеи компью¬терной науки пришли в практику.

2, Развитие XML (Extensible Markup Language) призвано облегчить электронную ком¬мерцию тем, что ее участникам доступны соглашения о форматах ордеров, описаний товаров, и многих других видов документов. Существенной частью XML является определение типа документа (DTD — Document Type Definition), представляющее собой КС-грамматику, которая описывает допустимые дескрипторы (tags) и способы их вложения друг в друга. Дескрипторы являются привычными ключевыми словами в угловых скобках, которые читателю, возможно, известны по языку HTML, напри¬мер, <ЕМ> и </ЕМ> для указания текста, который нужно выделить. Однако деск¬рипторы XML связаны не с форматированием текста, а с тем, что он означает. На¬пример, можно было бы заключить в скобки <PHONE> и </PHONE> последователь¬ности символов, интерпретируемые как телефонные номера.

5.3.1. Синтаксические анализаторы

Многие объекты языка программирования имеют структуру, которая может быть опи¬сана с помощью регулярных выражений. Например, мы обсуждали в примере 3.9, как идентификаторы можно представлять регулярными выражениями. Вместе с тем, существу¬ет также несколько весьма важных объектов в языках программирования, которые нельзя представить с помощью только лишь регулярных выражений. Приведем два примера.

Пример 5.19. Обычные языки программирования используют круглые и/или квад¬ратные скобки во вложенном и сбалансированном виде, т.е. так, что можно некоторой левой скобке поставить в соответствие правую, которая записана непосредственно за ней, удалить их и повторять эти действия вплоть до удаления всех скобок. Например, (())> (XX (00) и е являются сбалансированными скобками, а )( и (() — нет.

Все цепочки сбалансированных скобок (и только они) порождаются грамматикой Gbai = ({В}, {(> Ж Л £)> где Р состоит из продукций В -> ВВ\ (В) | е.

Первая продукция, В —> ВВ, гласит, что конкатенация двух цепочек сбалансированных ско¬бок сбалансирована. Это утверждение очевидно, поскольку можно сопоставить скобки в двух цепочках независимо друг от друга. Вторая продукция, В -н> (В), говорит, что если по¬местить пару скобок вокруг сбалансированной цепочки, то новая цепочка также будет сба¬лансированной. Это утверждение тоже очевидно, так как если скобки внутренней цепочки соответствуют друг другу, их можно удалить, и новые скобки становятся соседними. Тре¬тья продукция, В —> 8, является базисной, гласящей, что пустая цепочка сбалансирована.

Приведенные выше неформальные доводы должны убедить нас, что G/,ai порождает только цепочки сбалансированных скобок. Нам еще нужно доказать обратное: что каж¬дая цепочка сбалансированных скобок порождается этой грамматикой. Однако доказа¬тельство индукцией по длине сбалансированной цепочки весьма просто и оставляется в качестве упражнения.

Мы отмечали, что множество цепочек сбалансированных скобок не является регуляр¬ным языком, и теперь докажем это. Если бы был регулярным, то для него по лемме о накачке для регулярных языков существовала бы константа п. Рассмотрим сбалансиро¬ванную цепочку w = («)», т.е. п левых скобок, за которыми следуют п правых. Если разбить w = xyz в соответствии с леммой, то у состоит только из левых скобок, и цепочка xz содер¬жит больше правых скобок, чем левых. Эта цепочка несбалансированна, т.е. получено про¬тиворечие с предположением, что язык сбалансированных скобок регулярен. □

Языки программирования содержат, конечно же, не только скобки, но скобки состав¬ляют существенную часть арифметических и условных выражений. Грамматика, изобра¬женная на рис. 5.2, более типична для структуры арифметических выражений, хотя там использованы всего два оператора, сложения и умножения, и включена детальная струк¬тура идентификаторов, которая, вероятней всего, обрабатывалась бы лексическим анали¬затором компилятора, как мы упоминали в разделе 3.3.2. Однако язык, представленный на рис. 5.2, также нерегулярен. Например, в соответствии с этой грамматикой, (па)п явля¬ется правильным выражением. Мы можем использовать лемму о накачке для того, чтобы показать, что если бы язык был регулярным, то цепочка с некоторыми удаленными ле¬выми скобками, символом а и всеми нетронутыми правыми скобками также была бы правильным выражением, что неверно.

Многие объекты типичного языка программирования ведут себя подобно сбалансирован¬ным скобкам. Обычно это сами скобки в выражениях всех типов, а также начала и окончания блоков кода, например, слова begin и end в языке Pascal, или фигурные скобки { и } в С. Таким образом, любое появление фигурных скобок в С-программе должно образовывать сба¬лансированную последовательность с { в качестве левой скобки и } — правой.

Есть еще один способ балансирования «скобок», отличающийся тем, что левые скоб¬ки могут быть несбалансированны, т.е. не иметь соответствующих правых. Примером является обработка if и else в С. Произвольная if-часть может быть как сбалансиро¬вана, так и не сбалансирована некоторой else-частью. Грамматика, порождающая воз¬можные последовательности слов if и else, представленных /’ и е соответственно, име¬ет следующие продукции.

S->e\SS\iS\iSeS

Например, ieie, iie и iei являются возможными последовательностями слов if и else, и каждая из этих цепочек порождается данной грамматикой. Примерами непра¬вильных последовательностей, не порождаемых грамматикой, являются е/ и /ее/7.

Простая проверка (доказательство ее корректности оставляется в качестве упражнения) того, что последовательность символов / не порождается грамматикой, состоит в рассмот¬рении каждого е по очереди слева направо. Найдем первое /’ слева от рассматриваемого е. Если его нет, цепочка не проходит проверку и не принадлежит языку. Если такое /’ есть, вычеркнем его и рассматриваемое е. Затем, если больше нет символов е, цепочка проходит проверку и принадлежит языку. Если символы е еще есть, то проверка продолжается.

Пример 5.20. Рассмотрим цепочку /ее. Первое е соответствует / слева от него. Оба удаляются. Оставшееся е не имеет / слева, и проверка не пройдена; слово /ее не принад¬лежит языку. Отметим, что это заключение правильно, поскольку в С-программе слов else не может быть больше, чем if.

В качестве еще одного примера рассмотрим iieie. Соответствие первого е и / слева от него оставляет цепочку iie. Соответствие оставшегося е и /’ слева оставляет /’. Символов е больше нет, и проверка пройдена. Это заключение также очевидно, поскольку последо¬вательность iieie соответствует С-программе, структура которой подобна приведенной на рис. 5.10. В действительности, алгоритм проверки соответствия (и компилятор С) гово¬рит нам также, какое именно if совпадает с каждым данным else. Это знание сущест¬венно, если компилятор должен создавать логику потока управления, подразумеваемую программистом. □

if (Условие) {

if (Условие) Инструкция; else Инструкция;

}

Рис. 5.10. Структура if-else; два слова else соответствуют предыдущим if, а первое if несбалансированно

5.3.2. Генератор синтаксических анализаторов YACC

Генерация синтаксического анализатора (функция, создающая деревья разбора по ис¬ходным программам) воплощена в программе YACC, реализованной во всех системах UNIX. На вход YACC подается КС-грамматика, запись которой отличается от исполь¬зуемой здесь только некоторыми деталями. С каждой продукцией связывается действие (action), представляющее собой фрагмент С-кода, который выполняется всякий раз, ко¬гда создается узел дерева разбора, соответствующий (вместе со своими сыновьями) этой продукции. Обычно действием является код для построения этого узла, хотя в некоторых приложениях YACC дерево разбора не создается, и действие задает что-то другое, на¬пример, выдачу порции объектного кода.

Пример 5.21. На рис. 5.11 показан пример КС-грамматики в нотации YACC. Грамматика совпадает с приведенной на рис. 5.2. Мы опустили действия, показав лишь их (требуемые но¬тацией) фигурные скобки и расположение во входной последовательности YACC.

Exp : Id { . ..}

| Exp ‘ + ‘ Exp {.• . }

| Exp ‘*’ Exp {••.}

| ‘ (‘ Exp ‘) ‘ { . — . } t

Id : ‘a’ {…}

‘b’ {…}

| Id ‘a’ { . . . }

| Id ‘b’ {…}

| Id ‘0’ {•■.}

| Id ‘1’ {…}

Рис. 5.11. Пример грамматики в нотации YACC

Отметим следующие соответствия между нотацией YACC и нашими грамматиками.

Двоеточие используется в качестве символа продукции —
Все продукции с данной головой группируются вместе, и их тела разделены вер¬тикальной чертой.
Список тел для данной головы заканчивается точкой с запятой. Завершающий символ не используется.
Терминалы записываются в апострофах. Некоторые буквы могут появляться в одиночных апострофах. Хотя у нас они не показаны, YACC позволяет пользова¬телю определять также и символические терминалы. Появление таких термина¬лов в исходной программе обнаруживает лексический анализатор и сигнализиру¬ет об этом синтаксическому анализатору через свое возвращаемое значение.
Цепочки символов и цифр, не взятые в апострофы, являются именами пере¬менных. Мы воспользовались этой возможностью для того, чтобы дать нашим переменным более выразительные имена— Ехр и Id, хотя можно было ис¬пользовать Ew. I.

□

5.3.3. Языки описания документов

Рассмотрим семейство «языков», которые называются языками описания документов (markup languages). «Цепочками» этих языков являются документы с определенными метками, которые называются дескрипторами (tags). Дескрипторы говорят о семантике различных цепочек внутри документа.

Читатель, возможно, знаком с таким языком описания документов, как HTML (Hypertext Markup Language). Этот язык имеет две основные функции: создание связей между документами и описание формата («вида») документа. Мы дадим лишь упрощен¬ный взгляд на структуру HTML, но следующие примеры должны показать его структуру и способ использования КС-грамматики как для описания правильных HTML- документов, так и для управления обработкой документа, т.е. его отображением на мо¬ниторе или принтере.

Пример 5.22. На рис. 5.12, а показан текст, содержащий список пунктов, а на рис. 5.12, б— его выражение в HTML. На рис. 5.12, б, показано что HTML состоит из обычного текста, перемежаемого дескрипторами. Соответствующие друг другу, т.е. пар¬ные дескрипторы имеют вид <х> и </х> для некоторой цепочки х. Например, мы видим парные дескрипторы <ЕМ> и </ЕМ>, которые сигнализируют, что текст между ними должен быть выделен, т.е. напечатан курсивом или другим подходящим шрифтом. Мы

видим также парные дескрипторы <0L> и </OL>, указывающие на упорядоченный спи¬сок, т.е. на нумерацию элементов списка. Вещи, которые я ненавижу.

Заплесневелый хлеб.
Людей, которые ведут машину по узкой дороге слишком медленно.

а) видимый текст <Р>Вещи, которые я <ЕМ>ненавижу</ЕМ>: <OL>

<Ы>Заплесневелый хлеб.

<Ы>Людей, которые ведут машину по узкой дороге слишком медленно. </OL>

6) исходный HTML-текст Рис. 5.12. HTML-документ и его видимая версия

Мы видим также два примера непарных дескрипторов: <Р> и <LI>, которые вводят абзацы и элементы списка, соответственно. HTML допускает, а в действительности по¬ощряет, чтобы эти дескрипторы сопровождались парными им </Р> и </LI> на концах абзацев и списков, однако не требует этого. Поэтому эти парные дескрипторы не рас¬сматриваются, что обеспечивает некоторую сложность нашей HTML-грамматике, разви¬ваемой далее. □

Существует много классов цепочек, связанных с HTML-документом. Мы не будем стремиться перечислить их все, а представим только существенные для понимания тек¬стов, подобных приведенному в примере 5.22. Для каждого класса мы введем перемен¬ную с содержательным именем.

Text (текст) — это произвольная цепочка символов, которая может быть проинтер¬претирована буквально, т.е. не имеющая дескрипторов. Примером элемента-текста служит «Заплесневелый хлеб» (см. рис. 5.12).
Char (символ) — цепочка, состоящая из одиночного символа, допустимого в HTML- тексте. Заметим, что пробелы рассматриваются как символы.
Doc (документ) представляет документы, которые являются последовательностями «элементов». Мы определим элементы следующими, и это определение будет вза¬имно рекурсивным с определением класса Doc.
Element (элемент) — это или цепочка типа Text, или пара соответствующих друг другу дескрипторов и документ между ними, или непарный дескриптор, за которым следует документ.
Listltem (элемент списка) есть дескриптор <LI> со следующим за ним документом, который представляет собой одиночный элемент списка.
List (список) есть последовательность из нуля или нескольких элементов списка.
Char —> a\A
Text —> e \ Char Text
Doc —> £ | Element Doc
Element —> Text I .

<ЕМ> Doc </ЕМ> | <Р> Doc | <OL> List </OL> |

Listltem <LI> Doc
List —> e | Listltem List Рис. 5.13. Часть грамматики HTML

На рис. 5.13 представлена КС-грамматика, которая описывает часть структуры языка HTML, рассмотренную нами в примерах. В строке 1 подразумевается, что символами могут быть «а», «А» или многие другие символы из набора HTML. Строка 2 с использо¬ванием двух продукций гласит, что Text может быть либо пустой цепочкой, либо любым допустимым символом с текстом, следующим за ним. Иными словами, Text есть после¬довательность символов, возможно, пустая. Заметим, что символы < и > не являются до¬пустимыми, хотя их можно представить последовательностями < и > соответст¬венно. Таким образом, мы не сможем случайно вставить дескриптор в Text.

Строка 3 гласит, что документ является последовательностью из нуля или нескольких «элементов». Элемент, в свою очередь, согласно строке 4 есть либо текст, либо выделен¬ный документ, либо начало абзаца с документом, либо список. Мы также предполагаем, что существуют и другие продукции для элементов, соответствующие другим видам де¬скрипторов HTML. Далее, в строке 5 мы находим, что элемент списка представляет со¬бой дескриптор <LI>, за которым следует произвольный документ, а строка 6 гласит, что список есть последовательность из нуля или нескольких элементов списка.

Для некоторых объектов HTML мощность КС-грамматик не нужна; достаточно регу¬лярных выражений. Например, строки 1 и 2 (см. рис. 5.13) просто говорят, что Text пред¬ставляет тот же язык, что и регулярное выражение (а + А + …)*. Однако для некоторых объектов мощность КС-грамматик необходима. Например, каждая пара соответствую¬щих друг другу дескрипторов, вроде <ЕМ> и </ЕМ>, подобна сбалансированным скоб¬кам, которые, как мы уже знаем, нерегулярны.

5.3.4. XML и определения типа документа

Тот факт, что HTML описывается грамматикой, сам по себе не является значитель¬ным. Практически все языки программирования можно описать соответствующими им КС-грамматиками, поэтому более удивительным было бы, если бы мы не смогли описать

HTML. Однако если мы обратимся к другому важному языку описания документов, XML (extensible Markup Language), то обнаружим, что КС-грамматики играют более су¬щественную роль как часть процесса использования этого языка.

Цель XML состоит не в описании форматирования документа; это работа для HTML. Вместо этого XML стремится описать «семантику» текста. Например, текст наподобие «Кленовая ул., 12» выглядит как адрес, но является ли им? В XML дескрипторы окружа¬ли бы фразу, представляющую адрес, например: <ADDR>KjieHOBafl ул., 12</ADDR>

Однако сразу не очевидно, что <ADDR> означает адрес дома. Например, если бы до¬кумент говорил о распределении памяти, мы могли бы предполагать, что дескриптор <ADDR> ссылается на адрес в памяти. Ожидается, что стандарты описания различных типов дескрипторов и структур, которые могут находиться между парами таких дескрип¬торов, будут развиваться в различных сферах деятельности в виде определений типа до¬кумента (DTD — Document-Type Definition).

DTD, по существу, является КС-грамматикой с собственной нотацией для описания переменных и продукций. Приведем простое DTD и представим некоторые средства, ис¬пользуемые в языке описания DTD. Язык DTD сам по себе имеет КС-грамматику, но не она интересует нас. Мы хотим увидеть, как КС-грамматики выражаются в этом языке.

DTD имеет следующий вид. <!DOCTYPE имя-DTD [

список определений элементов

Определение элемента, в свою очередь, имеет вид

<! ELEMENT имя-элемента (описание элемента)>

Описания элементов являются, по существу, регулярными выражениями. Их базис обра¬зуется следующими выражениями.

Имена других элементов, отражающие тот факт, что элементы одного типа могут появляться внутри элементов другого типа, как в HTML мы могли бы найти выде¬ленный текст в списке.
Специальное выражение \#PCDATA, обозначающее любой текст, который не включает дескрипторы XML. Это выражение играет роль переменной Text в при¬мере 5.22.

Допустимы следующие знаки операций.

|, обозначающий объединение, как в записи регулярных выражений, обсуждавшихся в разделе 3.3.1.
Запятая для обозначения конкатенации.

Три варианта знаков операции замыкания, как в разделе 3.3.1. Знак * означает «нуль или несколько появлений», + — «не менее одного появления», ? — «нуль или одно появление».

Скобки могут группировать операторы и их аргументы; в их отсутствие действуют обычные приоритеты регулярных операций.

Пример 5.23. Представим себе, что продавцы компьютеров собрались, чтобы создать общедоступный стандарт DTD для описания разнообразных ПК (персональных компью¬теров), которыми они торгуют. Каждое описание ПК будет иметь номер модели и спе¬цификацию ее свойств, например, объем памяти, количество и размер дисков и т.д. На рис. 5.14 представлено гипотетическое, весьма упрощенное DTD для ПК.

<!DOCTYPE PcSpec [

< ELEMENT PCS (PC*)>

< ELEMENT PC (MODEL, PRICE, PROCESSOR, RAM,

< ELEMENT MODEL (\#PCDATA)>

< ELEMENT PRICE (\#PCDATA)>

< ELEMENT PROCESSOR (MANF, MODEL , SPEED)>

< ELEMENT MANF (\#PCDATA)>

< ELEMENT MODEL (\#PCDATA)>

< ELEMENT SPEED (\#PCDATA)> ‘

< ELEMENT RAM (\#PCDATA)>

< ELEMENT DISK (HARDDISK | CD | DVD) >

< ELEMENT HARDDISK (MANF, MODEL, SIZE)>

< ELEMENT SIZE (\#PCDATA)>

< ELEMENT CD (SPEED)>

< ELEMENT DVD (SPEED)>

Рис. 5.14. DTD для персональных компьютеров

Именем DTD является PcSpec. PCS (список спецификаций) является первым эле¬ментом, аналогичным стартовому символу КС-грамматики. Его определение, PC*, гла¬сит, что PCS — это нуль или несколько элементов PC (ПК).

Далее мы видим определение элемента PC. Оно состоит из конкатенации пяти ком¬понентов. Первые четыре — это другие элементы, соответствующие модели (MODEL), цене (PRICE), типу процессора (PROCESSOR) и памяти (RAM). Каждый из них должен появляться один раз в указанном порядке, поскольку запятая обозначает конкатенацию. Последний компонент, DISK+, говорит, что у ПК будет один или несколько дисководов.

Многие компоненты представляют собой просто текст; к этому типу относятся MODEL, PRICE и’RAM. Однако PROCESSOR имеет структуру. Из его определения видно, что он состоит из названия производителя (manufacturer, MANF), модели и скорости (SPEED), в указанном порядке. Каждый из этих элементов является простым текстом.

Элемент DISK наиболее сложен. Во-первых, диск— это либо жесткий диск (HARDDISK), либо CD, либо DVD, что указано в правиле для элемента DISK операциями «логического или». Жесткие диски, в свою очередь, имеют структуру, в которой опреде¬ляются производитель (MANF), модель (MODEL) и размер (SIZE), тогда как CD и DVD представлены только их скоростью.

На рис. 5.15 показан пример XML-документа, соответствующего определению на рис. 5.14. Заметим, что каждый элемент представлен в документе дескриптором с именем элемента и парным дескриптором в конце с дополнительной чертой «/», как и в HTML. Та¬ким образом, на внешнем уровне (см. рис. 5.15) виден дескриптор <PCS>. . .</PCS>. Между этими дескрипторами появляется список элементов, по одному на каждый прода¬ваемый ПК; только один из этих списков показан полностью.

В пределах представленного входа <РС> мы видим, что модель имеет номер 4560, цена ее $2295, и она имеет процессор Intel Pentium 800MHz. Она также имеет 256Mb па¬мяти, жесткий диск 30.5Gb Maxtor Diamond и читающее устройство 32х CD-ROM. Важ¬но не то, что мы можем распознать все эти сведения, а то, чтобы читать и правильно ин¬терпретировать числа и имена (см. рис. 5.15) этого документа могла программа под управлением DTD (см. рис. 5.14), которое должно быть ею прочитано вначале. □ <PCS> <РС>

<MANF>Intel</MANF> <MODEL>Pentium</MODEL> <SPEED>8 00mhZ</SPEED> </PROCESSOR> <RAM>256</RAM> <DISK><HARDDISK>

<MANF>Maxtor</MANF> <MODEL>Diamond</MODEL> <SIZE>30.5Gb</SIZE> </HARDDISKX/DISK> <DISK><CD>

</ PC-> </PCS>

Рис. 5.15. Часть документа, удовлетворяющая структуре DTD (см. рис. 5.14)

Возможно, читатель заметил, что правила для элементов в DTD (см. рис. 5.14) не полностью совпадают с продукциями в КС-грамматиках. Многие правила имеют кор¬ректный вид, например, правило

<!ELEMENT PROCESSOR (MANF, MODEL, SPEED)> аналогично продукции

Processor —> Manf Model Speed. Однако в правиле

<!ELEMENT DISK (HARDDISK | CD | DVD)>

определение для DISK не похоже на тело продукции. Расширение в этом случае является простым: это правило можно интерпретировать как три продукции, у которых верти¬кальная черта играет ту же роль, что и в продукциях обычного вида. Таким образом, это правило эквивалентно следующим трем продукциям.

Disk Harddisk \ Cd | Dvd Труднее всего следующее правило. <! ELEMENT PC (MODEL, PRICE, PROCESSOR, RAM, DISK+)> Здесь «тело» содержит оператор замыкания. Решение состоит в замене DISK+ новой пере¬менной, скажем, Disks, которая порождает с помощью пары продукций один или несколько экземпляров переменной Disk. Итак, мы получаем следующие эквивалентные продукции.

Рс —> Model Price Processor Ram Disks Disks -» Disk \ Disk Disks Существует общая техника преобразования КС-грамматики с регулярными выраже¬ниями в качестве тела продукций в обычные КС-грамматики. Идею этого преобразова¬ния опишем неформально; возможно, читатель захочет уточнить как смысл КС- грамматик с регулярными выражениями, так и доказательство того, что такое расшире¬ние не приводит к порождению языков, не являющихся КС-языками. Мы покажем, как продукция с регулярным выражением в качестве тела преобразуется в совокупность обычных продукций. Для этого применим индукцию по размеру выражения в теле.

Базис. Если тело представляет собой конкатенацию элементов, то продукция уже имеет допустимый в КС-грамматиках вид, поэтому преобразовывать нечего. Индукция. В зависимости от старшего оператора возможны пять ситуаций.

При конкатенации продукция имеет вид А —> Еи Е2, где Е, и Е2 — выражения, до¬пустимые в языке DTD. Введем две переменные, В и С, не используемые больше ни¬где. Заменим А —> Е,, Е2:

А ВС ■ В->Е, С ->Е2

Первая продукция, А —> ВС, допустима в КС-грамматиках. Две последние могут быть как допустимыми, так и недопустимыми. Однако их тела короче, чем тело исходной продук¬ции, поэтому на основании индукции их можно преобразовать в форму КС-грамматик.

Для оператора объединения продукция имеет вид А —> Е, | Е2. Заменим ее следую¬щей парой продукций.

А->Е,

А-+Е2

Аналогично, эти продукции могут иметь недопустимый вид, но их тела короче, чем тело исходной. Применяем эти же правила рекурсивно и преобразуем их к ви¬ду КС-грамматик.

Продукция имеет вид А —> ()*. Введем новую переменную В, не используемую больше нигде, и заменим продукцию следующими тремя.

А—>ВА А -> £ В->Е,

Для продукции А —> (Е/У вводим новую переменную В, не используемую больше нигде, и заменяем продукцию следующими тремя.

А-^ВА А В В Ei

Продукция имеет вид А —> (Е,)1. Заменим ее:

А -> £ А-+Е,

Пример 5.24. Рассмотрим преобразование DTD-правила

<!ELEMENT PC (MODEL, PRICE, PROCESSOR, RAM, DISK+)>

в обычные для КС-грамматик продукции. Тело этого правила рассмотрим как конкате¬нацию двух выражений, первое из которых есть MODEL, PRICE, PROCESSOR, RAM, а второе— DISK+. Создав для этих подвыражений переменные А и В, соответственно, используем следующие продукции.

Рс —> АВ

А —> Model Price Processor Ram В Disk+

Только последняя не имеет нужного вида. Введем еще одну переменную С и сле¬дующие продукции.

В С В | С С -> Disk

В данном частном случае переменные А и С в действительности не нужны, поскольку выражение, порождаемое из А, есть просто конкатенация переменных, a Disk — одиночная переменная. Вместо приведенных продукций можно было бы использовать следующие.

Рс —> Model Price Processor Ram В В -> Disk В | Disk

□

5.3.5. Упражнения к разделу 5.3

5.3.1. Докажите, что если цепочка скобок сбалансирована (как в примере 5.19), то она порождается грамматикой В —> ВВ | (В) | е. Указание. Проведите индукцию по длине цепочки.

5.3.2. Рассмотрим множество всех цепочек сбалансированных скобок двух типов, круглых и квадратных. Следующий пример показывает их происхождение. Если взять выражения в языке С, которые используют круглые скобки для группиро¬вания и для вызовов функций и квадратные скобки для индексов массивов, и удалить из них все, кроме скобок, то получим цепочки сбалансированных ско¬бок этих двух типов. Например,

f (a[i]* (b[i] [j]+c[g(x) ] ) ,d[i] )

превращается в сбалансированную цепочку ( [ ] ( [ ] [ ] [ () ] ) [ ] ). Построить грамматику для всех сбалансированных цепочек из круглых и квадратных ско¬бок, и только для них.

5.3.3. В разделе 5.3 рассматривалась грамматика S —> е \ SS | iS \ iSeS и утверждалось, что принадлежность цепочки w языку L этой грамматики можно проверить пу¬тем повторения следующих действий, начиная с w.

Если текущая цепочка начинается с е, то проверка не пройдена; w g L.
Если текущая цепочка не содержит е, то проверка пройдена; we L.
В противном случае удалить первое е и / непосредственно слева от него. Повторить эти три шага с полученной цепочкой.

Докажите, что этот процесс правильно распознает цепочки языка L.

5.3.4. Добавьте к грамматике HTML (см. рис. 5.13) следующие формы:

а) (*) элемент списка должен заканчиваться закрывающим дескриптором </LI>;

б) элемент может быть как неупорядоченным, так и упорядоченным списком. Не¬упорядоченные списки заключаются в парные дескрипторы <UL> и </UL>;

в) (!) элемент может быть таблицей, которая заключается в парные дескрипто¬ры <TABLE> и </TABLE>. Между ними находятся одна или несколько це¬почек, каждая из которых заключается в <TR> и </TR>. Первая цепочка яв¬

ляется заголовком с одним или несколькими полями, каждое из которых на¬чинается дескриптором <ТН> (будем предполагать, что эти дескрипторы не закрываются, хотя в действительности они парные). Поля в следующих це¬почках начинаются дескриптором <TD>.

< < < < <

< ! DOCTYPE CourseS^c[

ELEMENT COURSES (COURSE+)>

ELEMENT COURSE (CNAME, PROF, STUDENT*, TA?)> ELEMENT CNAME (\#PCDATA)> ELEMENT STUDENT (\#PCDATA)> ELEMENT ТА (\#PCDATA)>

Рис. 5.16. DTD для курсов 5.3.5. Преобразуйте DTD (рис. 5.16) в КС-грамматику.

5.4. Неоднозначность в грамматиках и языках

Как мы увидели, в приложениях КС-грамматики часто служат основой для обеспече¬ния структуры различного рода файлов. Например, в разделе 5.3 грамматики использо¬вались для придания структуры программам и документам. Там действовало неявное предположение, что грамматика однозначно определяет структуру каждой цепочки сво¬его языка. Однако мы увидим, что не каждая грамматика обеспечивает уникальность структуры.

Иногда, когда грамматика не может обеспечить уникальность структуры, ее можно преобразовать, чтобы структура была единственной для каждой цепочки. К сожалению, это возможно не всегда, т.е. существуют «существенно неоднозначные» языки; каждая грамматика для такого языка налагает несколько структур на некоторые его цепочки.

5.4.1. Неоднозначные грамматики

Вернемся к грамматике выражений (см. рис. 5.2). Эта грамматика дает возможность порождать выражения с любой последовательностью операторов + и *, а продукции £ —> Е + Е \ Е* Е позволяют порождать эти выражения в произвольно выбранном порядке.

Пример 5.25. Рассмотрим выводимую цепочку Е + Е* Е. Она имеет два порожде¬ния из Е:

£=>£ + £=>£ + £*£
£=>£*£=>£ + £*£

Заметим, что в порождении 1 второе Е заменяется на £ * £, тогда как в порождении 2 — первое Е на Е + £. На рис. 5.17 показаны два действительно различных дерева разбора.

» * Е ^ + с.

а) б)

Рис. 5.17. Два дерева разбора с одной и той же кроной

Разница между этими двумя порождениями значительна. Когда рассматривается структура выражений, порождение 1 говорит, что второе и третье выражения перемно¬жаются, и результат складывается с первым. Вместе с тем, порождение 2 задает сложе¬ние первых двух выражений и умножение результата на третье. Более конкретно, первое порождение задает, что 1+2*3 группируется как 1 + (2 * 3) = 7, а второе — что группи¬рование имеет вид (I + 2) * 3 = 9. Очевидно, что первое из них (но не второе) соответст¬вует нашему понятию о правильном группировании арифметических выражений.

Поскольку грамматика, представленная на рис. 5.2, дает две различные структуры любой цепочке терминалов, порождаемой заменой трех выражений в Е + Е* Е иденти¬фикаторами, для обеспечения уникальности структуры она не подходит. В частности, хо¬тя она может давать цепочкам как арифметическим выражениям правильное группиро¬вание, она также дает им и неправильное. Для того чтобы использовать грамматику вы¬ражений в компиляторе, мы должны изменить ее, обеспечив только правильное группирование. □

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

Пример 5.26. Используя ту же грамматику выражений, мы находим, что цепочка а+Ь имеет много разных порождений. Вот два из них.

E=>E+E=*I+E=>a + E=>a + I=$a + b
E=>E+E=>E + I=>I+I=>I+b=*a + b

Заметим, что настоящей разницы между структурами, заданными этими двумя порожде¬ниями, нет. Каждая из них говорит, что а и b— идентификаторы, и что их значения нужно сложить. В действительности, оба эти порождения приводят к одному и тому же дереву разбора, если применяются конструкции теорем 5.18 и 5.12. □

Два примера, приведенные выше, показывают, что неоднозначность происходит не от множественности порождений, а от существования двух и более деревьев разбора. Итак, мы говорим, что КС-грамматика G = (V,T, P,S) является неоднозначной, если найдется хотя бы одна цепочка w в Т’, для которой существуют два разных дерева разбора, каждое

с корнем, отмеченным 5, и кроной и>. Если же каждая цепочка имеет не более одного де¬рева разбора в грамматике, то грамматика однозначна.

Е + Е

I Е

а I

Пример 5.25 почти показал неоднозначность грамматики, изображенной на рис. 5.2. Нам нужно лишь доказать, что деревья разбора на рис. 5.17 можно пополнить так, чтобы они имели терминальные кроны. На рис. 5.18 приведен пример такого пополнения.

Е * Е

Е + Е 1

I а

а а а а

а) б)

Рис. 5.18. Деревья с кроной а + а * а, показывающие неоднозначность грамматики выражений

5.4.2. Исключение неоднозначности из грамматик

В идеальном мире мы смогли бы дать алгоритм исключения неоднозначности из КС-грамматик, почти как в разделе 4.4, где был приведен алгоритм удаления несущест¬венных состояний конечного автомата. Однако, как будет показано в разделе 9.5.2, не существует даже алгоритма, способного различить, является ли КС-грамматика неодно¬значной. Более того, в разделе 5.4.4 мы увидим, что существуют КС-языки, имеющие только неоднозначные КС-грамматики; исключение неоднозначности для них вообще невозможно.

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

Сначала заметим, что есть следующие две причины неоднозначности в грамматике, изображенной на рис. 5.2.

Не учитываются приоритеты операторов. В то время как на рис. 5.17, а оператор * правильно группируется перед оператором +, на рис. 5.17, б показано также допусти¬мое дерево разбора, группирующее + перед *. Необходимо обеспечить, чтобьг в одно¬значной грамматике была допустимой только структура, показанная на рис. 5.17, а.

Последовательность одинаковых операторов может группироваться как слева, так и справа. Например, если бы операторы * (см. рис. 5.17) были заменены операторами +, то мы увидели бы два разных дерева разбора для цепочки Е + Е + Е. Поскольку оба оператора ассоциативны, не имеет значения, группируем ли мы слева или спра¬ва, но для исключения неоднозначности нам нужно выбрать что-то одно. Обычный подход состоит в группировании слева, поэтому только структура, изображенная на рис. 5.17, б, представляет правильное группирование двух операторов +.

Разрешение неоднозначности в YACC

Если используемая грамматика выражений неоднозначна, нас может удивить реали¬стичность YACC-программы, приведенной на рис. 5.11. Действительно, данная грам¬матика неоднозначна, однако генератор синтаксических анализаторов YACC обеспе¬чивает пользователя простыми механизмами разрешения большинства общих причин неоднозначности. Для грамматики выражений достаточно потребовать следующее.

Приоритет у оператора * выше, чем у +, т.е. операторы * должны группироваться раньше, чем соседние с обеих сторон операторы +. Это правило говорит нам ис¬пользовать порождение 1 из примера 5.25, а не порождение 2.
И *, и + левоассоциативны, т.е. последовательности выражений, связанных только знаком *, группируются слева, и это же относится к последовательно¬стям, связанным +.

YACC позволяет нам устанавливать приоритеты операторов путем перечисления их в порядке возрастания приоритета. Технически приоритет оператора применяется к использованию любой продукции, в теле которой этот оператор является крайним справа терминалом. Мы можем также объявить операторы как лево- или правоас- социативные с помощью ключевых слов %left и % right. Например, для того, чтобы объявить оба оператора * и + левоассоциативными и с более высоким при¬оритетом у *, в начале грамматики (см. рис. 5.11) можно поместить следующие ин¬струкции.

%left ‘+’ %left ‘*’

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

Сомножитель> или фактор (factor), — это выражение, которое не может быть раз¬делено на части никаким примыкающим оператором, ни *, ни +. Сомножителями в нашем языке выражений являются только следующие выражения:

а) идентификаторы. Буквы идентификатора невозможно разделить путем при¬соединения оператора;

б) выражения в скобках, независимо от того, что находится между ними. Имен¬но для предохранения операндов в скобках от действия внешних операторов и предназначены скобки.

Терм (term), или слагаемое, — это выражение, которое не может быть разорвано оператором +. В нашем примере, где операторами являются только + и *, терм пред¬ставляет собой произведение одного или несколько сомножителей. Например, терм а* Ь может быть «разорван», если мы используем левую ассоциативность * и помес¬тим а\* слева, поскольку а\ * а * b группируется слева как (al * a)* b, разрывая а* Ь. Однако помещение аддитивного выражения слева, типа а 1+, или справа, типа +а\, не может разорвать а* Ь. Правильным группированием выражения а\ + a* b является а\ + (а* Ь), а выражения a* b + а 1 — (а* Ь) + а\.
Выражение (expression) будет обозначать любое возможное выражение, включая те, которые могут быть разорваны примыкающими + и *. Таким образом, выражение для нашего примера представляет собой сумму одного или нескольких термов.

I a\b\Ia\Ib\IQ\l\

F 1\(Е)

Т F\T*F

Е Т\Е+Т

Рис. 5.19. Однозначная грамматика выражений

Пример 5.27. На рис. 5.19 приведена однозначная грамматика, порождающая тот же язык, что и грамматика, изображенная на рис. 5.2. Посмотрим на F, Т и Е как на пере¬менные, языками которых являются сомножители, слагаемые и выражения в описанном выше смысле. Например, эта грамматика допускает только одно дерево разбора для це¬почки а + а* а; оно показано на рис. 5.20.

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

Цепочка, порождаемая из Т, т.е. терм, должна быть последовательностью из од¬ного или нескольких сомножителей, связанных знаками *. Сомножитель, по оп¬ределению и как это следует из продукций для F (см. рис. 5.19), есть либо оди¬ночный идентификатор, либо выражение в скобках.
Вследствие вида продукций для Т единственным деревом разбора для последова¬тельности сомножителей будет такое, которое разрывает* f2 * …*/„ где п > 1, на терм fi * f2 * ■■■*/„-! и сомножитель f„. Причина в том, что F не может поро¬

дить выражение вида fn.i *f„ без введения скобок вокруг него. Таким образом, при использовании продукции Т —> Т * F из F невозможно породить ничего, кро¬ме последнего из сомножителей, т.е. дерево разбора для терма может выглядеть только так, как на рис. 5.21.

Е +

г г

F F

I I

Аналогично, выражение есть последовательность термов, связанных знаками +. Когда используется продукция Е—>Е+Т для порождения // + t2 + … +1„, из Т должно порождаться только t„, а из £ в теле — // + t2 + … + !„./■ Причина этого опять-таки в том, что из Т невозможно породить сумму двух и более термов без

заключения их в скобки.

/\\

Т * F

/\\

Т * F

/\\

j * F

Рис. 5.20. Единственное дерево разбора Рис. 5.21. Форма всех деревьев разбора для цепочки а + а * а для термов

5.4.3. Левые порождения как способ выражения неоднозначности

Хотя порождения не обязательно уникальны, даже если грамматика однозначна, ока- зь вается, что в однозначной грамматике и левые, и правые порождения уникальны. Рас¬смотрим только левые.

Пример 5.28. Заметим, что оба дерева разбора, представленные на рис. 5.18, имеют крону Е + Е * Е. По ним получаются следующие соответствующие им левые порождения.

а) Е => Е + Е => I + Е => а + Е => а + Е* Е => а + I* Е =>

lm lm lm lm lm 1т

а + а * Е => а + а * I => а + а * а

1т !т

б) Е => Е* Е => Е + Е* Е => 1+ Е* Е => а + Е* Е =>

lm lm lm /т 1т

а + I * Е => а + а * Е => а + а * / => а + а* а

lm 1т 1т

Заметим, что эти левые порождения различаются. Данный пример не доказывает теоре¬му, но демонстрирует, как различия в деревьях разбора влияют на выбор шагов в левом порождении. □

Теорема 5.29. Для каждой грамматики G = (V, Т, Р, S) и w из Т’ цепочка w имеет два разных дерева разбора тогда и только тогда, когда w имеет два разных левых порожде¬ния из S.

Доказательство. (Необходимость) Внимательно рассмотрим построение левого по¬рождения по дереву разбора в доказательстве теоремы 5.14. В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продук¬ции, левые порождения, которые строятся, также используют разные продукции и, сле¬довательно, являются различными.

(Достаточность) Хотя мы предварительно не описали непосредственное построение дерева разбора по левому порождению, идея его проста. Начнем построение дерева с корня, отмеченного стартовым символом. Рассмотрим порождение пошагово. На каждом шаге заменяется переменная, и эта переменная будет соответствовать построенному крайнему слева узлу дерева, не имеющему сыновей, но отмеченному этой переменной. По продукции, использованной на этом шаге левого порождения, определим, какие сы¬новья должны быть у этого узла. Если существуют два разных порождения, то на первом шаге, где они различаются, построенные узлы получат разные списки сыновей, что га¬рантирует различие деревьев разбора. □

5.4.4. Существенная неоднозначность

Контекстно-свободный язык L называется существенно неоднозначным, если все его грамматики неоднозначны. Если хотя бы одна грамматика языка L однозначна, то L яв¬ляется однозначным языком. Мы видели, например, что язык выражений, порождаемый грамматикой, приведенной на рис. 5.2, в действительности однозначен. Хотя данная грамматика и неоднозначна, этот же язык задается еще одной грамматикой, которая од¬нозначна — она изображена на рис. 5.19.

Мы не будем доказывать, что существуют неоднозначные языки. Вместо этого рас¬смотрим пример языка, неоднозначность которого можно доказать, и объясним нефор¬мально, почему любая грамматика для этого языка должна быть неоднозначной:

L = {a»bncmdm | п> 1, т > 1} U {апЬтстсГ | п> 1, т > 1}.

Из определения видно, что L состоит из цепочек вида a+b+c+d+, в которых поровну сим¬волов а и Ь, а также cud, либо поровну символов а и d, а также Ьис.

L является КС-языком. Очевидная грамматика для него показана на рис. 5.22. Для по¬рождения двух видов цепочек в ней используются два разных множества продукций.

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

S => АВ => аАЬВ => aabbB => aabbccBd => aabbccdd

Im Im Im Im Im

S => С => aCd => aaDdd => aabDcdd => aabbccdd

lm Im lm lm Im

Соответствующие деревья разбора показаны на рис. 5.23.

S -» АВ | С

А -» аАЬ | ab

В cBd|cd

С aCd | aDd

D -» bDc | be

Рис. 5.22. Грамматика для существенно неоднозначного языка

а) б)

Рис. 5.23. Два дерева разбора для aabbccdd

Доказательство того, что все грамматики для языка L неоднозначны, весьма непросто, однако сущность его такова. Нужно обосновать, что все цепочки (за исключением конечно¬го их числа), у которых поровну всех символов, должны порождаться двумя различными путями. Первый путь — порождение их как цепочек, у которых поровну символов а и b, а также с и d, второй путь — как цепочек, у которых поровну символов а и d, как ибис.

Например, единственный способ породить цепочки, у которых поровну а и Ь, состоит в использовании переменной, подобной А в грамматике, изображенной на рис. 5.22. Ко¬нечно же, возможны варианты, но они не меняют картины в целом, как это видно из сле¬дующих примеров.

Некоторые короткие цепочки могут не порождаться после изменения, например, базисной продукции А —» ab на А —» aaabbb.
Мы могли бы организовать продукции так, чтобы переменная А делила свою ра¬боту с другими, например, используя переменные А, и Л2, из которых А/ порож¬дает нечетные количества символов а, а А2— четные: AjaA2b\ ab; А2 aAjb | ab.
Мы могли бы организовать продукции так, чтобы количества символов а и Ь, по¬рождаемые переменной А, были не равны, но отличались на некоторое конечное число. Например, можно начать с продукции S—>AaB и затем использовать А —» аАЬ | а для порождения символов а на один больше, чем Ь.

В любом случае, нам не избежать некоторого способа порождения символов а, при кото¬ром соблюдается их соответствие с символами Ь.

Аналогично можно обосновать, что должна использоваться переменная, подобная В, которая порождает соответствующие друг другу символы с и d. Кроме того, в граммати¬ке должны быть переменные, играющие роль переменных Си Д порождающих соответ¬ственно парные а и d и парные b и с. Приведенные аргументы, если их формализовать, доказывают, что независимо от изменений, которые можно внести в исходную грамма¬тику, она будет порождать хотя бы одну цепочку вида a»bncn<f двумя способами, как и грамматика, изображенная на рис. 5.22.

5.4.5. Упражнения к разделу 5.4

5.4.1. Рассмотрим грамматику S —» aS | aSbS | е. Она неоднозначна. Докажите, что для цепочки aab справедливо следующее:

а) для нее существует два дерева разбора;

б) она имеет два левых порождения;

в) она имеет два правых порождения.

5.4.2. (!) Докажите, что грамматика из упражнения 5.4.1 порождает те, и только те цепочки из символов а и Ь, у которых в любом префиксе символов а не мень¬ше, чем Ь.

5.4.3. (*!) Найдите однозначную грамматику для языка из упражнения 5.4.1.

5.4.4. (!!)В грамматике из упражнения 5.4.1 некоторые цепочки имеют только одно дерево разбора. Постройте эффективную проверку, является ли цепочка одной

из указанных. Проверка типа «проверить все деревья разбора, чтобы увидеть, сколько их у данной цепочки» не является достаточно эффективной.

5.4.5. (!) Воспроизведем грамматику из упражнения 5.1.2:

5 -» А\В А OA | Е В 05 | 16 |£

а) докажите, что данная грамматика неоднозначна;

б) найдите однозначную грамматику для этого же языка и докажите ее одно¬значность.

5.4.6. (*!) Однозначна ли ваша грамматика из упражнения 5.1.5? Если нет, измените ее так, чтобы она стала однозначной.

5.4.7. Следующая грамматика порождает префиксные выражения с операндами х иу и операторами +, — и *:

Е-ч> + ЕЕ\* ЕЕ\-ЕЕ\х\у

а) найдите левое и правое порождения, а также дерево разбора для цепочки

+ *-хуху;

б) (!) докажите, что данная грамматика однозначна.

Резюме

♦ Контекстно-свободные грамматики. КС-грамматика— это способ описания языка с помощью рекурсивных правил, называемых продукциями. КС-грамматика состоит из множества переменных, терминальных символов, стартовой перемен¬ной, а также продукций. Каждая продукция состоит из головной переменной и те¬ла— цепочки переменных и/или терминалов, возможно, пустой.

♦ Порождения и языки. Начиная со стартового символа, мы порождаем терминаль¬ные цепочки, повторяя замены переменных телами продукций с этими перемен¬ными в голове. Язык КС-грамматики— это множество терминальных цепочек, которые можно породить; он называется КС-языком.

♦ Левые и правые порождения. Если мы всегда заменяем крайнюю слева (крайнюю справа) переменную, то такое порождение является левым (правым). Каждая це¬почка в языке КС-грамматики имеет, по крайней мере, одно левое и одно правое порождения.

♦ Выводимые цепочки. Любой шаг порождения дает цепочку переменных и/или терминалов. Она называется выводимой цепочкой. Если порождение является ле¬вым (правым), то цепочка называется левовыводимой (правовыводимой).

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

♦ Эквивалентность деревьев разбора и порождений. Терминальная цепочка при¬надлежит языку грамматики тогда и только тогда, когда она является кроной, по крайней мере, одного дерева разбора. Таким образом, существование левых по¬рождений, правых порождений и деревьев разбора является равносильным усло¬вием того, что все они определяют в точности цепочки языка КС-грамматики.

♦ Неоднозначные грамматики. Для некоторых грамматик можно найти терминаль¬ную цепочку с несколькими деревьями разбора, или (что равносильно) с несколь¬кими левыми или правыми порождениями. Такая грамматика называется неодно¬значной.

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

♦ Синтаксические анализаторы. Контекстно-свободная грамматика является ос¬новным понятием для реализации компиляторов и других процессоров языков программирования. Инструментальные средства, вроде YACC, получают на вход КС-грамматику и порождают синтаксический анализатор — часть компилятора, распознающую структуру компилируемых программ.

♦ Определения типа документа. Развивающийся стандарт XML для распределения информации посредством Web-документов имеет нотацию, называемую DTD, для описания структуры таких документов. Для этого в документ записываются вложен¬ные семантические дескрипторы. DTD является, по существу, КС-грамматикой, язык которой — это класс связанных с этим определением документов.

Литература

Контекстно-свободная грамматика была впервые предложена Хомским как способ описания естественных языков в [4]. Бэкус и Наур вскоре использовали подобную идею для описания машинных языков Фортран [2] и Алгол [7]. В результате КС-грамматики иногда называются «формами Бэкуса-Наура», или БНФ.

Неоднозначность в грамматиках была выделена в качестве проблемы почти одновре¬менно Кантором [3] и Флойдом [5]. Существенная неоднозначность была впервые указа¬на Гроссом [6].

О приложениях КС-грамматик в компиляции рекомендуем прочитать в [1]. DTD опи¬саны в документе о стандартах XML [8].

А. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading MA, 1986. (Ахо А. В., Сети P., Ульман Дж. Компиляторы: принципы, технологии и инструменты. — М.: Издательский дом «Вильяме», 2001.)
J. W. Backus, «The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM conference», Proc. Intl. Conf. on Information Processing (1959), UNESCO, pp. 125-132.
D. C. Cantor, «On the ambiguity problem of Backus systems», J. ACM 9:4 (1962), pp. 477-479.
N. Chomsky, «Three models for the description of language», IRE Trans, on Information Theory 2:3 (1956), pp. 113-124. (Хомский H. Три модели для описания языка. — Ки¬бернетический сборник, вып. 2. — М.: ИЛ, 1961. — С. 237-266.)
R. W.Floyd, «On ambiguity in phrase-structure languages», Comm. ACM 5:10 (1962), pp. 526-534.
M. Gross, «Inherent ambiguity of minimal linear grammars», Information and Control 7:3 (1964), pp. 366-368.
P. Naur et al., «Report on the algorithmic language ALGOL 60», Comm. ACM3:5 (1960), pp. 299-314. См. также Comm. ACM6A (1963), pp. 1-17. (Алгоритмический язык Ал¬гол 60,—M.: Мир, 1965.)
World-Wide-Web Consortium, http://www.w3.org/TR/REC-xml (1998)

В помощь студентам ПМР