CODEWITHSUNDEEP
parsingcompiler-constructiongrammarcontext-free-grammar
sv_jan5
sv_jan5

Reputation: 1573

Is entry under $ column in LL(1) parse table necessary?

Is it necessary to get at least one entry under the column for $ in parse table for LL(1) grammar for a programming language.

If yes what possible errors can we look for in our grammar.

Upvotes: 1

Views: 512

Answers (1)

user824425
user824425

Reputation:

It's possible for the $ (end of input) column to be empty. One class of grammars where this happens is where all productions for S are non-empty and end in a terminal.

Let's take the example of S -> ( S* ), or more explicitly:

  1. S -> ( T )
  2. T -> S T
  3. T -> ε

We can build the following LL(1) parsing table for this grammar:

   |  (      |  )  |  $  |
---+---------+-----+-----+
S  |  ( T )  |     |     |
T  |  S T    |  ε  |     |

Keep in mind that an LL parser stack contains terminals and non-terminals. If the input and the stack start with the same terminals, they're both removed. The same goes for the end of the input (which is often represented as a special terminal): parsing has successfully completed if and only if we've reached the end of the input and our parser stack is empty.

The only sensible entry for the $ column that I can think of would be ε. After all, it would be impossible to parse an empty string if you have any (non-empty) terminals on your stack. When the $ column contains an ε for some terminal, it means that you can remove it from the stack when you've reached the end of your input. In the case of our example, we have no reason to allow this.

Upvotes: 1

Related Questions