Язык языков. Часть вторая

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

META II

В 1963-1964 годах, буквально через несколько лет после появления BNF, за авторством Dewey Val Schorre работавшим тогда в Калифорнийском университете в Лос-Анджелесе (UCLA) выходит в свет язык программирования META II. Примечательно, что в 1963 году была разработана и стандартизована ASCII-таблица.

Основная сфера применения этого языка — создание компиляторов. В документации по языку, META II описывается как «синтакс-ориентированный язык для написания компиляторов», а так же «язык похожий на BNF». В этом языке были введены такие понятия и конструкции, которые в том или ином виде дожили и до наших дней в виде продолжения в EBNF и ABNF, о которых мы поговорим ниже.

В META II рекурсивное определение BNF было заменено циклом. Для этого была введена математическая группировка при помощи скобок $( и ). Фактически, следующее выражение:

$(foo)

следует понимать как ноль или более повторений foo. Например, для следующего BNF правила:

<expr> := <term> | <expr> + <term> | <expr> - <term>

мы должны были бы написать что-то вроде:

expr = term
       $( '+' term .out('ADD')
        / '-' term .out('SUB'));

На что тут следует обратить внимание:

Символы целевого языка (терминалы), стали определяться с помощью строк в одинарных кавычках (здесь это + и -)
Были удалены угловые скобки, что наложило ограничения на допустимый набор символов
Металингвистическая связка ::= была заменена на =
Для указания выбора используется наклонная черта (/) вместо вертикальной (|)
Правило заканчивается точкой с запятой (;)
Отныне пользователю предлагались уравнения, вместо металингвистических правил, как это называлось в BNF

Рассмотрим шаг за шагом как работает грамматика, приведённая выше.

Выражение оценивается слева направо. Первое, что проверяется это term. Если сопоставление с term не удалось, всё выражение откидывается, и анализатор двигается дальше. Если сопоставление оказалось успешным, анализатор входит в $( ... ). Затем анализатор пытается протестировать +. В случае неудачи срабатывает альтернатива (/) и анализатор оценивает -. Если хоть один из вариантов сопоставления с образцом оказался успешным, анализатор пытается провести сопоставление с тем term, который находится по правую сторону от знака. Если оба варианта сопоставления не удались, т.е. вторые term не удалось сопоставить, результат сопоставления остаётся успешным только для самого первого term, который мы видим сразу же после знака =. Тут всё достаточно просто. А теперь самое интересное. Так как оператор $( ) означает цикл из нуля или более итераций, то после успешного сопоставления со вторым term, цикл повторяется до тех пор, пока сопоставление не провалится. Так решалась задача рекурсивных определений BNF.

Любопытные штуки типа .out('ADD'), как мог догадаться читатель — служебный код, печатающий т.н. опкоды в стандартный вывод. Работало это так: если сопоставление удалось полностью, например - term, то печатаем SUB.

Мне показался забавным тот факт, что в документации указанно об обязательной точке с запятой в конце каждого уравнения, однако в самой документации, вместо этого используется точка, за которой сразу идёт запятая («due to keypuch limitations»). Вспомнилось, что в отчёте ALGOL 60 таких проблем не было. Там всё решалось ручным написанием всех нужных закорючек.

Если бы мы хотели как-то обозначить синтаксический элемент необязательным, в META II нам предлагалось служебное слово empty:

subsecondary = '*' primary / empty  ;
   secondary = primary subsecondary ;

Первую строку следует понимать так: либо символ *, за которым идёт нетерминал primary, либо ничего.

Кроме того, в META II появилось три типа данных: идентификаторы (обозначались через id), строки (обозначались через string) и числа (обозначались через number). Теперь давайте рассмотрим следующий пример целевого языка:

A
A + B
A + B * C
(A + B) * C

Это выдуманный алгебраический язык, с приоритетом операторов и группировкой. Если бы мы хотели покрыть этот язык грамматикой используя META II, то нам понадобилось бы написать следующий набор уравнений:

expr3 = id / '(' expr1 ')'        ;
expr2 = expr3 ('*' expr2 / empty) ;
expr1 = expr2 ('+' expr1 / empty) ;

Это в действительности не сложная грамматика. И если присмотреться, то всё становится достаточно очевидным, кроме одного понятия, с которым мы ещё не сталкивались — группировка. Только на первой строке скобки обрамлены кавычками, указывая на принадлежность скобок к символам целевого языка. Группировку скобками на второй и третьей строке следует расценивать так — сопоставление с группой считается успешным только в случае полного сопоставления с каждой альтернативой внутри группы.

