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

不是真的，它们似乎有不同的错误。第一个序列在“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”的选项，因为所有其他选项只是将递归用作昂贵的循环构造。如果您愿意给我更多信息，我可能会给出更好的答案。

编辑：基于 Jorn 的出色观察（带有一个小模型）。

如果你重写“sequence3”来移除递归，你会得到以下结果：

sequence5 ::= 
    (item extra*)+

它认为这将是我的首选版本，而不是“sequence4”。

我必须指出，上述所有三个版本在功能上都是等效的（作为识别器或生成器）。3 的解析树与 4 和 5 不同，但我认为这会影响性能以外的任何东西。

编辑： 关于以下内容：

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

这个产生式的意思是 alineto-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

所以 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

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

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

于 2010-06-20T20:25:51.327 回答