CODEWITHSUNDEEP
parsingcontext-free-grammar
furyhunter
furyhunter

Reputation: 139

LL(1) Parsing table with grammar

I'm trying to get LL(1) Parsing Table with grammar below,

S -> ( L ) | a
L -> L , S | S

I think it has indirect left recursion because of this, 

L -> S

so I change it to, 

S -> ( L ) | a
L -> L , ( L ) | L , a | ( L ) | a

then like this,

S -> ( L ) | a
L -> ( L ) L' | aL'
L' -> , ( L ) L' | ,aL' | epsilon

with this, I get FIRSTs and FOLLOWs

FIRST(S) = { (, a }          FOLLOW(S) = { $ }
FIRST(L) = { (, a }          FOLLOW(L) = { ) }
FIRST(L') = { , , epsilon}   FOLLOW(L') = { ) }

But when I draw LL parsing table, It doesn't go to $.

Did I make mistake or misunderstanding?

Upvotes: 2

Views: 3773

Answers (1)

user824425
user824425

Reputation:

(My parsing theory is rusty, so I may have made some mistakes here.)

L -> S is part of indirect recursion, but not left recursion. The production can only "expand" into L ->+ ( L ) or L ->+ a, both of which start with a terminal. The only left recursion here is in the production L -> L , S. After removing this direct left recursion, I end up with the following grammar:

S -> ( L ) | a
L -> S L'
L' -> , S L' | ε

With this, the FIRST and FOLLOW sets you have computed are the same, except that FOLLOW(S) is incomplete. Besides $ (because S is the start state), FOLLOW(S) must include all elements of FIRST(L') (because L -> S L' and L' -> , S L') and FOLLOW(L') (because L' -> ε). I get FOLLOW(S) = { $, ,, ), ε }.

The parsing table I get is as follows:

    |  (     |  a     |  ,       |  )  |  $  |
----+--------+--------+----------+-----+-----+
S   |  L )   |  a     |          |     |     |
L   |  S L'  |  S L'  |          |     |     |
L'  |        |        |  , S L'  |  ε  |     |

I'm not sure what you mean by "it doesn't go to $". All I can say is that the column $ is empty, because all productions of S are non-empty and end in a terminal.

Upvotes: 1

Related Questions