Как читать альтернативы в грамматике EBNF - PullRequest
Новая
       5

Как читать альтернативы в грамматике EBNF

0 голосов
/ 21 июня 2010

У меня есть грамматика 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 ]

2 голосов
/ 21 июня 2010

Это правило также будет эквивалентно sequence ::= (item extra*)*, что исключит рекурсию для sequence.

2 голосов
/ 21 июня 2010

Не совсем, похоже, у них разные ошибки.Первая последовательность неоднозначна вокруг «элемента», видя, что «дополнительный» является необязательным.Вы можете переписать его следующим образом, чтобы убрать неоднозначность: 

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-pair, разделенных необязательной белой / запятой.Любое из следующего будет составлять 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 последовательных number с.

Я разработал грамматику в 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

он создает это дерево разбора.

альтернативный текст http://www.freeimagehosting.net/uploads/85fc77bc3c.png

0 голосов
/ 21 июня 2010

Да, эти две грамматики описывают один и тот же язык.

Но действительно ли это EBNF? Статья в Википедии о EBNF не включает оператора Kleene star.

...