stringtranslate.com

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

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

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

Обзор

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

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

где:

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

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

Пример

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

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

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

Обратите внимание, что многие вещи (такие как формат имени, номера квартиры, почтового индекса и римской цифры) здесь не указаны. При необходимости их можно описать с помощью дополнительных правил 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

Синтаксис 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, которые можно найти сегодня в сети, предназначены для чтения человеком и являются неформальными. Они часто включают в себя многие из следующих правил синтаксиса и расширений:

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

Программное обеспечение, которое принимает BNF (или надмножество) в качестве входных данных

Похожее программное обеспечение

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

Ссылки

  1. ^ abc Яников, Цезари З. «Что такое БНФ?» (PDF) .
  2. ^ abcdefg Значение синтаксической формулы можно объяснить, сказав, что слова, заключенные в скобки < >, например <ab>, обозначают классы, членами которых являются последовательности основных символов. Обозначения классов такого рода встречаются в любом описании языка. Для описания обычных естественных языков используются обозначения, например, слово, глагол, существительное. . [8] : 5, Примечание 1 
  3. ^ Статья основана на материале, взятом из Backus-Naur+Form в Free On-line Dictionary of Computing до 1 ноября 2008 года и включенном в соответствии с условиями «перелицензирования» GFDL версии 1.3 или более поздней.
  4. ^ "Биография Панини". Школа математики и статистики, Университет Сент-Эндрюс, Шотландия . Получено 22.03.2014 .
  5. ↑ Ингерман, Питер Зилахи (март 1967 г.). «Предложена форма Панини-Бэкуса». Сообщения ACM . 10 (3). Ассоциация вычислительной техники: 137. doi : 10.1145/363162.363165 . S2CID  52817672.Ингерман предлагает переименовать нормальную форму Бэкуса в форму Панини -Бэкуса, чтобы воздать должное Панини как самому раннему независимому изобретателю.
  6. ^ Хомский, Ноам (1956). «Три модели описания языка» (PDF) . Труды IRE по теории информации . 2 (3): 113–24. doi :10.1109/TIT.1956.1056813. S2CID  19519474. Архивировано из оригинала (PDF) 2010-09-19.
  7. ^ Хомский, Ноам (1957). Синтаксические структуры . Гаага: Mouton.
  8. ^ Наур, Питер (1961). «КУРС ПРОГРАММИРОВАНИЯ АЛГОЛ 60 с особым упором на систему DASK ALGOL» (PDF) . Копенгаген: Regnecentralen . Получено 26 марта 2015 г.
  9. ^ ab Backus, JW (1959). «Синтаксис и семантика предложенного международного алгебраического языка Цюрихской конференции ACM-GAMM». Труды Международной конференции по обработке информации . ЮНЕСКО. С. 125–132.
  10. ^ Фаррелл, Джеймс А. (август 1995 г.). "Основы компиляции: расширенная форма Бэкуса-Наура". Архивировано из оригинала 5 июня 2011 г. Получено 11 мая 2011 г.
  11. ^ Фултон, III, Скотт М. (20 марта 2007 г.). "Джон В. Бэкус (1924 - 2007)". BetaNews. Inc. Получено 3 июня 2014 г.
  12. ^ Кнут, Дональд Э. (1964). «Нормальная форма Бэкуса против формы Бэкуса-Наура». Сообщения ACM . 7 (12): 735–736. doi : 10.1145/355588.365140 . S2CID  47537431.
  13. ^ Ингерман, ПЗ (1967). «Предложена «Форма Панини Бэкуса». Коммуникации АКМ . 10 (3): 137. дои : 10.1145/363162.363165 . S2CID  52817672.
  14. ^ Пересмотренный раздел отчета ALGOL 60. 1.1. "ALGOL 60" . Получено 18 апреля 2015 г.
  15. ^ Сол Розен (январь 1967). Системы и языки программирования . Серия компьютерных наук McGraw Hill. Нью-Йорк/Нью-Йорк: McGraw Hill. ISBN 978-0070537088.
  16. ^ РБНФ.
  17. ^ "Онлайн-демонстрация", RPatk, заархивировано из оригинала 2012-11-02 , извлечено 2011-07-03
  18. ^ "Инструменты", Act world, архивировано из оригинала 2013-01-29
  19. ^ Если целевой процессор — System/360 или родственный ему, вплоть до z/System, а целевой язык похож на PL/I (или, конечно, XPL), то требуемые «излучатели» кода могут быть адаптированы из «излучателей» XPL для System/360.
  20. ^ Маккиман, WM; Хорнинг, JJ; Вортман, DB (1970). Генератор компиляторов . Prentice-Hall. ISBN 978-0-13-155077-3.
  21. ^ "BNF parser²", Исходный код (проект)
  22. ^ bnf2xml
  23. ^ "JavaCC". Архивировано из оригинала 2013-06-08 . Получено 2013-09-25 .
  24. ^ "Синтаксис скрипта - Qlik Sense в Windows". Qlik.com . QlikTech International AB . Получено 10 января 2022 г. .
  25. ^ "BNFC", Языковые технологии, SE : Чалмерс

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

Грамматики языка