Re: detecting recursive pattern

[joao lobato <btnfdp.lobato@...>]

If I remember my compiler classes correctly there was a dynamic
programming algorithm for left recursion detection in CFG's. My
professor called it "Kleene construction" and a google search for that
string yields his slides on it.

Perhaps you should try:
Compilers: Principles, Techniques and Tools , Alfred Aho, Ravi Sethi,
Jeffrey Ullman, 1985, Addison-Wesley

On 3/2/10, spir <denis.spir@gmail.com> wrote:
> Hello,
>
> The discussion about left-recursion in PEG let me wonder how any kind of
> recursion can be detected in a grammar.
> I had to face this topic when writing two kinds of parsing libraries, one
> purely in code (ie mainly implementing various Pattern types and a Node type
> for parse results), one having a kind of PEG language (a grammar beeing then
> "metaparsed" and rewritten into a code parser).
>
> It seemed to me this is a complicated issue, since recursive references can
> be hidden in a arbitrary chain of sub-patterns, so that the only way to find
> them was too traverse the whole tree (actually, the forest) of pattern
> definition. I would like to be wrong on this (this is very probably since my
> CS culture is close to nil ;-). But I thought this was too much for the
> benefit anyway and decided to let the user cope with the issue:
> * in code, create a pattern of special Recursion type (a symbolic reference,
> similar to LPEG V)
> * in text grammar, flag them, so that the parser generator creates a
> Recursion symbolic reference
>
> An adhoc solution may be to catch variable errors (or in Lua references
> pointing to nil) at runtime and then find a way to create symbolic
> references in the current scope on the fly -- but this seemed "dirty" to me.
> (Also, this scheme does not differenciate a recursive pattern from a trivial
> name error.)
>
> I would enjoy any pointer to a method to "recognize" a recursive pattern, or
> any other way to detect and cope with them.
>
> Denis
> --
> ________________________________
>
> la vita e estrany
>
> spir.wikidot.com
>
>