在 Java 中编写递归下降解析来解析 epsilon(?)

Question

例如，

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（空字符串集）？

Answer 1

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

看到不同？

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

所以，ParseA 调用 ParseB。

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

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

有道理？

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