0

このパターンのいくつかのルールを持つ 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)*
4

3 に答える 3

3

そうではありませんが、それらにはさまざまなバグがあるようです。最初のシーケンスは、"extra" がオプションであることから、"item" の周りがあいまいです。あいまいさを取り除くために、次のように書き直すことができます。

sequence3 ::= 
    item extra* sequence3

2 つ目は、基本的に「extra」で始まる 2 つのネストされたループであるため、「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」とラベル付けしたオプションに個人的に傾くでしょう。もっと詳しく教えていただければ、より良い回答ができるかもしれません。

編集: Jorn の優れた観察に基づいています (小さな mod を使用)。

"sequence3" を書き換えて再帰を削除すると、次のようになります。

sequence5 ::= 
    (item extra*)+

「sequence4」ではなく、これが私の好みのバージョンになると思います。

上記の 3 つのバージョンはすべて (レコグナイザーまたはジェネレーターとして) 機能的に同等であることを指摘する必要があります。3 の解析ツリーは 4 および 5 とは異なりますが、それがおそらくパフォーマンス以外に影響を与えるとは考えられません。

編集： 以下に関して：

lineto-argument-sequence:
    coordinate-pair
    | coordinate-pair comma-wsp? lineto-argument-sequence

このプロダクションが言っていることは、 aは、オプションの白/コンマで区切られた 0 個以上の s が続くlineto-argument-sequence少なくとも 1 つの要素で構成されているということです。次のいずれかが(read -> as 'becomes') を構成します。coordinate-paircoordinate-pairlineto-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

したがって、acoordinate-pairは実際には任意の 2 つの連続numberする s です。

動作するように見える 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

于 2010-06-20T22:22:03.103 に答える
2

このルールもと同等sequence ::= (item extra*)*であるため、の再帰は削除されsequenceます。

于 2010-06-20T21:00:41.227 に答える
0

はい、これら 2 つの文法は同じ言語を記述しています。

しかし、それは本当に EBNF ですか? EBNF に関するウィキペディアの記事には、Kleene スター演算子は含まれていません。

于 2010-06-20T20:25:51.327 に答える