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

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) Эта статья написана как руководство или справочник .Пожалуйста, помогите переписать эту статью и удалить советы или инструкции. ( Декабрь 2023 ) Эта статья может оказаться слишком сложной для понимания большинством читателей .Пожалуйста, помогите улучшить его, чтобы сделать его понятным для неспециалистов , не удаляя технические детали. ( Декабрь 2023 )( Узнайте, как и когда удалить это сообщение ) Для проверки данной статьи необходимы дополнительные цитаты .Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденный материал может быть оспорен и удален. Найти источники:  "Backus–Naur form" – новости  · газеты  · книги  · ученый  · JSTOR ( Декабрь 2023 )( Узнайте, как и когда удалить это сообщение ) ( Узнайте, как и когда удалить это сообщение )

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

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

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

 < символ >  ::= __выражение__

где:

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

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

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

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

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

 < почтовый-адрес >  ::=  < часть-имени >  < улица-адрес >  < часть-почтового индекса > < часть-имени >  ::=  < личная-часть >  < фамилия >  < часть-суффикса-опц >  < EOL > | < личная-часть >  < часть-имени > < личная-часть >  ::=  < имя > | < инициал > "." < адрес-улицы >  ::=  < номер-дома >  < название-улицы >  < номер-опт-квартиры >  < EOL > < часть-почтового индекса >  ::=  < название-города > "," < код-штата >  < почтовый-код >  < EOL >< opt-suffix-part >  ::= "Ст." | "Мл." | < римская-цифра > | "" < opt-apt-num >  ::= "Apt" < apt-num > | ""

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

• Почтовый адрес состоит из части, содержащей имя, за которой следует часть, содержащая почтовый адрес , и часть, содержащая почтовый индекс .
• Часть имени состоит либо из личной части, за которой следует фамилия , за которой следует необязательный суффикс (мл., ст. или династический номер) и конец строки , либо из личной части, за которой следует часть имени (это правило иллюстрирует использование рекурсии в БНФ, охватывая случай людей, которые используют несколько имен, отчеств и инициалов). ^[3]
• Личная часть состоит либо из имени , либо из инициалов, за которыми следует точка.
• Почтовый адрес состоит из номера дома, за которым следует название улицы, затем необязательный указатель квартиры и, наконец, конец строки.
• Почтовый индекс состоит из названия города , за которым следует запятая, код штата , затем почтовый индекс и конец строки.
• Часть opt-suffix-part состоит из суффикса, например «Sr.», «Jr.» или римской цифры , или пустой строки (т. е. ничего).
• opt-apt-num состоит из префикса «Apt», за которым следует номер квартиры или пустая строка (т. е. ничего).

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

Идея описания структуры языка с использованием правил переписывания восходит, по крайней мере, к работам Панини , древнеиндийского грамматика санскрита и почитаемого учёного в индуизме, который жил где-то между VI и IV веками до нашей эры . ^{[4] [5]} Его обозначения для описания структуры санскритских слов эквивалентны по мощности обозначениям Бэкуса и имеют много схожих свойств.

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

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

Джон Бэкус , разработчик языка программирования в IBM , предложил метаязык «металингвистических формул» ^{[2] [9] [10]} для описания синтаксиса нового языка программирования IAL, известного сегодня как ALGOL 58 (1959). Его нотация была впервые использована в отчете ALGOL 60.

BNF — это нотация для контекстно-свободных грамматик Хомского. Бэкус был знаком с работой Хомского. ^[11]

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

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

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

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

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

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

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

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

Наур изменил два символа Бэкуса на общедоступные символы. ::=Первоначально символ был a :≡. |Первоначально символ был словом " или " (с чертой над ним). ^{[9] : 14}

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

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

< выражение >  ::=  < термин > | < выражение >< добавление >< термин >

Первым символом альтернативы может быть определяемый класс, повторение, как пояснил Наур, имеет функцию указания того, что альтернативная последовательность может рекурсивно начинаться с предыдущей альтернативы и может повторяться любое количество раз. ^[2] Например, выше <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>. Класс является абстракцией; мы можем говорить о нем независимо от его формирования. Мы можем говорить о термине, независимо от его определения, как о том, что добавляется или вычитается в expr. Мы можем говорить о термине, как о конкретном типе данных, и о том, как expr должен быть оценен с использованием конкретных комбинаций типов данных или даже о переупорядочении выражения для группировки типов данных и результатов оценки смешанных типов. Дополнение на естественном языке предоставило конкретные детали семантики языкового класса, которые будут использоваться реализацией компилятора и программистом, пишущим программу на ALGOL. Описание на естественном языке также дополнительно дополнило синтаксис. Правило целых чисел является хорошим примером естественного и метаязыка, используемого для описания синтаксиса:

