Concept:
Recursive descent parser
Headline
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:
import Control.Monad
-- 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:
import Control.Monad
-- 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
Ralf Lämmel
edited this article at
Fri, 30 Jun 2017 12:08:53 +0200
User contributions
User edits
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.