В информатике , 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]
Согласно предложению Бэкуса, в формуле определены «классы», имена которых заключены в угловые скобки. Например,
. Каждое из этих имен обозначает класс основных символов. [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] Например, вышеупомянутое
обозначено как a,
за которым следует любое количество
.
В некоторых более поздних метаязыках, таких как META II Шорре, конструкция рекурсивного повтора BNF заменена оператором последовательности и символами целевого языка, определенными с помощью строк в кавычках. <
И >
скобки были удалены. (
)
Добавлены круглые скобки для математической группировки.
Правило появится в META II , как
EXPR = TERM $ ('+' TERM .OUT ('ДОБАВИТЬ') | '-' TERM .OUT ('SUB'));
Эти изменения позволили META II и производным от нее языкам программирования определить и расширить свой собственный метаязык за счет возможности использовать описание на естественном языке, металингвистическую переменную, описание языковой конструкции. Многие побочные метаязыки были вдохновлены BNF. [ необходима ссылка ] См. META II , TREE-META и Metacompiler .
Класс BNF описывает формирование языковой конструкции, причем формирование определяется как шаблон или действие по формированию шаблона. Имя класса expr описывается на естественном языке как
последовательность, за которой следует последовательность
. Класс - это абстракция; мы можем говорить о нем независимо от его образования. Мы можем говорить о термине, независимо от его определения, как о добавляемом или вычитаемом в expr. Мы можем говорить о термине, являющемся определенным типом данных, и о том, как должно оцениваться выражение, имеющее определенные комбинации типов данных. Или даже переупорядочить выражение, чтобы сгруппировать типы данных и результаты оценки смешанных типов. Приложение для естественного языка предоставило конкретные детали семантики языковых классов, которые будут использоваться реализацией компилятора и программистом, пишущим программу на Алголе. Описание на естественном языке также дополнило синтаксис. Целочисленное правило - хороший пример естественного и метаязыка, используемого для описания синтаксиса:
< целое число > :: = < цифра > | < целое число > < цифра >
В приведенном выше тексте нет никаких подробностей о пустом пространстве. Согласно правилу, между цифрами может быть пробел. На естественном языке мы дополняем метаязык BNF, объясняя, что последовательность цифр не может иметь пробелов между цифрами. Английский - только один из возможных естественных языков. Переводы отчетов ALGOL были доступны на многих естественных языках.
Происхождение BNF не так важно, как его влияние на развитие языков программирования. [ необходима цитата ] В период сразу после публикации отчета по Алголу 60 BNF был основой многих систем компилятор-компилятор .
Некоторые из них, такие как «Синтаксически управляемый компилятор для Алгола 60», разработанный Эдгаром Т. Айронсом, и «Система построения компилятора», разработанная Брукером и Моррисом, напрямую использовали BNF. Другие, такие как Schorre Metacompilers , превратили его в язык программирования с небольшими изменениями.
стали идентификаторами символов, отбрасывая заключительные <,> и используя строки в кавычках для символов целевого языка. Группировка, подобная арифметике, обеспечивала упрощение, которое исключало использование классов, в которых группировка была единственным значением. Правило арифметических выражений 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" | "к" | "л" | "м" | "п" | "о" | "р" | "q" | "г" | "s" | "т" | "u" | "v" | "ш" | «х» | "у" | "z" < цифра > :: = "0" | «1» | «2» | «3» | «4» | «5» | «6» | «7» | «8» | "9" < символ > :: = "|" | "" | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | «+» | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | «[» | "\" | "]" | "^" | "_" | "` "| "{" | "}" | "~" < символ1 > :: = < символ > | "'" < символ2 > :: = < символ > | '"' < имя-правила > :: = < буква > | < имя-правила > < символ-правила > < символ-правила > :: = < буква > | < цифра > |" - "
Обратите внимание, что "" - это пустая строка .
Исходный BNF не использовал кавычки, как показано в
правиле. Это предполагает, что для правильной интерпретации правила не нужны пробелы .
представляет соответствующий спецификатор конца строки (в ASCII , возврат каретки, перевод строки или оба в зависимости от операционной системы ).
и
должны быть заменены объявленным именем / меткой правила или буквальным текстом, соответственно.
В приведенном выше примере почтового адреса США вся цитата является синтаксисом. Каждая строка или непрерывная группа строк - это правило; например одно правило начинается с
. Другая часть этого правила (помимо конца строки) - это выражение, которое состоит из двух списков, разделенных вертикальной чертой |
. Эти два списка состоят из некоторых терминов (соответственно три и два термина). Каждый термин в этом конкретном правиле - это имя правила.
Варианты
Существует множество вариантов и расширений BNF, как правило, либо для простоты и краткости, либо для адаптации к конкретному приложению. Общей чертой многих вариантов является использование операторов повторения регулярных выражений, таких как *
и +
. Расширен Бэкуса-Наура (РБНФ) является общим.
Еще одно распространенное расширение - использование квадратных скобок вокруг необязательных элементов. Хотя нет в оригинальном Алголе 60 доклада (вместо введен через несколько лет в IBM «s PL / I определение), обозначение теперь общепризнанный.
Расширенная форма Бэкуса – Наура (ABNF) и форма Бэкуса – Наура маршрутизации (RBNF) [13] - это расширения, обычно используемые для описания протоколов Internet Engineering Task Force (IETF) .
Грамматики синтаксического анализа основаны на нотации BNF и регулярных выражений, чтобы сформировать альтернативный класс формальной грамматики , который по сути является аналитическим, а не порождающим .
Многие спецификации BNF, которые сегодня можно найти в Интернете, предназначены для удобства чтения и являются неформальными. Они часто включают в себя многие из следующих синтаксических правил и расширений:
- Необязательные элементы заключены в квадратных скобках:
[
.] - Элементы, существующие 0 или более раз, заключаются в фигурные скобки или обозначаются звездочкой (
*
), например
или::= { }
соответственно.::= * - Пункты существующих 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 2 , [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 - ранний инструмент для написания компиляторов и нотаций
Рекомендации
- ^ "Биография Панини" . Школа математики и статистики Университета Сент-Эндрюс, Шотландия . Проверено 22 марта 2014 .
- ^ Ингерман, Питер Зилахи (март 1967). « » Панини-Backus Форма «Похожие». Коммуникации ACM . Ассоциация вычислительной техники. 10 (3): 137. DOI : 10,1145 / 363162,363165 . S2CID 52817672 .Ингерман предлагает переименовать нормальную форму Бэкуса в Форму Панини- Бэкуса, чтобы отдать должное Панини как первому независимому изобретателю.
- ^ Хомский, Ноам (1956). «Три модели для описания языка» (PDF) . Сделки IRE по теории информации . 2 (3): 113–24. DOI : 10.1109 / TIT.1956.1056813 . Архивировано из оригинального (PDF) 19 сентября 2010 года.
- ^ Хомский, Ноам (1957). Синтаксические структуры . Гаага: Мутон.
- ^ a b c d e f g h Значение синтаксической формулы можно пояснить, сказав, что слова, заключенные в квадратные скобки
< >
, например
, обозначают классы, члены которых являются последовательностями основных символов. Такие обозначения классов встречаются в любом описании языка. Для описания обычных естественных языков используются такие обозначения, как слово, глагол, существительное. Питер Наур (1961). «КУРС ПО АЛГОЛЬНОМУ ПРОГРАММИРОВАНИЮ» . п. 5, примечание 1 . Проверено 26 марта 2015 года . - ^ а б Backus, JW (1959). «Синтаксис и семантика предложенного международного алгебраического языка Цюрихской конференции ACM-GAMM» . Материалы Международной конференции по обработке информации . ЮНЕСКО. С. 125–132.
- ^ Фаррелл, Джеймс А. (август 1995 г.). «Основы компилятора: расширенная форма Бэкуса Наура» . Архивировано 5 июня 2011 года . Проверено 11 мая 2011 года .
- ^ Фултон, III, Скотт М. (20 марта 2007 г.). «Джон В. Бэкус (1924 - 2007)» . BetaNews. Inc . Проверено 3 июня 2014 года .
- ^ Кнут, Дональд Э. (1964). «Нормальная форма Бэкуса против формы Бэкуса Наура». Коммуникации ACM . 7 (12): 735–736. DOI : 10.1145 / 355588.365140 . S2CID 47537431 .
- ^ Ингерман, ПЗ (1967). « » Панини Backus Форма «предложил». Коммуникации ACM . 10 (3): 137. DOI : 10,1145 / 363162,363165 . S2CID 52817672 .
- ^ Пересмотренный раздел отчета АЛГОЛ 60. 1.1. «АЛГОЛ 60» . Проверено 18 апреля 2015 года .
- ^ Сол Розен (январь 1967 г.). Системы программирования и языки . Серия компьютерных наук Макгроу Хилла. Нью-Йорк / Нью-Йорк: Макгроу Хилл. ISBN 978-0070537088.
- ^ RBNF .
- ^ "BNFC", Языковые технологии , SE : Chalmers
- ^ «Онлайн-демо», РПатк
- ^ "Tools", мир действий, архивировано из оригинала 29 января 2013 г.
- ^ Если целевой процессор System / 360 или связанный, даже до z / System, и целевой язык похож на PL / I (или, действительно, XPL), то требуемый код "эмиттеры" может быть адаптирован из XPL "эмиттеры" для System / 360.
- ^ "BNF parser²", Source forge (проект)
- ^ bnf2xml
- ^ «JavaCC» . Архивировано из оригинала на 2013-06-08 . Проверено 25 сентября 2013 .
- Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.
Внешние ссылки
- Гаршол, Ларс Мариус, BNF и EBNF: Что это такое и как они работают? , НЕТ : Priv.
- RFC 5234 - Расширенный BNF для спецификаций синтаксиса: ABNF.
- RFC 5511 - Маршрутизация BNF: синтаксис, используемый в различных спецификациях протокола.
- ISO / IEC 14977: 1996 (E) Информационные технологии - синтаксический метаязык - Extended BNF , доступны «Общедоступно», Стандарты , ISO или из Кун, Маркус, ISO 14977 (PDF) , Великобритания : 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) стандарта.