Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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