Useful Chompers
Tags: elm
Published: 2023-08-16 09:05:27

---
title: Useful Chompers
published: true
description: Learn about useful chompers that can help you write better parsers.
tags: elm
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2ku92kfd7c6mldhj7bz1.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-08-15 01:47 +0000
---

There are useful chompers, not defined in [elm/parser](https://package.elm-lang.org/packages/elm/parser/1.1.0), that can help you in the lexical analysis stage of your parser.

## What are chompers?

[Chompers](https://package.elm-lang.org/packages/elm/parser/1.1.0/Parser#chompers) or the "chomping" family of functions are special functions, that return `Parser ()`, that allow you to validate a sequence of characters. `elm/parser` defines two such functions called [`chompIf`](https://package.elm-lang.org/packages/elm/parser/1.1.0/Parser#chompIf) and [`chompWhile`](https://package.elm-lang.org/packages/elm/parser/1.1.0/Parser#chompWhile) but there are many others, for e.g. `chompOptional`, `chompOneOrMore`, `chompExactly`, `chompAtLeast`, `chompAtMost`, and `chompBetween`, that can be useful to define as well.

## What is lexical analysis?

A parser is usually separated into two stages. The first stage does the lexical analysis, or token generation, by which the input characters are split into meaningful symbols defined by a grammar of [regular expressions](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions).

For e.g. the meaningful symbols in the [context-free grammar for spreadsheet formulas](https://github.com/dwayne/elm-7guis/blob/2db8da1903eb0e288c711912eba272b82194b676/src/Task/Cells/Data/Formula/grammar.ebnf) are `Text`, `Decimal`, `Coord`, and `Identifier`.

```ebnf
Formula     ::= '=' Expr | Text
Expr        ::= Number
              | Cell
              | Range
              | Application
Number      ::= Decimal
Cell        ::= Coord
Range       ::= Coord ':' Coord
Application ::= Identifier '(' ( Expr ( ',' Expr )* )? ')'

/* Lexemes */

Text       ::= [^=] .*
Decimal    ::= '-'? [0-9]+ ('.' [0-9]*)?
Coord      ::= [A-Z] ( '0' | [1-9] [0-9]? )
Identifier ::= [a-zA-Z_] [a-zA-Z0-9_]*
```

## Lexical analysis with chompers

You can use chompers to write the equivalent of any regular expression. As a result, chompers become pretty handy for lexical analysis.

For e.g. the lexemes `Text`, `Decimal`, `Coord`, and `Identifier` are defined by regular expressions in the grammar above. This means we can rewrite them in `elm/parser` using a combination of chompers. `Decimal` could be defined as follows:

```elm
decimal : Parser Float
decimal =
    chompDecimal
        |> P.mapChompedString (\s _ -> String.toFloat s |> Maybe.withDefault 0)
        |> lexeme


chompDecimal : Parser ()
chompDecimal =
    let
        decimalPart =
            P.succeed ()
                |. P.chompIf ((==) '.')
                |. P.chompWhile Char.isDigit
    in
    P.succeed ()
        |. chompOptional ((==) '-')
        |. chompOneOrMore Char.isDigit
        |. chompZeroOrOne decimalPart
```

Read the [Lexer.elm](https://github.com/dwayne/elm-7guis/blob/2db8da1903eb0e288c711912eba272b82194b676/src/Task/Cells/Data/Formula/Lexer.elm) module to see how the rest of them could be defined.

**N.B.** *Assume [elm/parser](https://package.elm-lang.org/packages/elm/parser/1.1.0) is installed and the following imports have been made available in the code snippets below.*

```elm
import Parser as P exposing ((|.), (|=), Parser)
```

### `chompOptional`

It validates zero or one occurrences of the matching characters. It is equivalent to the question mark `?` in regular expressions.

```elm
chompOptional : (Char -> Bool) -> Parser ()
chompOptional isGood =
    P.oneOf
        [ P.chompIf isGood
        , P.succeed ()
        ]
```

For e.g. we can define `optionalSign ::= ( '+' | '-' )?` as follows:

```elm
chompOptionalSign : Parser ()
chompOptionalSign =
	chompOptional (\c -> c == '+' || c == '-')
```

Check out a [full example](https://github.com/dwayne/elm-chompers/blob/a6a8c2baf385469226aef8f2061c6233e29dbcd7/tests/Test/Chompers.elm#L226-L253).

### `chompOneOrMore`

It validates one or more occurrences of the matching characters. It is equivalent to the plus sign `+` in regular expressions.

```elm
chompOneOrMore : (Char -> Bool) -> Parser ()
chompOneOrMore isGood =
    P.succeed ()
        |. P.chompIf isGood
        |. P.chompWhile isGood
```

For e.g. we can define `natural ::= [0-9]+` as follows:

```elm
chompNatural : Parser ()
chompNatural =
	chompOneOrMore Char.isDigit
```

Check out a [full example](https://github.com/dwayne/elm-chompers/blob/a6a8c2baf385469226aef8f2061c6233e29dbcd7/tests/Test/Chompers.elm#L270-L298).

### `chompExactly`

`chompExactly n` is equivalent to `{n}` in regular expressions. It validates that the matching characters occurred exactly `n` times.

Here's a straightforward but slow implementation:

```elm
chompExactlySlow : Int -> (Char -> Bool) -> Parser ()
chompExactlySlow n isGood =
    if n <= 0 then
        P.succeed ()

    else
        -- if n > 0 then
        P.succeed ()
            |. P.chompIf isGood
            |. chompExactlySlow (n - 1) isGood
```

And, here's a faster implementation that uses [`loop`](https://package.elm-lang.org/packages/elm/parser/1.1.0/Parser#loop):

```elm
chompExactlyFast : Int -> (Char -> Bool) -> Parser ()
chompExactlyFast n isGood =
    P.loop n
        (\i ->
            if i <= 0 then
                P.succeed <| P.Done ()

            else
                P.chompIf isGood
                    |> P.andThen (\_ -> P.succeed (P.Loop (i - 1)))
        )
```

I ran some [benchmarks](https://github.com/dwayne/elm-chompers/blob/a6a8c2baf385469226aef8f2061c6233e29dbcd7/benchmarks/src/Main.elm#L26-L31) and it turns out that `chompExactlyFast` is about 70% faster than `chompExactlySlow`.

![The results of a benchmark for chompExactly](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/be6nla6mnjwrauon6cg5.png)

As an example, you can use `chompExactly` to help you parse [ZIP+4](https://en.wikipedia.org/wiki/ZIP_Code#ZIP+4) formatted zip codes, where `zipCode ::= [0-9]{5} '-' [0-9]{4}`.

```elm
type alias ZipCode =
	{ basic : String
	, geoSegment : String
	}

zipCode : Parser ZipCode
zipCode =
	P.succeed ZipCode
		|= nDigits 5
		|. P.chompIf ((==) '-')
		|= nDigits 4

nDigits : Int -> Parser String
nDigits =
	P.getChompedString << chompNDigits

chompNDigits : Int -> Parser ()
chompNDigits n =
	chompExactly n Char.isDigit
```

Check out a [full example](https://github.com/dwayne/elm-chompers/blob/a6a8c2baf385469226aef8f2061c6233e29dbcd7/tests/Test/Chompers.elm#L302-L362).

### `chompAtLeast`

`chompAtLeast min` is equivalent to `{min,}` in regular expressions. It validates that the matching characters occurred `min` or more times.

```elm
chompAtLeast : Int -> (Char -> Bool) -> Parser ()
chompAtLeast min isGood =
    P.succeed ()
        |. chompExactly min isGood
        |. P.chompWhile isGood
```

Check out some [examples of `chompAtLeast`](https://github.com/dwayne/elm-chompers/blob/a6a8c2baf385469226aef8f2061c6233e29dbcd7/tests/Test/Chompers.elm#L95-L117).

### `chompAtMost`

`chompAtMost max` is equivalent to `{, max}` in regular expressions. It validates that the matching characters occurred up to `max` times.

```elm
chompAtMost : Int -> (Char -> Bool) -> Parser ()
chompAtMost max isGood =
    P.loop 0
        (\i ->
            if i < max then
                P.oneOf
                    [ P.chompIf isGood
                        |> P.andThen (\_ -> P.succeed (P.Loop (i + 1)))
                    , P.succeed <| P.Done ()
                    ]

            else
                P.succeed <| P.Done ()
        )
```

Firstly, notice that `chompAtMost max` always succeeds just like `chompWhile`. The only difference is that it is bounded by `max`. While `i < max`  we try to consume the next character, `P.chompIf isGood`. But, if it fails that's fine since it means we've matched all the characters we could match up to this point, i.e. `i` of them. That's why we stop with success. In the case, `i == max`, we've match the most we're allowed to match so again we stop with success.

Check out some [examples of `chompAtMost`](https://github.com/dwayne/elm-chompers/blob/a6a8c2baf385469226aef8f2061c6233e29dbcd7/tests/Test/Chompers.elm#L118-L152).

### `chompBetween`

`chompBetween min max` is equivalent to `{min, max}` in regular expressions. It validates that the matching characters occurred at least `min` times, but not more than `max` times.

```elm
chompBetween : Int -> Int -> (Char -> Bool) -> Parser ()
chompBetween min max isGood =
    if min > max then
        P.succeed ()

    else
        let
            l =
                Basics.max min 0

            h =
                Basics.max l max
        in
        chompExactly l isGood
            |> P.andThen (\_ -> chompAtMost (h - l) isGood)
```

Given, `0 < min <= max`, then to implement `chompBetween min max` we first try to match exactly `min` characters. Then, the most characters we're allowed to match after that is `max - min`.

Check out some [examples of `chompBetween`](https://github.com/dwayne/elm-chompers/blob/a6a8c2baf385469226aef8f2061c6233e29dbcd7/tests/Test/Chompers.elm#L153-L221).

## Conclusion

Chompers work at the character level just like regular expressions. They can be used to describe the lexemes or tokens of your grammar. Because of this, I recommend putting your chomping functions in a `Lexer.elm` module and having a `Parser.elm` module that depends on it.

You can view an example of my approach in my [formula lexer](https://github.com/dwayne/elm-7guis/blob/2db8da1903eb0e288c711912eba272b82194b676/src/Task/Cells/Data/Formula/Lexer.elm) and [formula parser](https://github.com/dwayne/elm-7guis/blob/2db8da1903eb0e288c711912eba272b82194b676/src/Task/Cells/Data/Formula/Parser.elm) (here's the [grammar](https://github.com/dwayne/elm-7guis/blob/2db8da1903eb0e288c711912eba272b82194b676/src/Task/Cells/Data/Formula/grammar.ebnf#L16-L21)) for the [7GUIs Cells task](https://dwayne.github.io/elm-7guis/cells.html).

For now I'm just collecting useful chompers in [dwayne/elm-chompers](https://github.com/dwayne/elm-chompers) and some day I may turn it into an Elm package, but for now I'm still exploring. Feel free to copy and paste these chompers into your own projects if you find them useful.