Search code examples
parsingcompiler-constructiongrammar

Is this grammar left factored?

Consider the following grammar 

S --> A|B  
A --> aa   
B --> ab

Is this grammar left factored?

I feel this grammar is not left factored, since the choices between the two productions of S is not clear we could rewrite the productions to defer this decision until enough of the input has been seen that we can make right choice.

Am I missing something or this is not left factored?

Solution

  • There are a few reasons why a grammar isn't LL(1). In this case, you have a FIRST/FIRST conflict between S -> A and S -> B: because FIRST(A) and FIRST(B) overlap, there are cases where you don't know which production to pick.

    The techniques that are commonly taught to resolve these conflicts are left factoring and left recursion removal, but this grammar is already left-factored (for each non-terminal, each productions has a distinct prefix) and it's free of any left recursion.

    There is another technique you can use, however: substitution. In your case, you could remove the rule A -> aa by replacing S -> A with S -> aa.

    To solve the conflict in your grammar, one would first have to substitute A and B in S:

    S -> aa | ab

    Now we still have a FIRST/FIRST conflict between the two productions for S, but this time, we can resolve it through left factoring:

    S -> a T
T -> a | b

    The grammar is now free of LL(1) conflicts.

    (Unfortunately, I'm not well-versed enough in parser construction to know of a mechanical way to determine when and where substitution should be applied. Nevertheless, it's a valid technique.)