Язык и мозг

Разбор арифметических выражений требует изрядного количества усилий… А почему так сложно?

Почему у первоклассников, которых учат, что сначала надо выполнять умножение, а уже потом сложение — и сначала действия в скобках, а потом все остальные — никогда никаких проблем с этим материалом не возникает, а чтобы запрограммировать «робота», выполняющего тоже самое, нужны особенные (не тривиальные — не в том смысле, что сложные, а в том смысле, что своими силами до них нормальному человеку не так-то просто дойти) алгоритмы и инструменты?

Зададимся несколькими другими риторическими вопросами из той же серии:

• почему распознаванию лиц человеческое дитя учится до практического совершенства примерно год, а компьютеры за совокупный «налёт» в тысячи лет едва-едва вышли на приемлимый уровень?
• почему навыку ходьбы человеческое дитя учится пару лет, а роботы только-только к нашим годам научились имитировать в лабораторных условиях на фоне неограниченного финансирования от всяких DARPA?
• почему навыки речи человеческое дитя за три года доводит до такого уровня, которым компьютеры не овладеют в ближайшие лет 30, не смотря на миллиардные вливания от чуть ли не всех крупнейших корпораций планеты?

Похоже, что навык распознавания скобочных структур (у людей) опирается на встроенный «речевой процессор».

Отцом-основателем теории о врождённых механизмах производства и восприятия языка (речи) является американский лингвист Ноам Хомский.

Ноам Хомский — «научный дедушка» всех языков высокого уровня — любит интересно порассуждать на и на общие актуальные темы.

Хомский резюмирует годы своей (начальной) работы в книге «Синтаксические структуры» в 1957 году.

В том же году Джон Бэкус (создатель BNF, Backus normal form, «нормальной формы Бэкуса», к описанию которой мы вскоре перейдём) создаёт первый язык программирования высокого уровня «Фортран».

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

Источник картинки

Джон Бэкус на фоне своего творения.

Нормальная форма Бэкуса (BNF)

Важная оговорка: далее мы будем говорить

Для формальной записи грамматики формальных языков получила широкое распространение так называемая «нормальная форма Бэкуса» (backus normal form, BNF).

BNF сама по себе является (достаточно простым) формальным языком.

BNF состоит из набора правил вывода для нетерминальных символов («нетерминалов»), которые позволяют (после повторно-рекурсивного применения правил, в конечном итоге) получить набор терминальных символов.

Состав некоего сомнительного кондитерского изделия

Всё просто:

• терминальные символы — это «базовые химические элементы» продукта;
• нетерминальные символы — это промежуточная группировка базовых (и других нетерминальных) элементов;
• правила вывода показывают один или несколько (альтернативных) рецептов получения одного нетерминала из одного или более терминалов и нетерминалов;
• стартовый символ — нетерминальный символ, который захватывает «весь продукт в целом»;

<тортик> ::= <сметанный_продукт> "мука" "молоко" "масло" <крем>
<сметанный продукт> ::= "молоко" "заменитель жира" "закваска"
<крем> ::= "жир" "декстроза" "соль"

Альтернативные правила вывода

Если для получение некоего нетерминала можно использовать разные «рецепты», то альтернативные рецепты либо записываются один под другим с повтором знака ::=, либо разделяются вертикальной чертой | («логическое ИЛИ»).

Например, <цвет> может быть чёрный или белый. Три эквивалентных варианта записи:

<цвет> ::= "чёрный" | "белый"

<цвет> ::= "чёрный"
       ::= "белый"

<цвет> ::=
  "чёрный"
  | "белый"

Комментарии

Для комментариев используется символ ;:

<цвет> ::= "синий" ; разрешён только один цвет

Пустая строка

Пустая строка (отсутствие символа) обозначается в данном цикле лекций символом ε (эпсилон, от английского empty).

Пускай в нашем «зарплатном языке» разрешены строки вида “100 рублей”, “100 рублей и премия” и “” (пустая строка).

