elm-pratt-parser

Top-Down Operator Precedence Parsing

Face complex precedence and associativity rules without fear using elm/parser.

    elm install elm/parser
    elm install dmy/elm-pratt-parser

Overview

Writing parsers using elm/parser is usually simple and fun, but handling complex operators precedence and associativity rules in an expression parser can be tricky, or even hard and frustrating for more complex cases.

This library goal is to fix this by adding a single expression parser to elm/parser:

    expression : Config expr -> Parser expr

This functions is configured with smaller standard parsers, precedence values and associativity rules, thanks to a minimalist flexible API, and handles the whole expression parsing complexity using a simple but powerful algorithm inherited from the one described by Vaughan Pratt in his 1973 paper "Top Down Operator Precedence" [1].

Helpers are provided for literals, constants, prefix, infix and postfix operations but custom ones can be defined when needed.

The library is small, has a test suite, benefits from tail-call elimination for left-associative operations, and allows to produce excellent error messages, as usual with elm/parser, using Parser.Advanced if wanted.

Getting Started

Calculator Example

Here is a quite complete calculator.

It evaluates the result during parsing, without generating an explicit intermediate abstract syntax tree (AST), so it directly uses Float as the expr type.

import Parser exposing (..)
import Pratt exposing (..)

-- Parsers used at the start of expressions
-- or after an operator
nuds : List (Config Float -> Parser Float)
nuds =
    [ literal float
    , constant (keyword "pi") pi
    , prefix 3 (symbol "-") negate
    , prefix 5 (keyword "cos") cos
    , \config ->
        -- Sub-expression between parentheses
        succeed identity
            |. symbol "("
            |= subExpression 0 config
            |. symbol ")"
    ]

-- Infix and postfix operations parsers
leds : List (Config Float -> (Int, Float -> Parser Float))
leds =
    [ infixLeft 1 (symbol "+") (+)
    , infixLeft 1 (symbol "-") (-)
    , infixLeft 2 (symbol "*") (*)
    , infixLeft 2 (symbol "/") (/)
      -- Exponentiation is right associative
    , infixRight 4 (symbol "^") (^)
      -- Postfix operator to convert degrees to radians
    , postfix 6 (symbol "°") degrees
    ]

-- Expression parser configuration
conf : Config Float
conf =
    configure
        { nuds = nuds
        , leds = leds
        , spaces = spaces -- eat spaces between parsers
        }

-- Include the expression parser in an upper-level one
parser : Parser Float
parser =
    succeed identity
        |= expression conf
        |. end -- string must end after an expression


-- TESTS
run parser "-2^2^3" --> Ok -(2^(2^3))
run parser "-2^2^3" --> Ok -256

run parser "3--4" --> Ok (3-(-4))
run parser "3--4" --> Ok 7

run parser "cos (2*pi)" --> Ok 1
run parser "cos (2*180°)" --> Ok 1
run parser "1 - cos 360°" --> Ok 0

Step by Step

Let's describe step by step each part of the example.

1. Define nud parsers

First we define the so-called nud parsers, for_"Null Denotation"_, because they don't use a preceding expression.

These parsers are used at the start of expressions, or after an operator, and include among others literals, constants, prefix operations or sub-expressions parsers:

nuds : List (Config Float -> Parser Float)
nuds =
    [ literal float
    , constant (keyword "pi") pi
    , prefix 3 (symbol "-") negate
    , prefix 5 (keyword "cos") cos
    , \config ->
        -- Sub-expression between parentheses
        succeed identity
            |. symbol "("
            |= subExpression 0 config
            |. symbol ")"
    ]

Note that literal, constant and prefix helpers all take a Parser () argument, like float, keyword pi or symbol "-", so you have full control on parsing and produced error messages.

The prefix helper first needs an Int argument, called the binding power. It represents the precedence level, so the higher it is, the higher the operator precedence level is.

All parsers last argument is a Config expr, passed automatically by the expression parser, that allows to call recursively the whole expression parser, or a sub-expression with a different binding power using subExpression.
This is used above in the last parser for expressions between parentheses and inside prefix, infix and postfix helpers.
This is why the type of each nud parser is Config expr -> Parser expr.

2. Define led parsers

Then we define the so-called led parsers, for_"Left Denotation"_. These parsers are used after a nud parser and take a left expression argument. They typically include infix and postfix operations parsers:

