Глава 8. Языки и грамматики

Все средства общения включают язык. Обычно мы «общаемся» с компьютером при помощи языка, который каким-либо образом записывается (перфокарты, телетайп, экран дисплея и т.п.) и, следовательно, предложения языка состоят из строк символом. Действительно, весь вычислительный процесс может рассматриваться как преобразование одного множества строк в другое. Такие процессы ведут себя совершенно определённым образом, и, следовательно, с ними можно обращаться как с математическими объектами – по крайней мере строки могут рассматриваться как элементы моноида. В этой главе мы будем подходить к изучению языка скорее с математической точки зрения, чем с литературной. В § 1 будет введено понятие строки и будут рассмотрены некоторые проблемы, относящиеся к этому вопросу; в § 2 будут введены языковые структуры. Далее будут более детально исследованы некоторые важные классы языков и рассмотрено введение в грамматический разбор.

§ 1. Основные понятия

1.1. Строки. Буква (или символ) – это простой неделимый знак, или символ; множество букв образует алфавит.

П р и м е р 1.1.

Здесь мы можем рассматривать как бинарный алфавит, – как алфавит языка Кобол (в котором слова типа PERFORM не могут быть разделены), а – как английский алфавит.

Алфавиты являются множествами, и поэтому к ним можно применять теоретико-множественные обозначения. В частности, если и такие алфавиты, что , то будем говорить, что A является подалфавитом , или что является расширением .

Строки являются упорядоченными совокупностями букв алфавита (например, алфавита A) и, следовательно, выглядят подобно элементам Однако будет более естественным записывать их в виде , а не Буквы сами по себе также являются строками для случая n = 1. Мы будем допускать случай, когда строка не имеет букв (пустая строка), и обозначать эту строку через . Заметим, что не является символом, т.е. для любого алфавита .

По аналогии с лингвистикой будем строки также называть словами. Множество всех строк (слов) над алфавитом называют замыканием и обозначают , так что

Для удобства определим также множество непустых строк над следующим образом:

Как уже упоминалось в примере 2.1 гл. 5, основная операция над строками называется конкатенацией; формально она может быть определена как бинарная операция на следующим образом:

Аналогично эта же операция определяется для . Операция ассоциативна, но не коммутативна; является единицей в по отношению к . Сформулируем ниже основные свойства операции на и .

П р е д л о ж е н и е. По отношению к операции

а) является моноидом;

б) – полугруппа. //

Результат слияния строк и , т.е. , заключается в следующем: строка записывается сразу же за строкой . Другой способ определения строки – рекурсивный: является строкой над алфавитом , если , или , где , а – строка над . Здесь означает, что буква стоит непосредственно перед строкой .

Все слова в состоят точно из букв; в этом случая говорят, что строка имеет длину . Длина обозначается как и тогда и только тогда, когда .

Очевидно, что и тогда и только тогда, когда .

Если строки состоят из повторяющихся букв, то обычно принимают сокращённые обозначения, чтобы показать, что строку следует рассматривать как произведение (по отношению к операции конкатенации). Поэтому для будем писать

, , , .

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

Этот пример иллюстрирует одну из основных трудностей при рассмотрении строк, и, следовательно, мы должны иметь возможность различать используемые алфавиты. Если приведённые выше выражения рассматривались над алфавитом , а символов «(» и «)» в нет, тогда смысл понятен; с другой стороны, если круглые скобки есть в , то выражение может быть понято как . При условии что мы осознаём возможность таких проблем и знаем, какие алфавиты используются, этих ошибок можно избежать, используя различные алфавиты и биекцию между двумя алфавитами. В некоторых случаях может быть более удобно построить мономорфизм между множествами строк, так что одно множество рассматривается над существенно более простым алфавитом.

П р и м е р 1.2. Пусть и . Тогда , определённое соотношением

,

где и

, , ,

