CODEWITHSUNDEEP
compiler-constructiongrammarll-grammar
Bee
Bee

Reputation: 12502

How to left factor a context-free grammar?

As I understand, in the following case left factoring is required to build top-down parser. But it's hard to understand how to do that? Can someone help me here? Thanks.

s = a | b
b = c d
c = (e | f) g
e = a | h

Upvotes: 5

Views: 4016

Answers (1)

500 - Internal Server Error
500 - Internal Server Error

Reputation: 28829

Every non-terminal is only referenced once here, so we can pull the entire grammar together in a single expression: 

s = a | ((a | h | f) g d)

So we have two basic variations, the terminal a optionally followed by g then d, or else one of h or f always followed by g then d.

So we have

s =  b' | c'
b' = a | a g d
c' = (h | f) g d

or, pulling the common g d sequence into its own production

s =  b' | c'
b' = a | a e'
c' = (h | f) e'
e' = g d

We can then pull a up as a common starting symbol in b' by introducing an E (empty) option:

s =  b'' | c'
b'' = a (e' | E)
c' = (h | f) e'
e' = g d

The grammar is now unambiguous.

Upvotes: 6

Related Questions