2. Resolving Conflicts

LL(1) Grammar

An LL(1) grammar requires that for any two productions A -> alpha and A -> beta with the same left-hand side, the intersection of their predictive sets PS(A -> alpha) and PS(A -> beta) should be empty. In other words, the predictive lookahead symbols should never overlap. If they do, for instance, C = PS(A -> alpha) & PS(A -> beta) = {'('}, it is not possible to tell which production is taken when the lookahead token is '(', because both are available.

Practically, some non-LL(1) grammar can be parsed in LL(1) fashion by explicitly assuming a precedence. For the instance above, we assign higher priority to the production A -> alpha, and when '(' is the lookahead symbol, A -> alpha rather than A -> beta will be applied by the parser. By modifying the predictive set for A -> beta as PS(A -> beta)' = PS(A -> beta) - C, we see that PS(A -> alpha) & PS'(A -> beta) is now empty and hence satisfies the definition of LL(1) grammar.

Consider grammar G[S]:

S -> if C then S E
E -> else S | <empty>

Grammar G is not LL(1) because PS(E -> else S) & PS(E -> <empty>) = {else}. Nonetheless, we can assign higher priority to E -> else S and parse a G program by LL(1) technique.

Resolving Conflicts

When conflicts (like above) appear, we assign higher priority to former defined productions. For instance, the rule definition

S : r1 | r2 | r3

implies that S -> r1 has the higher priority than S -> r2, and S -> r2 has the higher priority than S -> r3.

For the if-expression example above, to assign E -> else S with higher priority, simply define the rule like this:

E : else S | /* empty */

In such a situation, our tool will report a warning to inform you that a conflict is auto-resolved.