[Haskell-cafe] Left-factoring with Parsec
Lennart Augustsson
lennart at augustsson.net
Wed Apr 11 15:56:14 EDT 2007
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
More information about the Haskell-Cafe
mailing list