develooper Front page | perl.perl6.internals.api.parser | Postings from November 2000

Re: Backtracking through the source

Thread Previous | Thread Next
From:
Tom Hughes
Date:
November 27, 2000 16:16
Subject:
Re: Backtracking through the source
Message ID:
2b5a40244a.tom@compton.compton.nu
In message <5.0.1.4.0.20001127163751.024354e0@24.8.96.48>
          Dan Sugalski <dan@sidhe.org> wrote:

> Is there any reasonable case where we would need to backtrack over
> successfully parsed source and redo the parsing? I'm not talking about the
> case where regular expressions run over text and ultimately fail, but
> rather cases where we need to chuck out part of what we have and restart?

That's effectively analogous to asking how much lookahead you need
to have, and the answer to that is that it depends entirely on the
grammar you're trying to parse.

With infinite lookahead you would never need to backtrack as you
could, if necessary, look right to the end of the program to decide
what the next token meant. Equally with no lookahead you will quite
likely need to backtrack unless your grammar is fairly restrictive, and
we all know that perl's grammar is anything but restrictive ;-)

Tom

-- 
Tom Hughes (tom@compton.nu)
http://www.compton.nu/
...Lonely men seek companionship.  Lonely women sit at home - they never meet.


Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About