Re: Res: lpeg and left recursion

[Wesley Smith <wesley.hoke@...>]

> It also seems rather tied to packrat parsers, so it isn't clear if/how it
> could be adapted to other implementation techniques.

Perhaps, but if I'm reading his papers correctly
(http://www.vpri.org/pdf/tr2007002_packrat.pdf), the pseudo-code for
how to go from detecting left-recursion to handling it.  LPEG already
detects left-recursion.  For example:

require("lpeg")

local G = {
	[1] = lpeg.V'Rule',
	Rule = lpeg.V'Rule' * lpeg.P'/' * lpeg.V'Constant',
	Constant = lpeg.R'09'^-1,
}

local P = lpeg.P(G)

error: error ...uaav3/extra/samples/state.view/test.left.recurse.lua:9:
rule '1' is left recursive
	stack traceback:
	[C]: in function 'P'
	...uaav3/extra/samples/state.view/test.left.recurse.lua:9: in main chunk



And even indirectly:

require("lpeg")

local G = {
	[1] = lpeg.V'Rule',
	Rule = lpeg.V'Rule2' * lpeg.P'/' * lpeg.V'Constant',
	Rule2 = lpeg.V'Rule',
	Constant = lpeg.R'09'^-1,
}

local P = lpeg.P(G)

error: error ...uaav3/extra/samples/state.view/test.left.recurse.lua:10:
rule '1' is left recursive
	stack traceback:
	[C]: in function 'P'
	...uaav3/extra/samples/state.view/test.left.recurse.lua:10: in main chunk


So would it really be all that much different to apply Warth's
technique from Packrat to LPEG?  As for the argument that it doesn't
define the semantics, what would those have to be exactly?  From what
I can tell, the modifications to the matching function are internal to
the system and do not produce any semantic differences at the PEG
level since it's possible to transform a left recursive PEG into a non
left recursive PEG but it takes some serious contortions to do so that
inhibit their use.  Am I wrong about this?

wes