Форма Бэкуса – Наура

Не путать с нормальной формой Бойса-Кодда .

В информатике синтаксиса форма Бэкуса-Наура ( / ˌ b æ k ə s ˈ n aʊər / ) (BNF или нормальная форма Бэкуса ) — это обозначение, используемое для описания языков программирования или других формальных языков . Его разработали Джон Бэкус и Питер Наур . BNF можно описать как метасинтаксическую нотацию для контекстно-свободных грамматик . Форма Бэкуса-Наура применяется везде, где необходимы точные описания языков, например, в спецификациях официальных языков, в руководствах и учебниках по теории языков программирования. BNF можно использовать для описания форматов документов , наборов команд и протоколов связи .

Со временем было создано множество расширений и вариантов исходной нотации Бэкуса – Наура; некоторые из них точно определены, включая расширенную форму Бэкуса-Наура (EBNF) и расширенную форму Бэкуса-Наура (ABNF).

Обзор

BNF описывают, как комбинировать разные символы для создания синтаксически правильной последовательности. БНФ состоят из трех компонентов: набора нетерминальных символов, набора терминальных символов и правил замены нетерминальных символов последовательностью символов. Эти так называемые «правила вывода» записываются как

 <symbol> ::= __expression__

где:

• <symbol> — это нетерминальная переменная, которая всегда заключена между парой <>.
• ::= означает, что символ слева необходимо заменить выражением справа.
• __expression__ состоит из одной или нескольких последовательностей терминальных или нетерминальных символов, где каждая последовательность разделена вертикальной чертой «|». указывает на выбор , причем все это является возможной заменой символа слева.

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

• Инициализируйте последовательность так, чтобы она содержала только один начальный символ.
• Примените правила вывода к этому начальному символу и последующим последовательностям символов.

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

Пример

В качестве примера рассмотрим возможный BNF для почтового адреса в США :

 <postal-address> ::= <name-part> <street-address> <zip-part>

      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part>

  <personal-part> ::= <first-name> | <initial> "."

 <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>

       <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>

<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
    <opt-apt-num> ::= "Apt" <apt-num> | ""

На английский это переводится как:

• Почтовый адрес состоит из части имени, за которой следует часть почтового адреса , за которой следует часть почтового индекса .
• Часть имени состоит либо из личной части, за которой следует фамилия , за которой следует необязательный суффикс (младший старший или династический номер) и конца строки , либо личная часть, за которой следует часть имени (это Правило иллюстрирует использование рекурсии в BNF, охватывая случай людей, которые используют несколько имен, отчества и инициалов).
• Личная часть состоит из имени или инициала , за которым следует точка.
• Уличный адрес состоит из номера дома, за которым следует название улицы, за которым следует необязательный указатель квартиры , за которым следует конец строки.
• Почтовый индекс состоит из названия города , за которым следует запятая, за которой следует код штата , за которым следует почтовый индекс, за которым следует конец строки.
• Часть opt-suffix состоит из суффикса, например «старший», «младший». или римская цифра , или пустая строка (т.е. ничего).
• opt-apt-num состоит из префикса «Apt», за которым следует номер квартиры или пустая строка (т. е. ничего).

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

История

Идея описания структуры языка с помощью правил переписывания восходит, по крайней мере, к работам Панини , древнего индийского грамматика санскрита и уважаемого ученого в индуизме, который жил где-то между 6-м и 4-м веками до нашей эры . Его обозначения для описания структуры санскритских слов эквивалентны по силе обозначениям Бэкуса и имеют много схожих свойств.

В западном обществе грамматика долгое время рассматривалась как предмет преподавания, а не научного изучения; описания были неформальными и ориентированы на практическое использование. В первой половине 20-го века такие лингвисты, как Леонард Блумфилд и Зеллиг Харрис, начали попытки формализовать описание языка, включая структуру фраз .

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

Джон Бэкус , разработчик языка программирования в IBM , предложил метаязык «металингвистических формул». для описания синтаксиса нового языка программирования IAL, известного сегодня как АЛГОЛ 58 (1959 г.). Его обозначения впервые были использованы в отчете ALGOL 60.

BNF — это обозначение контекстно-свободных грамматик Хомского. Бэкус был знаком с работами Хомского.

По предложению Бэкуса, формула определяла «классы», имена которых заключены в угловые скобки. Например, <ab>. Каждое из этих названий обозначает класс основных символов.

Дальнейшее развитие АЛГОЛА привело к созданию АЛГОЛА 60 . В отчете комитета за 1963 год Питер Наур назвал нотацию Бэкуса нормальной формой . Дональд Кнут утверждал, что BNF скорее следует читать как форму Бэкуса-Наура , поскольку это «не нормальная форма в общепринятом смысле слова». в отличие, например, от нормальной формы Хомского . Название «форма Панини Бэкуса» также однажды было предложено ввиду того факта, что нормальная форма расширения Бэкуса может быть неточной, и что Панини ранее независимо разработал аналогичные обозначения.

