Patrick~ On 10/9/05, Patrick R. Michaud <[EMAIL PROTECTED]> wrote: > On Sun, Oct 09, 2005 at 09:55:44AM -1000, Joshua Hoblitt wrote: > > > > What is the status of this bug? Should this be a PGE todo item? > > > > > > My opinion is that it's "not a bug" -- the normal behavior for > > > most programs with infinite recursive loops is that they > > > eventually explode. > > > > Sounds reasonable. I'm sure it would be nearly impossible to catch all > > possible cases of infinite recursion when the grammar is compiled but > > how difficult would it be to trap at runtime? A simple warning along > > the lines of "Warning: production foo has recursed 10,000 times without > > matching any terminal\n" would certainly be useful in figuring why it > > blew up... > > We can enter "trap recursions without terminals" as a possible PGE > todo item, but unless someone knows an easy implementation or wants > to take on the task of implementation it's not likely to be resolved > anytime soon. :-)
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. The only place where this technique will fail is where a rule that it is attempting to match changes dynamically (i.e. mid match). In such an event you have to consider the number of productions infinite. Matt -- "Computer Science is merely the post-Turing Decline of Formal Systems Theory." -Stan Kelly-Bootle, The Devil's DP Dictionary
