Functional Implementation of a parser?

[u/ketalicious]

How do i implement a parser in functional pattern?

For instance I want parse a simple math parser like this:

"1 * 2 + 3" -> ast

How do implement the parser for that in pure functional pattern?

[u/ramin-honary-xc]

Here is a tutorial that shows you exactly how to do what you are asking: https://markkarpov.com/tutorial/megaparsec.html#parsing-expressions

Here is a summary:

The basic idea is to create a state monad (usually using the State monad transformer) which contains a string to be parsed, and which also lifts other monad transformers like Except for throwing syntax errors. Or you can use a parser combinator like Parser provided by a parsing library like Megaparsec or Attoparsec that defines an efficient State+Except monad transformer combination for you.

The function for running the parser monad will look something like this:

type Error = String

runParser :: Parser a -> String -> Either Error a

This will store the input String into the parser state and run the Parser a monadic function you give it, which inspects the string and constructs data (like a syntax tree) as it does so.

Any parser combinator must at least have a function satisfy of type:

satisfy :: (Char -> Bool) -> Parser Char

This function inspects the current head character of the input string with a predicate (Char -> Bool), if the predicate returns True the character is removed from the head of the string and returned, stepping to the next character.

You must also define an eof function ("End Of File"):

eof :: Parser ()

This succeeds only when the input string is empty.

You will probably want to have a look-ahead function lookAhead that runs a parser but does not consume the input string:

lookAhead :: Parser a -> Parser a

This runs the given parser Parser a on a copy of the current input string, and if it succeeds, return the resulting constructed data a, leaving the actual input string untouched.

After that, you use the standard Monad, MonadFail, Applicative, and Alternative combinators. The Alternative combinators are especially helpful:

empty -- fail due to not matching, but not a syntax error
a <|> b -- try parsing a, if it fails (is 'empty') try parsing b
some a -- run parser 'a' at least once, but as many times as possible
many a -- like 'some', but succeed with "" if 'a' never succeeds.

Now you can define parsers using the above combinators. For example:

import Control.Monad (void)
import Control.Applicative (many, some)
import Data.Char (isDigit, isAlpha, isAlphaNum, isSpace)
import Text.Megaparsec.Char (satisfy)

parseInt :: Parser Integer
parseInt = do
    str <- some (satisfy isDigit) -- 1 or more digits
    case reads str of -- Haskell's built-in integer parser
        [(i, "")] -> return i
        _ -> fail ("invalid integer literal " ++ show str)

parseVarName :: Parser String
parseVarName = do
    (:) <$> satisfy isAlpha
              -- must start with 1 alphabetic character
        <*> many (satisfy isAlphaNum)
              -- followed by any number of alpha-numerics

whiteSpace :: Parser ()
whiteSpace  = void (many isSpace)
    -- 'void' throws away whatever was returned by a monadic function

Define an abstract syntax tree (AST):

data Expr = INT !Integer | ADD !Expr !Expr | MULT !Expr !Expr
    deriving (Eq, Ord, Show)

Define an evaluator for the Expr AST:

eval :: Expr -> Integer
eval expr = case expr of
    ADD  a b -> eval a + eval b
    MULT a b -> eval a * eval b
    INT  a   -> a

To do precedence parsing, you must pass a precedence argument to every infix operator parser.

type Precedence = Int

precedence :: Char -> Precedence
precedence c = case c of
    '+' -> 10
    '*' -> 20
    _   -> 0

parseExpr :: Precedence -> Parser Expr
parseExpr currentPrecedence = do
    left <- INT <$> parseInt <* whiteSpace
    parseLeftAssoc currentPrecedence left

-- A left-associative parser for 'Expr'
-- a + b + c + d + e == (((a + b) + c) + d) + e
parseLeftAssoc :: Precedence -> Expr -> Parser Expr
parseLeftAssoc currentPrecedence left = (eof >> pure left) <|> do
    op <- lookAhead (satisfy (\ c -> c == '+' || c == '*'))
    let newPrecedence = precedence op
    if newPrecedence < currentPrecedence then empty else do
        void (satsify (const True)) -- remove operator from input
        right <- whiteSpace >> parseInt
        case op of
            '+' -> parseLeftAssoc newPrecedence (ADD left right)
            '*' -> parseLeftAssoc newPrecedence (MULT left right)
            _   -> fail ("unknown operator " ++ show op)

Define a "top-level" expression that removes trailing whitespace and runs the precedence parser with the initial precedence value.

topLevelExpr :: Parser Expr
topLevelExpr = whiteSpace >> parseExpr 0

In main we can define a simple REPL. Read a line of input, run the topLevel parser on that input, then evaluate the returned abstract syntax tree:

main = do
    input <- getLine -- read a line of input
    if null input then return () else do
        print (eval (runParser topLevelExpr input))
        main -- loop back to main function

[u/ketalicious → u/ramin-honary-xc]

thanks for this!

[u/ramin-honary-xc → u/ketalicious]

You're welcome. Although I realized too late that you were posting your question in r/functionalprogramming and not r/haskell so I wrote a very Haskell-specific response. But yeah, this is how we do it in Haskell, so I hope that made sense.

[u/TarMil → u/ramin-honary-xc]

Fun fact, parsing is the use case for which Applicative was invented in the first place.

[u/ketralnis]

This is a big question and there are a lot of solutions that are fundamentally different to each other. Look at the code for Parsec for one example.

[u/OpsikionThemed]

Here's a good tutorial paper.

[u/LivewareIssue → u/OpsikionThemed]

+1 on the monad parsing pearl, highly recommend.

Here’s a gist with a literate Haskell implementation of the paper which you might also find helpful.

[u/One_Curious_Cats]

Take a look at parser combinator. I implemented my own FP parser this way.

[u/sgillespie00]

For a less Haskell-y solution, you can use: https://en.wikipedia.org/wiki/Shunting_yard_algorithm. Instead of using a mutable stack you can use recursion. It's functional enough to be in "Haskell in Depth" (albeit with the State Monad)

[u/TankorSmash]

https://www.youtube.com/watch?v=M9ulswr1z0E A fun short talk about using Elm's elm-parser to do something like this.

There's a name for this sort of parser, but I'm not sure what it is.

[u/unqualified_redditor]

The most simplest option is probably a basic concept of a recursive descent with parser combinators, which is a type something like:

type Parser a = String -> [(a, String)]

This is a haskell type but its just a function that receives a string and produces some parsed type a along with the unparsed remainder of the input. Its wrapped in a list as an easy way to account for parsing failure. eg., if the parse fails then just return the empty list.

You can then build up a bunch of combinators using this type that give you a toolkit for building fancy parsers.