BNF описан Питером Науром в отчете ALGOL 60 как металингвистическая формула :

Последовательности символов, заключенные в скобки <>, представляют собой металингвистические переменные, значениями которых являются последовательности символов. Знаки "::=" и "|" (последние со значением «или») являются метаязыковыми связками. Любой знак в формуле, не являющийся переменной или связкой, обозначает сам себя. Сопоставление знаков или переменных в формуле означает сопоставление обозначенной последовательности.

Другой пример из отчета ALGOL 60 иллюстрирует основное различие между метаязыком BNF и бесконтекстной грамматикой Хомского. Металингвистические переменные не требуют правила, определяющего их формирование. Их формирование можно просто описать на естественном языке в скобках <>. Следующая спецификация комментариев к разделу 2.3 отчета ALGOL 60 показывает, как это работает:

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

Последовательность основных символов:	эквивалентно
; comment <любая последовательность, не содержащая ';'>;	;
начать комментарий <любая последовательность, не содержащая ';'>;	начинать
end <любая последовательность, не содержащая 'end' или ';' или «еще»>	конец

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

Наур изменил два символа Бэкуса на общедоступные символы. ::= изначально символ был :≡. | Первоначально символом было слово « или » (с чертой над ним).

БНФ очень похож на канонической формы уравнения булевой алгебры , которые в то время использовались при проектировании логических схем. Бэкус был математиком и разработчиком языка программирования FORTRAN. Изучение булевой алгебры обычно является частью учебной программы по математике. Ни Бэкус, ни Наур не описали имена, заключенные в < > как нетерминалы. Терминология Хомского изначально не использовалась при описании БНФ. Позже Наур описал их как занятия по материалам курса ALGOL. В отчете ALGOL 60 они были названы металингвистическими переменными. Все, кроме метасимволов ::=, |и имена классов, заключенные в < > являются символами определяемого языка. Метасимвол ::= следует интерпретировать как «определяется как». | используется для разделения альтернативных определений и интерпретируется как «или». Метасимволы < > являются разделителями, заключающими в себе имя класса. BNF описан как метаязык Питером Науром и Солом Розеном разговоров об АЛГОЛЕ .

В 1947 году Сол Розен стал участвовать в деятельности молодой Ассоциации вычислительной техники , сначала в комитете по языкам, который стал группой IAL и в конечном итоге привел к созданию ALGOL. Он был первым ответственным редактором журнала Communications of ACM. BNF впервые был использован в качестве метаязыка для обсуждения языка АЛГОЛ в отчете АЛГОЛ 60. Именно так это объясняется в материалах курса программирования ALGOL, разработанного Питером Науром в 1962 году. Ранние руководства по АЛГОЛу от IBM, Honeywell, Burroughs и Digital Equipment Corporation следовали за отчетом по АЛГОЛу 60, используя его в качестве метаязыка. Сол Розен в своей книге описывает BNF как метаязык разговоров об АЛГОЛЕ. Примером его использования в качестве метаязыка может быть определение арифметического выражения:

<expr> ::= <term>|<expr><addop><term>

Первым символом альтернативы может быть определяемый класс, повторение, как объяснил Наур, имеет функцию указания того, что альтернативная последовательность может рекурсивно начинаться с предыдущей альтернативы и может повторяться любое количество раз. Например, выше <expr> определяется как <term> за которым следует любое количество <addop> <term>.

Шорра В некоторых более поздних метаязыках, таких как META II , конструкция рекурсивного повтора BNF заменяется оператором последовательности и символами целевого языка, определенными с использованием строк в кавычках. < и > брекеты сняли. Круглые скобки () для математической группировки были добавлены. <expr> правило появится в META II как

EXPR = TERM $('+' TERM .OUT('ADD') | '-' TERM .OUT('SUB'));

Эти изменения позволили META II и производным от него языкам программирования определить и расширить свой собственный метаязык за счет возможности использовать описание естественного языка, металингвистическую переменную и описание языковых конструкций. Многие побочные метаязыки были вдохновлены BNF. См. META II , TREE-META и Metacompiler .

Класс BNF описывает формирование языковой конструкции, причем формирование определяется как шаблон или действие по формированию шаблона. Имя класса expr описывается на естественном языке как <term> за которым следует последовательность <addop> <term>. Класс — это абстракция; мы можем говорить о нем независимо от его формирования. Мы можем говорить о термине, независимо от его определения, как о добавлении или вычитании в выражении. Мы можем говорить о том, что термин представляет собой определенный тип данных и о том, как выражение должно оцениваться с использованием определенных комбинаций типов данных или даже о переупорядочении выражения для группировки типов данных и результатов оценки смешанных типов. Дополнение к естественному языку предоставило конкретные детали семантики языковых классов, которые будут использоваться реализацией компилятора и программистом, пишущим программу ALGOL. Описание на естественном языке также дополняло синтаксис. Правило целых чисел — хороший пример естественного и метаязыка, используемого для описания синтаксиса:

