Лекция 1. Формальные языки

Естественные и формальные языки

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

С тех пор язык распространялся через долгий исторический процесс завоеваний, торговли и ассимиляции. Сегодня основные великие языки -- английский, хинди и китайский -- являются родными для более чем трех миллиардов человек, и это продукт тысячелетней социальной эволюции. Такие языки называются естественными, и все мы используем один или несколько естественных языков для различных целей: для занятий наукой, поэзией, для юмора или просто для того, чтобы провести время в беседе.

Формальные языки, напротив, обязаны своим существованием усилиям нескольких талантливых людей; в отличие от естественных языков, они созданы для четко определенной цели; и мы часто можем очень точно датировать их происхождение. Их структура намного проще, чем у естественных языков, а элементов в лексиконе гораздо меньше. Языки программирования -- это представители формальных языков; так что C (изобретенный Ричи и Томпсоном в 1973 году) и Fortran (изобретенный Бэкусом и его командой в 1957 году) являются примерами формальных языков.

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

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

1. Каждый формальный язык (и, следовательно, каждая система доказательств) имеет синтаксис, который однозначно определяет, какие элементы лексикона составляют значимые формулы, а какие бессмысленны. Например, в языке программирования BASIC выражение let X = 3 является допустимым утверждением. Но X let 3 = недопустимо. В арифметике 3 + 1 = 5 допустимо (хотя и неверно), но 3 + 1 5 = недопустимо. Именно синтаксис формального языка определяет, какие комбинации символов могут рассматриваться как часть языка, а какие недопустимы.

2. Система доказательств должна иметь семантику, которая определяет, как мы можем интерпретировать символы этой системы доказательств. Например, мы можем интерпретировать a, b, c в a + b = c как обозначающие 1, 2 и 3 соответственно, но не Тома, Дика и Гарри. Семантика алгебры запрещает такую интерпретацию.

3. В системе доказательства должны быть правила доказательства, которые определяют, что считается доказательством в системе, а что нет. В идеале правила доказательства должны позволять механическую проверку любого доказательства, чтобы гарантировать его точность. Например, в алгебре у нас есть правило доказательства, которое позволяет нам сократить общие члены с каждой стороны уравнения, поэтому из x + a = x + b мы можем вывести a = b.

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

Языки программирования имеют много общих черт, наиболее очевидной из которых является синтаксис. Раньше семантика компьютерных языков объяснялась в довольно объемных руководствах на естественном языке, но в настоящее время большинство специалистов по информатике используют более точные инструменты для выражения значения таких утверждений, как let X = 3. В наши дни книги типа "How To" распространены в программировании (например, "Как стать мастером C ++ за 48 часов"), но (к сожалению) гораздо меньше представлены в математике и логике.

Синтаксис и форма Бэкуса-Наура

Языки программирования и системы доказательства пересекаются по части синтаксиса; ибо без точного синтаксиса не может быть формального языка.

Отец синтаксиса в информатике - Джон Бэкус.

Джон Бэкус (1924 - 2007)

Бэкус руководил разработкой первого языка программирования высокого уровня -- Fortran (Formula Translation Language -- язык перевода формул) в 1957 году и участвовал в разработке Algol 60.

Чтобы точно описать Algol, необходимо было использовать нотацию для выражения его синтаксиса. Бэкус дал свое имя нотации для синтаксиса, используемой сегодня большинством информатиков -- форме Бэкуса-Наура, или БНФ. Эта нотация была адаптацией более ранней работы по синтаксису Ноама Хомского.

Мы начнем изучение БНФ с синтаксиса очень простого формального языка$L_0$ . Этот язык состоит из строк различной длины, состоящих из символа $a$. Это означает, что наш формальный язык включает следующие предложения:

$a, aa, aaa, aaaa, ...$

Мы не можем описать все предложения$L_0$, перечислив их, потому что количество допустимых предложений бесконечно. БНФ предлагает решение. Вместо того, чтобы пытаться перечислить бесконечный набор предложений, мы формулируем правила, которые определяют, когда что-то является предложением$L_0$. В БНФ для$L_0$таких правил два:

1. $\langle sentence \rangle := a$
2. $\langle sentence \rangle := {a}^\wedge{\langle sentence \rangle}$

Мы можем прочитать $:=$ как "может состоять из". Первое правило, переведенное на естественный язык, гласит, что "$\langle sentence \rangle$ может состоять из одной буквы $a$". Второе правило гласит: "$\langle sentence \rangle$ может состоять из единственной буквы $a$, соединенной с $\langle sentence \rangle$". $\wedge$-- оператор конкатенации; это указывает на то, что задействованные объекты соединены вместе без пробелов.

