Parse: Restaring rule evaluation
[1/7] from: robert:muench:robertmuench at: 15-Nov-2001 21:10
Hi, I have found out that 'parse restarts the rule evaluation at the top as soon
as one rule could be satisfied. Wouldn't it be faster to continue to evaluate
the rest of the rules? Further it would be possible to solve some parsing
problems easier if rule ordering could be used. Robert
[2/7] from: brett::codeconscious::com at: 16-Nov-2001 9:52
Hi Robert,
I don't understand. Could you supply an example please?
Thanks
Brett.
[3/7] from: robert:muench:robertmuench at: 16-Nov-2001 14:32
> -----Original Message-----
> From: [rebol-bounce--rebol--com] [mailto:[rebol-bounce--rebol--com]]On Behalf Of
<<quoted lines omitted: 3>>
> Subject: [REBOL] Re: Parse: Restaring rule evaluation
> I don't understand. Could you supply an example please?
Hi, ok:
rules: [
rule1
| rule2
| rule3
| rul4 call rule5
]
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? How does the pattern look like if a
sub-rule in rule5 can't be satisfied? Return to where the rule5 block was
called?
I would be happy if the call/return pattern for grammars would be documented. To
me it doesn't seem to be to obvious? Does a 'newline trigger a start at rule1 in
all cases? What are the events to restart with rule1? Robert
[4/7] from: lmecir:mbox:vol:cz at: 16-Nov-2001 15:28
Hi Robert,
Robert: <<
rules: [
rule1
| rule2
| rule3
| rul4 call rule5
]
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? How does the pattern look like if a
sub-rule in rule5 can't be satisfied? Return to where the rule5 block was
called?
>>
let's suppose:
rule1: [(print "rule1, unsatisfied") end skip]
rule2: [(print "rule2, satisfied")]
Then parse used like:
parse "a" rules
yields:
rule1, unsatisfied
rule2, satisfied
== false
So, no restart happened (exactly as I expected). At the same time, there is
no reason why RULE3 or any other rule should be used, when RULE2 was
satisfied.
Cheers
Ladislav
[5/7] 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
[6/7] from: robert:muench:robertmuench at: 17-Nov-2001 12:21
> -----Original Message-----
> From: [rebol-bounce--rebol--com] [mailto:[rebol-bounce--rebol--com]]On Behalf Of
<<quoted lines omitted: 5>>
> no reason why RULE3 or any other rule should be used, when RULE2 was
> satisfied.
Why not? If there is more input and parse satisfied one rule it "starts" over to
parse the rest of the input with the actual rule set. But it might continue to
evaluate the rest of the rule set with the new input... don't know if this would
yield in a speed improvement but either choice could be selected. Why go for
starting over? Robert
[7/7] from: lmecir:mbox:vol:cz at: 17-Nov-2001 14:17
Hi,
> So, no restart happened (exactly as I expected). At the same time, there
is
> no reason why RULE3 or any other rule should be used, when RULE2 was
> satisfied.
<<
Why not? If there is more input and parse satisfied one rule it "starts"
over to
parse the rest of the input with the actual rule set. But it might continue
to
evaluate the rest of the rule set with the new input... don't know if this
would
yield in a speed improvement but either choice could be selected. Why go for
starting over? Robert
>>
I should have said it more precisely: PARSE doesn't restart the rule to find
another possibility that could "consume" more input. This is the way how
PARSE is implemented.
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted