I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with the follow exception. I've provided the simplest case to illustrate the problem below.

S -> a b S | T
T  -> a c T | d T | ϵ

This grammar rightly generate a FIRST(S) - FIRST(T) clash, as both S and T can generate a as a first terminal.

One (clearly wrong) attempt to left-factor the a terminal was to substitute T into the S production.

S -> a b S | a c S | d S | ϵ

This would allow for left factoring like so:

S -> a U | d S | ϵ
U -> b S | c S

However, this grammar is no longer equivalent, as it would accept the string acab when the original grammar would not.

I'm hoping that there is some way to manipulate this grammar that I'm not aware of to eliminate the FIRST(S) and FIRST(T) clash. Is there a method to left-factor a terminal in recursive nested productions as is described above?

  • 1
    $\begingroup$ Huh? Expanding T in S -> a b S | T produces S -> a b S | a c T | d T | ϵ, not S -> a b S | a c S | d S | ϵ. $\endgroup$ – reinierpost Mar 29 '18 at 19:18

I'm nearly certain that I've discovered the following equivalent left-factored grammar.

S -> a X | W
T -> b S

U -> c Y
V -> a U

W -> d Y | ϵ

X -> T | U
Y -> V | W

This was obtained by enumerating the following list of test cases and manually checking them.

Test strings that the grammar should accept:

  • ϵ
  • ab
  • abab
  • abac
  • abacac
  • abacd
  • ac
  • acac
  • abd
  • acd
  • dac
  • d
  • dd

Test strings that the grammar should reject:

  • dab
  • acab
  • abdab
  • abacab
  • $\begingroup$ This grammar seems to work for all my test cases, but I'm not 100% certain that it is equivalent to the original grammar. Any feedback, comments or suggestions appreciated! $\endgroup$ – LanceLafontaine Feb 27 '18 at 16:34

You can solve this with regular expressions:

S -> a b S | T

is equivalent to

S -> (a b)* T


T -> a c T | d T | ϵ

is equivalent to

T -> (a c | d)*

Subtitute T into the rule for S:

S -> (a b)* (a c | d)*

Now, you can use a standard method to derive a right regular grammar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.