Войти
В информатика, форма Бэкуса – Наура или нормальная форма Бэкуса (BNF ) - это обозначение метасинтаксиса для контекста -свободные грамматики, часто используемые для описания синтаксиса языков, используемых в вычислениях, таких как компьютерные языки программирования, форматы документов, наборы команд и протоколы связи. Они применяются везде, где требуется точное описание языков: например, в спецификациях официальных языков, в руководствах и в учебниках по теории языков программирования.
Используются многие расширения и варианты исходной нотации Бэкуса – Наура; некоторые из них точно определены, включая расширенную форму Бэкуса-Наура (EBNF) и расширенную форму Бэкуса-Наура (ABNF).
Идея описания структуры языка с помощью правил перезаписи восходит, по крайней мере, к работе Панини, древний индийский грамматик санскрита и уважаемый знаток индуизма, живший где-то между VI и IV веками до н.э.. Его обозначения для описания структуры слов санскрита эквивалентны по силе обозначениям Бэкуса и имеют много схожих свойств.
В западном обществе грамматика долгое время считалась предметом преподавания, а не научным изучением; описания были неформальными и ориентированы на практическое использование. В первой половине 20 века лингвисты, такие как Леонард Блумфилд и Зеллиг Харрис, начали попытки формализовать описание языка, включая структуру фраз.
Между тем, правила перезаписи строк как формальные логические системы были введены и изучены математиками, такими как Аксель Туэ (в 1914 году), Эмиль Пост (1920-40-е годы) и Алан Тьюринг (1936). Ноам Хомский, преподающий лингвистику студентам теории информации в Массачусетском технологическом институте, объединил лингвистику и математику, взяв то, что по сути является формализмом Туэ, в качестве основы для описания синтаксис естественного языка. Он также провел четкое различие между порождающими правилами (те из контекстно-свободных грамматик ) и правилами преобразования (1956).
Джон Бэкус, разработчик языков программирования в IBM, предложил метаязык «металингвистических формул» для описания синтаксиса нового языка программирования IAL, известного сегодня как АЛГОЛ 58 (1959). Его обозначения были впервые использованы в отчете ALGOL 60.
BNF - это обозначение контекстно-свободных грамматик Хомского. Бэкус был знаком с работами Хомского.
Согласно предложению Бэкуса, формула определяла «классы», имена которых заключены в угловые скобки. Например,
Дальнейшее развитие АЛГОЛА привело к АЛГОЛу 60. В отчете комитета за 1963 год Питер Наур назвал обозначение Бакуса Бэкусом нормальной формой. Дональд Кнут утверждал, что BNF лучше читать как форму Бэкуса-Наура, поскольку это «не нормальная форма в общепринятом смысле», в отличие, например, от Хомского нормальная форма. Форма имени Панини Бэкус также была однажды предложена ввиду того факта, что нормальная форма расширения Бэкуса может быть неточной, и что Панини независимо разработал подобную нотацию ранее.
БНФ - это описанный Питером Науром в отчете ALGOL 60 как металингвистическая формула:
Последовательности символов, заключенные в скобки, <>представляют металингвистические переменные, значения которых являются последовательностями символов. Знаки ":: =" и "|" (последнее со значением «или») являются металингвистическими связками. Любой знак в формуле, который не является переменной или связкой, обозначает сам себя. Сопоставление меток или переменных в формуле означает сопоставление обозначенной последовательности.
Другой пример из отчета ALGOL 60 иллюстрирует основное различие между метаязыком BNF и контекстно-свободной грамматикой Хомского. Металингвистические переменные не требуют правила, определяющего их формирование. Их образование можно просто описать естественным языком в скобках <>. Следующая спецификация комментариев к разделу 2.3 отчета ALGOL 60 иллюстрирует, как это работает:
Для включения текста в символы программы соблюдаются следующие соглашения о «комментариях»:
| Последовательность основных символов: | эквивалентно |
| ;comment | ; |
| begincomment | begin |
| end | end |
Под эквивалентностью здесь подразумевается, что любая из трех структур, показанных в левый столбец может быть заменен в любом случае за пределами строк символом, показанным в той же строке в правом столбце, без какого-либо влияния на действие программы.
Наур заменил два символа Бэкуса общедоступными. Символ «:: =» изначально был «: ≡». Знак "|" Первоначально символом было слово «или» (с полосой над ним). Работая на IBM, Бэкус заключил бы соглашение о неразглашении и не мог бы говорить о своем источнике, если бы он исходил из частного проекта IBM.
BNF очень похож на каноническая форма логическая алгебра уравнения, которые использовались и использовались в то время при проектировании логических схем. Бэкус был математиком и разработчиком языка программирования FORTRAN. Изучение булевой алгебры обычно является частью математики. Что мы действительно знаем, так это то, что ни Бэкус, ни Наур не описывали имена, заключенные в <>, как нетерминалы. Терминология Хомского изначально не использовалась при описании БНФ. Позже Наур описал их как классы в материалах курса АЛГОЛА. В отчете ALGOL 60 они были названы металингвистическими переменными. Все, кроме метасимволов :: =, | и имен классов, заключенных в <,>, являются символами определяемого языка. Метасимволы :: = следует интерпретировать как «определяется как». | используется для разделения альтернативных определений и интерпретируется как «или». Метасимволы <,>являются разделителями, заключающими имя класса. BNF описан как метаязык для разговоров об АЛГОЛе Питером Науром и Солом Розеном.
В 1947 году Саул Розен стал участвовать в деятельности молодой Ассоциации. for Computing Machinery, сначала в комитете по языкам, который стал группой IAL и в конечном итоге привел к ALGOL. Он был первым управляющим редактором коммуникаций ACM. Что мы действительно знаем, так это то, что BNF впервые использовался в качестве метаязыка для обсуждения языка ALGOL в отчете ALGOL 60. Именно так это объясняется в материалах курса программирования ALGOL, разработанных Питером Науром в 1962 году. Ранние руководства по ALGOL от IBM, Honeywell, Burroughs и Digital Equipment Corporation следовали за отчетом ALGOL 60, используя его в качестве метаязыка. Саул Розен в своей книге описывает BNF как метаязык для разговоров об АЛГОЛе. Примером его использования в качестве метаязыка могло бы быть определение арифметического выражения:
:: = |
Первым символом альтернативы может быть определяемый класс, повторение, как объяснил Наур, имеющее функцию указание, что альтернативная последовательность может рекурсивно начинаться с предыдущей альтернативы и может повторяться любое количество раз. Например, приведенный выше
. В некоторых более поздних метаязыках, таких как META II Шорре, конструкция рекурсивного повтора BNF заменяется оператором последовательности и символы целевого языка, определенные с помощью строк в кавычках. Скобки <и >были удалены. Добавлены круглые скобки ()для математической группировки. Правило
EXPR = TERM $ ('+' TERM.OUT ('ADD') | '-' TERM.OUT ('SUB'));Эти изменения позволили META II и производным от нее языкам программирования определить и расширить свой собственный метаязык за счет возможности использовать описание естественного языка, металингвистическую переменную, описание языковой конструкции. Многие побочные метаязыки были вдохновлены BNF. См. META II, TREE-META и Metacompiler.
Класс BNF описывает формирование языковой конструкции, при этом формирование определяется как шаблон или действие по формированию шаблона. Имя класса expr описывается на естественном языке как
:: = |
В приведенном выше тексте нет специфики для пробелов. Согласно правилу, между цифрами может быть пробел. На естественном языке мы дополняем метаязык BNF, объясняя, что последовательность цифр не может иметь пробелов между цифрами. Английский - только один из возможных естественных языков. Переводы отчетов ALGOL были доступны на многих естественных языках.
Происхождение BNF не так важно, как его влияние на развитие языков программирования. В течение периода, непосредственно следующего за публикацией отчета по Алголу 60, BNF была основой многих систем компилятор-компилятор.
Некоторые, такие как «Компилятор, управляемый синтаксисом для ALGOL 60», разработанный и «Система построения компилятора», разработанная Брукером и Моррисом, напрямую использовали BNF. Другие, например, превратились в язык программирования с небольшими изменениями.
Сегодня BNF - один из старейших компьютерных языков, которые все еще используются.
Спецификация BNF - это набор правил образования, записанный как
: : = __expression__
где <symbol >- это нетерминал, а __expression__ состоит из одной или нескольких последовательностей символов; другие последовательности разделены вертикальной чертой "|", что указывает на выбор, при этом целиком является возможная замена символа слева. Символы, которые никогда не появляются слева, - это клеммы. С другой стороны, символы, которые появляются слева, являются нетерминалами и всегда заключены между парой <>.
. ":: =" означает, что символ слева должен быть заменен на выражение справа.
В качестве примера рассмотрим этот возможный BNF для почтового адреса в США :
:: = :: = | :: = "." | :: = :: = "," :: = "Старший" | "Младший" | | "" :: = | ""
Это переводится на английский как:
Обратите внимание, что многие вещи (например, формат имени, спецификатора квартиры, почтового индекса и римской цифры) здесь не указаны. При необходимости их можно описать с помощью дополнительных правил BNF.
Сам синтаксис BNF может быть представлен с помощью BNF следующим образом:
:: = | :: = "<" ">" ":: =" :: = "" | "" :: = |
"|" :: = | :: =
|
:: = | "<" ">" :: = '"' '"' | "'" "'" :: = "" | :: = '' | :: = | | :: = "A" | «Б» | "C" | «Д» | "E" | "F" | "G" | "H" | «Я» | "J" | «К» | "L" | «М» | «N» | «О» | «П» | «Q» | "R" | "S" | «Т» | "U" | "V" | "W" | «Х» | «Y» | "Z" | "а" | "б" | "с" | "д" | "е" | "е" | "г" | "h" | «я» | "j" | "к" | "л" | "м" | «п» | "о" | "р" | "q" | "г" | "s" | "т" | "u" | "v" | "ш" | «х» | "у" | "z" :: = "0" | «1» | «2» | «3» | «4» | «5» | «6» | «7» | «8» | "9" :: = "|" | "" | "!" | "#" | "$" | "%" | "" | "(" | ")" | "*" | «+» | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | «[» | "\" | "]" | "^" | "_" | "` "| "{" | "}" | "~" :: = | "'" :: = | '"' :: = | :: = | |" - "
Обратите внимание, что" "- это пустая строка.
Исходный BNF не использовал кавычки как показано в правиле
В приведенном выше примере почтового адреса в США вся цитата является синтаксисом. Каждая строка или непрерывная группа строк является правилом; например, одно правило начинается с |. Эти два списка состоят из некоторых терминов (трех терминов и двух условия, соответственно). Каждый термин в этом конкретном правиле является именем правила.
Есть много вариантов ts и расширений BNF, как правило, либо для простоты и краткости, либо для адаптации к конкретному приложению. Одной из общих черт многих вариантов является использование регулярных выражений операторов повторения, таких как *и +. Расширенная форма Бэкуса – Наура (EBNF) является распространенной.
Другое распространенное расширение - использование квадратных скобок вокруг необязательных элементов. Хотя эта нотация не присутствует в исходном отчете ALGOL 60 (вместо этого введена несколькими годами позже в определении PL / I в IBM ), теперь эта нотация признана повсеместно.
Расширенная форма Бэкуса – Наура (ABNF) и форма Routing Backus – Naur (RBNF) - это расширения, обычно используемые для описания протоколов Internet Engineering Task Force (IETF) .
Parsing грамматики выражений построены на нотациях BNF и регулярных выражений, чтобы сформировать альтернативный класс формальной грамматики, который по сути является аналитическим, а не генеративным в символе.
Многие спецификации BNF, которые сегодня можно найти в Интернете, предназначены для удобства чтения и не являются формальными. К ним часто относятся многие из следующих синтаксических правил и расширений:
[] .*) например, :: = {} :: = * +.