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

Re: Backtracking through the source

Thread Previous | Thread Next
From:
Dan Sugalski
Date:
November 28, 2000 11:34
Subject:
Re: Backtracking through the source
Message ID:
5.0.1.4.0.20001128142649.02458110@24.8.96.48
At 06:58 PM 11/28/00 +0000, Tom Hughes wrote:
>In message <20001128003154.A30145@pembro33.pmb.ox.ac.uk>
>           Simon Cozens <simon@cozens.net> wrote:
>
> > I doubt it; I get the feeling that what Dan is talking about is infinite
> > look-*behind*. Nine times out of ten, you won't need to redo your parsing,
> > so having an infinite lookahead will just slow everything down.
>
>I didn't say that having infinite lookahead was better than allowing
>backtracking. I simply said that the two were equivalent and that any
>problem that can be solved by one can be solved by the other.

The big reason I was thinking about this is becase I'd like to be able to 
chop pieces off the front of the 'to be parsed' stream, so regexes can 
start with ^  instead of something else, but that's a minor issue, and one 
that's likely to be caught early-on in testing--I can't see us sending out 
a production release of perl with a whoops like that in the parser source.

> >     sub bar { ... }
> >     print foo bar();
> >
> > Now, having parsed this far, we know that foo is a filehandle that we're
> > printing to, so we build up our op tree to print the results of calling 
> bar()
> > to a filehandle called foo; ooh, but what do we see now:
> >
> >     sub foo { ... }
> >
> > Eek, foo was actually a subroutine, and we mean print(foo(bar())); need to
> > redo our parse tree. That's when the lookbehind comes into play.
>
>That's quite a nasty example for a number of reasons. Firstly you
>might have to back up and reparse a very large amount of code as the
>subroutine definition could be a very long way away from the print
>statement.

Luckily that particular case can probably be dealt with without reparsing 
source--we'd just have to tromp back through the syntax tree and change the 
attribute of a node somewhere. (Or leave it until runtime, I suppose)

It's also something that will be dealt with by the bytecode compiler rather 
than the parser, and it'll have a fully-enough parsed program to deal with 
things appropriately.

(I suppose it would mean that if someone did this in a BEGIN block that the 
code in the BEGIN would treat foo as a filehandle but the rest of the 
program would treat it as a sub call, which could be an issue)

>Secondly in order to know that you needed to back up you'd have to
>remember that you hadd had to guess that foo was a filehandle but
>that it might also be a subroutine and it raises a whole serious of
>questions about what other similar things you might need to remember.

Well, we do have the syntax tree, and can make whatever notes we want in 
the stash of the interpreter we're dealing with. Maybe an "intederminate" 
on the foo slot or something.

					Dan

--------------------------------------"it's like this"-------------------
Dan Sugalski                          even samurai
dan@sidhe.org                         have teddy bears and even
                                      teddy bears get drunk


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