<integer> ::= <digit>|<integer><digit>

Выше нет никаких подробностей о пустом пространстве. Согласно правилу, между цифрами может быть пробел. В естественном языке мы дополняем метаязык БНФ, объясняя, что последовательность цифр не может иметь пробелов между цифрами. Английский — лишь один из возможных естественных языков. Переводы отчетов ALGOL были доступны на многих естественных языках.

Происхождение BNF не так важно, как его влияние на развитие языков программирования. В период сразу после публикации отчета об Алголе 60 BNF был основой многих систем компилятора-компилятора .

Некоторые, такие как «Компилятор с синтаксическим управлением для АЛГОЛА 60», разработанный Эдгаром Т. Айронсом, и «Система построения компилятора», разработанная Брукером и Моррисом, напрямую использовали BNF. Другие, такие как метакомпиляторы Шорре, превратили его в язык программирования лишь с небольшими изменениями. <class name> стали идентификаторами символов, отбросив включающие их <, > и использование строк в кавычках для символов целевого языка. Группировка, подобная арифметике, обеспечивает упрощение, исключающее использование классов, для которых группировка была единственным значением. Правило арифметического выражения META II показывает использование группировки. Выражения вывода, помещенные в правило META II, используются для вывода кода и меток на языке ассемблера. Правила в META II эквивалентны определениям классов в BNF. Утилита Unix yacc основана на BNF, а создание кода аналогично META II. yacc чаще всего используется в качестве генератора синтаксического анализатора , и его корни, очевидно, BNF.

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

Дальнейшие примеры

БНФ Синтаксическая диаграмма

Сам синтаксис BNF может быть представлен с помощью BNF следующим образом:

 <syntax>         ::= <rule> | <rule> <syntax>
 <rule>           ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= " " <opt-whitespace> | ""
 <expression>     ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
 <line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
 <list>           ::= <term> | <term> <opt-whitespace> <list>
 <term>           ::= <literal> | "<" <rule-name> ">"
 <literal>        ::= '"' <text1> '"' | "'" <text2> "'"
 <text1>          ::= "" | <character1> <text1>
 <text2>          ::= "" | <character2> <text2>
 <character>      ::= <letter> | <digit> | <symbol>
 <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"
 <digit>          ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
 <symbol>         ::= "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"
 <character1>     ::= <character> | "'"
 <character2>     ::= <character> | '"'
 <rule-name>      ::= <letter> | <rule-name> <rule-char>
 <rule-char>      ::= <letter> | <digit> | "-"

Обратите внимание, что «» — это пустая строка .

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

<EOL> представляет соответствующий спецификатор конца строки (в ASCII , возврат каретки, перевод строки или и то, и другое, в зависимости от операционной системы ). <rule-name> и <text> должны быть заменены именем/меткой или буквальным текстом объявленного правила соответственно.

В приведенном выше примере почтового адреса США вся блок-кавычка представляет собой <syntax>. Каждая строка или непрерывная группа строк — это правило; например одно правило начинается с <name-part> ::=. Другая часть этого правила (кроме конца строки) представляет собой выражение, состоящее из двух списков, разделенных вертикальной чертой. |. Эти два списка состоят из нескольких терминов (три термина и два термина соответственно). Каждый термин в этом конкретном правиле является именем правила.

Варианты

ЕБНФ

Основная статья: Расширенная форма Бэкуса – Наура

Существует множество вариантов и расширений BNF, как правило, либо ради простоты и краткости, либо для адаптации к конкретному приложению. Одной из общих черт многих вариантов является использование операторов повторения регулярных выражений, таких как * и +. Расширенная форма Бэкуса-Наура (EBNF) является распространенной.

Еще одним распространенным расширением является использование квадратных скобок вокруг необязательных элементов. Хотя эта нотация не присутствовала в исходном отчете по ALGOL 60 (вместо этого была введена несколько лет спустя в IBM определении PL/I ), теперь она общепризнана.

АБНФ

Основная статья: АБНФ

Расширенная форма Бэкуса-Наура (ABNF) и форма Бэкуса-Наура маршрутизации (RBNF) — это расширения, обычно используемые для описания Инженерной группы Интернета (IETF) протоколов .

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

Другие

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

