# Parser Combinators — Haskell

Source: https://www.geekswithgeeks.com/en/haskell/w-parsing

> Parse structured text with megaparsec by combining small parsers.

## Parsers are values

Haskell is famous for **parser combinators**: small parsers for numbers, symbols or keywords are combined with ordinary functions into parsers for whole languages. A parser is a value of a type such as `Parser a`, which consumes input and produces an `a` or an error. Because parsers are **Functors, Applicatives and Monads**, you combine them with familiar tools: `<$>` to transform results, `<*>`, `*>` and `<*` to sequence, `<|>` (from `Alternative`) for choice, `many` and `some` for repetition, and `do` notation for context-sensitive parsing. **megaparsec** is the most widely used library, with excellent error messages, `Text` support and helpers for lexing (`Text.Megaparsec.Char.Lexer`); **attoparsec** is faster for machine formats, and **parsec** is the classic predecessor. Common pattern: define a `lexeme` combinator that skips trailing whitespace and build the grammar from the bottom up, handling operator precedence with layered parsers or `makeExprParser` from `parser-combinators`. Parsers built this way are type-checked, testable and much more maintainable than regular expressions for anything non-trivial.

## An arithmetic expression parser and evaluator

Precedence by layering: expressions, terms and atoms.

```haskell
import Data.Void (Void)
import Text.Megaparsec
import Text.Megaparsec.Char (space)
import qualified Text.Megaparsec.Char.Lexer as L

type Parser = Parsec Void String

data Expr = Num Integer | Add Expr Expr | Mul Expr Expr
  deriving Show

lexeme :: Parser a -> Parser a
lexeme = L.lexeme space

symbol :: String -> Parser String
symbol = L.symbol space

atom :: Parser Expr
atom = Num <$> lexeme L.decimal
   <|> between (symbol "(") (symbol ")") expr

term :: Parser Expr                  -- multiplication binds tighter
term = foldl Mul <$> atom <*> many (symbol "*" *> atom)

expr :: Parser Expr
expr = foldl Add <$> term <*> many (symbol "+" *> term)

eval :: Expr -> Integer
eval (Num n)   = n
eval (Add a b) = eval a + eval b
eval (Mul a b) = eval a * eval b

main :: IO ()
main = do
  case parse (space *> expr <* eof) "<input>" "2 + 3 * (4 + 1)" of
    Left err -> putStr (errorBundlePretty err)
    Right e  -> print (eval e)                    -- 17
  parseTest (space *> expr <* eof) "2 + * 3"      -- prints a helpful error message
```

## Lego bricks for grammars

Parser combinators are Lego bricks: a brick that reads a digit, a brick that reads a plus sign, and connectors that say "one after another", "either this or that" or "as many as you like". Snap them together and you have a parser for a whole language.

**Quiz:** What does the <|> combinator do between two parsers?

- [ ] Runs both and combines results
- [ ] Repeats a parser
- [ ] Skips whitespace
- [x] Tries the first parser and, if it fails without consuming input, tries the second

*Answer:* Tries the first parser and, if it fails without consuming input, tries the second. <|> expresses choice between alternatives.