В информатике расширенная форма Бэкуса–Наура ( РБНФ ) представляет собой семейство метасинтаксических нотаций, любая из которых может быть использована для выражения контекстно-свободной грамматики . РБНФ используется для создания формального описания формального языка, такогокак язык программирования . Они являются расширениями базовой метасинтаксической нотации формы Бэкуса–Наура (БНФ). Самая ранняя РБНФ была разработана Никлаусом Виртом , включив некоторые концепции (с другим синтаксисом и нотацией) из синтаксической нотации Вирта . Сегодня используется множество вариантов РБНФ. Международная организация по стандартизации приняла стандарт РБНФ, ISO/IEC 14977, в 1996 году. [1] [2] Однако, по словам Зайцева, этот стандарт «в итоге лишь добавил еще три диалекта к хаосу» и, отметив его отсутствие успеха, также отмечает, что РБНФ ISO даже не используется во всех стандартах ISO. [3] Уилер выступает против использования стандарта ISO при использовании EBNF и рекомендует рассмотреть альтернативные обозначения EBNF, такие как обозначение из W3C Extensible Markup Language (XML) 1.0 (пятое издание). [4] В этой статье EBNF используется в соответствии с указаниями ISO для примеров, применимых ко всем EBNF. Другие варианты EBNF используют несколько иные синтаксические соглашения.
EBNF — это код , выражающий синтаксис формального языка. [5] EBNF состоит из терминальных символов и нетерминальных правил производства, которые являются ограничениями, регулирующими, как терминальные символы могут быть объединены в допустимую последовательность. Примерами терминальных символов являются буквенно-цифровые символы , знаки препинания и пробельные символы .
EBNF определяет правила продукций , в которых последовательности символов соответственно назначаются нетерминалу :
цифра без нуля = "1" | "2" | "3" | "4" | " 5" | " 6" | "7" | "8" | "9" ; цифра = "0" | цифра без нуля ; Это правило производства определяет нетерминальную цифру , которая находится на левой стороне назначения. Вертикальная черта представляет альтернативу, а терминальные символы заключены в кавычки, за которыми следует точка с запятой в качестве завершающего символа. Таким образом, цифра — это 0 или цифра, исключающая ноль , которая может быть 1 , 2 или 3 и так далее до 9 .
Правило продукций может также включать последовательность терминалов или нетерминалов, разделенных запятой:
двенадцать = "1" , "2" ; двести один = "2" , "0" , "1" ; триста двенадцать = "3" , двенадцать ; двенадцать тысяч двести один = двенадцать , двести один ;Выражения, которые могут быть опущены или повторены, можно представить с помощью фигурных скобок { ... }:
натуральное число = цифра без нуля , { цифра } ;В этом случае строки 1 , 2 , ..., 10 , ..., 10000 , ... являются правильными выражениями. Чтобы представить это, все, что установлено внутри фигурных скобок, может повторяться произвольно часто, включая и не повторяться вообще.
Опция может быть представлена с помощью квадратных скобок [ ... ]. То есть, все, что указано в квадратных скобках, может присутствовать только один раз или не присутствовать вообще:
целое число = "0" | [ "-" ], натуральное число ;Таким образом, целое число — это ноль ( 0 ) или натуральное число , которому может предшествовать необязательный знак минус .
EBNF также предоставляет, помимо прочего, синтаксис для описания повторений (определенного количества раз), для исключения некоторой части последовательности и для вставки комментариев в грамматику EBNF.
Ниже представлен предлагаемый стандарт ISO/IEC 14977, разработанный RS Scowen, страница 7, таблицы 1 и 2.
Даже EBNF можно описать с помощью EBNF. Рассмотрим следующую грамматику (используя такие соглашения, как «-» для обозначения дизъюнкции множеств, «+» для обозначения одного или нескольких совпадений и «?» для необязательности):
буква = "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" ;символ = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">" | "'" | '"' | "=" | "|" | "." | "," | ";" | "-" | "+" | "*" | "?" | "\n" | "\t" | "\r" | "\f" | "\b" ;символ = буква | цифра | символ | "_" | " " ; идентификатор = буква , { буква | цифра | "_" } ;S = { " " | "\n" | "\t " | "\r" | "\f" | "\b" } ;терминал = "'" , символ - "'" , { символ - " '" } , "'" | '"' , символ - '"' , { символ - '"' } , '"' ;терминатор = ";" | "." ;term = "(" , S , rhs , S , ")" | "[" , S , rhs , S , "]" | "{" , S , rhs , S , "}" | терминал | идентификатор ;фактор = термин , S , "?" | термин , S , "*" | термин , S , "+" | термин , S , "-" , S , термин | термин , S ;конкатенация = ( S , фактор , S , "," ? ) + ; чередование = ( S , конкатенация , S , "|" ? ) + ;rhs = чередование ; lhs = идентификатор ;правило = левая часть , S , "=" , S , правая часть , S , терминатор ;грамматика = ( S , правило , S ) * ;Язык программирования, подобный Pascal , который допускает только присваивания, может быть определен в EBNF следующим образом:
(* простой синтаксис программы в EBNF - Википедия *) программа = 'PROGRAM' , пробел , идентификатор , пробел , 'BEGIN' , пробел , { присваивание , ";" , пробел }, 'END.' ; идентификатор = буквенный символ , { буквенный символ | цифра } ; число = [ "-" ], цифра , { цифра } ; строка = '"' , { все символы - '"' }, '"' ; назначение = идентификатор , ":=" , ( число | идентификатор | строка ) ; буквенный символ = "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" ; пробел = ? пробельные символы ? ; все символы = ? все видимые символы ? ; Например, синтаксически правильная программа могла бы быть такой:
ПРОГРАММА DEMO1 НАЧАЛО A := 3 ; B := 45 ; H :=- 100023 ; C := A ; D123 := B34A ; БАБУИН := ЖИРАФ ; ТЕКСТ := " Привет, мир !" ; КОНЕЦ . Язык можно легко расширить потоками управления , арифметическими выражениями и инструкциями ввода/вывода. Затем будет разработан небольшой, удобный язык программирования.
Любая грамматика, определенная в EBNF, также может быть представлена в BNF, хотя представления в последней обычно более длинные. Например, опции и повторения не могут быть напрямую выражены в BNF и требуют использования промежуточного правила или альтернативного производства, определенного как ничто или необязательное производство для option, или либо повторное производство себя, рекурсивно, для repeat. Те же самые конструкции по-прежнему могут использоваться в EBNF.
BNF использует символы ( <, >, |, ::=) для себя, но не включает кавычки вокруг терминальных строк. Это предотвращает использование этих символов в языках и требует специального символа для пустой строки. В EBNF терминалы строго заключены в кавычки ( "... "или '... '). Угловые скобки (" <... >") для нетерминалов можно опустить.
Синтаксис BNF может представлять правило только в одну строку, тогда как в EBNF завершающий символ, символ точки с запятой « ;», отмечает конец правила.
Кроме того, EBNF включает механизмы для усовершенствований, определения количества повторений, исключения альтернатив, комментариев и т. д.
* повторение-символа - исключение-символа , объединение-символа | определение-разделитель-символа = определение-символа ; символ-терминатор . символ-терминатор (* начало-символа-комментария конец-символа-комментария *) ' первый-символ-кавычек первый-символ-кавычек ' ( начало-символа-группы конец-символа-группы ) [ начало-символа-опции конец-символа-опции ] { начало-символа-повтора конец-символа-повтора } ? специальный-символ-последовательности специальный-символ-последовательности ? " второй-символ-кавычек второй-символ-кавычек "'); шрифт, используемый в ISO/IEC 14977:1996(E), очень похож на острый, Unicode U+00B4 ( ´), поэтому иногда возникает путаница. Однако стандарт ISO Extended BNF ссылается на ISO/IEC 646:1991, «7-битный кодированный набор символов ISO для обмена информацией», как на нормативную ссылку и не упоминает никаких других наборов символов, поэтому формально путаницы с символами Unicode за пределами 7-битного диапазона ASCII не возникает.В качестве примеров следующие синтаксические правила иллюстрируют возможности выражения повторения:
аа = "А" ; бб = 3 * аа , "Б" ; сс = 3 * [ аа ], "В" ; дд = { аа }, "Д" ; ее = аа , { аа }, "Э" ; фф = 3 * аа , 3 * [ аа ], "Ж" ; гг = { 3 * аа }, "Г" ; чч = ( аа | бб | сс ), "Н" ;Терминальные строки, определяемые этими правилами, следующие:
аа: Абб: АААБКопия: C AC AAC AAACдд: Д АД ААД АААД АААД и т.д.ee: AE AAE AAAE AAAAE AAAAAE и т. д.фф: ААААА ААААА АААААА АААААgg: G AAAG AAAAAAG и т. д.чч: АААААХ Ч АЧ АААХ АААХ
Согласно стандарту ISO 14977, EBNF должен быть расширяемым, и упоминаются два средства. Первое является частью грамматики EBNF, специальной последовательности, которая представляет собой произвольный текст, заключенный в вопросительные знаки. Интерпретация текста внутри специальной последовательности выходит за рамки стандарта EBNF. Например, символ пробела может быть определен следующим правилом:
пробел = ? символ ASCII 32 ? ;Второе средство расширения использует тот факт, что скобки в EBNF не могут быть размещены рядом с идентификаторами (они должны быть объединены с ними). Ниже приведена допустимая EBNF:
что-то = фу , ( бар );Следующее не является действительным EBNF:
что-то = фу ( бар );Поэтому расширение EBNF может использовать эту нотацию. Например, в грамматике Lisp применение функции может быть определено следующим правилом:
применение функции = список ( символ , { выражение } );