[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