Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Вывод цепочки 'aabcbaa' в грамматике
S-+aSa
Gm
S-S-
¦bSb
представляется деревом
aabcbaa
или эквивалентной скобочной записью
[а [а [Ь [с] Ь] а] а],
SSSS
которая могла бы быть порождена непосредственно с помощью слегка видоизмененной грамматики G1m, содержащей два новых терминальных символа '[' и ']', а именно с помощью грамматики 134
Часть II. Некоторые замечательные классы языков
Gm
S S S-
• [aSa]
S
•[bSb]
s
•[с]
Ha этом примере еще нельзя увидеть, какие преимущества дает использование пометок при скобках, поскольку в Gm имеется только одна пометка. По существу мы привели этот пример только для того, чтобы иметь возможность сопоставить его со следующим.
8.2.2. Нормальная грамматика, порождающая Lm
Рассмотрим вывод той же самой цепочки в некоторой нормальной грамматике, также порождающей язык Lm. Пусть дана нормальная грамматика
Va = {S, Т, U}; Vt = {а, Ь, с}; аксиома 5;
Gm
S-T-S-U-S-
Ta ¦aS Ub bS
Вывод цепочки 'aabcbaa' в этой грамматике дает следующее дерево: Гл. VIII. Нераспознаваемые свойства КС-грамматик
135
Скобочная запись, соответствующая этому дереву, такова:
[ И [a[[b[c] }Ь] ]я] ]а].
ST ST SUSSUST STS
Пометки при правых скобках можно и не писать, поскольку они однозначно определяются по соответствующим левым пометкам. При таком упрощении приведенное выражение примет вид
[\а[{а{[Ь{с]]Ь]]а]]а].
ST ST SUS
В некоторых случаях можно даже вводить соглашения, позволяющие вообще опускать правые скобки.
8.2.3. Неоднозначность1)
Будем говорить, что цепочка неоднозначна относительно данной грамматики, если она может быть получена в этой грамматике с помощью по крайней мере двух выводов, изображаемых разными деревьями. Количество разных выводов (точнее, деревьев), возможных в данной грамматике для данной цепочки, характеризует «степень неоднозначности» этой цепочки.
Ясно, что неоднозначность должна определяться относительно одной грамматики, поскольку разные, но эквивалентные грамматики (как, например, Gm и G"m в предыдущем параграфе), порождая один и тот же язык, могут сопоставлять одинаковым цепочкам разные синтаксические структуры.
Пример. Рассмотрим грамматику
S-^-SX S S-+S + S (С) : 5 -> T Т->\Т
Цепочки, порождаемые этой грамматикой, могут интерпретироваться следующим образом. Палочки (|) служат для записи натуральных чисел: |=1, Ц = 2, ||| = 3 ...; знаки X и + имеют обычный арифметический смысл.
') В некоторых оригинальных и переводных работах на русском языке (в частности, в переводе книги Гинзбурга [1966]) вместо неоднозначный, неоднозначность (фр. ambigu, ambiguite, англ. ambiguous, ambiguity) употребляются термины неопределенный, неопределенность. Такое словоупотребление следует признать неудачным: оно расходится с лингвистической терминологией (соответствующее явление в естественных языках принято называть синтаксической неоднозначностью) и в чисто математическом контексте также ведет к известным неудобствам. Пишущий эти строки вынужден отметить, что именно он был инициатором введения этих неудачных терминов. — Прим. ред. 136
Часть II. Некоторые замечательные классы языков
Рассмотрим цепочку ||х||| + |. Ее структуру можно описать либо деревом
которое отвечает интрепретации
Il X (ЦІ + І), что дает число 8,
либо деревом
S
которому соответствует
(11 X 111) +1, т. е. 7.
Подобные неоднозначности могут возникать, в частности, в языках программирования; чтобы избежать их, прибегают к следующим методам:
. Упорядочивают символы операций по старшинству; это по существу означает упорядочение правил грамматики и введение порядка в процесс анализа заданной цепочки. Гл. VIII. Нераспознаваемые свойства КС-грамматик
137
.. Вводят дополнительные терминальные символы (например, скобки в только что разобранном примере). ... Используют бесскобочную запись, например:
(Cp)
S-S-S-T-T-
-XSS - + SS -T IT
Точка в правой части последнего правила вводится в качестве маркера, разделяющего записи чисел; без такого маркера конкатенация цепочек, состоящих из палочек, приводила бы к неоднозначности.
В бесскобочной записи разные интерпретации приведенной выше цепочки выглядят по-разному:
(1р)Х||.+ III.|.
(2р)+Х||.|||.|.
Определения. Грамматика, порождающая язык, содержащий неоднозначные относительно нее цепочки, называется неоднозначной.
Если некоторая цепочка имеет в данной грамматике р разных (т. е. представляемых разными деревьями) выводов, мы говорим, что степень ее неоднозначности равна р.
8.2.4. Нераспознаваемость неоднозначности
Возникает следующий вопрос: существует ли алгоритм, который для любой КС-грамматики определял бы, является ли она неоднозначной?
Покажем, что эта проблема неразрешима уже для случая линейных грамматик с тремя вспомогательными символами.
Рассмотрим п пар цепочек в алфавите {а,Ь}:
(gi, hy).....(gb ht).....(gn, hn).
Рассмотрим также n различных маркеров du d2, ..., dn и две минимальные линейные грамматики с центральным маркером с;
