tail recursion

[S. Doaitse Swierstra]

Using the combinators at:

http://www.cs.uu.nl/groups/ST/Software/UU_Parsing

the problem is solved by (see also the file demo.hs there):

pLetter = pAnyOf "abcdefghijklmnopqrstuvwxyz"
pString = pList pLetter
pAll elems =  foldr ((*>) . pSym) (pSucceed []) elems

pRoot keys =   pString 
             <* pPacked (pSym '<') (pSym '>')
                        (foldr (<|>) pFail (map pAll keys))
             <* pString

Doaitse Swierstra

PS: small modifications may be needed depending on what you want to 
do with the part after the keyword


At 01:24 -0500 2/8/00, Christopher Sharpe wrote:
>Hello,
>
>Thanks to those who pointed out that my previous function p was not tail
>recursive.
>I think "exclude" (below) is. It seems to work on large files, although
>on a 160K
>file garbage collection fails to get enough space.
>
>What I am trying to do is find, in input such as an HTML file, like
>"ab<table>c",
>the string before the keyword such as "table".  So I try the keyword
>parsers
>(in the list "ps" below) at each point in the input, and add the
>character to
>my answer if all the parsers fail.  Something like a Boyer-Moore string
>search might
>be used to, though that would add complexity.  I couldn't find such an
>algorithm
>in any Hugs library.
>
>---------------------------- program -----------------------------
>
>import ParseLib
>
>exclude ans parsers  = P (\inp -> case inp of
>            []      -> [(reverse ans,"")]
>            (c:cs)  -> case papply try inp of
>			        [(_,remaining)] -> [(reverse ans,remaining)]
>			        []		  -> papply (exclude 
>(c:ans) parsers) cs
>                  	 )
>   where try = commonSubstring >> foldr1 (+++) parsers
>
>
>test  = papply (exclude "" ps) "ab<table>c"
>
>commonSubstring = string "<"
>
>ps = [string "table>",string "/table>" ]
>Content-Type: Haskell;
>  name="ww.hs"
>Content-Transfer-Encoding: 7bit
>Content-Disposition: inline;
>  filename="ww.hs"
>
>Attachment converted: Doaitse:ww.hs 2 (????/----) (00006585)

-- 
__________________________________________________________________________
S. Doaitse Swierstra, Department of Computer Science, Utrecht University
                       P.O.Box 80.089, 3508 TB UTRECHT,   the Netherlands
                       Mail:  mailto:doaitse@cs.uu.nl
                       WWW:   http://www.cs.uu.nl/
                       PGP Public Key: http://www.cs.uu.nl/people/doaitse/
                       tel:   +31 (30) 253 3962, fax: +31 (30) 2513791
__________________________________________________________________________