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
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,
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;
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@haskell.org
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