CODEWITHSUNDEEP
parsingcompiler-constructionll-grammar
Osama Jarrar
Osama Jarrar

Reputation: 13

Does an empty column in an LL(1) parsing table mean that it is wrong?

I have a grammar and I am asked to build a parsing table and to verify that it is an LL(1) grammar. I noticed after building the parsing table that some of the columns were empty and had no production rules in them. Does this mean that it is wrongfully built? Or that it is not LL(1)? Or maybe something is missing?

Thank you.

Upvotes: 1

Views: 942

Answers (1)

templatetypedef
templatetypedef

Reputation: 372794

That’s nothing to worry about. An empty column indicates that there’s a terminal symbol that never starts a production (among other things). For example, take this simple LL(1) grammar:

S → abcdefg

Here, in the row for S, the columns for b, c, d, e, f, and g will all be empty, and the column for a will be the rule S → abcdefg. More specifically, the augmented grammar looks like this:

S' → S

S → abcdefg

The parsing table looks like this:

   |    a    | b | c | d | e | f | g
---+---------+---+---+---+---+---+---
 S'|    S    |   |   |   |   |   |
 S | abcdefg |   |   |   |   |   |

Notice that most columns are empty.

Upvotes: 1

Related Questions