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

В этой статье объясняются грамматики и общие системы описания грамматик, такие как BNF, EBNF и ABNF. Данный текст не претендует на академическую точность и носит скорее ознакомительный, вводный характер.

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

Статья разбита на несколько частей. Это первая часть, а здесь вторая.

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

Мотивация

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

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

Вы занимаетесь разработкой статического анализатора кода
Вы занимаетесь разработкой языка программирования, разметки, описания и т.п.
Вы хотели бы добавить новые возможности в текущий язык
Вы занимаетесь анализом некоторого текста, например HTTP заголовков
Вы разрабатываете поддержку некоторого языка в Emacs, ItelliJ, Atom и т.п.
Вы разрабатываете новый шаблонизатор для вашего веб-фреймворка
Вы хотели бы разработать клиент для обмена сообщениями с некоторым демоном, но для этого нужно научится читать из сокета, куда пишет демон
Вы хотели бы иметь возможность «конвертировать» код на исходном языке из одной версии этого языка, в другую или даже в другой целевой язык
Вы хотели бы глубже изучить используемый язык
Все те области деятельности, где вы часто употребляете слово «распарсить»

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

Определение языка

В информатике языки определяют область вычислений. Например, областью вычислений языка SQL является база данных, а HTML используется как язык разметки веб-страницы.

Языки программирования, спецификация протоколов, языки запросов, форматы файлов, языки шаблонов, формальные языки, конфигурационные файлы, языки разметки, языки форматирования и мета-языки определяют способ, которым мы проводим вычисления. Все они накладывают некоторые требования (ограничения) к способу и области вычислений, фактически формируя то, как мы эти вычисления производим.

А что формирует сами языки? Что накладывает на них ограничения и диктует правила? Языки определяются двумя вещами: синтаксисом и семантикой. Под синтаксисом обычно понимают то, что с помощью языка можно выразить (сказать, написать), а семантика — это как следует интерпретировать выраженное. В идеальном мире и синтаксис, и семантика должны быть формально определены. Когда в контексте языков говорят формально, то подразумевают некоторое абстрактное описание, не привязанное к какой-либо реализации.

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

Описанием синтаксиса занимаются грамматики. Грамматики являются языками языков. За каждым языком стоит своя грамматика, которая определяет его структуру и набор допустимых лексем. Язык не может выйти за рамки своей грамматики и полностью ею формируется. Грамматика однозначно определяет язык, но один и тот же язык может быть порождён разными грамматиками.

Лингвистики Панини

Саму идею, как то описать и определить язык можно проследить по крайней мере до работ Панини (Pāṇini), жившего предположительно около V века до н. э. и ставшего предтечей современной структурной лингвистики, порождающей грамматики, семиотики и логики. Сегодня о Панини мало что достоверно известно.

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

Грамматика Панини пытается вывести полную, максимально лаконичную и подкрепленную теоретической частью систему анализа грамматической структуры санскрита. Говоря простым языком — формализовать системный и непротиворечивый подход для грамматического анализа санскрита. Она является основанием всех традиционных и современных систем анализа санскрита и заслужила не малый интерес с исторической и теоретической точки зрения. Западная теория грамматики испытывала влияние грамматики Панини на каждом этапе своего развития на протяжении двух последних веков. В начале 19 века, сторонники сравнительного подхода, увидели в этой грамматике принципы морфологического анализа. А выдающийся лингвист XX века, Леонард Блумфилд (Leonard Bloomfield), известный трудами по индоевропеистике, тагальскому языку, алгонкинским языкам, общей морфологии и общей теории языка, использовал грамматику Панини в своей классической работе по моделированию алгонкинской грамматики.

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

Более подробно ознакомится с лингвистикой Панини можно в работе Пола Кипарский (Paul Kiparsky) The Encyclopedia of Language and Linguistics.

Наши дни

Нотация Панини, по силе эквивалентна нотации, которую уже в наше время разработал Джон Бэкус, и имеет много схожих свойств.

По широко известной классификации Ноама Хомского, существует четыре вида грамматик:

