Расширенная форма Бэкуса – Наура - Extended Backus–Naur form

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

Самый ранний EBNF был разработан Никлаус Вирт включение некоторых концепций (с другим синтаксисом и обозначениями) из Обозначение синтаксиса вирта. Однако используются многие варианты EBNF. В Международная организация по стандартизации принял стандарт EBNF (ISO / IEC 14977 ) в 1996 г. Однако, по словам Зайцева, этот стандарт «только добавил еще три диалекта к хаосу» и, отметив его безуспешность, также отмечает, что ISO EBNF даже не используется во всех стандартах ISO. Уилер выступает против использования стандарта ISO при использовании EBNF и рекомендует рассмотреть альтернативные нотации EBNF, например, из W3C Extensible Markup Language (XML) 1.0 (пятое издание).

В этой статье используется EBNF, как указано в ISO для примеров, применимых ко всем EBNF. В других вариантах EBNF используются несколько иные синтаксические соглашения.

Основы

EBNF - это код который выражает грамматику формального языка. 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, предложенный Р. С. Скоуэном, стр. 7, таблица 1.

использованиеОбозначение
определение=
конкатенация,
прекращение;
чередование|
необязательный[ ... ]
репетиция{ ... }
группировка( ... )
терминальная строка" ... "
терминальная строка' ... '
комментарий(* ... *)
особая последовательность? ... ?
исключение-

Примеры

Даже EBNF можно описать с помощью EBNF. Рассмотрим схематическую грамматику ниже:

письмо = "А" | "B" | "C" | "D" | "E" | "F" | "ГРАММ"       | "ЧАС" | "Я" | "J" | "К" | "L" | "М" | "N"       | "О" | "П" | "Q" | "Р" | "S" | "Т" | "U"       | "V" | "W" | "ИКС" | "Y" | "Z" | "а" | "б"       | "c" | "d" | "е" | "е" | "грамм" | "час" | "я"       | "j" | "к" | "л" | "м" | "п" | "о" | "п"       | "q" | "р" | "s" | "т" | "u" | "v" | "ш"       | "Икс" | "у" | "z" ;цифра = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;символ = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"       | "'" | '"' | "=" | "|" | "." | "," | ";" ;персонаж = письмо | цифра | символ | "_" ; идентификатор = письмо , { письмо | цифра | "_" } ;Терминал = "'" , персонаж , { персонаж } , "'"          | '"' , персонаж , { персонаж } , '"' ; lhs = идентификатор ;rhs = идентификатор     | Терминал     | "[" , rhs , "]"     | "{" , rhs , "}"     | "(" , rhs , ")"     | rhs , "|" , rhs     | rhs , "," , rhs ;правило = lhs , "=" , rhs , ";" ;грамматика = { правило } ;

А Паскаль -подобный язык программирования, допускающий только назначения, может быть определен в EBNF следующим образом:

 (* простой программный синтаксис в EBNF - Википедия *) программа = "ПРОГРАММА", white_space, идентификатор, white_space,             'НАЧИНАТЬ', white_space,             { назначение, ";", white_space },             'КОНЕЦ.' ; идентификатор = alphabetic_character, { alphabetic_character | цифра } ; номер = [ "-" ], цифра, { цифра } ; нить = '"' , { all_characters - '"' }, '"' ; назначение = идентификатор , ":=" , ( номер | идентификатор | нить ) ; alphabetic_character = "А" | "B" | "C" | "D" | "E" | "F" | "ГРАММ"                      | "ЧАС" | "Я" | "J" | "К" | "L" | "М" | "N"                      | "О" | "П" | "Q" | "Р" | "S" | "Т" | "U"                      | "V" | "W" | "ИКС" | "Y" | "Z" ; цифра = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; white_space = ? символы white_space? ; all_characters = ? все видимые персонажи? ;

Например, синтаксически правильной программой может быть:

 ПРОГРАММА DEMO1 НАЧИНАТЬ   А:=3;   B:=45;   ЧАС:=-100023;   C:=А;   D123:=B34A;   БАБУН:=ЖИРАФА;   ТЕКСТ:="Привет Мир!"; КОНЕЦ.

Язык можно легко расширить с помощью потоки управления, арифметические выражения и инструкции ввода / вывода. Затем будет разработан небольшой удобный язык программирования.

Преимущества перед BNF

