Gratt

Gratt is a generic implementation of a Pratt parser in C# for .NET Standard.

A Pratt parser is the affectionate name for a simple parsing technique presented by Vaughn Pratt in his 1973 paper “Top down operator precedence” (TDOP).

Gratt was inspired by the design of the Java implementation presented by Bob Nystrom in his journal entry “Pratt Parsers: Expression Parsing Made Easy”. The actual inspiration was the simplification and separation of interfaces in terms of prefix (nud) and infix (led) parselets (rather than the full Java implementation):

interface PrefixParselet {
  Expression parse(Parser parser, Token token);
}

interface InfixParselet {
  Expression parse(Parser parser, Expression left, Token token);
}

The unit tests for Gratt re-create and test the parser for the toy language Bantam discussed in Bob's journal entry.

The unit tests also contain a complete implementation for parsing and evaluating C# pre-processing expressions used in conditional directives #if and #elif.

Unlike Bob's Java implementation, Gratt's parser is completely generic:

class Parser<TState, TKind, TToken, TPrecedence, TResult>
{
    // ...
}

It can therefore work with any model of tokens (TToken), token types (TKind), precedence (TPrecedence) and result (TResult). It can also hold any user-defined state (TState) that may be needed during parsing although it is not required. An overload without any user-state simply assumes a unit.

Unlike Bob's Java implementation, Gratt does not define any interfaces to represent (prefix or infix) parselets. Instead, it relies on them being simple functions:

// version 2.0+

public static TResult
    Parse<TState, TKind, TToken, TPrecedence, TResult>(
        TState state,
        TPrecedence initialPrecedence, IComparer<TPrecedence> precedenceComparer,
        IEqualityComparer<TKind> kindEqualityComparer,
        TKind eoi, Func<TToken, Exception> eoiErrorSelector,
        Func<TKind, TToken, TState, Func<TToken, Parser<TState, TKind, TToken, TPrecedence, TResult>, TResult>> prefixFunction,
        Func<TKind, TToken, TState, (TPrecedence, Func<TToken, TResult, Parser<TState, TKind, TToken, TPrecedence, TResult>, TResult>)?> infixFunction,
        IEnumerable<(TKind, TToken)> lexer)

The above might read a little dense so below is a brief explanation of each parameter in order:

• a user-defined state that is associated with the parser object during parsing
• the initial precedence (this is usually 0 if TPrecedence is an int)
• a precedence comparer
• an equality comparer that can compare two token kinds
• a token kind marking end of input (EOI)
• a function used to project an Exception when the EOI token is not the the last token of the tokens sequence
• a prefix function
• an infix function
• a sequence of token kind and token pairs (2-tuple) yielded by a lexer implementation

A prefix function receives a token kind, a token and a user-defined state as input and it must return a parsing function if the token kind has prefix parsing semantics. If the token kind is invalid as a prefix, then the token and user-defined state may be used for the purpose of providing details in a thrown exception (e.g., while TKind may be a simple enum type, TToken will usually be a rich object containing the position of the token in the source text among other data). The parsing function returned by the prefix function then receives the token and the parser as arguments and produces some result (TResult).

An infix function receives a token kind, a token and a user-defined state as input as arguments and optionally returns a precedence (left binding power) and parsing function pair. The parsing function then receives the token, the left result and the parser as arguments and produces some result (TResult).