Расширенная форма Бэкуса – Наура
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Май 2020 г. ) |
В информатике обозначений , расширенная форма Бэкуса-Наура ( EBNF ) представляет собой семейство метасинтаксических любая из которых может использоваться для выражения контекстно-свободной грамматики . EBNF используется для формального описания формального языка, такого как язык компьютерного программирования . Они являются расширениями базовой нотации метасинтаксиса формы Бэкуса – Наура (BNF).
Самый ранний EBNF был разработан Никлаусом Виртом , включив в себя некоторые концепции (с другим синтаксисом и обозначениями) из синтаксической нотации Вирта . Сегодня используется множество вариантов EBNF. Международная организация по стандартизации EBNF приняла стандарт ISO/IEC 14977 в 1996 году. [ 1 ] [ 2 ] Однако, по словам Зайцева, этот стандарт «лишь добавил к хаосу еще три диалекта» и, отметив его неуспех, также отмечает, что ISO EBNF даже не используется во всех стандартах ISO. [ 3 ] Уиллер выступает против использования стандарта ISO при использовании EBNF и рекомендует рассмотреть альтернативные нотации EBNF, например, из расширяемого языка разметки W3C (XML) 1.0 (пятое издание). [ 4 ]
В этой статье используется EBNF, указанный ISO, для примеров, применимых ко всем EBNF. Другие варианты EBNF используют несколько другие синтаксические соглашения.
Основы
[ редактировать ]EBNF — это код , выражающий синтаксис формального языка. [ 5 ] EBNF состоит из терминальных символов и нетерминальных правил производства, которые представляют собой ограничения, определяющие, как терминальные символы могут быть объединены в действительную последовательность. Примеры терминальных символов включают буквенно-цифровые символы , знаки препинания и символы пробелов .
EBNF определяет правила производства , в которых последовательности символов соответственно присваиваются нетерминалу :
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit excluding zero ;
Это производственное правило определяет нетерминальную цифру , которая находится в левой части присвоения. Вертикальная черта представляет альтернативу, а символы терминала заключаются в кавычки, за которыми следует точка с запятой в качестве завершающего символа. Следовательно, цифра — это 0 или цифра, исключая ноль , который может быть 1 , 2 или 3 и так далее до 9 .
Продукционное правило также может включать последовательность терминалов или нетерминалов, каждый из которых разделен запятой:
twelve = "1", "2" ;
two hundred one = "2", "0", "1" ;
three hundred twelve = "3", twelve ;
twelve thousand two hundred one = twelve, two hundred one ;
Выражения, которые можно опустить или повторить, можно представить с помощью фигурных скобок { ... }:
natural number = digit excluding zero, { digit } ;
В этом случае строки 1 , 2 , ..., 10 , ..., 10000 , ... являются правильными выражениями. Чтобы представить это, все, что установлено в фигурных скобках, может повторяться сколь угодно часто, в том числе не повторяться вообще.
Опцию можно представить через квадратные скобки [...]. То есть все, что указано в квадратных скобках, может присутствовать только один раз или не присутствовать вообще:
integer = "0" | [ "-" ], natural number ;
Таким образом, целое число — это ноль ( 0 ) или натуральное число , которому может предшествовать необязательный знак минус .
EBNF также предоставляет, среди прочего, синтаксис для описания повторений (определенного количества раз), исключения некоторой части продукции и вставки комментариев в грамматику EBNF.
Таблица символов
[ редактировать ]Ниже представлен предлагаемый стандарт ISO/IEC 14977, разработанный RS Scowen, стр. 7, таблицы 1 и 2.
| Использование | Обозначения | Альтернатива | Значение |
|---|---|---|---|
| определение | = | ||
| конкатенация | , | ||
| прекращение | ; | . | |
| чередование | | | / или ! | |
| необязательный | [ ... ] | (/ ... /) | ни один или один раз |
| повторение | { ... } | (: ... :) | ни одного или более |
| группировка | ( ... ) | ||
| терминальная строка | "..." | ' ... ' | |
| комментарий | (* ... *) | ||
| специальная последовательность | ? ... ? | ||
| исключение | - |
Примеры
[ редактировать ]Синтаксическая диаграмма
[ редактировать ]
ЕБНФ
[ редактировать ]Даже EBNF можно описать с помощью EBNF. Рассмотрим приведенную ниже грамматику (используя такие соглашения, как «-» для обозначения дизъюнкции множеств, «+» для обозначения одного или нескольких совпадений и «?» для обозначения необязательности):
letter = "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" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
| "'" | '"' | "=" | "|" | "." | "," | ";" | "-"
| "+" | "*" | "?" | "\n" | "\t" | "\r" | "\f" | "\b" ;
character = letter | digit | symbol | "_" | " " ;
identifier = letter , { letter | digit | "_" } ;
S = { " " | "\n" | "\t" | "\r" | "\f" | "\b" } ;
terminal = "'" , character - "'" , { character - "'" } , "'"
| '"' , character - '"' , { character - '"' } , '"' ;
terminator = ";" | "." ;
term = "(" , S , rhs , S , ")"
| "[" , S , rhs , S , "]"
| "{" , S , rhs , S , "}"
| terminal
| identifier ;
factor = term , S , "?"
| term , S , "*"
| term , S , "+"
| term , S , "-" , S , term
| term , S ;
concatenation = ( S , factor , S , "," ? ) + ;
alternation = ( S , concatenation , S , "|" ? ) + ;
rhs = alternation ;
lhs = identifier ;
rule = lhs , S , "=" , S , rhs , S , terminator ;
grammar = ( S , rule , S ) * ;
Паскаль
[ редактировать ]Язык программирования, подобный Паскалю , допускающий только присваивания, можно определить в EBNF следующим образом:
(* a simple program syntax in EBNF - Wikipedia *)
program = 'PROGRAM', white space, identifier, white space,
'BEGIN', white space,
{ assignment, ";", white space },
'END.' ;
identifier = alphabetic character, { alphabetic character | digit } ;
number = [ "-" ], digit, { digit } ;
string = '"' , { all characters - '"' }, '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ;
alphabetic character = "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" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
white space = ? white space characters ? ;
all characters = ? all visible characters ? ;
Например, синтаксически правильная программа может выглядеть так:
PROGRAM DEMO1
BEGIN
A:=3;
B:=45;
H:=-100023;
C:=A;
D123:=B34A;
BABOON:=GIRAFFE;
TEXT:="Hello world!";
END.
Язык можно легко расширить за счет потоков управления , арифметических выражений и инструкций ввода/вывода. Затем будет разработан небольшой, удобный язык программирования.
Преимущества перед БНФ
[ редактировать ]Любая грамматика, определенная в EBNF, также может быть представлена в BNF, хотя представления в последнем обычно более длинные. Например, варианты и повторения не могут быть напрямую выражены в BNF и требуют использования промежуточного правила или альтернативного производства, определенного как ничего, или необязательного производства для варианта, или либо повторного производства самого себя, рекурсивно, для повторения. Те же конструкции по-прежнему можно использовать в EBNF.
BNF использует символы ( <, >, |, ::=) сам по себе, но не включает кавычки вокруг терминальных строк. Это предотвращает использование этих символов в языках и требует специального символа для пустой строки. В EBNF терминалы заключаются строго в кавычки ( "... " или '... '). Угловые скобки (" <... >") для нетерминалов можно опустить.
Синтаксис BNF может представлять правило только в одной строке, тогда как в EBNF завершающий символ, символ точки с запятой « ;» отмечает конец правила.
Кроме того, EBNF включает в себя механизмы улучшений, определяющие количество повторов, исключающие альтернативы, комментарии и т. д.
Конвенции
[ редактировать ]- Согласно разделу 4 стандарта ISO/IEC 14977 используются следующие условные обозначения:
- Каждый метаидентификатор расширенного BNF записывается как одно или несколько слов, соединенных дефисами . Однако соединение слов, похоже, применимо только к ссылкам на метаидентификаторы вне самого метаязыка, как видно из примеров стандарта.
- Метаидентификатор, заканчивающийся на -symbol, представляет собой имя терминального символа расширенного BNF.
- Обычный символ, представляющий каждый оператор расширенного BNF и его подразумеваемый приоритет (наивысший приоритет вверху):
* repetition-symbol - except-symbol , concatenate-symbol | definition-separator-symbol = defining-symbol ; terminator-symbol . terminator-symbol
- Обычный приоритет переопределяется следующими парами скобок:
Символом первой кавычки является апостроф , определенный в ISO/IEC 646:1991, то есть Unicode U+0027 (
(* start-comment-symbol end-comment-symbol *) ' first-quote-symbol first-quote-symbol ' ( start-group-symbol end-group-symbol ) [ start-option-symbol end-option-symbol ] { start-repeat-symbol end-repeat-symbol } ? special-sequence-symbol special-sequence-symbol ? " second-quote-symbol second-quote-symbol "
'); шрифт, используемый в ISO/IEC 14977:1996(E), очень похож на острый шрифт Unicode U+00B4 (´), поэтому иногда возникает путаница. Однако стандарт ISO Extended BNF использует ISO/IEC 646:1991, «7-битный набор кодированных символов ISO для обмена информацией», в качестве нормативной ссылки и не упоминает какие-либо другие наборы символов, поэтому формально нет путаницы с Символы Юникода вне 7-битного диапазона ASCII.
В качестве примеров следующие синтаксические правила иллюстрируют возможности выражения повторения:
aa = "A";
bb = 3 * aa, "B";
cc = 3 * [aa], "C";
dd = {aa}, "D";
ee = aa, {aa}, "E";
ff = 3 * aa, 3 * [aa], "F";
gg = {3 * aa}, "G";
hh = (aa | bb | cc), "H";
Терминальные строки, определенные этими правилами, следующие:
aa: A bb: AAAB cc: C AC AAC AAAC dd: D AD AAD AAAD AAAAD etc. ee: AE AAE AAAE AAAAE AAAAAE etc. ff: AAAF AAAAF AAAAAF AAAAAAF gg: G AAAG AAAAAAG etc. hh: AH AAABH CH ACH AACH AAACH
Расширяемость
[ редактировать ]Согласно стандарту ISO 14977, EBNF должен быть расширяемым, и упоминаются две возможности. Первый — это часть грамматики EBNF, специальная последовательность, представляющая собой произвольный текст, заключенный в вопросительные знаки. Интерпретация текста внутри специальной последовательности выходит за рамки стандарта EBNF. Например, символ пробела можно определить по следующему правилу:
space = ? ASCII character 32 ?;
Второе средство расширения использует тот факт, что круглые скобки в EBNF нельзя размещать рядом с идентификаторами (они должны быть объединены с ними). Действителен следующий EBNF:
something = foo, ( bar );
Следующее не является допустимым EBNF:
something = foo ( bar );
Следовательно, расширение EBNF может использовать это обозначение. Например, в грамматике Лиспа применение функции может быть определено следующим правилом:
function application = list( symbol, { expression } );
Связанная работа
[ редактировать ]- W3C . EBNF нотацию публикует
- W3C другой использовал EBNF для определения синтаксиса XML .
- Британский институт стандартов опубликовал стандарт EBNF: BS 6154 в 1981 году.
- IETF ( ABNF использует расширенный BNF ), указанный в РФК 5234 .
См. также
[ редактировать ]- Meta-II - ранний инструмент для написания компиляторов и обозначений.
- Правила построения фраз – прямой эквивалент EBNF в естественных языках.
- Регулярное выражение
- Платформа парсера Spirit
Ссылки
[ редактировать ]- ^ Роджер С. Скоуэн: Расширенный BNF — общий базовый стандарт. Симпозиум по стандартам разработки программного обеспечения, 1993 г.
- ^ Международный стандарт ( ISO 14977 ), который является одним из многих форматов EBNF, теперь доступен бесплатно как PDF-файл, сжатый в формате Zip .
- ^ Зайцев, Вадим (26–30 марта 2012 г.). «Здесь был BNF: что мы сделали с ненужным разнообразием обозначений синтаксических определений?» (PDF) . Материалы 27-го ежегодного симпозиума ACM по прикладным вычислениям (SAC '12) . Рива дель Гарда, Италия. п. 1.
- ^ Уилер, Дэвид А. (2019). «Не используйте расширенную форму Бэкуса-Наура (EBNF) ISO/IEC 14977» . Проверено 26 февраля 2021 г.
- ^ Паттис, Ричард Э. «EBNF: обозначение для описания синтаксиса» (PDF) . ICS.UCI.edu . Калифорнийский университет в Ирвайне . п. 1 . Проверено 26 февраля 2021 г.
Внешние ссылки
[ редактировать ]- ИСО/МЭК 14977: 1996(Е)
- Варианты BNF/EBNF - таблица Пита Джинкса, сравнивающая несколько синтаксисов.