Любой грамматика определенные в EBNF, также могут быть представлены в BNF, хотя представления в последнем обычно более длинные. Например, варианты и повторения не могут быть напрямую выражены в BNF и требуют использования промежуточного правила или альтернативного производства, определенного как «ничто», либо как необязательное производство для варианта, либо либо рекурсивное повторение самого себя для повторения. Те же конструкции все еще можно использовать в EBNF.

BNF использует символы (<, >, |, ::=) для себя, но не включает кавычки вокруг терминальных строк. Это предотвращает использование этих символов в языках и требует специального символа для пустой строки. В EBNF, терминалы строго заключаются в кавычки ("…" или же '…'). Угловые скобки ("<…>") за нетерминалы можно не указывать.

Синтаксис BNF может представлять правило только в одной строке, тогда как в EBNF символ завершения, символ точки с запятой «;»Отмечает конец правила.

Кроме того, EBNF включает механизмы для улучшений, определения количества повторов, исключения альтернатив, комментариев и т. Д.

Конвенции

  1. Используются следующие условные обозначения:
    • Каждый метаидентификатор расширенного BNF записывается как одно или несколько слов, соединенных вместе дефисы.
    • Метаидентификатор, оканчивающийся на -символ - это имя терминального символа расширенного BNF.
  2. Обычный символ, представляющий каждый оператор расширенного BNF и его подразумеваемый приоритет (наивысший приоритет вверху):
     * символ повторения - исключительный символ , символ конкатенации | определение-разделитель-символ = определяющий символ ; символ-терминатор . символ-терминатор
  3. Обычный приоритет отменяется следующими парами скобок:
     (* начальный-символ-комментария конечный-символ-комментария *) '  символ первой кавычки символ первой кавычки ' (  символ начальной группы символ конечной группы ) [  начальный-параметр-символ конечный-параметр-символ ] {  символ начала повторения символ конца повторения } ?  символ специальной последовательности символ специальной последовательности ? "  второй символ кавычек второй символ кавычек "
    Символ первой кавычки - это апостроф как определено в ISO / IEC 646: 1991, то есть Unicode U + 0027 ('); шрифт, используемый в ISO / IEC 14977: 1996 (E), очень похож на острый, Unicode U + 00B4 (´), поэтому иногда возникает путаница. Однако стандарт ISO Extended BNF использует ISO / IEC 646: 1991, «7-битный кодированный набор символов ISO для обмена информацией» в качестве нормативной ссылки и не упоминает какие-либо другие наборы символов, поэтому формально нет никакой путаницы с Символы Юникода вне 7-битного диапазона ASCII.

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

аа = "А";bb = 3 * аа, "B";cc = 3 * [аа], "C";дд = {аа}, "D";ее = аа, {аа}, "E";ff = 3 * аа, 3 * [аа], "F";gg = {3 * аа}, "ГРАММ";

Терминальные строки, определенные этими правилами, следующие:

aa: Abb: AAABcc: C AC AAC AAACdd: D AD AAD AAAD AAAAD и т. д. см .: AE AAE AAAE AAAAE AAAAAE и т. д. f: AAAF AAAAF AAAAAF AAAAAAFgg: G AAAG AAAAAAG и т. д.

Расширяемость

Согласно стандарту ISO 14977 EBNF должен быть расширяемым, и упоминаются два объекта. Первая - это часть грамматики EBNF, особая последовательность, которая представляет собой произвольный текст, заключенный в вопросительные знаки. Интерпретация текста внутри специальной последовательности выходит за рамки стандарта EBNF. Например, пробел можно определить по следующему правилу:

 Космос = ? 32-й символ ASCII?;

Вторая возможность расширения заключается в том, что скобки в EBNF не могут быть помещены рядом с идентификаторами (они должны быть связаны с ними). Следующее является действительным EBNF:

 что нибудь = фу, ( бар );

Следующее нет действующий EBNF:

 что нибудь = фу ( бар );

Следовательно, расширение EBNF может использовать это обозначение. Например, в Лисп грамматика, применение функции может быть определено следующим правилом:

 приложение-функция = список( символ, { выражение } );

Связанных с работой

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

Рекомендации

дальнейшее чтение

  • Паттис, Ричард Э. «EBNF: Нотация для описания синтаксиса» (PDF). ICS.UCI.edu. Калифорнийский университет в Ирвине.

внешняя ссылка