• Необязательные элементы, заключенные в квадратные скобки: [<item-x>].
• Элементы, существующие 0 или более раз, заключаются в фигурные скобки или заканчиваются звездочкой ( *) такой как <word> ::= <letter> {<letter>} или <word> ::= <letter> <letter>* соответственно.
• К элементам, существующим 1 или более раз, добавляется символ сложения (плюс). +, такой как <word> ::= <letter>+.
• Терминалы могут быть выделены жирным шрифтом, а не курсивом, а нетерминалы - обычным текстом, а не угловыми скобками.
• Если элементы сгруппированы, они заключаются в простые круглые скобки.

Программное обеспечение, использующее BNF или варианты

Программное обеспечение, которое принимает BNF (или его расширенный набор) в качестве входных данных.

• ANTLR , генератор парсера, написанный на Java.
• Coco/R , генератор-компилятор, принимающий атрибутивную грамматику в EBNF
• DMS Software Reengineering Toolkit , система анализа и преобразования программ для произвольных языков
• GOLD — генератор парсера BNF.
• RPA-парсер BNF. Онлайн-парсинг демо-версии (PHP): JavaScript, XML
• Система XACT X4MR, основанная на правилах экспертная система для перевода языков программирования
• XPL Analyser — инструмент, который принимает упрощенный BNF для языка и создает синтаксический анализатор для этого языка в XPL; его можно интегрировать в поставляемую программу SKELETON, с помощью которой можно отлаживать язык. ( программа, предоставленная SHARE , которой предшествовал A Compiler Generator )
• бнфпарсер ² , универсальная утилита проверки синтаксиса
• бнф2xml, Разметка ввода с помощью XML-тегов с использованием расширенного сопоставления BNF.
• JavaCC , Компилятор Java Compiler tm (JavaCC tm) — генератор синтаксического анализатора Java

Подобное программное обеспечение

• GNU bison , GNU-версия yacc
• Yacc , генератор синтаксического анализатора (чаще всего используется с препроцессором Lex )
• Инструменты парсера Racket , синтаксический анализ в стиле lex и yacc (версия Beautiful Racket)
• Qlik Sense, инструмент бизнес-аналитики, использует вариант BNF для написания сценариев.
• Конвертер BNF (BNFC ), работающий на варианте, называемом «меченой формой Бэкуса – Наура» (LBNF). В этом варианте каждому произведению данного нетерминала присваивается метка, которую можно использовать в качестве конструктора алгебраического типа данных, представляющего этот нетерминал. Конвертер способен создавать типы и анализаторы абстрактного синтаксиса на нескольких языках, включая Haskell и Java.

См. также

• Дополненная форма Бэкуса – Наура (ABNF)
• Язык описания компилятора (CDL)
• Грамматика определенного предложения – более выразительная альтернатива BNF, используемая в Прологе.
• Расширенная форма Бэкуса – Наура (EBNF)
• Meta-II - ранний инструмент для написания компиляторов и обозначений.
• Синтаксическая диаграмма – схема железной дороги
• Трансляционная форма Бэкуса – Наура (TBNF)
• Грамматика Ван Вейнгаардена - используется вместо BNF для определения Algol68.
• Синтаксическая нотация Вирта - альтернатива BNF 1977 года.

Внешние ссылки

• Гаршол, Ларс Мариус, БНФ и ЕБНФ: Что это такое и как они работают? , НЕТ : Приват .
• RFC   5234 — Расширенный BNF для спецификаций синтаксиса: ABNF.
• RFC   5511 — Маршрутизация BNF: синтаксис, используемый в различных спецификациях протоколов.
• ISO/IEC 14977:1996(E) Информационные технологии. Синтаксический метаязык. Расширенный BNF , доступен по адресу: «Общедоступно», Стандарты , ISO или из Кун, Маркус, Iso 14977 (PDF) , Великобритания : CAM (у последнего отсутствует титульная страница, но в остальном он намного чище)

Языковые грамматики

• Бернхард, Алгол-60 БНФ , DE : LRZ Мюнхен , оригинальный БНФ.
• «Грамматики BNF для SQL-92, SQL-99 и SQL-2003», Savage , AU : Net , свободно доступные грамматики BNF для SQL .
• «Веб-клуб BNF», исследование БД , CH : Unige, заархивировано из оригинала 24 января 2007 г. , получено 25 января 2007 г. , свободно доступные грамматики BNF для SQL, Ada , Java .
• «Грамматики языка свободного программирования для построения компиляторов», Исходный код , Свободная страна , свободно доступные грамматики BNF/ EBNF для C/C++, Pascal , COBOL , Ada 95 , PL/I .
• «Файлы BNF, относящиеся к стандарту STEP», движок Exp ( SVN ), Source forge, заархивировано из оригинала 25 декабря 2012 г. Включает части 11, 14 и 21 стандарта ISO 10303 (STEP).