用Java编写递归下降解析器以解析ε。

Question

例如，

EBNF A ::= B c; B ::= T1 | T2 | ε T1 ::= a T2 ::= b

（注：EBNF是一种用于描述语法的扩展巴克斯-瑙尔范式，其中A、B、T1和T2是非终结符号，c、a和b是终结符号，ε表示空串。）

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

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

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

- korrawit

Answer 1

无论是Java还是其他语言，重点在于你有一串标记流。你不会“获取”一个标记然后决定要做什么。相反，你会“查看”下一个标记，如果可以使用它，你就会“接受”它。
看到区别了吗？
不要“获取”然后“决定”。
要“查看并决定”，然后再“接受”。
这是“向前查看”的核心概念。
因此，ParseA调用ParseB。
ParseB查看流中的下一个标记。
如果是“a”，则接受并返回。
如果是“b”，则接受并返回。
否则，它将简单地返回到ParseA（而不接受任何内容）。
然后ParseA查看下一个标记。
如果是“c”，则接受并返回。
否则，它将失败。
有道理吗？
为了做到这一点，您应该在流的末尾添加一个哨兵标记，它永远不会被接受。最后，这应该是流中唯一剩下的标记。如果不是，则表示您有一个语法错误，其中包含额外的垃圾内容。

- Mike Dunlavey

---

+1 很好的解释；这个例子使用 StreamTokenizer.TT_EOF 作为哨兵标记：http://sites.google.com/site/drjohnbmatthews/enumerated-functions - trashgod

超级好的解释，让我明白了如何以整洁的方式解析我的语言。 - Charanor

Answer 2

epsilon只是一个标记，表示“可以在此处使用空字符串”，因此您不需要解析任何内容；下降已经完成。尽管如此，您似乎不会实际拥有该令牌；您需要检测是否没有可用的令牌或下一个令牌是否可以在另一个产生式中使用。

例如，您可能会得到输入c。您需要意识到这匹配产生式A ::= B c;，因为B可以缩减为epsilon——没有epsilon令牌，您只需要意识到B规则是可选的，在这种情况下需要跳过它以将c缩减为A

- Michael Mrozek

---

是的，我明白你的意思。所以解析epsilon时应该是“case Token.c:”对吧？而且在那种情况下什么也不做，只是虚拟语句，对吧？ 但是我的老师要求我实现解析epsilon方法，但我知道如果它不能解析epsilon，它会进入默认情况并报告错误，这是不正确的。对吧？ - korrawit

Answer 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

B ::= a | b | ε

C ::= c | d

由于“B”仍具有相同的定义，因此您不应该只是因为某些其他定义发生了变化而改变它。同样，您可以添加到语法中以允许（例如）一系列任意的B后跟C。

- Jerry Coffin

---

好的，我明白你的意思。但是如何使用 switch-case 实现呢？因为它必须有 default case 来告知错误。 - korrawit

@Atom：永远不要在解析“B”时检测错误——因为它允许匹配空，所以它只匹配“a”、“b”或空。此时，没有任何输入应该被视为错误。当您解析“A”时，查找后面跟着“c”的“B”，如果没有找到，则会发出错误信号（我通过返回“false”来表示）。 - Jerry Coffin

Answer 4

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

- Chris Dodd

---

这个概念名称是使用跟随集合的吗？这是递归下降解析，还是其他的？ - korrawit