Ремесло программиста

Объявление

форум на движке phpBB доступен для тестирования
www.strategia.space
www.strategia.space/forum/
по предложению Лиса - канал на Matrix - #remdev:matrix.org

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.



ABNF vs EBNF

Сообщений 1 страница 7 из 7

1

ABNF - первая публикация 1977-11-21, последняя публикация 2008-01

русский текст (перевод):
https://rfc2.ru/5234.rfc
английский текст (исходный):
https://tools.ietf.org/html/rfc5234

"в качестве набора символов используется USASCII" - это конечно не UTF-8.
Хитрый (неявный) способ задания регистронезависимых строк.
Есть механизм создания производных спецификаций (но неясно, как им пользоваться).
Есть возможность задавать диапазоны кодов для символов.
В отличие от EBNF не содержит операции исключения.
Мне осталось неясным, как указать произвольный символ.
упоминается возможность задавать неупорядоченные группы, но такой возможности нет в формальном описании синтаксиса, это путает.

EBNF - 1996 год
русский текст можно найти тут:
https://groups.google.com/forum/?hl=ru#!forum/localizations
исходный текст
https://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf

тут нужны запятые и точка с запятой для разделения терминалов и правил (больше текста писать)
комментарии оформляются как (* ... *) вместо ; ...

есть "syntactic exception", за который я эту спецификацию и люблю.

можно сказать, что ABNF соотносится с EBNF как python с C#. Первые более компактнее в записи, но в них меньше синтаксического сахара.

Отредактировано Лис (2017-03-23 09:02:53)

2

Перевод EBNF так-себе. Тяжелый и не совсем корректный.

4.7 Синтаксическое-исключение

Синтаксическое-исключение состоит из синтаксического-фактора, являющегося предметом ограничения последовательностей символов, представленных синтаксическим-исключением, которое могло бы быть представлено идентичным образом с помощью синтаксического фактора,  не содержащего метаидентификаторов.
ПРИМЕЧАНИЕ: Если бы синтаксическому-исключению разрешено было быть произвольным синтаксическим фактором, то Расширенная ФБН могла бы определить более широкий класс языков, чем контекстно-независимые грамматики, включая попытки, которые приводят к парадоксам, подобным парадоксу Рассела, например:
xx = “A” – xx;
Является ли “A” примером xx? Такое разрешение является нежелательным, и поэтому форма синтаксического-исключения ограничена, оправдывая данное ограничение предоставлением безопасности подобных случаев.  Т.о., несмотря на то, что синтаксический-фактор в общем является эквивалентом некоторой контекстно-независимой грамматики, синтаксическое исключение  всегда является эквивалентом некоторой регулярной грамматики. Может показаться, что различием между контекстно-свободной грамматикой и регулярной грамматикой всегда является другая контекстно-независимая грамматика; следовательно синтаксический-термин (и следовательно
любая грамматика, определённая согласно данному стандарту) эквивалентна некоторой контекстно-независимой грамматике.

"Может показаться" - на самом деле следует переводить как "можно доказать" (It may be shown).
"Такое разрешение является нежелательным" - тоже неясный перевод, он формальный, но на английском понятнее (Such licence is undesirable).

Отредактировано Лис (2017-03-23 08:20:40)

3

Как определить, является ли некоторая часть контекстно-свободной грамматики регулярной?

У меня есть интуитивное ощущение, что это происходит, когда в части грамматики нет циклов (нетерминал не может раскрываться сам в себя), но оно необоснованное.
"a syntactic-factor that could be replaced by a syntactic-factor containing no meta-identifiers"
"Which I think means that a syntactic exception cannot be recursive and therefore must be the equivalent of a regular expression"

википедия ясности не добавляет:
https://en.wikipedia.org/wiki/Context-f … ar_grammar

ответ на Quora нравится попыткой формализации:
https://www.quora.com/What-is-the-diffe … e-language
но всё равно мне не ясен

пример на stackoverflow говорит, что моё интуитивное ощущение неверное:
http://stackoverflow.com/questions/5597 … e-grammars

S->ABA
A->something
B->something
You can clearly see that palindromes cannot be expressed in regular grammar since it needs to be either right or left linear and as such cannot have a non-terminal on both side.


Зачем мне это нужно?

Например я хочу определить нетерминалы:

любой символ = ? . ? ;
любое слово = любой символ , { любой символ } ;
нематерное слово = любое слово - ( "х" , { любой символ } | "п" , { любой символ }  | "б" , { любой символ } ) ;

Я вижу, что могу так формально написать в соответствии с грамматикой ISO EBNF, но не понимаю, как генератор парсера будет определять регулярность правой части.

Отредактировано Лис (2017-03-23 08:38:36)

4

https://www.youtube.com/watch?v=Ob60IirEm4s

Ясности пока не наступило. Пока идея в том, что надо превращать EBNF в BNF, затем проверять является ли BNF праворекурсивной.

Но даже если я это выясню, то мне не ясно, как реализовывать сам оператор "-".

Отредактировано Лис (2017-03-23 08:33:36)

5

Ответ на сообщение №6.
Ваше решение имеет кубическую сложность вместо линейной. И стиль речи... над ним надо поразмышлять.

Отредактировано Павиа (2017-03-23 16:33:41)

6

Лис написал(а):

У меня есть интуитивное ощущение, что это происходит, когда в части грамматики нет циклов (нетерминал не может раскрываться сам в себя), но оно необоснованное.

Не путайте регулярную граматику и регулярные выражения.

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

Все генераторы парсеров не являются законченными программами.  В том смысле что они не решают задачу разбора всех правил, а решают частную проблему.
По умолчанию они используют левую рекурсию, которую можно сменить модификатором

Ваша грамматика будет разобрана так как она регулярна. Вот с нерегулярной есть проблемы читай конфликт свёртка-свёртка и свёртка-сдвиг.

Лис написал(а):

Но даже если я это выясню, то мне не ясно, как реализовывать сам оператор "-".

Выполняешь вначале свёртку (не важно левая или правая) потом к результату свёртки применяешь условие(регулярное выражение).

7

Так как технически отменить действия Лиса нет возможно, то порядок сообщений перепутан.

Лис написал(а):

Ваше решение имеет кубическую сложность вместо линейной. И стиль речи... над ним надо поразмышлять.

Это зависит от генератора-парсеров, если он умеет распознавать регулярную грамматику, то он сделает код линейным.
Без учёта регулярных сообщений да сложность доходит до квадратичной, но в реальны программах таких правил очень мала, поэтому парсеры генерированные генераторами работают быстро. Что касается кубической сложности то её нет, так как регулярные выражения  в стандарте ограничены и могут быть закодированы линейно.

Так что в лучшем случае сложность линейная в худшем квадратичная.