Re: lpeg could infer the validity of this grammar.

[Sam Putman <atmanistan@...>]

On Sun, Dec 14, 2014 at 8:24 PM, Dirk Laurie <dirk.laurie@gmail.com> wrote:

2014-12-15 4:49 GMT+02:00 Sam Putman <atmanistan@gmail.com>:

> The grammar, as written, will not loop, and the compiler can reason through
> the call chain, just like we do, to confirm that.

In this case, it can. But a mechanism that can in general determine whether
a given grammar will terminate for all input --- didn't Alan Turing prove that
to be impossible?

^_^  

rule : patt / func

func = function() return func() end

Clearly we cannot infer all non-termination. 

I would accept, a la Turing the Great, a grammar for which this #patt business cannot be sorted into "may be left recursive" or "is not left recurisve".