Patrick~
On 10/10/05, Patrick R. Michaud <[EMAIL PROTECTED]> wrote:
> On Mon, Oct 10, 2005 at 09:11:02AM -0400, Matt Fowles wrote:
> > Patrick~
> >
> > The theoretical implementation of this is quite simple. Keep a
> > counter. everytime a token is consumed from the input stream reset it.
> > Every time a rule is followed increment the counter. If the counter
> > is ever greater than the number of productions in the grammer, then
> > you have gone into infinite recursion.
>
> What happens with something like:
>
> rule atom { A }
> rule binary { . <atom> | <expr> \* <atom> }
> rule expr { <binary> }
>
> "AB" ~~ / <expr> /
>
> Here, the '.' in <binary> keeps "consuming" the initial "A" (thus
> resetting the counter), but the <atom> rule fails, so we take
> the alternation which recurses back to <expr> and does the whole
> thing all over again (with the counter having been reset to zero).
> So I guess we'd need to backtrack the counter as well...?
>
> Perhaps what we want to be watching is "positions", so that we detect
> when the depth of nested subrules activated from a common input position
> is greater than the total number of defined rules?
>
> And, of course, in the case of rules containing closures, all bets
> should be off for detecting infinite recursion, since the closure
> could be handling the termination of the recursion based on some
> criteria other than tokens consumed from the input stream. (But it's
> also probably easy to know when we've executed a closure and thus
> disable the check for infinite recursion when that happens.)
You are right about backtracking, rather than a simple counter we need
to keep track of the current recursion depth from a particular
position. I agree that we would have to disable this for rules
containing code. Perhaps a better approach would be to perform a bit
of static analysis on the grammar and look for left recursions at
creation time (I believe that is a known problem). Then we can just
warn once up front and go on our merry way recursing at matchtime.
Matt
--
"Computer Science is merely the post-Turing Decline of Formal Systems Theory."
-Stan Kelly-Bootle, The Devil's DP Dictionary
