Recursive descent parser for grammar S -> baSab ∣ baS ∣ b

gistfile1.hs

module Main where

import Debug.Trace
import Control.Applicative
import Control.Monad

{-- recursive descent parser for grammar S -> baSab ∣ baS ∣ b --}

term :: Char -> String -> Maybe String
term _ [] = Nothing
term c (x:xs)
    | x == c    = Just xs
    | otherwise = Nothing

pS :: String -> Maybe String
pS s | trace ("pS " ++ s) False = undefined
pS s = pS1 s <|> pS2 s <|> pS3 s

pS1 :: String -> Maybe String
pS1 s | trace ("pS1 " ++ s) False = undefined
pS1 s = (term 'b' >=> term 'a' >=> pS >=> term 'b' >=> term 'a') s

pS2 :: String -> Maybe String
pS2 s | trace ("pS2 " ++ s) False = undefined
pS2 s = (term 'b' >=> term 'a' >=> pS) s

pS3 :: String -> Maybe String
pS3 s | trace ("pS3 " ++ s) False = undefined
pS3 s = term 'b' s 

main::IO()
main = print $ pS "babab"