3

例如，

EBNF

A ::= B c;

B ::= T1 | T2 | ε

T1 ::= 一个

T2 ::= b

parseA()
{
switch(currentToken.kind){
case Token.a :
    parseT1();
case Token.b :
    parseT2();
break;

case <epsilon> :
    
break;
default:
    // report error
break;
}
}

如何编写解析器在 Java 中解析 epsilon（空字符串集）？

4

4 回答 4

5

无论是 Java 还是任何语言，关键是你有一个令牌流。您不会“获得”令牌并决定要做什么。相反，您“查看”下一个令牌，如果可以使用它，则“接受”它。

看到不同？

不要“得到”然后“决定”。
做“看看和决定”，然后“接受”。
这是“前瞻”概念的核心。

因此，ParseA 调用 ParseB。

Parse B 查看流中的下一个标记。
如果它是“a”，它接受它并返回。
如果它是“b”，它接受它并返回。
否则，它只会返回 ParseA（不接受任何内容）。

然后 ParseA 查看下一个标记。
如果它是“c”，它接受它并返回。
否则失败。

说得通？

为此，您应该在流的末尾添加一个标记标记，该标记永远不会被接受。最后，这应该是流中剩下的唯一标记。如果没有，你会得到一个语法错误，最后包含额外的垃圾。

于 2010-07-31T19:13:39.267 回答
4

epsilon只是“此处允许空字符串”的标记，因此您无需解析任何内容；下降结束。不过，您实际上似乎不太可能为此获得令牌；您需要检测是否没有可用的令牌，或者下一个令牌是否可以在另一个生产中使用。

例如，您可能会得到 input c。您需要意识到这与生产相匹配A ::= B c;，因为B可以简化为epsilon- 没有epsilon令牌，您只需要意识到 B 规则是可选的，在这种情况下需要跳过以简化c为A

于 2010-07-31T18:20:02.667 回答
3

就目前而言，作为解析器，这有点过于简单化了。整个事情可以写成一个简单的正则表达式：“[ab]?c”。如果您真的坚持将其编写为解析器，则代码可能类似于：

Boolean parseA() { 
    // an A is a B followed by a `c`:
    return parseB() && (get_token() == Token.c);
}

Boolean parseB  {
    // Get a token. 
    //     If it's an `a` or a `b`, consume it. 
    //     Otherwise, throw it back (match null string by consuming nothing).
    // Either way, return true (successful match).
    //
    token current_token = get_token();
    if (token != Token.a && token != Token.b)
        push_back(current_token);
    return true;
}

编辑（回应对另一个答案的评论）：不，当你匹配 B 时，你不应该寻找Token.c。就 B 而言，存在三种可能性：匹配“a”、匹配“b”或什么都不匹配。然后由解析 A 的部分来检查它是否有一个 B 后跟一个 Token.c。

例如，如果您要将语法更改为：

A ::= 公元前

B ::= 一个 | 乙 | ε

C ::= c | d

由于“B”仍然具有相同的定义，因此您不必仅仅因为其他一些定义发生更改而对其进行更改。同样，您可以添加到语法中以允许（例如）任意字符串 B 后跟 C。

于 2010-07-31T18:36:57.510 回答
0

当您在当前非终端的 FOLLOW 集中看到任何内容时，您会“解析”一个 epsilon。因此，由于 FOLLOW(B) = { 'c' }，您case Token.c:在 parseB 中的 switch 中使用它

于 2010-07-31T19:15:54.050 回答