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

В информатике , Backus-Наура ^{[ произношение? ]} Или Бакус нормальная форма ( BNF ) является metasyntax обозначения для контекстно-свободных грамматик , часто используется для описания синтаксиса из языков , используемых при вычислении, таких как компьютерные языки программирования , форматы документов , наборы команд и протоколы связи . Они применяются везде, где необходимы точные описания языков: например, в спецификациях официальных языков, в руководствах и учебниках по теории языков программирования.

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

История [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Наур заменил два символа Бэкуса общедоступными. Первоначально ::=символ был :≡. Первоначально |символом было слово « или » (с полосой над ним). ^{[6] : 14 [ требуется пояснение ]} Работая в IBM, Бэкус заключил бы соглашение о неразглашении и не мог бы говорить о своем источнике, если бы он исходил из частного проекта IBM. ^{[ необходима цитата ]}

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

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

< выражение >  :: =  < термин > | < expr > < addop > < term >

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

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

EXPR = TERM $ ('+' TERM .OUT ('ДОБАВИТЬ') | '-' TERM .OUT ('SUB'));

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

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

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

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

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

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

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

Введение [ править ]

Спецификация BNF - это набор правил деривации, записанный как

 < символ >  :: = __expression__

где < символ > ^[5] - нетерминал , а __expression__ состоит из одной или нескольких последовательностей символов; другие последовательности разделены вертикальной чертой «|», указывающей на выбор , причем целиком является возможная замена символа слева. Символы, которые никогда не появляются слева, являются терминалами . С другой стороны, символы, которые появляются слева, не являются терминалами и всегда заключены между парой <>. ^[5]

«:: =» означает, что символ слева необходимо заменить выражением справа.

Пример [ править ]

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

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

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

• Почтовый адрес состоит из части имени, за которой следует часть почтового адреса , за которой следует часть почтового индекса .
• Часть имени состоит либо из: личной-части, за которой следует фамилия, за которой следует необязательный суффикс (младший, старший или династический номер) и конца строки , либо личная часть, за которой следует часть имени ( это правило иллюстрирует использование рекурсии в BNF, охватывая случай людей, которые используют несколько имен, отчеств и инициалов).
• Личная-часть состоит из имени или инициала, за которым следует точка.
• Уличный адрес состоит из номера дома, за которым следует название улицы, за которым следует необязательный указатель квартиры , за которым следует конец строки.
• Почтовый индекс состоит из названия города , за которым следует запятая, за которым следует код штата , за которым следует почтовый индекс, за которым следует конец строки.
• Часть opt-суффикса состоит из суффикса, например "Sr.", "Jr." или римская цифра , или пустая строка (т. е. ничего).
• Opt-apt-num состоит из номера квартиры или пустой строки (т. Е. Ничего).

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

Дальнейшие примеры [ править ]

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

 < синтаксис >  :: =  < правило > | < правило >  < синтаксис >  < правило >  :: =  < opt-whitespace > "<" < имя-правила > ">" < opt-whitespace > " :: = " < opt-whitespace >  < выражение >  < конец строки >  < opt-whitespace >  :: = "" <opt-whitespace > | "" <выражение >  :: =  < список > | < список >  < opt-whitespace > "|" < opt-whitespace >  < выражение >  < конец строки >  :: =  < opt-whitespace >  < EOL > | < Конца строки >  < конца строки >  < список >  :: =  < терм > | < термин >  <opt-whitespace >  <список >  < термин >  :: =  < литерал > | "<" < имя-правила > ">" < литерал >  :: = '"' < text1 > '"' | "'" < text2 > "'" < text1 >  :: = "" | < Character1 >  < text1 >  < text2 >  :: = '' | <character2 >  < text2 >  < символ > :: =  < буква > | < цифра > | < символ >  < буква >  :: = "A" | «Б» | "C" | «Д» | "E" | "F" | "G" | "H" | «Я» | "J" | «К» | "L" | «М» | «N» | «О» | «П» | «Q» | «Р» | "S" | «Т» | "U" | "V" | "W" | «Х» | «Y» | "Z" | "а" | "б" | "с" | "д" | "е" | "е" | "г" | "h" | «я» | "j" | "к" | " 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» | «3» | «4» | «5» | «6» | «7» | «8» | "9" < символ > :: =| «1» | «2» | «3» | «4» | «5» | «6» | «7» | «8» | "9" < символ > :: = "|" | "" | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | «+» | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | «[» | "\" | "]" | "^" | "_" | "` "| "{" | "}" | "~" < символ1 >  :: =  < символ > | "'" < символ2 >  :: =  < символ > | '"' <имя-правила >  :: =  < буква > | < имя-правила >  < символ-правила >  < символ-правила >  :: =  < буква > | <цифра > | "-"

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

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

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

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

Варианты [ править ]

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

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

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

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

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

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

Программное обеспечение с использованием BNF [ править ]

• ANTLR , еще один генератор парсеров, написанный на Java
• Qlik Sense, инструмент бизнес-аналитики , использует вариант BNF для написания сценариев.
• Конвертер BNF (BNFC ^[14] ), работающий на варианте, называемом «помеченная форма Бэкуса – Наура» (LBNF). В этом варианте каждому продукту для данного нетерминала дается метка, которую можно использовать в качестве конструктора алгебраического типа данных, представляющего этот нетерминал. Конвертер может создавать типы и синтаксические анализаторы для абстрактного синтаксиса на нескольких языках, включая Haskell и Java.
• Coco / R , компилятор-генератор, принимающий атрибутивную грамматику в EBNF
• DMS Software Reengineering Toolkit , система анализа и преобразования программ для произвольных языков
• Парсер GOLD BNF
• GNU bison , версия yacc для GNU
• Парсер RPA BNF. ^[15] Разбор демонстрации онлайн (PHP): JavaScript, XML
• XACT X4MR System, ^[16] основанная на правилах экспертная система для перевода языков программирования.
• XPL Analyzer, инструмент, который принимает упрощенный BNF для языка и создает синтаксический анализатор для этого языка в XPL; он может быть интегрирован в поставляемую программу SKELETON, с помощью которой язык может быть отлажен ^[17] ( программа, предоставленная SHARE , которой предшествовал A Compiler Generator , ISBN  978-0-13-155077-3 )
• Yacc , генератор парсеров (чаще всего используется с препроцессором Lex )
• bnfparser ² , ^[18] универсальная утилита проверки синтаксиса
• bnf2xml, ^[19] Разметка входных данных с помощью тегов XML с использованием расширенного соответствия BNF.
• JavaCC, ^[20] Java Compiler Compiler tm (JavaCC tm) - Генератор синтаксического анализатора Java.
• Инструменты синтаксического анализатора Racket, синтаксический анализ в стиле lex и yacc (версия Beautiful Racket)
• Belr , Генератор парсеров, написанный на C ++ 11. Он использует ABNF .

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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

Языковые грамматики [ править ]

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