Неограниченная
Контекстно-зависимая
Контекстно-свободная
Регулярная

В информатике наиболее распространённым типом грамматики является контекстно-свободная грамматика. Смысл термина «контекстно-свободная» заключается в том, что контекстно-свободные языки не позволяют выражать зависимость от контекста. Например в языке Си, выражение a * b, в зависимости от значений a и b может означать объявление указателя, либо мультипликативное выражение. Контекстно-свободные грамматики являются ниспадающими, то есть некоторые объекты, обозначающие какую-либо сущность языка выражают в терминах других объектов, которые в свою очередь, можно выразить в терминах третьих объектов и так далее.

И в этой статье мы сфокусируемся именно на таких грамматиках. Контекстно-свободные грамматики достаточно богаты, чтобы описать рекурсивную синтаксическую структуру многих (хотя, конечно же, не всех) языков.

Компоненты контекстно-свободной грамматики

Основным компонентом грамматики является набор правил.

Каждое правило имеет 2 части: (1) имя и (2) во что это имя разворачивается (расширяется) или другими словами, через что это имя определяется.

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

существительное-фраза (1) может выражаться через артикль существительное (2)

Вот так просто: сначала идёт артикль, а за ним идёт существительное. Из чего в конечном итоге мы можем сделать вывод, что «the dog» это существительное-фраза. Или, если мы описываем алгебраическое выражение, мы могли бы определить правило вроде этого:

expression может выражаться через digit + digit (2 + 3)

Здесь я сознательно упростил пример. Известно, что например символ 5 можно интерпретировать как выражение (expression), значением которого является число 5. С другой стороны, последовательность символов 5 + 5 так же можно интерпретировать как выражение, но более сложное. В канонических текстах предыдущий пример записывают так:

expression может выражаться через expression + expression

Когда мы работаем с грамматическими элементами как с математическими объектами, то вместо написания «может выражаться через» или «определяется как» мы просто используем стрелку →:

существительное-фраза → артикль существительное
expression → expression + expression

Определение, которое стоит по правую сторону от стрелки, может быть и сложнее. Например, если мы посмотрим на формулу площади равнобедренного треугольника:

S = 1/2 * a^2 * sin α

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

S → expression
expression → expression * expression

Выражение одного объекта чрез другой принято называть продукцией. Главное практическое условие при составлении грамматики — она должна быть полной, то есть описывать все возможные ситуации входного потока.

В качестве примера рассмотрим классическую грамматику однозначного выражения:

expr → term + expr
expr → term

term → term ∗ factor
term → factor

factor → (expr)
factor → const

const → integer

Первая и вторая строки описывают две возможные ситуации входного потока:

expr выражается через term, за которым следует символ +, за которым следует expr
expr выражается через term

По другому на это можно смотреть так: выражение (term) это либо (1) либо (2). Шаг за шагом мы выражаем «сложное» через «более простое». Хотя на практике это и не всегда так — мы можем выражать один объект через другой, не обязательно являющийся более простым.

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

Выведем правило:

Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение.
Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

Итак, как же мы можем понять, что запись 3 * 7 является допустимым алгебраическим выражением, используя выше определённую грамматику? Мы просто произведём некоторое количество продукций, конечным результатом которых будет доказательство, что мы имеем дело с допустимым выражением:

Мы знаем, что expr может выражаться через term
Что, в свою очередь может выражаться через term ∗ factor
Что может выражаться через factor ∗ factor
Что может выражаться через const ∗ factor
Что может выражаться через const ∗ const
Что может выражаться через 3 ∗ const
Что может выражаться через 3 ∗ 7

За 7 шагов продукции мы доказали, что 3 * 7 является допустимым выражением. При определённой сноровке, мы могли бы произвести эти шаги в обратном порядке.

Важно отметить, что в любой грамматике, в т.ч. и в контекстно-свободной, обязательно должен быть стартовый нетерминал. Самая высокая абстракция, то, с чего всё начинается.

BNF нотация

Историческая справка

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

