[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