0
$\begingroup$

I came across following problem:

If the CFG is left factored then it must be Unambiguous and Not left Recursive. TRUE/FALSE?

I have many thoughts about this. But I feel they are somewhat contradicting and hence form a bigger doubt. May be I lack some understanding.

Thought 1

Ambiguity has nothing to do with determinism (even if grammar does not have productions with same prefix of their right side, they still can have a string with two parse trees). So CFG is still ambiguous after left refactoring. Hence, the sentence should be false.

Thought 2

Left factoring is used to eliminate common prefixes of right hand side of productions in the grammar. Doesnt that make grammar deterministic? Deterministic grammar derive deterministic context free languages. So isnt turning grammar deterministic makes it unambiguous? If yes, given statement should be true.

Thought 3

I have completely ignored left recursion in thought 1 and 2. Is it ok?

Doubt: I feel thought 1 and thought 2 are contradicting. And I am not able to figure it out which one is correct. Which of the above thoughts are incorrect and why? Am I missing any more subtleties?

$\endgroup$
0
$\begingroup$

Left factoring does not significantly change the derivations produced by a grammar. It introduces new non-terminals, which adds steps to the derivations, but the original derivation is still present.

So if the grammar were ambiguous before, it is still ambiguous afterwards. Recall that an ambiguous grammar has more than one leftmost derivation for the sane sentence; after left-factoring, this will still be the case.)

Left-factoring is necessary to produce a top-down parser, but that is because top-down parsing requires a stronger condition than non-determinism. (Informally, a top-down parser must decide which alternative to pursue before it starts to explore that alternative, while a deterministic parser only requires that the decision can be made within a bounded time after the alternative is complete.)

$\endgroup$
  • $\begingroup$ I believe my thought 1 adheres with your first two paragraphs. So my thought 2 is wrong. " You said left factoring is necessary to produce a top down parser. A top down LL(k) parser is deterministic pushdown automaton. And DPDAs accept deterministic context free languages, which are always unambiguous. " I am not able to see how you are proving my thought 2 is wrong with your last paragraph. Can you be please explain in some more words where my thought 2 or part of this comment in double quotes and italics is wrong? $\endgroup$ – anir Jan 24 at 15:13
  • $\begingroup$ @anir: the fact that all top-down parsers are deterministic does not indicate that all deterministic parsers are top-down. They are not. Top-down parsers are a proper subset of deterministic parsers $\endgroup$ – rici Jan 24 at 15:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.