Как гласит Wikipedia, правила трансформации строк, в виде формальных абстрактных систем были введены и изучены такими математиками как Аксель Ту (в 1914 году), Эмиль Пост (1920–40-е годы) и Алан Тьюринг (1936). Ноам Хомский, преподающий лингвистику студентам теории информации в Массачусетском технологическом институте, объединил лингвистику и математику в 1956 году, взяв за основу то, что по существу является формализмом Ту, для описания синтаксиса естественного языка. Он также ввел четкое различие между порождающими правилами и правилами преобразования текста.

BNF нотация впервые стала использоваться в качестве метаязыка для описания языка программирования ALGOL, позднее представленном в отчете ALGOL 60. Джон Бэкус, разработчик языков программирования ALGOL и FORTRAN, работавший в то время в IBM, предложил метаязык «металингвистических формул» для описания синтаксиса языка программирования IAL, известного сегодня как ALGOL 58 (1959). Суть предложенного метаязыка - нотация для контекстно-свободных грамматик Хомского. Видимо, Бэкус был знаком с работой Хомского.

Уже позже, в 1963 году, Питер Наур в отчёте комитета по языку ALGOL называл эту нотацию нормальной формой Бэкуса (Backus Normal Form), но Дональд Кнут утверждал, что BNF следует скорее читать как форму Бэкуса-Наура, так как она не является нормальной формой в общепринятом смысле, указывая на некоторые изменения, которые ввёл Наур.

Вот так и появилась нотация для контекстно-свободных грамматик Хомского названая BNF (Backus-Naur Form, Форма Бэкуса — Наура). Множество языков программирования, форматов или протоколов имеют BNF-описание в своей спецификации. Формальная природа этой нотации указывает на то, что мы можем её использовать где угодно. Для того, чтобы составить BNF-описание, нам нужен только текстовый редактор (или лист бумаги) — она не привязана к какому-либо языку программирования. Хотя разумеется, существуют модификации в том или ином виде, удобные в конкретном языке.

Ниже мы будем рассматривать именно эту версию BNF, впервые появившуюся в языке ALGOL в 1958 году и скорректированную в отчёте ALGOL 60.

Определение BNF

Итак, каждое правило в форме Бэкуса — Наура имеет следующую структуру:

<имя> ::= <замещение>

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

Каждый нетерминал (в примере выше — имя) в форме Бэкуса — Наура — это последовательность символов, заключенная в угловые скобки < >, независимо от того, указан он слева или справа от правила. Нетерминал представляет собой металингвистическую переменную, значением которой является последовательность символов.

Символ ::= означает «определяется как», «может быть замещено этим» или «выражается через». В ранней версии BNF, вместо этого символа использовался :≡.

Под терминальным символом, понимают литерал (типа + или begin) либо литеральный класс (типа integer), словом то, что имеет конкретное значение и может быть однозначно и не противоречиво выражено посредством языка.

В свою очередь замещение — это выражение, которое может содержать терминалы и / или нетерминалы, объединённые посредством последовательности или выбора. Непосредственное соседство нетерминалов и / или терминалов в формуле означает последовательность в том виде, в котором она была определена. А вертикальная черта | обозначает выбор (или).

Символы ::= и | называются металингвистическими связками (connectives). А всё выражение от начала и до конца строки — металингвистической формулой.

В BNF допускалось использование пробельных символов как например:

<relational operator>

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

