How to left factor a context-free grammar?
-
03-12-2019 - |
Question
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
Solution
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.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow