Форма Бэкуса – Наура - Backus–Naur form

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

В Информатика, Форма Бэкуса – Наура или Бэкус нормальная форма (BNF) это метасинтаксис обозначение для контекстно-свободные грамматики, часто используется для описания синтаксис из языки используется в вычислениях, таких как компьютер языки программирования, форматы документов, наборы инструкций и протоколы связи. Они применяются везде, где требуется точное описание языков: например, в спецификациях официальных языков, в руководствах и в учебниках по теории языков программирования.

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<expr> ::= <срок>|<expr><аддоп><срок>

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

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

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

Эти изменения позволили META II и производным от нее языкам программирования определить и расширить свой собственный метаязык за счет возможности использовать описание на естественном языке, металингвистическую переменную, описание языковой конструкции. Многие побочные метаязыки были вдохновлены BNF.[нужна цитата ] Увидеть МЕТА II, ДЕРЕВО-МЕТА, и Метакомпилятор.

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

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

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

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

Некоторые, например "Компилятор с синтаксической ориентацией для ALGOL 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 для США. почтовый адрес:

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

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

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

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

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

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

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

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

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

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

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

Варианты

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

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

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

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

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

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

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

  • ANTLR, еще один генератор парсеров, написанный на Ява
  • Qlik Sense, инструмент бизнес-аналитики, использует вариант BNF для написания сценариев.
  • Конвертер BNF (BNFC[14]), оперируя вариантом, называемым «меченой формой Бэкуса – Наура» (LBNF). В этом варианте каждому продукту для данного нетерминала дается метка, которую можно использовать как конструктор алгебраический тип данных представляющий этот нетерминал. Конвертер может создавать типы и парсеры для абстрактный синтаксис на нескольких языках, в том числе Haskell и Java.
  • Коко / Р, генератор компилятора, принимающий атрибутивную грамматику в EBNF
  • Набор инструментов для реинжиниринга программного обеспечения DMS, система анализа и преобразования программ для произвольных языков
  • ЗОЛОТО Парсер BNF
  • GNU bison, GNU-версия yacc
  • Парсер RPA BNF.[15] Разбор демонстрации онлайн (PHP): JavaScript, XML
  • Система XACT X4MR,[16] основанная на правилах экспертная система для перевода языков программирования
  • XPL Анализатор, инструмент, который принимает упрощенный BNF для языка и создает синтаксический анализатор для этого языка в XPL; он может быть интегрирован в прилагаемую программу SKELETON, с помощью которой язык может быть отлажен[17] (а ДОЛЯ внесенная программа, которой предшествовала Генератор компилятора, ISBN  978-0-13-155077-3)
  • Yacc, генератор парсеров (чаще всего используется с Лекс препроцессор)
  • bnfparser2,[18] универсальная утилита проверки синтаксиса
  • bnf2xml,[19] Разметка ввода с помощью тегов XML с использованием расширенного соответствия BNF.
  • JavaCC,[20] Компилятор Java Compiler Compiler tm (JavaCC tm) - Генератор парсера Java.
  • Инструменты парсера Racket, lex и yacc-style Parsing (Beautiful Racket edition)
  • Belr, Генератор парсера, написанный на C ++ 11. Оно использует ABNF.

Смотрите также

использованная литература

  1. ^ "Биография Панини". Школа математики и статистики Университета Сент-Эндрюс, Шотландия. Получено 2014-03-22.
  2. ^ Ингерман, Питер Зилахи (март 1967). ""Форма Панини-Бэкуса «Предлагаемая». Коммуникации ACM. Ассоциация вычислительной техники. 10 (3): 137. Дои:10.1145/363162.363165. S2CID  52817672. Ингерман предлагает переименовать нормальную форму Бэкуса в Панини -Backus Form, чтобы отдать должное Панини как первому независимому изобретателю.
  3. ^ Хомский, Ноам (1956). «Три модели описания языка» (PDF). Сделки IRE по теории информации. 2 (3): 113–24. Дои:10.1109 / TIT.1956.1056813. Архивировано из оригинал (PDF) 19 сентября 2010 г.
  4. ^ Хомский, Ноам (1957). Синтаксические структуры. Гаага: Мутон.
  5. ^ а б c d е ж г час Смысл синтаксической формулы можно пояснить, сказав, что слова, заключенные в скобки < >, любить <ab>, обозначают классы, членами которых являются последовательности основных символов. Такие обозначения классов встречаются в любом описании языка. Для описания обычных естественных языков используются такие обозначения, как слово, глагол, существительное. Питер Наур (1961).«КУРС ПО АЛГОЛЬНОМУ ПРОГРАММИРОВАНИЮ». п. 5, примечание 1. Получено 26 марта 2015.
  6. ^ а б Бэкус, Дж. У. (1959). «Синтаксис и семантика предлагаемого международного алгебраического языка Цюрихской конференции ACM-GAMM». Материалы Международной конференции по обработке информации. ЮНЕСКО. С. 125–132.
  7. ^ Фаррелл, Джеймс А. (август 1995 г.). «Основы компилятора: Расширенная форма Бэкуса Наура». В архиве из оригинала 5 июня 2011 г.. Получено 11 мая, 2011.
  8. ^ Фултон, III, Скотт М. (20 марта 2007 г.). "Джон В. Бэкус (1924 - 2007)". BetaNews. Inc. Получено 3 июня, 2014.
  9. ^ Кнут, Дональд Э. (1964). «Нормальная форма Бэкуса против формы Бэкуса Наура». Коммуникации ACM. 7 (12): 735–736. Дои:10.1145/355588.365140. S2CID  47537431.
  10. ^ Ингерман, П. З. (1967). ""Форма Панини Бэкуса «предложена». Коммуникации ACM. 10 (3): 137. Дои:10.1145/363162.363165. S2CID  52817672.
  11. ^ Пересмотренный раздел отчета АЛГОЛ 60. 1.1.«АЛГОЛ 60». Получено 18 апреля, 2015.
  12. ^ Саул Розен (Янв 1967). Системы программирования и языки. Серия компьютерных наук Макгроу Хилла. Нью-Йорк / Нью-Йорк: Макгроу Хилл. ISBN  978-0070537088.
  13. ^ RBNF.
  14. ^ «БНФК», г. Языковые технологии, SE: Чалмерс
  15. ^ «Онлайн-демонстрация», РПатк
  16. ^ "Инструменты", Закон мира, заархивировано из оригинал в 2013-01-29
  17. ^ Если целевой процессор System / 360 или связанный, даже до z / System, а целевой язык похож на PL / I (или, действительно, XPL), то требуемый код «эмиттеры» может быть адаптирован из XPL. излучатели »для System / 360.
  18. ^ "Парсер BNF²", Источник кузница (проект)
  19. ^ bnf2xml
  20. ^ "JavaCC". Архивировано из оригинал на 2013-06-08. Получено 2013-09-25.

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

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

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