Второе правило кажется бессмысленным, поскольку оно объясняет, что такое $\langle sentence \rangle$, ссылкой на $\langle sentence \rangle$. Эта форма определения называется рекурсивным определением, и бессмысленность эта кажущаяся, а не реальная. Используя эти два правила, мы можем доказать, что $aaa$ является предложением$L_0$.

Начнем с $\langle sentence \rangle$ в БНФ. Правило $R$ может применяться для расширения символа $S$, если символ $S$ встречается слева от $: =$ в $R$. $S$ расширяется путем замены $S$ тем, что находится справа от $: =$ в $R$. Таким образом, мы можем развернуть $\langle sentence \rangle$ в $a$ (по правилу 1) или в $a ^ \wedge \langle sentence \rangle$(по правилу 2). Покажем, что $aaa$ -- это предложение.

Подстановки	Правило
<sentence>
a <sentence>	По правилу 2.
aa <sentence>	По правилу 2.
aaa	По правилу 1.

Как только мы получили $aaa$, больше нет правил, которые можно было бы использовать для дальнейших подстановок. Следовательно, $aaa$ - это предложение $L_0$.

Процесс доказательства того, что формула $f$ является предложением языка, использующего БНФ, начинается с символа $\Sigma$ (называемого особым символом) и продолжается с использованием правил для расширения этого символа до тех пор, пока:

1. будет получена $f$ и...
2. получив $f$, мы не можем применить никаких правил для дальнейшего расширения $f$.

Синтаксический анализ (англ. parsing) -- это процесс использования грамматики для языка $L$, чтобы показать, что формула является предложением языка $L$. Синтаксический анализ является фундаментальной техникой в информатике, а в синтаксическом анализе с использованием БНФ компьютеры показывают превосходные результаты. Всякий раз, когда вы даете команду компьютеру, она должна быть написана на каком-то формальном языке, и требуется некоторая форма синтаксического анализа, чтобы компьютер мог интерпретировать вашу инструкцию. Парсер -- это компьютерная программа, которая выполняет синтаксический анализ.

Упражнение 1.1. Какие из следующих последовательностей символов содержат символы, которые можно расширить в соответствии с нашими правилами для $L_0$?

1. $bb \langle sentence \rangle$
2. $aaa$
3. $a \langle sentence \rangle$

Упражнение 1.2. Какие предложения будет содержать язык $L_0$, если удалить символ $\wedge$?

Немного терминологии

Набор правил, задающих синтаксис языка$L$, называется грамматикой$L$. Символ, который встречается только справа от $:=$, называется терминалом. Символ $\langle sentence \rangle$, который используется для доказательства того, что строка символов является предложением $L$, называется особым символом. Правило, которое имеет символ $S$ справа от $:=$, а также слева от $:=$, называется рекурсивным.

Упражнение 1.3. Какие символы используются в грамматике для терминалов? Какие не являются терминалами? Какие правила нашей грамматики рекурсивны?

Наша новая терминология позволяет нам дать сжатое определение того, что значит быть предложением $L$.

Формула $f$ является предложением $L$, когда $f$ может быть сгенерирована с использованием грамматики $G$ для $L$ из особого символа $Σ$, а $f$ содержит только терминалы.

Когда $f$ может быть сгенерировано таким образом, мы можем сказать, что $f$ соответствует грамматике $G$.

Упражнение 1.4. Язык состоит из строк, состоящих из символов $a$, за которыми следуют символы $b$. Грамматика для $L_1$ задается следующими правилами:

1. $\langle sentence \rangle := \langle as \rangle ^\wedge \langle bs \rangle$
2. $\langle as \rangle := a$
3. $\langle as \rangle := a ^\wedge \langle as \rangle$
4. $\langle bs \rangle := b$
5. $\langle bs \rangle := b ^\wedge \langle bs \rangle$

Докажите, что $aaabbb$ -- это предложение $L_1$.

Упражнение 1.5. Какие символы в грамматике $L_1$ являются терминалами? Какие не являются? Какие правила нашей грамматики рекурсивны?

Расширенная БНФ

В различной литературе можно встретить грамматику $L_1$в следующей форме:

1. $\langle sentence \rangle := \langle as \rangle ^\wedge \langle bs \rangle$
2. $\langle as \rangle := a | a ^ \wedge \langle as \rangle$
3. $\langle bs \rangle := b | b ^ \wedge \langle bs \rangle$

