Pidgin

Class ExpressionParser

Contains tools for parsing expression languages with associative infix operators.

To get started, write a Parser<TToken, T>, to parse an atomic term in your expression language, and use the Operator class to create a table of operator parsers in order of their precedence. Then call one of the Build<TToken, T>(Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>) overloads to compile the table of operators into a Parser<TToken, T>.

Inheritance
Declaration
public static class ExpressionParser : Object
Remarks

Since it's common for an expression language to have a recursive structure, overloads of Build<TToken, T>(Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>) are provided which take a function. The function's argument will be the completed parser for a whole expression. This allows you to write recursive parsers.

Examples

Here is an example of a parser for mathematical expressions. The parser computes the result of the expression (although in practice your parser would probably return an AST).

var operators = new[]
{
    Operator.Prefix(Char('-').ThenReturn<Func<int, int>>(x => -x)),
    Operator.InfixL(Char('*').ThenReturn<Func<int, int, int>>((x, y) => x * y)),
    Operator.InfixL(Char('+').ThenReturn<Func<int, int, int>>((x, y) => x + y))
};
var parser = ExpressionParser.Build(
    expr => Num.Or(expr.Between(Char('('), Char(')'))),
    operators
);
Console.WriteLine(parser.ParseOrThrow("-3*(370+9)*37"));
// Output:
// -42069

Methods

Build<TToken, T>(Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>)

Builds a parser for expressions built from the operators in operatorTable. operatorTable is a sequence of operators in precedence order: the operators in the first row have the highest precedence and operators in later rows have lower precedence.

Declaration
public static Parser<TToken, T> Build<TToken, T>(Parser<TToken, T> term, IEnumerable<OperatorTableRow<TToken, T>> operatorTable)
Parameters
Type Name Description

Parser<TToken, T>

term

A parser for a single term in an expression language.

IEnumerable<OperatorTableRow<TToken, T>>

operatorTable

A table of operators.
Returns
Type Description

Parser<TToken, T>

A parser for expressions built from the operators in operatorTable.
Type Parameters
Name Description

TToken

The token type.

T

The return type of the parser.

Build<TToken, T>(Parser<TToken, T>, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>)

Builds a parser for expressions built from the operators in operatorTable. operatorTable is a sequence of operators in precedence order: the operators in the first row have the highest precedence and operators in later rows have lower precedence.

Declaration
public static Parser<TToken, T> Build<TToken, T>(Parser<TToken, T> term, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>> operatorTable)
Parameters
Type Name Description

Parser<TToken, T>

term

A parser for a single term in an expression language.

IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>

operatorTable

A table of operators.
Returns
Type Description

Parser<TToken, T>

A parser for expressions built from the operators in operatorTable.
Type Parameters
Name Description

TToken

The token type.

T

The return type of the parser.

Build<TToken, T>(Parser<TToken, T>, Func<Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>>)

Builds a parser for expressions built from the operators in operatorTableFactory's result. The operator table is a sequence of operators in precedence order: the operators in the first row have the highest precedence and operators in later rows have lower precedence.

This overload is useful for recursive expressions (for example, languages with parenthesised subexpressions). operatorTableFactory's argument will be a parser which parses a full subexpression.

Declaration
public static Parser<TToken, T> Build<TToken, T>(Parser<TToken, T> term, Func<Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>> operatorTableFactory)
Parameters
Type Name Description

Parser<TToken, T>

term

A parser for a single term in an expression language.

Func<Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>>

operatorTableFactory

A function which produces a table of operators.
Returns
Type Description

Parser<TToken, T>

A parser for expressions built from the operators in the operator table.
Type Parameters
Name Description

TToken

The token type.

T

The return type of the parser.

Build<TToken, T>(Parser<TToken, T>, Func<Parser<TToken, T>, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>>)

Builds a parser for expressions built from the operators in operatorTableFactory's result. The operator table is a sequence of operators in precedence order: the operators in the first row have the highest precedence and operators in later rows have lower precedence.

This overload is useful for recursive expressions (for example, languages with parenthesised subexpressions). operatorTableFactory's argument will be a parser which parses a full subexpression.

Declaration
public static Parser<TToken, T> Build<TToken, T>(Parser<TToken, T> term, Func<Parser<TToken, T>, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>> operatorTableFactory)
Parameters
Type Name Description

Parser<TToken, T>

term

A parser for a single term in an expression language.

Func<Parser<TToken, T>, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>>

