detecting recursive pattern

[spir <denis.spir@...>]

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