CODEWITHSUNDEEP
compiler-constructiongrammarcontext-free-grammarll-grammarleft-recursion
Cosmin
Cosmin

Reputation: 33

How to transform a grammar into a top-down parsable grammar

I have this part of a grammar

S ‐> S a | S b a | a | S b c S | S b c b | c S | c b

and I need to use it in order to create some SD sets and later on a parse table.

But, before doing that, I should convert this into a top-down parsable grammar.

My question is how do you do that? I know that you have to get rid of left-recursiveness, but how do I go about in doing that?

I read the wikipedia article and some other one from an university, but I can't wrap my head around how I should do it.

Can you please give me some help?

Upvotes: 3

Views: 142

Answers (1)

Pyetras
Pyetras

Reputation: 1502

Here's the general agorithm:

Each rule like

A -> Aa
A -> b

becomes

A -> bA'
A'-> aA'
A'-> e

where e means empty (epsilon).

So for your case, you can start with

S ‐> S a | S b a | a   =>   S -> aS' , S' -> aS' | baS' | e

And figure out the rest

Upvotes: 2

Related Questions