< целое число >  ::=  < цифра > | < целое число >< цифра >

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

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

Некоторые, такие как "A Syntax Directed Compiler for ALGOL 60", разработанный Эдгаром Т. Айронсом, и "A Compiler Building System", разработанный Брукером и Моррисом, напрямую использовали BNF. Другие, такие как метакомпиляторы Шорре, превратили его в язык программирования с небольшими изменениями. <class name>стали идентификаторами символов, опустив закрывающий <, >и используя строки в кавычках для символов целевого языка. Арифметико-подобная группировка обеспечила упрощение, которое устранило использование классов, где группировка была его единственным значением. Правило арифметического выражения META II показывает использование группировки. Выходные выражения, помещенные в правило META II, используются для вывода кода и меток на языке ассемблера. Правила в META II эквивалентны определениям классов в BNF. Утилита Unix yacc основана на BNF с созданием кода, аналогичным META II. yacc чаще всего используется как генератор синтаксического анализатора , и его корни, очевидно, являются BNF.

BNF сегодня является одним из старейших языков программирования, используемых до сих пор. ^{[ необходима цитата ]}

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

 < синтаксис >  ::=  < правило > | < правило >  < синтаксис >  < правило >  ::=  < opt-whitespace > "<" < имя-правила > ">" < opt-whitespace > " ::= " < opt-whitespace >  < выражение >  < конец-строки >  < opt-whitespace >  ::= " " < opt-whitespace > | "" < выражение >  ::=  < список > | < список >  < opt-whitespace > "|" < opt-whitespace >  < выражение >  < конец-строки >  ::=  < opt-whitespace >  < EOL > | < конец-строки >  < конец-строки >  < список >  ::=  < термин > | < термин >  < opt-whitespace >  < список >  < термин >  ::=  < литерал > | "<" < имя-правила > ">" < литерал >  ::= '"' < текст1 > '"' | "'" < текст2 > "'" < текст1 >  ::= "" | < символ1 >  < текст1 >  < текст2 >  ::= "" | < символ2 >  < текст2 >  < символ >  ::=  < буква > | < цифра > | < символ >  < буква >  ::="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" < цифра >  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" < символ >  ::= "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~" < символ1 >  ::=  < символ > | "'" < символ2 >  ::=  < символ > | '"' < имя-правила >  ::=  < буква > | < имя-правила >  < символ-правила >  < символ-правила >  ::=  < буква > | < цифра > | "-"

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

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

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

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

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

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

Расширенная форма Бэкуса–Наура (ABNF) и маршрутная форма Бэкуса–Наура (RBNF) ^[16] являются расширениями, обычно используемыми для описания протоколов IETF ( Internet Engineering Task Force ) .

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

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

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

• ANTLR — генератор парсеров, написанный на Java
• Coco/R , генератор компилятора, принимающий атрибутированную грамматику в EBNF
• DMS Software Reengineering Toolkit , система анализа и преобразования программ для произвольных языков
• GOLD , генератор парсеров BNF
• Парсер RPA BNF. ^[17] Онлайн (PHP) демо парсинг: JavaScript, XML
• Система XACT X4MR, ^[18] экспертная система на основе правил для перевода языка программирования
• XPL Analyzer — инструмент, который принимает упрощенную BNF для языка и создает синтаксический анализатор для этого языка в XPL; он может быть интегрирован в поставляемую программу SKELETON, с помощью которой язык может быть отлажен ^[19] ( программа, предоставленная SHARE , которой предшествовал A Compiler Generator ^[20] )
• bnfparser ² , ^[21] универсальная утилита проверки синтаксиса
• bnf2xml, ^[22] Разметка входных данных с тегами XML с использованием расширенного сопоставления BNF
• JavaCC , ^[23] Компилятор Java Compiler tm (JavaCC tm) - Генератор парсеров Java

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

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

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

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