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

Re: Backtracking through the source

Thread Previous | Thread Next
Chaim Frenkel
November 29, 2000 08:18
Re: Backtracking through the source
Message ID:
>>>>> "SF" == Steve Fink <> writes:

SF> Handling the parser's state can be done in a backtracking DFA-like or a
SF> direct NFA-like way. The NFA way is to keep track of all possible parse
SF> states and advance each one in parallel based on the next token. The DFA
SF> way is recursive descent, backing out of blind alleys and trying again,
SF> keeping a single working hypothesis alive at a time. The DFA approach is
SF> probably easier to undo user code in, because in the NFA case you have
SF> to consider each token under the assumptions of all possible parses up
SF> to that point. The NFA case has the advantage that you never have to
SF> back up, so you can permanently forget about a token as soon as it
SF> whizzes by.

Can an NFA actually handle the interaction between the lexer and tokenizer?

	$foo = s;foo;bar;g;
	$foo = s#foo#bar#g; # change the world

Chaim Frenkel					     Nonlinear Knowledge, Inc.				               +1-718-236-0183

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About