Hi Petr, 7-Dec-1999 you wrote:
>> [...]
>> >> How about this:
>> >>
>> >> >> a: [skip a | "ing"]
>> >> == [skip a | "ing"]
>> >> >> parse "ringin" a
>> >> == false
>> >> >> parse "ringing" a
>> >> == true
>> >>
>> >> It should do the job. So actually backtracking in Parse can be achieved
by
>> use
>> >> of the "|" operator in Parse blocks.
>>
>> >What? | is simple OR or am I wrong? You will end up in recursion imho.
>>
>> That was the very point.
>Aha, I just thought that you thought "ing" is matched or skip is performed,
not
>knowing of recursion. Well, I should look better at your email adress, as I
would
>recognize, you are experienced reboller :-)
>Anyway ... your example will fail with "ing" being present somewhere in
middle of
>the text ... I would even sincerely dare to say - it has no sense. You are
nesting
>to recursion while end of string is not matched (let's imagine some 1000
chars =
>1000 subrules) and then backtracking by one char, while "ing" or we are not
back
>at the beginning of string ... Or am I wrong?
It is true that we get a ridiculously deep recursion. In effect, we first go
to the end of the string (by recursion), then we step backwards and each time
look if the string from the position we're at is "ing". So:
1: If we have a string with n chars, ending in "ing":
First make n recursive calls. On the third character on the way back, we find
out that our string ends with "ing", and we therefore return "success" all
the way up back through the recursion.
2: If we have a string with n chars, not ending in "ing":
First make n recursive calls, then at each step on our way back, see if the
string starting from our position is "ing".
So, yes, the solution is very, very stack-consuming and cumbersome. I simply
didn't pay attention at all to efficiency, just the principle that it could
be done that way.
>> I just don't see what the problem is. The examples above do exactly as I
>> wanted. I used "|" as "a backtracker", since it appears to do this:
>>
>> First, call recursively on the left side of the "|". If the match succeeds,
>> return success.
>No, no chance, You have no chance to match "ing". It will always reach the
end of
>the string. Once returning to upper levels from recursion, backtracking
starts
In my terminology, backtracking starts when the left side of a "|" is tested,
since we have to store information on our position in the string. But I guess
this is not the terminology everybody else uses, so sorry about that :-)
Why haven't I got a chance of matching "ing"? When we're at the point where we
have reached the end of the string, the part left to "|" will fail
immediately, since 'skip fails. Then we try to match "ing", which will fail.
Only when we go three steps back (i.e. we're at the position in the string
where we can see the last 3 characters in the string), the match on "img"
might succeed. If so, the "succeed" result is propagated all the way through
our recursive calls, since "skip a" has then succeeded for all the calls
above.
>> If the first call didn't return success,
>It can't because of the reasons mentioned above ...
>> call recursively on the right side of
>> the "|" (starting from the same position in the input stream as for the
call
>> on the left side of the "|"). If the match succeeds, return success,
>> otherwise return failure.
>>
>> This is effectively the same as backtracking.
>>
>pretty ineffective seems to me ...
>... no offense ...
No offence taken :-) By "effectively the same as backtracking", I meant
"another way of achieving backtracking". I didn't think about speed and stack
usage.
>> >PS: I am somehow tired today to study and comment another examples, sorry
:-)
>>
>> Me too, I still have to read quite a few pages (of _really_ boring
statistics)
>> before I can go to bed ;-)
>I think still better than really bad toothache :-)
Ouch!
Kind regards,
--
Ole Friis <[EMAIL PROTECTED]>
"Ignorance is bliss"
(Cypher, The Matrix)
