You need a "sequence" of b, and then a*. So expr = do p <- b <|> c <|> d q <- many (...) return ... On Apr 12, 2007, at 20:04 , Joel Reymont wrote:
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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe