3
$\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.

Improve this question
$\endgroup$
4
  • $\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, 2018 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, 2018 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, 2018 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, 2018 at 21:19

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
5
  • $\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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