[Haskell-cafe] Left-factoring with Parsec
Joel Reymont
joelr1 at gmail.com
Thu Apr 12 15:04:59 EDT 2007
How does
expr = b a*
translate back into the grammar? Assuming that I had b, c, d...
expr = b <|> c <|> d <|> many (do { symbol ":"; expr; symbol ":";
expr })
Like this?
Thanks, Joel
On Apr 11, 2007, at 8:56 PM, Lennart Augustsson wrote:
> I presume your grammar has other clauses for expr, otherwise the
> loop is inevitable.
> Assuming you have other clauses you can always left-factor.
>
> Here's how those of us with weak memory can remember how to do it:
>
> Say that you have
>
> expr ::= expr ":" expr ":" expr
> | b
> Let's call the part from the first ":" a, since it doesn't matter
> what it is. So we have
> expr ::= expr a | b
> Let's call expr x, and just change notation slightly
> x = x a + b
> Now use high school algebra
> x = x*a + b
> x - x*a = b
> x*(1-a) = b
> x = b / (1-a)
> x = b * 1/(1-a)
> Now you have to remember that the Taylor series expansion of 1/(1-
> a) is
> 1/(1-a) = 1 + a + a^2 + a^3 + a^4 + ...
>
> OK, now put your grammar hat back on. What's
> 1 | a | aa | aaa | aaaa | ...
> it's just an arbitrary number of a:s, i.e., a* (or 'many a' in
> parsec).
> So finally
> expr = b a*
>
> -- Lennart
>
> On Apr 11, 2007, at 18:15 , Joel Reymont wrote:
>
>> Suppose I have expr = expr ":" expr ":" expr.
>>
>> Can the above be left-factored to fail on empty input so that my
>> parser doesn't go into a loop?
>>
>> Thanks, Joel
>>
>> --
>> http://wagerlabs.com/
>>
>>
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
--
http://wagerlabs.com/
More information about the Haskell-Cafe
mailing list