grammarcontext-free-grammar

Relation between Left factoring a grammar and removing epsilon

Let's say I'd using below grammar for compiler

 S -> a | aB

if I perform left factoring on it, it would be like (e is epsilon)

 S -> aC
 C -> B | e

then I want to remove epsilon which ends up being like

 S -> a | aC
 C -> B

notice that it looks like I again need to perform left factoring, and doing so infinitely left factoring and removing epsilon back and forth. Am I doing something wrong ??

Is it require to remove both left factoring and epsilon on grammar for compiler?

Solution

  • You shouldn't need to do either transformation, most of the time. In fact, for some grammars, left-factoring will create shift-reduce conflicts for LALR(1) parser generators.