Creating Grammar LL (1)

Question

I have the following grammar:

S → a S b S | b S a S | ε

Since I am trying to write a small compiler for it, I would like to do it LL (1). I see that there is a FIRST / FOLLOW conflict, and I know that I need to use substitution to solve it, but I'm not quite sure how to do this. Here is my suggested grammar, but I'm not sure if this is correct:

S-> aSbT | epsilon

T-> bFaF | epsilon

F-> epsilon

Can anyone help?

Answer 1

In his original article on parsing LR , Knut gives the following grammar for this language, which, in his opinion, "is the shortest possible unique grammar for this language:"

S → & Epsilon; | aAbS | bBaS

A → & Epsilon; | Aaba

B → & Epsilon; | bBaB

Intuitively, it tries to break any string of As and Bs into blocks that are fully balanced. Some blocks start with a and end with b, while others start with b and end with.

We can calculate FIRST and FOLLOW as follows:

FIRST (S) = {& epsilon ;, a, b}

FIRST (A) = {& epsilon ;, a}

FIRST (B) = {& epsilon ;, b}

FOLLOW (S) = {$}

NEXT (A) = {b}

NEXT (B) = {a}

Based on this, we obtain the following LL (1) analysis table:

| a | b | $ --+-------+-------+------- S | aAbS | bBaS | e A | aAbA | e | B | e | bBaB | 

And therefore this grammar is not only LR (1), but also LL (1).

Hope this helps!