Эта нотация является частью расширенной БНФ, которая предлагает удобное сокращение для введенной нами ограниченной нотации. $|$ определяет альтернативные расширения нетерминала слева от $:=$. Таким образом, второе правило выше говорит:

$\langle as \rangle$может быть расширено до $a$или $a$может быть присоединено к $\langle as \rangle$

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

Еще одна особенность, которую иногда можно встретить в расширенной БНФ, -- использование специального символа $\varepsilon$ для пустого расширения. Правило $\langle bs \rangle := \varepsilon$ означает, что нетерминал $\langle bs \rangle$ можно вообще исключить из итоговой строки. Пустое расширение полезно, когда мы имеем дело с языками, где символ может встречаться ноль или более раз. Например, предположим, что $L_2$состоит из всех предложений, состоящих из одного или нескольких вхождений $a$, за которыми следует ноль или более $b$ (без конкатенации). Мы можем записать грамматику в расширенной нотации как

$$\begin{aligned} \langle sentence \rangle &:= \langle as\rangle \langle bs \rangle \\ \langle as \rangle &:= a | \langle as \rangle \\ \langle bs \rangle &:= \varepsilon | b | \langle bs \rangle \end{aligned}$$

Распространенное расширение -- использование надстрочного индекса$\ast$ для обозначения ноля или более вхождений символа и надстрочного индекса $+$ для обозначения одного или нескольких вхождений. Это позволяет сократить определение правил $L_2$ до одной строки:

$$\langle {sentence} \rangle {:=} a^+b^\ast$$

Упражнение 1.6. Определите грамматику БНФ для языка, который генерирует все строки формы $a_n b_n$, где $a_n$и $b_n$-- одинаковое количество символов $a$и $b$. Таким образом, $ab$, $aabb$, $aaabbb$ являются предложениями языка $L_2$, а $aaabb$и $aabbb$-- нет.

Следующий пример взят из реально используемого формального языка. Это язык $L_3$ или арифметика для первого класса (символ $\ast$-- это обычное компьютерное обозначение умножения). $L_3$включает все равенства вида $a = b$, где $a$ и $b$ -- арифметические значения, заключенные в скобки. Например, $4 = (2 + 2)$, $(3 * 4) = (6 - (5 / 2)$.

$$\begin{aligned} \langle {sentence} \rangle &:= \langle arithexpr \rangle = \langle arithexpr \rangle \\ \langle arithexpr \rangle &:= (^\wedge \langle arithexpr \rangle \langle op \rangle \langle arithexpr \rangle^\wedge) | \langle number \rangle \\ \langle op \rangle &:= + | - | * | / \\ \langle number \rangle &:= \langle digit \rangle | \langle digit \rangle^\wedge \langle number \rangle \\ \langle digit \rangle &:= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 \end{aligned}$$

Упражнение 1.7. Докажите, что $(31 + 4) = (23 - (3 * 8))$является предложением $L_3$.

За пределы БНФ

Грамматики БНФ соответствуют тому, что Ноам Хомский назвал типом 2 или контекстно-свободными грамматиками в своей основополагающей работе "Синтаксические структуры". Языки, синтаксис которых может быть описан с помощью контекстно-свободных грамматик, называются контекстно-свободными языками. Из теории формальных языков известно, что существуют некоторые простые языки, которые нельзя описать с помощью контекстно-свободных грамматик. Один из самых простых -- язык $a^n b^n c^n$, состоящий из предложений, содержащих одинаковое количество $a$, $b$ и $c$ друг за другом.

Обычно считается, что естественные языки, такие как английский, не контекстно-свободные, хотя ученые спорят по этому вопросу. Такие языки называются контекстно-зависимыми. Несомненно, большая часть синтаксиса английского языка может быть описана с помощью контекстно-свободной грамматики, хотя такая грамматика состояла бы из тысяч правил. Задача синтаксического анализа и описания таких грамматик относится к области обработки естественных языков (Natural Language Processing, NLP).

В области формальных языков БНФ с небольшими расширениями почти всегда подходит в качестве нотации для описания синтаксиса; то есть формальные языки обычно контекстно-свободные.

Дальнейшее чтение

Хомский (переиздание от 2002 г.) -- начало синтаксического анализа. Гоф (1988) анализирует формальные языки с точки зрения создания компилятора. Ахо и Ульман (1972) -- классический текст по компьютерному синтаксическому анализу.