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
Compare revisions Compare revisions

User contributions

    This user never has never made submissions.

    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.