java - 编写递归下降解析以在 Java 中解析 epsilon(ε)

Question

例如，

EBNF

A ::= B c;

B ::= T1 | T2 | ε

T1 ::= a

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 还是任何语言，关键是您拥有 token 流。您不会“获得” token 并决定要做什么。相反，您“查看”下一个 token ，如果可以使用它，您就“接受”了它。

看出区别了吗？

不要先“得到”再“决定”。
先“看再决定”再“接受”。
这是“前瞻”概念的核心。

因此，ParseA 调用 ParseB。

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

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

有道理吗？

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