Если BNF был формальным языком, не привязанным к каким либо реализациям и вычислениям, то в META II мы видим, как ситуация стала меняться.

Остальной синтаксис META II не сложнее чем то, что я уже показал, а сам язык обладает богатыми возможностями. Но надолго останавливаться на нём мы не будем. Я лишь хотел показать некоторые черты, которые мы рассмотрим далее.

Позднее, уже в 1970-ых, появилась небезызвестная утилита yacc, использующая BNF продукции очень похожие не те, которые использовались в META II. yacc чаще всего используется в качестве генератора LALR-парсеров, и корнями, очевидно, уходит в BNF. Когда вы где-то слышите или читаете, что yacc использует BNF, то знайте — только от части, оригинальный BNF был совсем другой.

EBNF нотация

EBNF (Extended BNF) является расширенной версией BNF нотации. По существу является коллекцией дополнений в классическую форму BNF и отличается от BNF более ёмкими конструкциями, позволяющими при той же выразительной способности упростить и сократить в объёме описание.

Годом официального утверждения EBNF принято считать 1996. Стандартизирующая организация — ISO. В истории появления этой нотации не всё гладко. Были возражения насчёт того, что к 1996 году только ленивый не делал свои версии нотаций и появление ещё одной, под названием EBNF ничего не решало. Мол даже сама организация ISO не везде использовала EBNF. Но мы не будем на долго останавливаться на обсуждении этих идей, а рассмотрим основные отличия от BNF.

К чисто стилистическим изменениям стоит отнести следующие меры, ставшие популярными за 30 лет модификаций и заимствований у оригинальной нотации BNF:

Символы целевого языка, стали определяться с помощью строк в кавычках (META II)
Были удалены угловые скобки у нетерминалов (META II)
Металингвистическая связка ::= была заменена на = (META II)
В EBNF всё, что находится между символами (* и *) считается комментарием
Символ ; или . сигнализирует об окончании правила (META II)

Но наиболее значимые на мой взгляд изменения были произведены в самой структуре грамматических определений. И вот некоторые из них:

Опциональные элементы

Мы видели как это делается в META II. Так что EBNF не является первооткрывателем этой концепции. Для того чтобы указать опциональные части в грамматике, в EBNF использует квадратные скобки ([ и ]). Правило ниже говорит, что знак минус не является обязательным:

term = [ "-" ] factor ;

Например, если значения factor являются десятичными числами, то вот некоторые допустимые значения term:

Повторения

Идея рекурсивных определений в EBNF похожа на аналогичную идею в META II. Для обозначения того факта, что объект (или группа объектов) может повторяться ноль или более рез, в EBNF используются фигурные скобки ({ и }). Под объектом здесь имеется ввиду терминал (символ целевого языка) или нетерминал. Давайте посмотрим как это работает:

args = arg { "," arg } ;

Это правило определяет некоторый список аргументов, разделённый запятыми. Например, если arg является последовательностью ASCII-символов в диапазоне 65-90, то вот некоторые допустимые значения args:

HOST, PORT, DATABASE
NAME
A, B, C, D

Рассмотрим ещё один пример. Предположим у нас есть язык со следующим способом декларации функций:

function connect (string host, port, string password)

Здесь мы имеем некоторый выдуманный язык, где тип аргумента может быть не указан (здесь — port). Для определения грамматики аргументов функции мы могли бы составить следующие правила:

       args = maybe typed { "," maybe typed } ;
maybe typed = [ type ] arg ;

Как уже было отмечено ранее, угловые скобки в EBNF были убраны. Здесь наглядно показано с чем может возникнуть сложность у неподготовленного читателя (maybe typed это два нетерминала или один?).

Группировка

Я уже показывал выше, как группировка была введена в META II. Давайте разберёмся, как она представлена здесь. Для того, чтобы описать грамматику арифметической операции в BNF мы писали что-то вроде этого:

<expr> ::= <term> <op> <expr>
  <op> ::= - | +

В EBNF допустим такой формат, однако если откинуть стилистическую разницу, то гораздо лаконичнее записывать это так:

expr = term ( "-" | "+" ) expr ;

Конкатенация (последовательности)

Под конкатенацией следует понимать упорядоченный список (последовательность) синтаксических термов, разделённых запятой. Правило ниже описывает некоторое присваивание, за которым идёт точка запятой, а следом пробельный символ. Именно в такой последовательности:

