Является ли альтернативный оператор в ABNF коммутативным?
Является ли альтернативный оператор (/) в расширенной форме Бэкуса-Наура коммутативно?
Например, это s = a / b такой же как s = b / a?
0 ответов
Я не нашел никаких первоисточников по BNF или ABNF, которые явно указывают / семантика, когда обе стороны будут давать действительные совпадения. Они также не ссылаются на контекстно-свободные грамматики и их допущение для недетерминизма. Если кто-нибудь знает уточняющие ссылки, пожалуйста, поделитесь.
РЕДАКТИРОВАТЬ: Ответ Тони указывает на RFC 3501 от 2003 года определяет семантику чередования ABNF, по крайней мере, как это используется в этом документе.
RFC 5234: расширенный BNF для синтаксических спецификаций: ABNF (2008)
Введение контрастирует с BNF и ABNF (с акцентом, добавленным здесь):
На протяжении многих лет модифицированная версия формы Бэкуса-Наура (BNF), названная Augmented BNF (ABNF), была популярна среди многих спецификаций Интернета. Это уравновешивает компактность и простоту с разумной представительной силой. В начале существования Arpanet каждая спецификация содержала свое собственное определение ABNF. Это включало спецификации электронной почты, RFC733 и затем RFC822, которые стали общими цитатами для определения ABNF. Текущий документ разделяет эти определения, чтобы разрешить выборочную ссылку.
Различия между стандартными BNF и ABNF заключаются в правилах именования, повторении, альтернативах, независимости от порядка и диапазонах значений.
"Выборочная ссылка" и "независимость от порядка" могут относиться к семантике чередования, но неясно.
RFC 822: Стандарт для формата текстовых сообщений ARPA Internet (1982)
Если я что-то упустил, как не указано в цитируемых RFC / семантика тоже. Раздел 2.2 уклоняется от проблемы.
2.2. ПРАВИЛО1 / ПРАВИЛО2: АЛЬТЕРНАТИВЫ
Элементы, разделенные косой чертой ("/"), являются альтернативами. Поэтому "foo / bar" будет принимать foo или bar.
Различные определения правил показывают, что они признают практическую важность избежания двусмысленности. Например, вот как RFC 822 определяет optional-field и его зависимости:
optional-field =
/ "Message-ID" ":" msg-id
/ "Resent-Message-ID" ":" msg-id
/ "In-Reply-To" ":" *(phrase / msg-id)
/ "References" ":" *(phrase / msg-id)
/ "Keywords" ":" #phrase
/ "Subject" ":" *text
/ "Comments" ":" *text
/ "Encrypted" ":" 1#2word
/ extension-field ; To be defined
/ user-defined-field ; May be pre-empted
extension-field =
<Any field which is defined in a document
published as a formal extension to this
specification; none will have names beginning
with the string "X-">
user-defined-field =
<Any field which has not been defined
in this specification or published as an
extension to this specification; names for
such fields must be unique and may be
pre-empted by published extensions>
Синтаксис и семантика предложенного международного алгебраического языка конференции ACM-GAMM в Цюрихе (Backus 1958)
BNF происходит от обозначения IAL. В статье вводится ̅o̅r "металингвистическая связка", которая интуитивно связана с /, Тем не менее, он также уклоняется от неоднозначной проблемы выбора и, по-видимому, просто использует ее осторожно.
Рекомендация
Из-за неустановленной семантики я предлагаю рассматривать каждое возможное совпадение в alternation Правило как действительное. Если грамматика не разработана тщательно, чтобы избежать неоднозначности, эта интерпретация может привести к нескольким действительным деревьям разбора для одного и того же ввода. Адресация неоднозначных разборов по мере их возникновения безопаснее, чем продвигаться вперед с непреднамеренно допустимым деревом разбора.
В качестве альтернативы, если у вас есть влияние на то, как указывается грамматика, вы можете рассмотреть нотацию с более четкой семантикой. Например, грамматика синтаксического анализа при разборе: основанная на распознавании синтаксическая основа (Ford 2004) дает альтернативы детерминированной приоритетной семантике выбора (выигрыши с крайним левым соответствием).
Некоторые RFC разъясняют это в явном виде, например, в RFC3501 IMAPv4, включая спецификацию PEG-подобного поведения в разделе 9 RFC 3501:
В случае альтернативных или необязательных правил, в которых более позднее правило перекрывается с более ранним правилом, правило, которое перечислено ранее, ДОЛЖНО иметь приоритет. Например, "\Seen", когда он анализируется как флаг, является именем флага \ Seen, а не расширением флага, даже если "\ Seen" может быть проанализировано как расширение флага. Некоторые, но не все, примеры этого правила указаны ниже.
Я не знаю, насколько распространены такие неоднозначности (ха), хотя. Многие другие RFC, на которые я смотрел (в последние дни я реализовывал библиотеку синтаксического анализатора ABNF), просто оставляют ее неопределенной. Многие грамматики RFC ABNF однозначны (например, RFC8259 (JSON)); однако многие из них неоднозначны (например, RFC5322 (Интернет-сообщения)) и требуют исправлений для работы с анализатором, сохраняющим неоднозначность:-(