[Haskell-cafe] Parser left recursion

[Kim-Ee Yeoh]

On Sun, Feb 24, 2013 at 10:04 PM, Tillmann Rendel <
rendel at informatik.uni-marburg.de> wrote:

> The recursion is well-founded if (drop n1 text) is smaller then text. So
> we have two cases, as Roman wrote:
>
> If the language defined by B contains the empty string, then n1 can be 0,
> so the recursion is not well-founded and the parser might loop.
>

Ah! So "A ::= B A" is really /not/ the full grammar of the language but an
abbreviated one, minus terminals. At the very least, partial parses make
sense and the input stream is assumed finite.

Because "A ::= B A" could be understood, not so much as a parsing rule, but
as the full definition of a language which comprises only one word: BBBBB
... ad infinitum. So all that mention of well-foundedness was confusing.

Thanks, Tillmann!

-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130225/4e23f274/attachment.htm>