operatorTableFactory

A function which produces a table of operators.
Returns
Type Description

Parser<TToken, T>

A parser for expressions built from the operators in the operator table.
Type Parameters
Name Description

TToken

The token type.

T

The return type of the parser.

Build<TToken, T>(Func<Parser<TToken, T>, Parser<TToken, T>>, IEnumerable<OperatorTableRow<TToken, T>>)

Builds a parser for expressions built from the operators in operatorTable. The operator table is a sequence of operators in precedence order: the operators in the first row have the highest precedence and operators in later rows have lower precedence.

This overload is useful for recursive expressions (for example, languages with parenthesised subexpressions). termFactory's argument will be a parser which parses a full subexpression.

Declaration
public static Parser<TToken, T> Build<TToken, T>(Func<Parser<TToken, T>, Parser<TToken, T>> termFactory, IEnumerable<OperatorTableRow<TToken, T>> operatorTable)
Parameters
Type Name Description

Func<Parser<TToken, T>, Parser<TToken, T>>

termFactory

A function which produces a parser for a single term.

IEnumerable<OperatorTableRow<TToken, T>>

operatorTable

A table of operators.
Returns
Type Description

Parser<TToken, T>

A parser for expressions built from the operators in operatorTable.
Type Parameters
Name Description

TToken

The token type.

T

The return type of the parser.

Build<TToken, T>(Func<Parser<TToken, T>, Parser<TToken, T>>, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>)

Builds a parser for expressions built from the operators in operatorTable. The operator table is a sequence of operators in precedence order: the operators in the first row have the highest precedence and operators in later rows have lower precedence.

This overload is useful for recursive expressions (for example, languages with parenthesised subexpressions). termFactory's argument will be a parser which parses a full subexpression.

Declaration
public static Parser<TToken, T> Build<TToken, T>(Func<Parser<TToken, T>, Parser<TToken, T>> termFactory, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>> operatorTable)
Parameters
Type Name Description

Func<Parser<TToken, T>, Parser<TToken, T>>

termFactory

A function which produces a parser for a single term.

IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>

operatorTable

A table of operators.
Returns
Type Description

Parser<TToken, T>

A parser for expressions built from the operators in operatorTable.
Type Parameters
Name Description

TToken

The token type.

T

The return type of the parser.

Build<TToken, T>(Func<Parser<TToken, T>, (Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>)>)

Builds a parser for expressions built from the operators in termAndOperatorTableFactory's second result. The operator table is a sequence of operators in precedence order: the operators in the first row have the highest precedence and operators in later rows have lower precedence.

This overload is useful for recursive expressions (for example, languages with parenthesised subexpressions). termAndOperatorTableFactory's argument will be a parser which parses a full subexpression.

Declaration
public static Parser<TToken, T> Build<TToken, T>(Func<Parser<TToken, T>, (Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>)> termAndOperatorTableFactory)
Parameters
Type Name Description

Func<Parser<TToken, T>, (, )<Parser<TToken, T>, IEnumerable<OperatorTableRow<TToken, T>>>>

termAndOperatorTableFactory

A function which produces a parser for a single term and a table of operators.
Returns
Type Description

Parser<TToken, T>

A parser for expressions built from the operators in the operator table.
Type Parameters
Name Description

TToken

The token type.

T

The return type of the parser.

Build<TToken, T>(Func<Parser<TToken, T>, (Parser<TToken, T>, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>)>)

Builds a parser for expressions built from the operators in termAndOperatorTableFactory's second result. The operator table is a sequence of operators in precedence order: the operators in the first row have the highest precedence and operators in later rows have lower precedence.

This overload is useful for recursive expressions (for example, languages with parenthesised subexpressions). termAndOperatorTableFactory's argument will be a parser which parses a full subexpression.

Declaration
public static Parser<TToken, T> Build<TToken, T>(Func<Parser<TToken, T>, (Parser<TToken, T>, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>)> termAndOperatorTableFactory)
Parameters
Type Name Description

Func<Parser<TToken, T>, (, )<Parser<TToken, T>, IEnumerable<IEnumerable<OperatorTableRow<TToken, T>>>>>

termAndOperatorTableFactory

A function which produces a parser for a single term and a table of operators.
Returns
Type Description

Parser<TToken, T>

A parser for expressions built from the operators in the operator table.
Type Parameters
Name Description

TToken

The token type.

T

The return type of the parser.
In This Article