Transform grammar into LL(1)

Question

I have the following grammar:

START -> STM $
STM -> VAR = EXPR
STM -> EXPR
EXPR -> VAR
VAR -> id
VAR -> * EXPR

With this firstand follow sets:

          First set     Follow set
START       id, *       $
STM         id, *       $
EXPR        id, *       $, =
VAR         id, *       $, =

I've created the parsing table that follows:

                $           =           id              *               $
START                           START → STM $        START → STM $
STM                             STM → VAR = EXPR    STM → VAR = EXPR
                                STM → EXPR          STM → EXPR
EXPR                            EXPR → VAR          EXPR → VAR
VAR                             VAR → id            VAR → id
                                VAR → * EXPR        VAR → * EXPR

From here I can see that this is not LL(1).

How can I modify this grammar so that it becomes LL(1)?

There's no systematic way to do it. You need to go through all the various ways of transforming grammars discussed in pretty much any compilers textbook. [This answer](http://stackoverflow.com/a/10616824/3438854) has a fairly good overview. — John C, Jun 08 '14 at 10:33

score 0 · Answer 1 · answered Mar 16 '16 at 21:51

If you think about what sorts of strings can be generated by this particular grammar, it's all the strings of one of the following forms:

 ***....**id
 ***....**id = ***...**id

With this in mind, you can design an LL(1) grammar for this language by essentially building a new grammar for the language from scratch. Here's one way to do this:

Start → Statement $

Statement → StarredID OptExpr

StarredID → * StarredID | id

OptExpr → ε | = StarredID

Here, the FIRST sets are given as follows:

FIRST(Start) = {*, id}
FIRST(Statement) = {*, id}
FIRST(StarredID) = {*, id}
FIRST(OptExpr) = {ε, *, id}
FOLLOW(Statement) = {$}
FOLLOW(StarredID) = {=, $}
FOLLOW(OptExpr) = {$}

The parse table is then shown here:

                  *                 | id                | =             $
 ---------------+-------------------+-------------------+-------------+-----------
 Start          | Statement$        | Statement$        |             |
 Statement      | StarredID OptExpr | StarredID OptExpr |             |
 StarredID      | * StarredID       | id                |             |
 OptExpr        |                   |                   | = StarredID | epsilon

So this grammar is LL(1).

Transform grammar into LL(1)

1 Answers1