0
$\begingroup$

I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:

When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing table may involve FIRST-FIRST and/or FIRST-FOLLOW conflicts, whereas LR parsing table may involve SR and/or RR conflicts. When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar. Does this means, eliminating LL conflicts also somehow eliminates LR conflicts? If yes how this happens? Or in other words, how LL conflicts are mapped to LR conflicts? (I believe there should have some minimum connection between LL conflicts and LR conflicts, shouldnt there be?)

$\endgroup$
  • 1
    $\begingroup$ LL grammars are subset of LR grammars, so making your grammar LL automatically makes it LR too. Sorry, I have no idea about conflicts, so don't put it as full-value answer. $\endgroup$ – Bulat Jun 23 at 8:22
  • $\begingroup$ Some grammars aren't LR because they are ambiguous, There are even inherently ambiguous languages, all grammars for them are ambiguous, And no ambiguous grammar can be LR. So this can't work in general. $\endgroup$ – vonbrand Jun 23 at 21:31
1
$\begingroup$

When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar.

To say that the grammar "becomes a valid LR grammar" implies that it was not a valid LR grammar before. But I will argue that if a mechanical procedure is used to transform a non-LL grammar $G$ into the LL grammar $G'$, then it is likely that both $G$ and $G'$ are LR grammars. In other words, the elimination of the LL conflict did not have any effect on LR conflicts, because there weren't any.

I'm not going to attempt to prove this assertion for all possible mechanical procedures. Indeed, it might not be correct for all heuristics. But it's pretty clear that the assertion is correct for the procedure used to left factor a grammar, because failure to left factor does not introduce any LR conflicts.

Both types of LR conflicts require that at least one production be reduceable. If left-factoring involves a factor which is not an entire right-hand side, then it does not apply to any SLR state including a reduceable production, and thus substituting a new non-terminal for the non-common part of the right-hand sides has no effect on any hypothetical LR conflict. Of course, it is possible that the factor is the entire right-hand-side of one production $A\to\beta$, and there is another production $A\to\beta\gamma$. So left-factoring will use a newly-created non-terminal $A'$ to produce:

$$\begin{align}A&\to \beta A'\\ A'&\to\gamma\mid\epsilon\\ \end{align}$$

The new grammar no longer has a prediction conflict on $A$, but there is no guarantee that the result is LL. For it to be LL, the parser needs to determined which alternative for $A'$ to use, which requires that $FOLLOW(\gamma)$ and $FOLLOW(A')$ be disjoint. But if that is true, there is no LR conflict; the shift and reduce actions are clearly differentiated by the lookahead.

So, if left-factoring results in an LL grammar, the grammar was originally LR. Left-factoring has not "made the grammar LR".

Left-recursion elimination is a bit more complex. To start to come to terms with that, consider a very simple left-recursive grammar $G_{sub}$:

$$\begin{align}S &\to E\\ E &\to T\\ E &\to E - E\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

That grammar is ambiguous because $5 - 2 - 1$ has two parses: (for clarity, I put the subnode evaluation [brackets] beside each operator, to indicate that the two different parses lead to different program semantics):

     - [4]                        - [2]
   /   \                        /   \
  /     - [1]                  - [3] \
 /    /   \                  /   \    \
5    2     1                5     2    1

Since $G_{sub}$ is ambiguous, it cannot be LR, and indeed when we try to construct the parsing automaton we find a shift-reduce conflict on lookahead $-$ in the state $\{[E\to E\bullet-E], [E\to E-E\bullet]\}$. The ambiguity also implies that the grammar cannot be LL, but in this case we can immediately see that it is not LL because no LL grammar has a left-recursive production.

We might chose to eliminate ambiguity by adding a precedence specification and using the precedence algorithm implemented in Yacc (and other parser generators). The precedence algorithm does not perform a transformation on the grammar. Rather, it transforms the parse automaton generated by the LR algorithm by removing all but one action from each conflict. (Hence, it is only applicable to LR parsing.) The resulting automaton could be transformed back into a deterministic CFG, but this is rarely done because the parse automaton is sufficient to implement a parser. (The procedure to convert a DPDA to a DCFG is outlined in Sipser, Introduction to the Theory of Computation, in Theorem 2.57; you can take that as an exercise.)

