Recursive descent parser

A top-down parser using mutually recursive procedures

Illustration

Consider this grammar for binary numbers:

[number] number : bits rest ;
[single] bits : bit ;
[many] bits : bit bits ;
[zero] bit : '0' ;
[one] bit : '1' ;
[integer] rest : ;
[rational] rest : '.' bits ;

A recursive descent parser could be implemented in Haskell as follows:

-- Accept and enforce complete input consumption
accept :: String -> Bool
accept i = case number i of
Just [] -> True
_ -> False

-- Functions for nonterminals
number, bits, bit, rest :: String -> Maybe String

-- [number] number : bits rest ;
number i = bits i >>= rest

-- [single] bits : bit ;
-- [many] bits : bit bits ;
bits i = if lookahead 2 (flip elem ['0','1']) i
then many
else single
where
single = bit i
many = bit i >>= bits

-- [zero] bit : '0' ;
-- [one] bit : '1' ;
bit i = if lookahead 1 ((==) '0') i
then zero
else one
where
zero = match '0' i
one = match '1' i

-- [integer] rest : ;
-- [rational] rest : '.' bits ;
rest i = if lookahead 1 ((==) '.') i
then rational
else integer
where
integer = Just i
rational = match '.' i >>= bits

-- Look ahead in input; avoid looking beyond end of input
lookahead :: Int -> (Char -> Bool) -> String -> Bool
lookahead l f i = length i >= l && f (i!!(l-1))
-- BEGIN ...
-- Match a terminal (a character)
match :: Char -> String -> Maybe String
match t (t':i) | t == t' = Just i
match _ _ = Nothing

This parser uses 'lookahead', i.e., it looks into the input stream to make decisions where necessary.

Here is a variation which uses backtracking instead:

-- Accept and enforce complete input consumption
accept :: String -> Bool
accept i = case number i of
Just [] -> True
_ -> False

-- Functions for nonterminals
number, bits, bit, rest :: String -> Maybe String

-- [number] number : bits rest ;
number i = bits i >>= rest

-- [single] bits : bit ;
-- [many] bits : bit bits ;
bits i = many `mplus` single
where
single = bit i
many = bit i >>= bits

-- [zero] bit : '0' ;
-- [one] bit : '1' ;
bit i = zero `mplus` one
where
zero = match '0' i
one = match '1' i

-- [integer] rest : ;
-- [rational] rest : '.' bits ;
rest i = rational `mplus` integer
where
integer = Just i
rational = match '.' i >>= bits

-- Match a terminal (a character)
match :: Char -> String -> Maybe String
match t (t':i) | t == t' = Just i
match _ _ = Nothing

this Ralf Lämmel edited this article at Fri, 30 Jun 2017 12:08:53 +0200

User contributions

This user never has never made submissions.

Syntax for editing wiki

For you are available next options:

will make text bold.

will make text italic.

will make text underlined.

will make text striked.

will allow you to paste code headline into the page.

will allow you to link into the page.

will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

will allow you to paste image into the page.

is list with bullets.

is list with numbers.

will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

will allow your to insert code snippets from @worker.

Syntax for editing wiki

For you are available next options:

will make text bold.

will make text italic.

will make text underlined.

will make text striked.

will allow you to paste code headline into the page.

will allow you to link into the page.

will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

will allow you to paste image into the page.

is list with bullets.

is list with numbers.

will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

will allow your to insert code snippets from @worker.