2
$\begingroup$

I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser".

It says:

If a language is context free, then some pushdown automaton recognizes it.

Let A be a CFL. From the definition we know that A has a CFG, G, generating it. We show how to convert G into an equivalent PDA, which we call P.

But what if G has left recursion?

Does the NPDA construction in this book can halt when it simulate a CFG which has left recursion?

What's the different between NPDA and Recursive-Descent Parsing (full backtracking) in Compilers Principles, Techniques, & Tools ?

Thanks.

$\endgroup$
  • $\begingroup$ Continue reading; the proof will show you how to handle left-recursion, if it's of interest at all. (Hint: it isn't. Non-determinism takes care of arbitrary lookahead, so to speak. Categories of deterministic parsing don't apply.) $\endgroup$ – Raphael Mar 20 '18 at 15:52
  • $\begingroup$ @Raphael Thanks for your reply, but could you tell me continue reading which book and chapter? There is a algorithm (Algorithm 4.19) which can systematically eliminates left recursion in dragon book. But in Sipser's book, I dont find any solution about how to handle left-recursion in chapter "Pushdown Automata". $\endgroup$ – chansey Mar 20 '18 at 16:42
  • $\begingroup$ @Raphael I am confusing about NPDA's halting problem when it meet left recursion. For example: I have CFG: S->Sa S->b and input: 'c', now I construct a NPDA according Sipser's book. Will the NPDA accept or reject or loop? $\endgroup$ – chansey Mar 20 '18 at 16:43
  • $\begingroup$ You quote: "We show how to convert G into an equivalent PDA" -- I was assuming that that proof would follow. If not, get a better book. Again, I guess that such a proof will never talk about left-recursion, for the reasons I state above. $\endgroup$ – Raphael Mar 20 '18 at 21:19
2
$\begingroup$

As stated in the second paragraph following the one you quote, the PDA being constructed is non-deterministic, which greatly simplifies the construction.

A non-deterministic machine is allowed to have points at which more than one action is possible, without any procedure for determining which one is correct. It is only necessary to prove that one possible action leads to correct termination.

Such machines are easy to construct in formal theory but building them in the real world is trickier. A back-tracking parser must explore alternatives in some order; if it chooses an alternative which fails to terminate, then it will never get around to trying another possibility.

In contrast, the non-deterministic machine terminates acts as if it took all possible branches at the same time. If any branch terminates in an accepting state, the machine can can terminate and accept the input. This can be simulated by making copies of the machine at every branch, and simulating the progress of all currently active copies by repeatedly advancing each one by one step. (More copies might be made at each step of each copy, so it can get a little closer unwieldy.)

Consequently, it does not matter to the PDA if there is left-recursion in the grammar. To be sure, the left-recursion means that some of the possible execution paths will never terminate, but as long as there is a path which terminates, the PDA will choose it.


There is a subtle but important point which I left out of the first version of this answer, which is that the definition of the language recognised by the PDA is the set of inputs for which the PDA terminates in an accepting state. Nothing guarantees that the PDA will eventually terminate on other inputs, and it is quite possible that the PDA will never halt if it is given a input which is not in the language it recognises. (This is another reason why non-deterministic PDAs aren't much use in practical parsers.)

This should not be surprising. If the machine were guaranteed to halt, then there would exist a machine which recognised the complement of the language. But if that were the case, the complement of every context-free language would be context-free, and we know that not to be true.

$\endgroup$
  • $\begingroup$ Non-deterministic machine says: If any branch accept, then the machine accept, but if evey branch reject except one loop, then the machine is recognizable (not decidable). My problem is the NPDA construction in Sipser's book maybe not decidable when we using left recursion grammar to construct it. This my major confusion. $\endgroup$ – chansey Mar 20 '18 at 19:19
  • $\begingroup$ For example: I have CFG: S->Sa S->b and input: 'c', now I construct a NPDA according Sipser's book. All branches in the NPDA will reject except one branch it infinitely push 'S' to the stack and never read input. $\endgroup$ – chansey Mar 20 '18 at 19:19
  • $\begingroup$ Sorry... I must clarify the word you mentioned 'DPA'. What's your DPA mean? Deterministic Pushdown Automaton or 'PushDown Automaton' $\endgroup$ – chansey Mar 20 '18 at 19:49
  • $\begingroup$ OK, since NPDA can only recognizes CFG instead of decide, there is not much difference between NPDA and recursive descent parsing. Because we can use variants of recursive descent parsing algorithm. For example: explore the tree by using depth-first search which like using DTM to simulate NTM. But the parser won't guarantees it will eventually terminate on every input. $\endgroup$ – chansey Mar 20 '18 at 20:14
  • $\begingroup$ @chansey: As I said in the answer, you would have to use breadth-first search. A depth-first search might not terminate on a string which should be recognised, while a breadth-first search is guaranteed to find the shortest path which terminates. However, breadth-first search is really not very much like recursive descent, since it requires a FIFO queue and is then not really recursive. $\endgroup$ – rici Mar 20 '18 at 20:21

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.