Why does JFlap fail to build a usable LL(1) parser from my calculator grammar?

Question

I entered the following grammar in JFlap:

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

and tried to parse i * (i + i). I am sure the LL(1) grammar is correct and the input string should be accepted but JFlap said that the string in rejected. (See screenshot). Why?

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.