Грамматика будет такая

Иногда ε не пишут, и остаётся просто пустое место. Так тоже можно.

<зарплата> ::=
  "100 рублей"
  | "100 рублей" "и премия"
  | ε

Формальная грамматика и формальный язык

Формальный язык — это совокупность всех возможных «фраз» (последовательностей терминальных символов, то есть строк), которые можно получить из грамматики.

Другими словами, мы можем взять стартовый символ грамматики (первый нетерминал BNF) и провести над ним ряд разрешённых грамматикой преобразований, придя в конечном итоге к строке только лишь из терминальных символов. Вот совокупность всех строк, которые мы таким образом можем получить, и есть наш формальный язык.

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

«Маршрут», по которому такая свёртка произойдёт (какие правила в каком порядке к какому месту исходной строки были применены) составляет дерево парсинга (parse tree) данной строки.

Если для каждой строки языка при данной грамматике существует только одно возможное дерево парсинга, то такая грамматика называется «однозначной».

Например, наивная грамматика инфиксных выражений не является однозначной.

Правило вида «1 и более»

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

Однако в регулярных выражениях у нас есть удобные символы ? («0 или 1 раз»), + («1 и более раз»), * («0 и более раз»).

В BNF подобные правила моделируются с помощью рекурсии.

Допустим, определим <здание> как то и только то, что является последовательностью:

• “фундамента”
• 1 и более “этажа”
• “крыши”

<здание> ::= "фундамент" <этажи> "крыша"

Слова “1 и более” выразим в промежуточном нетерминале <этажи> вот как:

<этажи> ::=
  "этаж"
  | "этаж" <этажи>

В самом деле, вообразим строительного робота, который строит здание по структуре, определяемой данной грамматикой:

Нетерминальными символами при этом будут являться «мысли» этого бота, а терминальными — то, что он реально делает.

Начнёт он «мыслить» со стартового символа <здание>, положит фундамент, затем подумает: “<этажи>!..”

Дальше у него два варианта развития событий:

• просто построить этаж и закончить на этом с <этажами> (возвращаясь к продолжению изначальной мысли <здание>);
• построить этаж, затем перейти рекурсивно к новой мысле <этажи>.

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

Не трудно видеть, что бот таким образом «зацикливается» и, в зависимости от настроения, может построить здание с любым количеством этажей (но один этаж железно будет). Что нам и требовалось.

Итак, формально, для создания правила типа “1 и более x” требуется ввести и использовать дополнительный нетерминал <one_or_more_x> (название условное):

<one_or_more_x> ::=
  "x"
  | "x" <one_or_more_x>

Правило вида «0 и более»

Для правила типа “0 и более x” требуется ввести и использовать дополнительный нетерминал <zero_or_more_x> (название условное):

; только для стартового символа!
<zero_or_more_x> ::=
  "x"
  | "x" <zero_or_more_x>
  | ε

Не углубляясь в тонкости конфликтов shift-reduce и проблем неоднозначных грамматик, отметим, что это правило подходит только для стартового символа.

Rule of thumb вот какой: ни одно правило вывода не должно содержать в качестве одной из веток только ε и больше ничего, кроме стартового правила.

Например, хорошая грамматика для массивов с 0 и более букв “a” (строки типа [], [a], [a,a], [a,a,a] и т. д.):

; хороший вариант
<array> ::=
  "[" <items> "]"
  | "[" ε "]"

<items> ::=
  "a"
  | "a" "," <items>

; другой хороший вариант
<array> ::=
   "[" <optional_items> "]"

<optional_items> ::= <items> | ε

<items> ::=
  "a"
  | "a" "," <items>

То есть ε должна оказаться на уровне «родительского правила». Плохой вариант, порождающий неоднозначную грамматику:

; плохой вариант - не использовать
<array> ::=
  "[" <items> "]"

<items> ::=
  "a"
  | "a" "," <items>
  | ε

