Как читать альтернативы в грамматике EBNF
У меня есть грамматика EBNF, которая имеет несколько правил с этим шаблоном:
sequence ::=
item
| item extra* sequence
Вышеуказанное эквивалентно следующему?
sequence ::=
item (extra* sequence)*
редактировать
Из-за того, что некоторые из вас наблюдают ошибки или неясности в обеих последовательностях, я приведу конкретный пример. Спецификация SVG предоставляет грамматику для данных пути. У этой грамматики есть несколько производителей с этим шаблоном:
lineto-argument-sequence:
coordinate-pair
| coordinate-pair comma-wsp? lineto-argument-sequence
Можно ли переписать вышеизложенное как следующее?
lineto-argument-sequence:
coordinate-pair (comma-wsp? lineto-argument-sequence)*
3 ответа
Не совсем, похоже, у них разные ошибки. Первая последовательность неоднозначна вокруг "элемента", видя, что "дополнительный" является необязательным. Вы можете переписать его следующим образом, чтобы убрать неоднозначность:
sequence3 ::=
item extra* sequence3
Второй вариант неоднозначен в отношении "extra", поскольку в основном это два вложенных цикла, оба начинаются с "extra". Вы можете переписать его следующим образом, чтобы убрать неоднозначность:
sequence4 ::=
item ((extra|item))*
Ваша первая версия, вероятно, захлебнется входной последовательностью, состоящей из одного "элемента" (это зависит от реализации синтаксического анализатора), потому что она не будет устранять неоднозначность.
Мои переписывания предполагают, что вы хотите сопоставить последовательность, начинающуюся с "item" и, возможно, за которой следует последовательность (0 или более) "item" или "extra" в любом порядке.
например
item
item extra
item extra item
item extra extra item
item item item item
item item item item extra
etc.
Без дополнительной информации я был бы лично склонен к опции, которую я назвал "sequence4", поскольку все остальные опции просто используют рекурсию в качестве дорогостоящей конструкции цикла. Если вы захотите дать мне больше информации, я смогу дать лучший ответ.
РЕДАКТИРОВАТЬ: на основе превосходного наблюдения Йорна (с небольшим модом).
Если вы переписали "sequence3" для удаления рекурсии, вы получите следующее:
sequence5 ::=
(item extra*)+
Думаю, это будет моя любимая версия, а не "sequence4".
Я должен указать, что все три версии выше функционально эквивалентны (как распознаватели или генераторы). Деревья разбора для 3 будут отличаться от 4 и 5, но я не могу думать, что это повлияет на что-то кроме, возможно, производительности.
РЕДАКТИРОВАТЬ: Относительно следующего:
lineto-argument-sequence:
coordinate-pair
| coordinate-pair comma-wsp? lineto-argument-sequence
Это производство говорит о том, что lineto-argument-sequence состоит как минимум из одного coordinate-pair с последующим нолем или более coordinate-pairs разделены необязательным белым / запятой. Любое из следующего будет составлять lineto-argument-sequence (читать -> как "становится"):
1,2 -> (1, 2)
1.5.6 -> (1.5, 0.6)
1.5.06 -> (1.5, 0.06)
2 3 3 4 -> (2,3) (3,4)
2,3-3-4 -> (2,3) (-3,-4)
2 3 3 -> ERROR
Так что coordinate-pair действительно любые 2 подряд numbers.
Я разработал грамматику в ANTLR, которая, кажется, работает. Обратите внимание на шаблон, используемый для lineto_argument_sequence похож на тот, который Jorn и я рекомендовал ранее.
grammar SVG;
lineto_argument_sequence
: coordinate_pair (COMMA_WSP? coordinate_pair)*
;
coordinate_pair
: coordinate COMMA_WSP? coordinate
;
coordinate
: NUMBER
;
COMMA_WSP
: ( WS+|WS*','WS*) //{ $channel=HIDDEN; }
;
NUMBER
: '-'? (INT | FLOAT) ;
fragment
INT
: '0'..'9'+ ;
fragment
FLOAT
: ('0'..'9')+ '.' ('0'..'9')* EXPONENT?
| '.' ('0'..'9')+ EXPONENT?
| ('0'..'9')+ EXPONENT
;
fragment
WS : ' ' | '\t' | '\r' | '\n' ;
fragment
EXPONENT
: ('e'|'E') ('+'|'-')? ('0'..'9')+ ;
Учитывая следующий вход:
2, 3 -3 -4 5.5.65.5.6
он производит это дерево разбора.
Это правило также будет эквивалентно sequence ::= (item extra*)*таким образом удаляя рекурсию на sequence,
Да, эти две грамматики описывают один и тот же язык.
Но действительно ли это EBNF? Статья в Википедии о EBNF не включает оператора Kleene star.