В информатике , расширенная Бэкуса-Наура ( РБНФ ) представляет собой семейство metasyntax обозначений, любой из которых может быть использован для выражения контекстно-свободной грамматики . EBNF используется для формального описания формального языка, такого как язык компьютерного программирования . Они являются расширением основной метасинтаксической нотации формы Бэкуса – Наура (BNF).
Самый ранний EBNF был разработан Никлаусом Виртом, включающим некоторые концепции (с другим синтаксисом и обозначениями) из синтаксической нотации Вирта . Однако используются многие варианты EBNF. [1] Международная организация по стандартизации приняла стандарт EBNF ( ISO / IEC 14977 ) , в 1996 г. Однако, по Зайцевой этого стандарта «только кончались добавляя еще один три диалекта в хаос» и, отметив его отсутствие успеха, также отмечает, что ISO EBNF даже не используется во всех стандартах ISO. Уилер выступает против использования стандарта ISO при использовании EBNF и рекомендует рассмотреть альтернативные нотации EBNF, например, из W3C Extensible Markup Language (XML) 1.0 (пятое издание).
В этой статье используется EBNF, как указано в ISO для примеров, применимых ко всем EBNF. В других вариантах EBNF используются несколько иные синтаксические соглашения.
Основы
EBNF - это код, который выражает синтаксис формального языка. [2] 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.
Применение | Обозначение |
---|---|
определение | знак равно |
конкатенация | , |
прекращение | ; |
чередование | | |
по желанию | [...] |
репетиция | {...} |
группировка | (...) |
клеммная строка | "..." |
клеммная строка | '...' |
комментарий | (* ... *) |
особая последовательность | ? ...? |
исключение | - |
Примеры
Диаграмма синтаксиса
Даже EBNF можно описать с помощью EBNF. Рассмотрим схематическую грамматику ниже:
письмо = "А" | «Б» | "C" | «Д» | "E" | "F" | "G" | "H" | «Я» | "J" | «К» | "L" | «М» | «N» | «О» | "П" | «Q» | «Р» | "S" | «Т» | "U" | "V" | "W" | «Х» | «Y» | "Z" | "а" | "б" | "с" | "д" | "е" | "е" | "г" | "h" | "я" | "j" | "к" | "л" | "м" | "п" | "о" | "р" | "q" | "г" | "s" | "т" | "u" | "v" | "ш" | «х» | "у" | "z" ; цифра = "0" | «1» | «2» | «3» | «4» | «5» | «6» | «7» | «8» | «9» ; символ = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">" | "'" | '"' | " = " | " | " | ". " | ", " | "; " ; символ = буква | цифра | символ | " _ " ; идентификатор = буква , { буква | цифра | "_" } ; терминал = "'" , символ , { символ } , "'" | '"' , символ , { персонаж } , '"' ; lhs = идентификатор ; rhs = идентификатор | терминал | "[" , rhs , "]" | "{" , rhs , "}" | "(" , rhs , ")" | rhs , "|" , правая | rhs , "," , rhs ;rule = lhs , "=" , rhs , ";" ; грамматика = { правило } ;
Паскаль -как язык программирования , который позволяет только задания могут быть определены в EBNF следующим образом :
(* простой программный синтаксис в EBNF - Википедия *) program = 'PROGRAM' , white_space , identifier , white_space , 'BEGIN' , white_space , { назначение , ";" , white_space }, 'КОНЕЦ.' ; идентификатор = alphabetic_character , { alphabetic_character | цифра } ; число = [ "-" ], цифра , { цифра } ; string = '"' , { all_characters - '"' }, '"' ; assignment = identifier , ": = " , ( число | идентификатор | строка ) ; 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» ; цифра = «0» | «1» | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; white_space = ? white_space символов ; all_characters = ? все видимые символы ;
Например, синтаксически правильной программой может быть:
ПРОГРАММА DEMO1 BEGIN A : = 3 ; В : = 45 ; H : = - 100023 ; С : = А ; D123 : = B34A ; БАБУН : = ЖИРАФ ; ТЕКСТ : = " Привет, мир !" ; КОНЕЦ .
Язык можно легко расширить с помощью потоков управления , арифметических выражений и инструкций ввода / вывода. Затем будет разработан небольшой удобный язык программирования.
Преимущества перед BNF
Любая грамматика, определенная в EBNF, также может быть представлена в BNF, хотя представления в последнем обычно более длинные. Например, варианты и повторения не могут быть напрямую выражены в BNF и требуют использования промежуточного правила или альтернативного производства, которое определяется как «ничто», либо как факультативное производство для варианта, либо как повторное производство себя, рекурсивно, для повторения. Те же конструкции все еще можно использовать в EBNF.
BNF использует символы ( <
, >
, |
, ::=
) для себя, но не включает в себя кавычки терминальных цепочек. Это предотвращает использование этих символов в языках и требует специального символа для пустой строки. В EBNF клеммы строго заключаются в кавычки ( "
... "
или '
... '
). Угловые скобки (« <
… >
») для нетерминалов можно опустить.
Синтаксис BNF может представлять правило только в одной строке, тогда как в EBNF символ завершения, точка с запятой « ;
» обозначает конец правила.
Кроме того, EBNF включает механизмы для улучшений, определения количества повторов, исключения альтернатив, комментариев и т. Д.
Условные обозначения
- Используются следующие условные обозначения:
- Каждый метаидентификатор расширенного BNF записывается как одно или несколько слов, соединенных дефисами .
- Метаидентификатор, оканчивающийся на -символ, - это имя терминального символа расширенного BNF.
- Обычный символ, представляющий каждый оператор расширенного BNF и его подразумеваемый приоритет (наивысший приоритет вверху):
* Повторение-символ - кроме-символ , конкатенация-символ | определение-разделитель-символ = определяющий-символ ; символ-терминатор . символ-терминатор
- Обычный приоритет отменяется следующими парами скобок: Символ первой кавычки - это апостроф, как определено в 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.
В качестве примеров следующие правила синтаксиса иллюстрируют возможности для выражения повторения:
aa = "А" ; bb = 3 * aa , «В» ; cc = 3 * [ aa ], "C" ; дд = { аа }, «Д» ; ее = аа , { аа }, «Е» ; ff = 3 * aa , 3 * [ aa ], «F» ; gg = { 3 * aa }, "G" ;
Терминальные строки, определенные этими правилами, следующие:
аа: Аbb: AAABКопия: C AC AAC AAACdd: D AD AAD AAAD AAAAD и т. д.ee: AE AAE AAAE AAAAE AAAAAE и т. д.ff: AAAF AAAAF AAAAAF AAAAAAFgg: G AAAG AAAAAAG и т. д.
Расширяемость
Согласно стандарту ISO 14977 EBNF должен быть расширяемым, и упоминаются два объекта. Первый - это часть грамматики EBNF, особая последовательность, которая представляет собой произвольный текст, заключенный в вопросительные знаки. Интерпретация текста внутри специальной последовательности выходит за рамки стандарта EBNF. Например, пробел можно определить по следующему правилу:
пробел = ? 32-й символ ASCII? ;
Вторая возможность расширения заключается в том, что скобки в EBNF не могут быть помещены рядом с идентификаторами (они должны быть связаны с ними). Следующее является действительным EBNF:
something = foo , ( бар );
Следующее является не действительным EBNF:
something = foo ( бар );
Следовательно, расширение EBNF может использовать эту нотацию. Например, в грамматике Лиспа приложение функции может быть определено следующим правилом:
функция приложение = список ( символ , { выражение } );
Связанных с работой
- W3C использовал другой EBNF указать XML - синтаксис.
- Британский институт стандартов опубликовал стандарт в EBNF: BS 6154 в 1981 году.
- IETF использует дополненной BNF (ABNF), указанный в RFC 5234.
Смотрите также
- Meta-II - ранний инструмент для написания компиляторов и нотаций
- Правила структуры фраз - прямой эквивалент EBNF в естественных языках.
- Регулярное выражение
- Фреймворк Spirit Parser
Рекомендации
- ↑ Зайцев, Вадим (26–30 марта 2012 г.). «Здесь был BNF: что мы сделали с ненужным разнообразием обозначений для синтаксических определений?» (PDF) . Материалы 27-го ежегодного симпозиума ACM по прикладным вычислениям (SAC '12) . Рива дель Гарда, Италия. п. 1.
- ^ Паттис, Ричард Э. «EBNF: Нотация для описания синтаксиса» (PDF) . ICS.UCI.edu . Калифорнийский университет в Ирвине . п. 1 . Проверено 26 февраля 2021 .
- Роджер С. Скоуэн: Расширенный BNF - общий базовый стандарт. Симпозиум по стандартам программной инженерии 1993.
- Дэвид А. Уиллер, Не используйте расширенную форму Бэкуса-Наура ISO / IEC 14977 (EBNF) , 2019.
- Международный стандарт ( ISO 14977 ), который является одним из многих форматов для EBNF, теперь свободно доступен в виде файла PDF, сжатого в формате Zip .
- Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.
Внешние ссылки
- ИСО / МЭК 14977: 1996 (E)
- RFC 4234 - расширенный BNF для спецификаций синтаксиса: ABNF (устарело в соответствии с RFC 5234)
- Варианты BNF / EBNF - таблица Пита Джинкса, сравнивающая несколько синтаксисов
- Парсер и рендерер в PHP5
- Представление синтаксической диаграммы SRFB с помощью функции Basis + генерация EBNF (javascript)