Solve this using predicitive parser LL1 parser

Question

Solve this question using predicitive parser LL1 parser

E-> E O E | (E) | id

O -> + /- / % /

Answer 1

Grammar

E -> E O E (1)
E -> (E)   (2)
E -> id    (3)
O -> +     (4)
O -> -     (5)
O -> %     (6)
O -> /     (7)

You will need to compute the First/Follow sets:

First(EOE) = First(E) = {'(', 'id'}
First('('E')') = {'('}
First('id') = {'id'}
First('+') = {'+'}
First('-') = {'-'}
First('%') = {'%'}
First('/') = {'/'}
First(O) = {'+', '-', '%', '/'}

Follow(E) = First(O) u {')', $} = {'+', '-', '%', '/', ')', $}
Follow(O) = First(E) = {'(', 'id'}

Parsing table:

. '('  ')' 'id' '+' '-' '%' '/'
E (1,2)    (3)
O               (4) (5) (6) (7)

As you can see, you have a conflict in parsing '(' when you have E on the top of the stack: on reading look-ahead symbol (, should you apply E->EOE or E->(E)? So you cannot create an LLk(1) parser for this grammar.

You could re-write the grammar to for example:

E -> (E) O   (1)
E -> id      (2)
O -> +E      (3)
O -> -E      (4)
O -> %E      (5)
O -> /E      (6)
O -> epsilon (7)

in which case the First/Follow sets are:

First('('E')') = {'('}
First('id') = {'id'}
First('+')
First('+') = {'+'}
First('-') = {'-'}
First('%') = {'%'}
First('/') = {'/'}
First(O) = {'+', '-', '%', '/'} u Follow(O)

Follow(E) = {')'} u Follow(O)
Follow(O) = {$} u Follow(E)

Parsing table:

. '(' ')' 'id' '+' '-' '%' '/' $
E (1)     (2)
O     (7)      (3) (4) (5) (6) (7)

As there are no conflicts in this table, the grammar is LLk(1).

Parsing the string (id)+id is as follows:

Stack  Input     Action
E$     (id)+id$  E/'(':     (1)
(E)O$  (id)+id$  '('/'(':   read
E)O$   id)+id$   E/'id':    (2)
id)O$  id)+id$   'id'/'id': read
)O$    )+id$     ')'/')':   read
O$     +id$      o/'+':     (3)
+E$    +id$      '+'/'+':   read
E$     id$       E/'id':    (2)
id$    id$       'id'/'id': read
$      $         $/$:       accept