[REBOL] Re: Parse: Restaring rule evaluation
From: greggirwin:mindspring at: 16-Nov-2001 11:45
Hi Robert,
<<
rules: [
rule1
| rule2
| rule3
| rul4 call rule5
]
;rule-x rule-y rule-z
rule5: [
rule51 rule5
| rule52 rule5
| rule53 rul5
]
Now: If parse starts with rules and rule2 can be satisifed it doesn't
continue
with rule3 but restarts with rule1. Why? >>
I don't know anything about how parse is implemented but...
Rules 1, 2, 3, and 4+5 are alternate rules. As soon as one of them is
matched, the parser doesn't need to evaluate the others (the alternates) to
proceed to the next rule.
If the alternation is the last rule in the grammar, it's done and doesn't
have to look at any more alternates.
If there are more rules it *may* go on to the next rule and continue trying
to match (e.g. trying rule-x rule-y rule-z if you had those in there, see
code above). If it fails then it can backtrack and try the next alternate
(e.g. rule2) and again continue to rule-x rule-y rule-z. Failing that it
backtracks and tries rule3...until it succeeds or runs out of alternates to
try. That's now an NFA engine works (someone please correct me if I'm
wrong). I don't think that's how parse works however.
If it's a DFA engine (again, someone please correct me if I'm off base
here), it will try all the alernates before continuing on to the next rule.
As soon as it gets a match on any of the alternations, it goes on to the
next rule. The alternations are evaluated in the order they are declared and
are handled in a non-greedy manner. E.g.
>> parse [a b c d] [['a | 'a 'b | 'a 'b 'c] 'd to end]
== false
>> parse [a b c d] [['a 'b 'c | 'a 'b | 'a] 'd to end]
== true
That's how I think parse works (given my brief experience with it).
RT would have to tell us definitively whether parse is an NFA or DFA engine
and whether the operators are greedy or not, though we could probably figure
out the details with some experimentation.
--Gregg
