[Haskell-cafe] Left-factoring with Parsec
Lennart Augustsson
lennart at augustsson.net
Thu Apr 12 16:32:24 EDT 2007
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
>>>
>>> --
>>> 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