end assignment = { assignment, ";", white space } ;

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

ABNF нотация

К 1977 году Arpanet использовала несколько неформальных стандартов для текстовых сообщений, отправляемых между ее хост-компьютерами. Было сочтено необходимым систематизировать эти методы и обеспечить те функции, которые казались неизбежными. Результатом этих усилий стал стандарт «Standard for the Format of ARPA Network Text Message» (RFC733), а затем обновлённый и дополненный в 1982 году (RFC822). В этих документах описывается модифицированная версия BNF нотации, которая была целесообразна для использования в Arpanet в те годы. И в документах, которые использовали эту модифицированную версию нотации, она называлась «Augmented Backus-Naur Form».

Сложно по одним лишь RFC судить когда всё это началось, потому что не ясно, в каких ещё работах и когда использовалась нотация ABNF. К этому времени, уже существовало множество модификаций BNF. Крупные проекты, связанные с разработкой языков программирования, протоколов сообщений и форматов всяческих данных просто делали себе очередную модифицированную версию. В дальнейшем, в Arpanet была предпринята попытка стандартизировать и систематизировать собственные изменения внесённые в оригинальную версию BNF. Результатом этой работы в 2008 году стал стандарт «Augmented BNF for Syntax Specifications: ABNF» (RFC5234).

Однако следует заметить, что к этому времени ABNF нотация уже использовалась в Arpanet на протяжении десятков лет. EBNF, как мы помним, появился аж в 1996 году, что примерно на 20 лет позже первых фактов использования ABNF. Многие RFC имели в своём определении копию определения ABNF. Выглядело это так: «вот документ, в котором мы описываем некоторые понятия, но в начале документа язык, который мы тут будем использовать». И спустя годы появился официальный документ, описывающий стандарт.

ABNF очень похож на EBNF, за исключением обозначения выбора, опциональных элементов и повторений. Рассмотрим основные отличия.

Имена нетерминалов определены с помощью регулярного выражения \b[A-Za-z][-A-Za-z0-9]+\b. А использование пробельных символов, как это было в первоначальной версии BNF, не допускается. В EBNF напомню пробельные символы в определении синтаксических термов допускались.

Заключение нетерминалов в угловые не является обязательным, но они могут использоваться вокруг нетерминала всякий раз, когда их наличие облегчает распознавание использование имени нетерминала. Для указания выбора используется наклонная черта (/) вместо вертикальной (|). Опциональные элементы обозначаются с использованием символов [ и ]. Символы целевого языка, стали определяться с помощью строк в кавычках.

Для указания повторений используется символ *. Для указания того факта, что элемент или группа элементов должны повторяться n раз используется синтаксис n*. А для указания повторений от n до m раз используется синтаксис n*m. Например следующее определение в EBNF форме:

{ expansion }

в ABNF записывается так:

*( expansion )

Или например, если у нас есть правило описывающее число:

DIGIT =  %x30-39

то, для указания двузначного числа, мы могли бы использовать 2DIGIT.

Для более полного понимания отличий ниже приводится определение даты и времени с использованием ABNF формы. Данный пример получен с RFC5322.

date-time       =   [ day-of-week "," ] date time [CFWS]
day-of-week     =   ([FWS] day-name) / obs-day-of-week
day-name        =   "Mon" / "Tue" / "Wed" / "Thu" /
                    "Fri" / "Sat" / "Sun"
date            =   day month year
day             =   ([FWS] 1*2DIGIT FWS) / obs-day
month           =   "Jan" / "Feb" / "Mar" / "Apr" /
                    "May" / "Jun" / "Jul" / "Aug" /
                    "Sep" / "Oct" / "Nov" / "Dec"
year            =   (FWS 4*DIGIT FWS) / obs-year
time            =   time-of-day zone
time-of-day     =   hour ":" minute [ ":" second ]
hour            =   2DIGIT / obs-hour
minute          =   2DIGIT / obs-minute
second          =   2DIGIT / obs-second
zone            =   (FWS ( "+" / "-" ) 4DIGIT) / obs-zone

Заключение

В заключении хочу сказать, что металингвистические возможности, позволяющие определить грамматику формально, были у множества языков, включая COBOL и FORTRAN 77. Кроме того, существует множество других нотаций, с разной степенью популярности. Однако наиболее распространёнными являются нотации из BNF семейства.

P.S. Функционал комментариев я пока не сделал, поэтому если у вас есть вопросы или комментарии — используйте контактную фому, я отвечу.