grammar - 为什么 JFlap 无法从我的计算器语法构建可用的 LL(1) 解析器？

Question

我在 JFlap 中输入了以下语法：

E → TK
K → +TK
K → λ
T → FM
M → *FM
M → λ
F → i
F → (E)

并试图解析i * (i + i). 我确信 LL(1) 语法是正确的，输入字符串应该被接受，但 JFlap 说该字符串被拒绝。（见截图）。为什么？

Answer 1

The grammar is fine.

However, you somehow entered it incorrectly. Notice that your parsing table has a λ column. That means that JFlap interpreted the λ as a character, not as an empty right-hand side, probably because you typed a real λ rather than letting JFlap fill it in automatically. You should just leave the right-hand side empty if you want an empty right-hand side. JFlap will then show that as λ but it won't treat it as a symbol.

By way of illustration, here are screenshots for the correctly entered grammar (with empty right-hand sides) and a grammar where I typed a λ instead of leaving the right-hand side empty. I stopped the second parse one step earlier than the error message, so that you can see the problem being reported: since M does not have an empty production, it blocks the parser from recognising the + sign.

Here's the correctly entered grammar:

And here's the one which I generated the same way that you did (if my guess is right). Note that it has a λ column in the transition table. You would also see it being handled differently in the FIRST and FOLLOW sets.

As a postscript, JFlap seems to handle most Unicode characters in tokens, but using a λ character as a token triggers a variety of bugs. So you shouldn't do that even if you intended the λ to be a legitimate character.