leds : List (Config Float -> (Int, Float -> Parser Float))
leds =
    [ infixLeft 1 (symbol "+") (+)
    , infixLeft 1 (symbol "-") (-)
    , infixLeft 2 (symbol "*") (*)
    , infixLeft 2 (symbol "/") (/)
      -- Exponentiation is right associative
    , infixRight 4 (symbol "^") (^)
      -- Postfix operator to convert degrees to radians
    , postfix 6 (symbol "°") degrees
    ]

Like nud parsers, they receive a Config expr, but return instead a tuple
(Int, expr -> Parser expr) because they need to provide their binding power to the algorithm, and a expr -> Parser expr parser that will be called with the preceding expression (the left expression).
See subExpression documentation to better understand the algorithm.

3. Complete configuration

We can them complete the configuration by adding a spaces parser of type Parser () that will be used between each nud and led parser. Parser.spaces is typically used, or succeed () if a general parser is not wanted.

conf : Config Float
conf =
    configure
        { nuds = nuds
        , leds = leds
        , spaces = spaces -- eat spaces between parsers
        }

4. Include the expression parser in an upper level one

Let's require the end of string after our expressions by including our parser into a top-level elm/parser one:

parser : Parser Float
parser =
    succeed identity
        |= expression conf
        |. end -- string must end after an expression

That's it!
And we have used all the functions exposed by the Pratt module.

A more complete example is included in the package source code, see examples/Calc.elm.

For a similar example but with an AST using a custom type, see examples/Math.elm instead.

Of course, you can define parsers for any expression, not only mathematical ones. For example have a look at examples/Boole.elm for a start with Boole's Algebra and an example of if then else expressions.

About Pratt Parsers

The parsers configured by this library use a variant of the algorithm described by Vaughan Pratt in his 1973 paper "Top Down Operator Precedence" [1]. Such parsers are usuall called "Pratt parsers", "Top-Down Operator Precedence parsers", or "TDOP" parsers.

This algorithm is used in this library because compared to alternatives, my experience confirmed what Vaughan Pratt claimed:

"The approach described [...] is very simple to understand, trivial to implement, easy to use, extremely efficient in practice if not in theory, yet flexible enough to meet most reasonable syntactic needs of users [...]. Moreover, it deals nicely with error detection."

Note that the later "precedence climbing" algorithm is now often considered as a special case of the earlier Pratt parsing algorithm.

See [2] to read more about them.

At last, Douglas Crockford, who implemented a Javascript parser using a Pratt parser for JSLint [4], said:

"Another explanation is that his technique is most effective when used in a dynamic, functional programming language."

I believe that this has already be proven to be wrong [5], and I hope that this implementation will help confirming it.

Terminology

The terminology inherited from Vaughan R. Pratt's paper used in this library is about the "led", "nud" and "binding power" terms.

I kept this original terminology because I couldn't find a better one, and less importantly because it would be kind of deceiving to change it for those used to it.

nud

In this library, nud parsers, for "Null Denotation", are parsers used at the start of expressions or after operators. They do not use a preceding expression and therefore do not take an expression argument.

Common nud parsers are literals, constants, or prefix operations parsers.

Here is how they are defined in the original paper:

"We will call the code denoted by a token without a preceding expression its null denotation or nud"

led

In this library, led parsers, for "Left Denotation", are parsers used after a nud one and use a preceding expression (left expression). Therefore they require an expression argument.

Common led parsers are infix and postfix operations parsers.

Here is how they are defined in the original paper:

"We will call the code denoted by a token with a preceding expression its left denotation or led"

Binding Power

The binding power is a kind of precedence value, so the higher it is, the higher the precedence of the operator is. This is enough to configure complex expression parsers, however a better understanding might be required to write custom parsers configuration helpers. For example, the binding power is also used to achieve right-associative operations.

See [3] and the algorithm described in subExpression documentation for more details.

Design and Implementation Considerations

The main differences with Pratt's design and implementation, that reflects on this library API, are:

1. Tokens are reduced to their minimal form:

   • just a parser for nud tokens
   • a binding power and a parser (with an expression argument) for led tokens

   There is therefore no actual token anymore and it is not necessary to tokenize the expression before parsing it.

2. nuds and leds are not stored in a Dict using the operator as the key, instead they are just two lists of parsers used with Parser.oneOf.

References

1. Vaughan R. Pratt, "Top Down Operator Precedence", 1973.
2. Andy Chu, Pratt Parsing Index and Updates, 2017 (updated regularly)
3. Eli Bendersky, Top-Down operator precedence parsing, 2010
4. Douglas Crockford, Top Down Operator Precedence Douglas Crockford, 2007
5. Andy Chu, Pratt Parsers Can Be Statically Typed, 2016

License

BSD-3-Clause