$G_{sub}$ has only a single operator, $-$, so there are only two possible precedence declarations: either we declare the operator to be left-associative or we declare it to be right-associative. Normally, we would choose left-associativity, since that is how we were taught in school to understand expressions like $5 - 2 - 1$. That produces the parse tree on the right above, the one which evaluates to 2.

But right associative operators are also plausible. For example, in many programming languages, assignment is right associative, because $a = b = 7$ must be evaluated by first setting $b$ to 7 (subexpression on the right) and only then setting $a$ to the result of the first assignment.

As I said, actually constructing the parse automaton, removing the conflicts, and then turning it back into a grammar is a bit tedious, although it is probably a good exercise; for the purposes of this answer, I didn't do it. But I can provide CFGs which will produce the same parses, and probably differ from the full procedure only in minor details.

Here is the usual left-associative grammar: $$\begin{align}S &\to E\\ E &\to T\\ E &\to E - T\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

And here is the right-associative grammar: $$\begin{align}S &\to E\\ E &\to T\\ E &\to T - E\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

The only difference from the original ambiguous grammar is the second production for $E$. In the ambiguous grammar it is $E\to E - E$. The left associative grammar turns that into a left-recursive production $E\to E - T$, and the right associative grammar tuns it into a right-recursive production $E\to T - E$.

Both of the above associative grammars are LR, and neither is LL. The right-associative grammar can easily be transformed into an LL grammar by left factoring:

$$\begin{align}S&\to E\\ E&\to T E'\\ E'&\to - E\\ E'&\to\epsilon\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

Again, this is an example of turning an non-LL grammar which was LR into an LL grammar (which is still LR).

To turn the left associative grammar into an LL grammar, we could try eliminating left recursion:

$$\begin{align}S&\to E\\ E&\to T E'\\ E'&\to - T E'\\ E'&\to\epsilon\\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

In this case, the resulting grammar is indeed LL. (And once again, both the original and the transformed grammar are LR.)

But here is something interesting. Left-factoring the right-associative grammar and eliminating left-recursion from the left-associative grammar produced virtually the same result. The only difference is that the first one has the production $E'\to - E$; in the second one, this production has had the $E$ pre-expanded, so it reads $E'\to - T E'$. Evidently, these two grammars parse the every input in the same way, despite the fact that we started with two grammars which produced different parses.

That's because the left-recursion-elimination algorithm does not preserve the parse tree. Or, to put it another way, you can turn a left-associative grammar into an LL grammar, but you sacrifice left-associativity.

Interesting though that is, it's really a side issue, since the point here was to try to find a relationship between LL and LR conflicts. And so far, we have found nothing even vaguely similar to a relationship. To close the circle, lets go back to the ambiguous grammar $G_{sub}$, which was neither LL nor LR, and try to turn it into an LL grammar by eliminating left-recursion. We get

$$\begin{align}S&\to E\\ E &\to T E' \\ E'&\to - E E' \\ E'&\to\epsilon \\ \\ T&\to 0|1|2|3|4|5|6|7|8|9 \end{align}$$

That successfully removed the left-recursion, but the resulting grammar is still not LL. We did not remove the ambiguity, and the resulting grammar is neither LL nor LR.

In summary:

  • An ambiguous grammar is neither LL nor LR. There will be conflicts produced by both algorithms, but it may be that they manifest in different ways.
  • If you can transform a non-LL grammar to an LL grammar using standard heuristics, then it probably had not LR conflicts to begin with.
  • LL and LR conflicts are completely different phenomena.
$\endgroup$
  • $\begingroup$ super thanks for efforts, please give me some time to go through this...sorry for late reply... $\endgroup$ – anir Jun 27 at 19:08

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.