如何阅读 EBNF 语法中的替代项

Question

我有一个 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)*

Answer 1

事实并非如此，他们似乎有不同的错误。第一个序列围绕“item”是不明确的，因为“extra”是可选的。您可以将其重写为以下内容以消除歧义：

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

因此坐标对实际上是任何2个连续的数量。

我在 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

Answer 2

此规则也相当于 sequence ::= (item extra*)*，从而删除 sequence 上的递归。

Answer 3

是的，这两种语法描述的是同一种语言。

但这真的是 EBNF 吗？ 关于 EBNF 的维基百科文章不包括 Kleene 星运算符。