<any sequence of symbols not containing ` or ' >

Фактически правила именования нетерминалов описывается регулярным выражением [:print:] за исключением переноса строк, что позволяло писать целые поэмы, заключённые в угловые скобки. В будущих инкарнациях и модификациях это правило не получило широкого распространения и было сокращено до регулярного выражения: \b[A-Za-z][-A-Za-z0-9]+\b. Одно остаётся неизменным и по сей день — имена нетерминалов не являются чувствительными к регистру: <rulename>, <Rulename>, <RULENAME> и <rUlENamE> считаются одним и тем же.

Следует отметить, что в отчёте ALGOL 60 использовалось обозначение or «подчёркнутое» сверху вместо вертикальной черты (|). Мне даже удалось видеть раннюю версию отчёта и это обозначение, как и :≡, написано там от руки, хотя весь остальной текст набран на печатной машинке. Вообще, к слову говоря, в отчёте очень много закорючек написано от руки. А сам отчёт следовало рассматривать под тремя точками зрения:

Целевой язык, собственно сам ALGOL. То, что описывал BNF
Язык публикации, тот набор символов который использовался при оформлении документации
Аппаратное (программное) представление, которое могло отличаться в выборе символов

Как говорилось в самом отчёте, символы в отчёте (2) определяются легкостью понимания, а не какими-либо компьютерными ограничениями, обозначениями кодировок или чисто математическими обозначениями.

Для полноты примера рассмотрим формат почтовых индексов Канады. Ниже представлены 3 примера таких индексов:

K1N 6N5
M5W 2E4
X0A 1A1

Для того, чтобы описать этот формат, мы могли бы использовать следующую формулу:

<postalcode> ::= <letter> <number> <letter> <number> <letter> <number>

Здесь мы видим, как именно в грамматике выражается последовательность — мы просто помещаем один объект за другим, в том порядке, в котором они грамматически верны. Кстати в документах того времени, не только по BNF, часто встречалось выражение «конкатенация», вместо «последовательная запись».

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

<postalcode> ::= <alnum> <alnum> <alnum>

<alnum> ::= <letter> <number>

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

; expr может быть выражен через term + expr
; или через term

  <expr> ::= <term> | <expr> + <term>
  <term> ::= <factor> | <term> * <factor>
<factor> ::= ( <expr> ) | <const>

Тут мы использовали последовательности и элементы выбора (|). Фактически, первая строка может читаться как expr может быть выражен через term или через expr + term. В декоративных целях правила выровнены по левой стороне, это допустимо. Обратите внимание, BNF нотация допускает использование комментариев. Комментарий начинается с символа ; и заканчивается в конце строки.

Терминалами в BNF грамматиках служат лексемы, которые означают сами себя (например +, switch или <<=) или имя литерального класса (например integer). Имена литеральных классов обычно выражают другими средствами, такими как регулярные выражения.

Для более детального ознакомления с понятием рекурсивных определений возьмём еще один пример, встречающийся в отчёте ALGOL 60:

<ab> ::= ( | [ | <ab> ( | <ab> <d>

Эта формула определяет рекурсивное правило для формирования значения <ab>. Она указывает на то, что значением <ab> может быть либо (, либо [, либо, если дано какое-то допустимое значение <ab>, может быть сформировано другое значение, за которым следует ( или некоторое значение нетерминала <d>. Например, если значения <d> являются десятичными числами, то вот некоторые допустимые значения <ab>:

[(((1(37(
(12345(
(((
[86

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

<identifier> ::= <prefix> | <letter> | <identifier> <digit> | <identifier> <letter>
    <prefix> ::= _ | $
     <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    <letter> ::= ...

Здесь опущено определение <letter> для краткости. Итак, о чём говорит это правило? Некий идентификатор, который мы можем использовать как правило для имён переменных, должен начинаться с символа подчёркивания (_), знака доллара ($) или буквы (<letter>); последующие символы могут быть всем тем же самым или цифрами (0-9).

Обычно при составлении грамматики формально, вводят некоторый набор зарезервированных и заранее оговорённых лексем. Рассмотрим пример некоторых из них. Их лексикографическое представление говорит само за себя, однако справа я поместил комментарии, чтобы вы поняли, как в то время было принято оформлять подобные блоки.

        <empty> ::= ; пустая строка
          <eol> ::= ; представляет соответствующий системе спецификатор конца строки
        <space> ::= ; пробел
      <comment> ::= ; символ начала комментария ;
<connective-eq> ::= ; металингвистическая связка ::=
<connective-or> ::= ; металингвистическая связка |

Обычно между ::= и ; вставлялся ещё один нетерминал, типа <any sequence not containing ;>. Так как это ещё не код, а всего лишь спецификация, то это допустимо:

<any sequence not containing ;>

Ну и конечно, если бы мы захотели определить грамматику для самих правил BNF, она бы выглядела как-то так:

 <syntax>         ::= <rule> | <rule> <syntax>
 <rule>           ::= <opt-whitespace> < <rule-name> > <opt-whitespace>
                      <connective-eq> <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= <space> <opt-whitespace> | <empty>
 <expression>     ::= <list> | <list> <opt-whitespace> <connective-or> <opt-whitespace>
                      <expression>
 <line-end>       ::= <opt-whitespace> <eol> | <line-end> <line-end>
 <list>           ::= <term> | <term> <opt-whitespace> <list>
 <term>           ::= <literal> | < <rule-name> >
 <literal>        ::= <text>
 <text>           ::= <empty> | <character> <text>
 <character>      ::= <letter> | <digit> | <symbol>
 <rule-name>      ::= <letter> | <rule-name> <rule-char>
 <rule-char>      ::= <letter> | <digit> | -

 <digit>          ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

 <symbol>         ::= <connective-or> | <space> | <comment> | # | $
                    | + | , | - | . | / | : | ! | > | = | <
                    | ? | @ | [ | \ | ] | ^ | _ | ` | ' | " | { | }
                    | ~ | % | & | ( | ) | *

 <letter>         ::= A | B | C | D | E | F | G | H | I | J
                    | K | L | M | N | O | P | Q | R | S | T
                    | U | V | W | X | Y | Z | a | b | c | d
                    | e | f | g | h | i | j | k | l | m | n
                    | o | p | q | r | s | t | u | v | w | x
                    | y | z

