CODEWITHSUNDEEP
parsingcompiler-constructioncomputer-scienceregex-lookarounds
sam smith
sam smith

Reputation: 59

proving that a grammar is LL(1)

I'm given the following grammar :

S -> A a A b | B b B a
A -> epsilon
B -> epsilon

I know that it's obvious that it's LL(1), but I'm facing troubles constructing the parsing table.. I followed the algorithm word by word to find the first and follow of each non-terminal , correct me if I'm wrong:

First(S) = {a,b}
First(A) = First(B) = epsilon

Follow(S) = {$}
Follow(A) = {a,b}
Follow(B) = {a,b}

when I construct the parsing table, according to the algorithm, I get a conflict under the $ symbol... what the hell am I doing wrong??

     a       b      $
 A                   A-> epsilon
 B                   B-> epsilon
 S                   S -> AaAb
                     S -> BbBa

is it ok if I get 2 productions under $ or something?? or am I constructing the parsing table wrong? please help I'm new to the compiler course

Upvotes: 2

Views: 1811

Answers (1)

Tareq
Tareq

Reputation: 63

There is a tiny mistake. Algorithm is as follows from dragon book,

for each rule (S -> A):
    for each terminal a in First(A):
        add (S -> A) to M[S, a]

    if First(A) contains empty:
        for each terminal b in Follow(S):
            add (S -> A) to M[S, b]

Let's take them one by one.

  • S -> AaAb. Here, First(AaAb) = {a}. So add S -> AaAb to M[S, a].
  • S -> BbBa. Here, First(BbBa) = {b}. So add S -> BbBa to M[S, b].
  • A -> epsilon. Here, Follow(A) = {a, b}. So add A -> epsilon to M[A, a] and M[A, b].
  • B -> epsilon. Here, Follow(B) = {a, b}. So add B -> epsilon to M[B, a] and M[B, b].

Upvotes: 4

Related Questions