Solve this using predicitive parser LL1 parser
문제
Solve this question using predicitive parser LL1 parser
E-> E O E | (E) | id
O -> + /- / % /
해결책
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
제휴하지 않습니다 StackOverflow