[Haskell-cafe] Designing a Parser

PR Stanley prstanley at ntlworld.com
Sun Feb 17 01:20:01 EST 2008

Hi friends
I'm in the process of designing a series of functions which you might 
collectively call a parser. The idea is to evaluate an input string 
for a proof software. So a typical input string would be something 
like "(P & Q) -> q".
There are a number of things to consider here, for example, does the 
string belong to the domain which is a subset of the 7-bit ASCII 
table, starting from 32 and ending at 126. Then you need to remove 
all space characters to make things a bit simpler.  Next we find out 
if the logical sentnece is bracketted. I start this by looking for a 
bracket in the string. If true then I isolate the brackets into a new 
set in order to spot any odd ones.

Here is what I've done so far:
domain :: [Char]
domain = [x | x <- ascii7, x >= ' ' && x <= '~']
   where ascii7 = ['\0'..'\127']

-- a legal input character is a member of domain.
isInDomain :: Char -> Bool
isInDomain x = any (==x) domain

-- a legal input string is a subset of domain.
isSubset :: [Char] -> Bool
isSubset input = all isInDomain input

-- delete spaces for easier parsing.
noSpace :: [Char] -> [Char]
noSpace input = [x | x <- input, x /= space]
   where space = ' '

-- set of brackets
brackets = ['(', ')', '[', ']', '{', '}']

-- Are there any brackets in input?
hasBrackets :: [Char] -> Bool
hasBrackets input = or [True | x <- input, any (==x) brackets]

-- filter all brackets into a subset.
getBrackets :: [Char] -> [Char]
getBrackets input = [x | x <- input, any (==x) brackets]

-- What are matching brackets?
areMatched :: Char -> Char -> Bool
areMatched '(' ')' = True
areMatched '[' ']' = True
areMatched '{' '}' = True
areMatched _ _ = False

-- Can all the brackets in input be paired up?
allMatched :: [Char] -> Bool

  I can't think of an elegant pattern for the last function. I've 
already tried set comprehension. However, something tells me that the 
answer may lie in a complex recursive pattern. I'm not afraid of 
complex solutions but I naturally see them as an easy way out. It's 
those clear simple patterns that separate men from mice. :-) I'd be 
grateful for any advice on this and indeed my approach as a whole. If 
you think I'm on the wrong path from the start feel free to let me 
know. I'm not asking for the answer. I'd like to work that out by 
myself although some guidance would be most appreciated.
Thanks, Paul

More information about the Haskell-Cafe mailing list