7
$\begingroup$

if I have a grammar having a production that contains both left recursion and left factoring like

$\qquad \displaystyle F \to FBa \mid cDS \mid c$

which one has priority, left recursion or left factoring?

$\endgroup$
  • 1
    $\begingroup$ What parsing strategy are you using? For recursive descent, left recursion must be avoided at all costs. Left factoring is important if you are doing a LL parsing for example. $\endgroup$ – Ken Li Jul 11 '12 at 16:37
  • 2
    $\begingroup$ Sorry, I've forgotten to write it. I'm using top-down parser strategy (LL(1)) $\endgroup$ – Andrea Tucci Jul 11 '12 at 16:40
  • $\begingroup$ According to inst.eecs.berkeley.edu it is the same! (on the 3rd exercise) $\endgroup$ – Andrea Tucci Jul 11 '12 at 16:46
11
$\begingroup$

Transformations such as left factoring or removing left recursion do not have precedence rules. Obviously, the resulting grammars may be different but they will recognize the same language.

The question's example grammar is more difficult than the typical undergrad homework problem. So showing our work will be useful.

Left Recursion

Let's define a transformation that removes left recursion.

Given

$\qquad \displaystyle A \to A\alpha_0 \mid A \alpha_1 \mid \dots \mid A \alpha_n \mid B \beta_0 \mid B \beta_1 \mid \dots \mid B\beta_n$,

we remove left recursion like this:

$\qquad \displaystyle \begin{align} A_h &\to B \beta_0 \mid B \beta_1 \mid \dots \mid B \beta_n \\ A_t &\to \alpha_0 \mid \alpha_1 \mid \dots \mid \alpha_n \\ A_{t^+} &\to A_t A_{t^+} \mid A_t \\ A &\to A_h A_{t^+} \mid A_h \end{align}$

The generality of above is typically not given in compiler texts, but parsing texts like Grune & Jacobs do cover this. Left factoring can be applied to the above transformed grammar but will be just introduce extra rules that will not change the answer. So we will simplify the presentation without extra left factoring being performed.

In this answer we will not cover indirect left recursion issues because we are only concerned with a single non-terminal's rules. Note that indirect left recursion can be dealt with, though. (Open a separate question if that is important.)

Left Factoring

Removing left factoring is in most introductory compiler texts done like this. Given

$\qquad \displaystyle A \to x y \mid x z$

left factoring yields:

$\qquad \displaystyle \begin{align} A_s &\to y \mid z \\ A &\to x A_s \end{align}$

Now that's perform the transformations in both ordering.

Left factoring first

Let's left factor the question's grammar

$\qquad \displaystyle \begin{align} F_s &\to D S \mid \varepsilon \\ F &\to F B a \mid c F_s \end{align}$

and then remove the left recursion:

$\qquad \displaystyle \begin{align} F_h &\to c F_s \\ F_t &\to B a \\ F_{t^+} &\to F_t F_{t^+} | F_t \\ F_s &\to D S \mid \varepsilon \\ F &\to F_h F_{t^+} \mid F_h \end{align}$

Removing left-recursion first

And for the other ordering, let's remove left recursion from the question's grammar

$\qquad \displaystyle \begin{align} F_h &\to c D S \mid c \\ F_t &\to B a \\ F_{t^+} &\to F_t F_{t^+} \mid F_t \\ F &\to F_h F_{t^+} \mid F_h \end{align}$

and then left factor the terminal $c$:

$\qquad \displaystyle \begin{align} F_{hs} &\to D S \mid \varepsilon \\ F_h &\to c F_{hs} \\ F_t &\to B a \\ F_{t^+} &\to F_t F_{t^+} \mid F_t \\ F &\to F_h F_{t^+} \mid F_h \end{align}$

Aha, the resulting grammars are the same!

In general, proving that two grammars are equivalent is undecidable. So if a series grammar transformations could influence the language that is recognized then, it would be disastrous.

$\endgroup$
  • $\begingroup$ Thank you, very well explained! So if I have both left recursion and left factoring, I can choose which one remove first. Thanks again $\endgroup$ – Andrea Tucci Jul 13 '12 at 10:43
  • $\begingroup$ "In general, proving that two grammars are equivalent is undecidable." -- do you mean, proving this is impossible, or do you mean there is no algorithm that does it always? Only the latter is correct. Also, it would not be "disastrous" if only one order would keep the language unchanged: you would have to use the correct order, then. But it is certainly clear that if both transformations are to be used independently of another that they can not influence the generated language. $\endgroup$ – Raphael Jul 17 '12 at 16:35
  • $\begingroup$ Note that we have quite sophisticated formatting tools at hand here (Markdown and LaTeX) to improve clarity. I edited your post accordingly, please have a look. $\endgroup$ – Raphael Jul 17 '12 at 17:06
  • 1
    $\begingroup$ @Raphael The "proving" language is ambiguous and the "disastrous" wording I guess is hyperbole. Good catch. $\endgroup$ – codeah Jul 18 '12 at 12:14
  • $\begingroup$ @Raphael Thanks for the heads up on the syntax. $\endgroup$ – codeah Jul 18 '12 at 12:16

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.