Re: [LPeg] intermittent stack exhaustion

[Sebastian Cato <seb.cato@...>]

On Tue, Sep 13, 2016 at 4:32 PM, Roberto Ierusalimschy
<roberto@inf.puc-rio.br> wrote:
> I think you are right about not being necessary to follow the next
> rule (sib2 of TRule), but we still need to control recursion in
> TCall nodes (as I said in the previous message). Try the following
> grammar with your patch:
>
> p = lpeg.C(-lpeg.P{lpeg.P'x' * lpeg.V(1) + lpeg.P'y'})
>
> p:match("xx")

Yes, I didn't think about that case. Interesting problem from a CS
perspective. I see some similarities with verifygrammar, verifyrule
and the testing for left recursive patterns here as well, maybe it's
possible to combine them?

A couple of options I can think about:

1) the way verifygrammar and verifyrule works, with an int
passed[MAXRULES], and npassed as a counter to keep track of the
visited rules. (I think 'passed' can be short ints, since keys are
short ints, if we want to save stack space).

2) reserve a bit in each TTree node (e.g., the upper most bit of tag)
to use as a 'visited' flag and perform the depth first search. If
encountering a node with the bit set, we know that the graph is
cyclic. Would require clearing the bits later if it's to be done more
than once. Could maybe be used for verifygrammar, verifyrule too.

3) use a strongly connected component (SCC) algorithm, e.g., Tarjan's
SCC. Maybe overkill.

4) use a lua table as a set, with keys being the addresses to the
visited nodes. Perform a DFS, for each TRule node: if the address is
in the set, the graph is cyclic. I'm thinking about the case where we
have TCall -> TRule, I don't know if there's any other nodes that can
lead to cycles.