Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Аналогичным образом в формальных грамматиках необходимо разграничивать терминальный, или основной, словарь (словарь символов собственно яаыка) и вспомогательный словарь, который используется только для формулирования правил.
Структуры фраз. Фраза, как правило, имеет в своем составе одно или несколько (однородных) подлежащих, одно или несколько сказуемых, одно или несколько дополнений, а также определения и обстоятельства.
Фразе
(1) Riquet aboie 'Рике лает' отвечает очень простая схема
(I) существительное (nom) + глагол (verbe).
Подлежащее может иметь при себе различные определители; вместе с ними оно составляет именную группу, являясь ее «ядром», Так, фраза 114
Часть II. Некоторые замечательные классы языков
(2) Le chien famelique aboie 'Голодная собака лает' имеет схему
(II) именная группа (groupe nominal) + глагол.
Посредством аналогичных расширений можно получать фразы
вроде
(3) Le chien famelique aboie plaintivement apres Ia caravane 'Голодная собака жалобно лает на караван'; эта фраза построена по схеме
(III) именная группа + глагольная группа + предлог + именная группа.
Введем следующие обозначения:
Ph — фраза;
Gn- именная группа;
Gv — глагольная группа;
Pr — предлог;
N — существительное;
Adj — прилагательное;
Art — артикль;
Adv — наречие;
V — глагол.
Теперь мы сможем записывать правила следующим способом, который будет пояснен на примерах. Например,
Ph-*'Gn Gv Pr Gn';
это означает: «Чтобы получить фразу, можно, в частности, взять именную группу, поместить справа от нее глагольную группу,.затем предлог и, наконец, еще одну именную группу».
Другие примеры правил:
Gn-*'Art N Adj', Gv-*'V Adv'.
Дерево фразы. Удобный способ представлять синтаксическую структуру фраз состоит в использовании скобок, помеченных символами синтаксических категорий. Так, фраза (3) имеет следующую структуру:
[ [ [ Le] [ chien] [ famelique] ] [ [ aboie] [ plaintivement] ]
Ph Gn Art N Ad! Go V Adv
[ apres] [ [ la] [ caravane] ] ].
Pr Gn Art N
Кроме того, синтаксическая структура фразы может быть изображена посредством дерева с помеченными узлами (пример см. ниже). Эти представления эквивалентны, и переход от одного Гл. VII. Контекстно-свободные языки
115
из них к другому выполняется чисто механически.
Ph
То, что для представления синтаксической структуры фраз выбраны именно деревья, является в некоторых отношениях актом произвола. В самом деле, можно было бы использовать графы более общего вида: например, с циклами. Данный выбор продиктован рядом эмпирических соображений. Деревья — достаточно простой тип графов; и хотя с их помощью невозможно выразить некоторые синтаксические явления (как, например, анафорические связи1)), их использование дает, по крайней мере в первом приближении, удовлетворительные результаты. Иначе говоря, простота достигается не слишком дорогой ценой.
Для языков программирования положение остается в общих чертах тем же самым: программа представляет собой структуру,
') Анафорическими связями обычно называют связи «отсылочного» типа, например связь между местоимением-заменителем он, она, оно, они и заменяемым им словом. Так, во фразе Mauia подвела дочку к дивану, затем она уложила ее на него три анафорических связи: она — Маша, ее — дочку и на него — на диван. Другие примеры анафорических связей: связь между союзным словом типа который, где, когда, ... и той словоформой, к которой относятся вводимые этими словами придаточные; связь между указательным местоимением типа этот, тот и той именной группой, на которую оно указывает; и т. п.
Заметим, что в собственно синтаксической структуре (дереве) фразы анафорические связи и не должны представляться; по крайней мере они не должны представляться тем же самым образом, которым представляются в дереве «настоящие» (т. е. структурные, иерархические) синтаксические связи. Прим. перев. 116
Часть II. Некоторые замечательные классы языков
построенную из последовательностей, принадлежащих к разным синтаксическим категориям.
Грамматики и структуры фраз. Дерево фразы играет важную роль в описании синтаксиса; мы будем требовать, чтобы грамматики не просто перечисляли фразы, но и приписывали каждой фразе одну или несколько структур (последнее — в случае ее синтаксической неоднозначности).
Особый интерес представляет для нас исследование таких алгоритмов, которые для каждой данной фразы решали бы, принадлежит ли она языку, и в случае положительного результата определяли ее синтаксическое дерево (или деревья).
В § 7.2 будут введены строгие определения, формализующие перечисленные интуитивные понятия.
7.1.3. Упражнения
1. Построить грамматику с такими правилами, которые обеспечили бы представление структуры фразы (3) в виде бинарного дерева.
2. Что получится, если ввести правило Gn-+Art Gti?
§ 7.2. ОПРЕДЕЛЕНИЯ. РАСПОЗНАВАЕМЫЕ СВОЙСТВА
Прежде всего мы определим некоторый исключительно важный тип грамматик и языков — столь важный, что к нему пришли независимо друг от друга многие исследователи, стоявшие на достаточно различных точках зрения. Однако наиболее четкую и глубокую характеристику этого класса дал Н. Хомский, и потому' мы назовем соответствующие языки языками Хомского. Сам Хомский назвал их «контекстно-свободными», или «бесконтекстными» (con-text-free); этот термин объясняется тем, что правила грамматик для контекстно-свободных языков формулируются независимо от какого бы то ни было контекста.