Здесь <rule-name> и <text> должны быть заменены объявленным именем/меткой правила или литеральным текстом, соответственно.

Непосредственно в отчёте ALGOL 60, для указания природы терменированности, лексемы if, then, а так же любые другие терминалы в документе просто подчёркивались. Это вводило некоторое ограничение на список допустимых лексем. Так, в отчёте рекомендуется не использовать зарезервированные для математических операций лексемы типа abs, sign, cos и т.п. Однако позже, в дальнейших модификациях BNF это не прижилось. Хотя справедливости ради следует отметить, что в формальной грамматике теории формальных языков это именно так и записывается:

ЦИФРА → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

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

<rule> ::= "A" | "B" | "C"

Однако в оригинальном BNF не было никаких строк, да и типов данных как таковых, в принципе. Так что все эти примеры, которые вы можете встретить, не являются оригинальным BNF.

Для того чтобы описать все возможные терминалы, наша грамматика использует их полное перечисление, что может быть несколько неудобным и делает нотацию «разговорчивой». Обычной практикой является введение символьного класса, обозначающего перечисление. Перенос строки считается окончанием правила. Если правило необходимо разбить на несколько строк, то продолжение правила пишут с отступом относительно строки вводящей нетерминал. Продолжение правила с нулевым отступом в BNF не допускается:

<proper string> ::=
        <any sequence of symbols not containing ` or ' >
        | <empty>

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

<foo> ::= <bar>
    | <baz>
        | <buz>

Более или менее конкретное описание отступов есть в RFC5234, однако тот документ описывает ABNF, о котором речь пойдёт во второй части.

На этом первая часть нашей с вами экскурсия в мир BNF грамматик заканчивается.

Заключение

Всё, что мы с вами рассмотрели в этой статье, фактически полностью описывает BNF нотацию. Но используя только представленный набор символов и средств, не возможно описать сколько-нибудь мощный язык программирования, ввиду того, что BNF - это формальная система описания грамматик. То, с помощью чего вы сможете создать спецификацию, а не конкретную реализацию. Относитесь к ней как к спецификации, которую будет читать программист. В конкретной реализации вы обязательно столкнётесь с тем, что вам нужно определить программно непечатаемые символы, обозначить окончания строк, пустые строки, NULL. Вероятно, также вы не будете перечислять все буквы в <letter>, а воспользуетесь регулярным выражением или литеральным классом и т.д. На практике, грамматике помогают некоторыми программными решениями. В качестве примера предлагаю взглянуть на Grammar-Kit от JetBrains.

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

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