[Haskell-cafe] Left-factoring with Parsec

Claus Reinke claus.reinke at talk21.com
Sat Apr 14 09:03:20 EDT 2007


>   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*

nice!-) different viewpoints yield new perspectives.

this made me wonder what those missing algebra operations would mean in terms 
of parsing/language generation; it hurts a bit to think about your algebraic manipulations
in that way, but if i got the interpretations right, they might be quite useful additions:

l1 - l2: things in l1 that are not in l2; generalising elimination of keywords from valid ids
l1 / l2: things that can be completed to be in l1, via suffixes in l2; standard tool in ides

thanks for the interesting detour,
claus



More information about the Haskell-Cafe mailing list