является гомоморфизмом моноида (нам надо сохранять комбинации) из в . Например,

.

В действительности этот метод построения может использоваться для отображения произвольного конечного алфавита в . //

Из определения длины строки следует, что если , то

, .

Более того, если , то

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

Пусть заданы строки и над алфавитом . Строка называется подстрокой , если

, .

П р и м е р 1.3. Пусть и . Тогда подстроками являются следующие строки:

В частности, заметим, что является подстрокой самой себя, а – подстрокой (и любой другой строки), поскольку

… //

Выделение подстроки естественно приводит к замене подстроки другой строкой. Однако пока мы ещё не достигли уровня, достаточного для корректного выполнения этой операции. Рассмотрим, что случится, если мы имеем «функцию» , которая замещает строку строкой при условии, что первая строка является подстрокой в операнде. Тогда

Однако неясно, что является результатом . Возможны два случая – или . Аналогично получается, если мы применяем несколько раз. Тогда , однако, применяя к получаем

, .

Таким образом, «функция» является не полностью определённой, и мы не можем поправить дело, потребовав, чтобы операция изменяла все подстроки, поскольку они могут частично перекрываться.

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

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

,

где , , и (если , то ; поэтому существует только одна возможность). Будем говорить, что специфицируют различные вхождения в и что даёт первое вхождение, а вхождение непосредственно за является первым вхождением.

П р и м е р 1.4. Пусть – функция такая, что , и заменяет первое вхождение в строке на . Тогда

, ,

.

Заметим также, что

,

;

поэтому

… //

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

1.2. Языки. Совокупность строк (или предложений) называется языком. Формально язык над алфавитом – это множество строк в ; поэтому . Следовательно, операции над строками индуцируют операции на языках. Отсюда получаем (транзитивное замыкание ) и (рефлексивное замыкание ) следующим образом:

а) ;

б) если и – языки, то ;

в) ;

г) ;

д) .

Сейчас обратим внимание на то, как слова могут составляться в предложения, а множество всех предложений, имеющих смысл, образует язык. Нас будут в основном интересовать искусственные языки, такие как языки программирования или языки, описывающие правильные математические выражения, однако вначале будет полезно рассмотреть случай английского языка. Это даст возможность сформулировать некоторые определения таким образом, что мы сможем сделать первые шаги в теорию языка. Возьмём предложение

«The dog bit me».

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

П р и м е р 1.5. В языках программирования Фортран и Кобол утверждения

,

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

. //

О сновным объектом нашего рассмотрения будет область синтаксиса. Чтобы проиллюстрировать класс структур, которые мы будем изучать, рассмотрим диаграмму на рис. 8.1.

Рис. 8.1

На самом деле эта диаграмма означает, что может быть построено путём слияния , и , хотя это требует формального определения. Подлежащее состоит из с , и окончательно получаем «the», «dog», …, что даёт нам предложение «the dog bit me».

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

Напомним, что для заданного алфавита язык L яв­ляется произвольным подмножеством множества *, од­нако произвольные подмножества представляют очень не­значительный интерес. Мы хотим сосредоточить внима­ние на специальных языках, содержащих строки, которые благодаря внешней информации об их семантике считаются осмысленными или хорошо сконструированными.

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

а) Как по заданной грамматике G (и связанным с ней языком L) порождать предложения ?

б) Как по заданным и устанавливать, принадлежит ли ?

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

Обозначим через язык, порожденный грамматикой . Тогда алгоритм проверки вхождения называется грамматическим разбором; он использует и . Часто первоначальная грамматика не подходит для определенной техники разбора, однако она может быть преобразована к эквивалентному, более подходящему виду. Вопросы, относящиеся к грамматическому разбору или модификации грамматики, будут рассматриваться в § 4.

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

У п р а ж н е н и е 8.1.1. Предположим, что и — непустые алфавиты такие, что

, ,

и , – биекции. Пусть определено как

а определено как

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

.