Хорошая грамматика однозначная — «свёртка» <items> произойдёт ровно столько раз, сколько элементов в массиве.

Плохая грамматика неоднозначная — «свёртка» <items> произойдет сколько угодно раз, поскольку неограниченное число раз может произойти применение последней ветки.

Формально, для создания правила типа “0 и более x” требуется:

Вариант 1:

• создать те же правила, что и для случая “1 и более x”;
• затем добавить к тем правилам, где x присутствует в правой части (но не в левой) альтернативные ветки, где на месте x стояла бы ε.

Вариант 2:

• создать те же правила, что и для случая “1 и более x” (создав нетерминал <one_or_more_x>);
• заменить <one_or_more_x> в правой части правил вывода (в тех правилах, где он при этом не стоит в левой части) на новый нетерминал <optional_x>;
• определить <optional_x> как <one_or_more_x> | ε.

Правило вида «0 или 1»

Правило вида 0 или 1 "x" можно задать, создав новый нетерминал <zero_or_one_x>:

<zero_or_one_x> ::= "x" | ε

Например, грамматику, задающую язык, в которой входят строки f и f(x), можно сформулировать так:

<function> ::= "f" <arguments>

<arguments> ::=
  "(" "x" ")"
  | ε

Не следует совмещать в одном нетерминале правила вида «0 или 1» и «1 и более» для предотвращения случайных ошибок в формулировке правил вывода.

Классы символов

В практических целях удобно опускать некие излишне подробные и повсеместно используемые определения нетерминалов. Например, цифру можно определить как:

<digit> ::= "1" | "2" | ... | "9" | "0"

Число как:

; см. раздел "1 и более" выше,
; число = 1 и более цифра
<number> ::=
  <digit>
  | <digit> <number>

Вместо того, чтобы в каждой грамматике каждой лекции, где используется BNF, дописывать эти определения (к тому, имеющие мало значения для практической реализации парсеров), мы используем просто слова number и digit:

<addition> ::= number "+" number

При этом слова number и digit не берутся ни в угловые скобки, ни в кавычки. С формально-теоретической точки зрения это нетерминал (определённый как показано выше), а с практической обрабатывается как терминальный символ.

Леворекурсивные и праворекурсивные правила вывода

Правило, которое прямо или опосредовано содержит ссылку на само себя в качестве первого символа одной из веток, называется «леворекурсивным»:

<letters_a> ::= <letters_a> a

Правило, которое прямо или опосредовано содержит ссылку на само себя в качестве последнего символа одной из веток, называется «праворекурсивным»:.

<letters_z> ::= z <letters_z>

Диалекты BNF

Существует две распространённых вариации/модификации BNF: EBNF и ABNF.

Применения

Множество различных средств для создания языков программирования используют диалект BNF.

Официальная спецификация ряда современных языков программирования содержит грамматику, записанную на диалекте BNF.

В пользовательской документации к языкам программирования иногда используется диалект BNF.

Стандарты на протоколы интернета, разрабатываемые IETF, зафиксированы на диалекте BNF.

Формальная грамматика BNF в BNF

Примерный вид грамматики BNF в BNF, с учётом изложенных выше рекомендаций:

<rules> ::=
  <rule>
  | <rule> <rules>

<rule> ::=
  <nonterminal> "::="                    ; правой части правила может не быть
  | <nonterminal> "::=" <alternatives>

<alternatives> ::=
  <symbol_sequence>
  | <symbol_sequence> "|"                ; правой части ветки может не быть
  | <symbol_sequence> "|" <alternatives>

<symbol_sequence> ::=
  <terminal_or_nonterminal>
  | <terminal_or_nonterminal> " " <symbol_sequence>

<terminal_or_nonterminal> ::= <terminal> | <nonterminal>

<terminal> ::=
  """ string """
  | "ε"

<nonterminal> ::= "<" identifier ">"

string — любая строка, не содержащая кавычек, или одна кавычка ";
identifier — любая строка, не содержащая угловых скобок;