Pidgin 3.3.0
dotnet add package Pidgin --version 3.3.0
NuGet\Install-Package Pidgin -Version 3.3.0
<PackageReference Include="Pidgin" Version="3.3.0" />
paket add Pidgin --version 3.3.0
#r "nuget: Pidgin, 3.3.0"
// Install Pidgin as a Cake Addin #addin nuget:?package=Pidgin&version=3.3.0 // Install Pidgin as a Cake Tool #tool nuget:?package=Pidgin&version=3.3.0
Pidgin
A lightweight, fast, and flexible parsing library for C#.
Installing
Pidgin is available on Nuget. API docs are hosted on my website.
Tutorial
There's a tutorial on using Pidgin to parse a subset of Prolog on my website.
Getting started
Pidgin is a parser combinator library, a lightweight, high-level, declarative tool for constructing parsers. Parsers written with parser combinators look like a high-level specification of a language's grammar, but they're expressed within a general-purpose programming language and require no special tools to produce executable code. Parser combinators are more powerful than regular expressions - they can parse a larger class of languages - but simpler and easier to use than parser generators like ANTLR.
Pidgin's core type, Parser<TToken, T>
, represents a procedure which consumes an input stream of TToken
s, and may either fail with a parsing error or produce a T
as output. You can think of it as:
delegate T? Parser<TToken, T>(IEnumerator<TToken> input);
In order to start building parsers we need to import two classes which contain factory methods: Parser
and Parser<TToken>
.
using Pidgin;
using static Pidgin.Parser;
using static Pidgin.Parser<char>; // we'll be parsing strings - sequences of characters. For other applications (eg parsing binary file formats) TToken may be some other type (eg byte).
Primitive parsers
Now we can create some simple parsers. Any
represents a parser which consumes a single character and returns that character.
Assert.AreEqual('a', Any.ParseOrThrow("a"));
Assert.AreEqual('b', Any.ParseOrThrow("b"));
Char
, an alias for Token
, consumes a particular character and returns that character. If it encounters some other character then it fails.
Parser<char, char> parser = Char('a');
Assert.AreEqual('a', parser.ParseOrThrow("a"));
Assert.Throws<ParseException>(() => parser.ParseOrThrow("b"));
Digit
parses and returns a single digit character.
Assert.AreEqual('3', Digit.ParseOrThrow("3"));
Assert.Throws<ParseException>(() => Digit.ParseOrThrow("a"));
String
parses and returns a particular string. If you give it input other than the string it was expecting it fails.
Parser<char, string> parser = String("foo");
Assert.AreEqual("foo", parser.ParseOrThrow("foo"));
Assert.Throws<ParseException>(() => parser.ParseOrThrow("bar"));
Return
(and its synonym FromResult
) never consumes any input, and just returns the given value. Likewise, Fail
always fails without consuming any input.
Parser<char, int> parser = Return(3);
Assert.AreEqual(3, parser.ParseOrThrow("foo"));
Parser<char, int> parser2 = Fail<int>();
Assert.Throws<ParseException>(() => parser2.ParseOrThrow("bar"));
Sequencing parsers
The power of parser combinators is that you can build big parsers out of little ones. The simplest way to do this is using Then
, which builds a new parser representing two parsers applied sequentially (discarding the result of the first).
Parser<char, string> parser1 = String("foo");
Parser<char, string> parser2 = String("bar");
Parser<char, string> sequencedParser = parser1.Then(parser2);
Assert.AreEqual("bar", sequencedParser.ParseOrThrow("foobar")); // "foo" got thrown away
Assert.Throws<ParseException>(() => sequencedParser.ParseOrThrow("food"));
Before
throws away the second result, not the first.
Parser<char, string> parser1 = String("foo");
Parser<char, string> parser2 = String("bar");
Parser<char, string> sequencedParser = parser1.Before(parser2);
Assert.AreEqual("foo", sequencedParser.ParseOrThrow("foobar")); // "bar" got thrown away
Assert.Throws<ParseException>(() => sequencedParser.ParseOrThrow("food"));
Map
does a similar job, except it keeps both results and applies a transformation function to them. This is especially useful when you want your parser to return a custom data structure. (Map
has overloads which operate on between one and eight parsers; the one-parser version also has a postfix synonym Select
.)
Parser<char, string> parser1 = String("foo");
Parser<char, string> parser2 = String("bar");
Parser<char, string> sequencedParser = Map((foo, bar) => bar + foo, parser1, parser2);
Assert.AreEqual("barfoo", sequencedParser.ParseOrThrow("foobar"));
Assert.Throws<ParseException>(() => sequencedParser.ParseOrThrow("food"));
Bind
uses the result of a parser to choose the next parser. This enables parsing of context-sensitive languages. For example, here's a parser which parses any character repeated twice.
/// parse any character, then parse a character matching the first character
Parser<char, char> parser = Any.Bind(c => Char(c));
Assert.AreEqual('a', parser.ParseOrThrow("aa"));
Assert.AreEqual('b', parser.ParseOrThrow("bb"));
Assert.Throws<ParseException>(() => parser.ParseOrThrow("ab"));
Pidgin parsers support LINQ query syntax. It may be easier to see what the above example does when it's written out using LINQ:
Parser<char, char> parser =
from c in Any
from c2 in Char(c)
select c2;
Parsers written like this look like a simple imperative script. "Run the Any
parser and name its result c
, then run Char(c)
and name its result c2
, then return c2
."
Choosing from alternatives
Or
represents a parser which can parse one of two alternatives. It runs the left parser first, and if it fails it tries the right parser.
Parser<char, string> parser = String("foo").Or(String("bar"));
Assert.AreEqual("foo", parser.ParseOrThrow("foo"));
Assert.AreEqual("bar", parser.ParseOrThrow("bar"));
Assert.Throws<ParseException>(() => parser.ParseOrThrow("baz"));
OneOf
is equivalent to Or
, except it takes a variable number of arguments. Here's a parser which is equivalent to the one using Or
above:
Parser<char, string> parser = OneOf(String("foo"), String("bar"));
If one of Or
or OneOf
's component parsers fails after consuming input, the whole parser will fail.
Parser<char, string> parser = String("food").Or(String("foul"));
Assert.Throws<ParseException>(() => parser.ParseOrThrow("foul")); // why didn't it choose the second option?
What happened here? When a parser successfully parses a character from the input stream, it advances the input stream to the next character. Or
only chooses the next alternative if the given parser fails without consuming any input; Pidgin does not perform any lookahead or backtracking by default. Backtracking is enabled using the Try
function.
// apply Try to the first option, so we can return to the beginning if it fails
Parser<char, string> parser = Try(String("food")).Or(String("foul"));
Assert.AreEqual("foul", parser.ParseOrThrow("foul"));
Recursive grammars
Almost any non-trivial programming language, markup language, or data interchange language will feature some sort of recursive structure. C# doesn't support recursive values: a recursive referral to a variable currently being initialised will return null
. So we need some sort of deferred execution of recursive parsers, which Pidgin enables using the Rec
combinator. Here's a simple parser which parses arbitrarily nested parentheses with a single digit inside them.
Parser<char, char> expr = null;
Parser<char, char> parenthesised = Char('(')
.Then(Rec(() => expr)) // using a lambda to (mutually) recursively refer to expr
.Before(Char(')'));
expr = Digit.Or(parenthesised);
Assert.AreEqual('1', expr.ParseOrThrow("1"));
Assert.AreEqual('1', expr.ParseOrThrow("(1)"));
Assert.AreEqual('1', expr.ParseOrThrow("(((1)))"));
However, Pidgin does not support left recursion. A parser must consume some input before making a recursive call. The following example will produce a stack overflow because a recursive call to arithmetic
occurs before any input can be consumed by Digit
or Char('+')
:
Parser<char, int> arithmetic = null;
Parser<char, int> addExpr = Map(
(x, _, y) => x + y,
Rec(() => arithmetic),
Char('+'),
Rec(() => arithmetic)
);
arithmetic = addExpr.Or(Digit.Select(d => (int)char.GetNumericValue(d)));
arithmetic.Parse("2+2"); // stack overflow!
Derived combinators
Another powerful element of this programming model is that you can write your own functions to compose parsers. Pidgin contains a large number of higher-level combinators, built from the primitives outlined above. For example, Between
runs a parser surrounded by two others, keeping only the result of the central parser.
Parser<TToken, T> InBraces<TToken, T, U, V>(this Parser<TToken, T> parser, Parser<TToken, U> before, Parser<TToken, V> after)
=> before.Then(parser).Before(after);
Parsing expressions
Pidgin features operator-precedence parsing tools, for parsing expression grammars with associative infix operators. The ExpressionParser
class builds a parser from a parser to parse a single expression term and a table of operators with rules to combine expressions.
More examples
Examples, such as parsing (a subset of) JSON and XML into document structures, can be found in the Pidgin.Examples
project.
Tips
A note on variance
Why doesn't this code compile?
class Base {}
class Derived : Base {}
Parser<char, Base> p = Return(new Derived()); // Cannot implicitly convert type 'Pidgin.Parser<char, Derived>' to 'Pidgin.Parser<char, Base>'
This would be possible if Parser
were defined as a covariant in its second type parameter (ie interface Parser<TToken, out T>
). For the purposes of efficiency, Pidgin parsers return a struct. Structs and classes aren't allowed to have variant type parameters (only interfaces and delegates); since a Pidgin parser's return value isn't variant, nor can the parser itself.
In my experience, this crops up most frequently when returning a node of a syntax tree from a parser using Select
. The least verbose way of rectifying this is to explicitly set Select
's type parameter to the supertype:
Parser<char, Base> p = Any.Select<Base>(() => new Derived());
Speed tips
Pidgin is designed to be fast and produce a minimum of garbage. A carefully written Pidgin parser can be competitive with a hand-written recursive descent parser. If you find that parsing is a bottleneck in your code, here are some tips for minimising the runtime of your parser.
- Avoid LINQ query syntax. Query comprehensions are defined by translation into core C# using
SelectMany
, however, for long queries the translation can allocate a large number of anonymous objects. This generates a lot of garbage; while those objects often won't survive the nursery it's still preferable to avoid allocating them! - Avoid backtracking where possible. If consuming a streaming input like a
TextReader
or anIEnumerable
,Try
buffers its input to enable backtracking, which can be expensive. - Use specialised parsers where possible: the provided
Skip*
parsers can be used when the result of parsing is not required. They typically run faster than their counterparts because they don't need to save the values generated. - Build your parser statically where possible. Pidgin is designed under the assumption that parser scripts are executed more than they are written; building a parser can be an expensive operation.
- Avoid
Bind
andSelectMany
where possible. Many practical grammars are context-free and can therefore be written purely withMap
. If you do have a context-sensitive grammar, it may make sense to parse it in a context-free fashion and then run a semantic checker over the result.
Comparison to other tools
Pidgin vs Sprache
Sprache is another parser combinator library for C# and served as one of the sources of inspiration for Pidgin. Pidgin's API is somewhat similar to that of Sprache, but Pidgin aims to improve on Sprache in a number of ways:
- Sprache's input must be a string. This makes it inappropriate for parsing binary protocols or tokenised inputs. Pidgin supports input tokens of arbitrary type.
- Sprache's input must be a string - an in-memory array of characters. Pidgin supports streaming inputs.
- Sprache automatically backtracks on failure. Pidgin uses a special combinator to enable backtracking because backtracking can be a costly operation.
- Pidgin comes bundled with operator-precedence tools for parsing expression languages with associative infix operators.
- Pidgin is faster and allocates less memory than Sprache.
- Pidgin has more documentation coverage than Sprache.
Pidgin vs FParsec
FParsec is a parser combinator library for F# based on Parsec.
- FParsec is an F# library and consuming it from C# can be awkward. Pidgin is implemented in pure C#, and is designed for C# consumers.
- FParsec only supports character input streams.
- FParsec supports stateful parsing - it has an extra type parameter for an arbitrary user-defined state - which can make it easier to parse context-sensitive grammars.
- FParsec is faster than Pidgin (though we're catching up!)
Benchmarks
This is how Pidgin compares to other tools in terms of performance. The benches can be found in the Pidgin.Bench
project.
BenchmarkDotNet=v0.11.5, OS=Windows 10.0.14393.3384 (1607/AnniversaryUpdate/Redstone1)
Intel Core i5-4460 CPU 3.20GHz (Haswell), 1 CPU, 4 logical and 4 physical cores
Frequency=3125000 Hz, Resolution=320.0000 ns, Timer=TSC
.NET Core SDK=3.1.100
[Host] : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT
DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT
ExpressionBench
Method | Mean | Error | StdDev | Ratio | RatioSD | Gen 0 | Gen 1 | Gen 2 | Allocated |
---|---|---|---|---|---|---|---|---|---|
LongInfixL_Pidgin | 625,148.8 ns | 3,015.040 ns | 2,672.7541 ns | 2.25 | 0.01 | - | - | - | 128 B |
LongInfixR_Pidgin | 625,530.1 ns | 4,104.833 ns | 3,839.6633 ns | 2.25 | 0.02 | - | - | - | 128 B |
LongInfixL_FParsec | 278,035.1 ns | 1,231.538 ns | 1,151.9816 ns | 1.00 | 0.00 | - | - | - | 200 B |
LongInfixR_FParsec | 326,047.3 ns | 931.485 ns | 871.3119 ns | 1.17 | 0.01 | - | - | - | 200 B |
ShortInfixL_Pidgin | 1,506.5 ns | 5.515 ns | 5.1590 ns | 2.67 | 0.01 | 0.0401 | - | - | 128 B |
ShortInfixR_Pidgin | 1,636.6 ns | 6.882 ns | 5.7467 ns | 2.90 | 0.02 | 0.0401 | - | - | 128 B |
ShortInfixL_FParsec | 564.1 ns | 1.894 ns | 1.6788 ns | 1.00 | 0.00 | 0.0629 | - | - | 200 B |
ShortInfixR_FParsec | 567.7 ns | 1.200 ns | 0.9373 ns | 1.01 | 0.00 | 0.0629 | - | - | 200 B |
JsonBench
Method | Mean | Error | StdDev | Ratio | RatioSD | Gen 0 | Gen 1 | Gen 2 | Allocated |
---|---|---|---|---|---|---|---|---|---|
BigJson_Pidgin | 684.6 us | 2.888 us | 2.701 us | 1.00 | 0.00 | 33.2031 | - | - | 101.7 KB |
BigJson_Sprache | 3,597.5 us | 17.595 us | 16.458 us | 5.25 | 0.03 | 1726.5625 | - | - | 5291.81 KB |
BigJson_Superpower | 2,884.4 us | 6.504 us | 5.766 us | 4.21 | 0.02 | 296.8750 | - | - | 913.43 KB |
BigJson_FParsec | 750.1 us | 3.516 us | 3.289 us | 1.10 | 0.01 | 111.3281 | - | - | 343.43 KB |
LongJson_Pidgin | 517.5 us | 2.418 us | 2.261 us | 1.00 | 0.00 | 33.2031 | - | - | 104.25 KB |
LongJson_Sprache | 2,858.5 us | 10.491 us | 9.300 us | 5.53 | 0.03 | 1390.6250 | - | - | 4269.33 KB |
LongJson_Superpower | 2,348.1 us | 14.194 us | 13.277 us | 4.54 | 0.03 | 230.4688 | - | - | 706.79 KB |
LongJson_FParsec | 642.5 us | 2.708 us | 2.533 us | 1.24 | 0.01 | 125.0000 | - | - | 384.3 KB |
DeepJson_Pidgin | 399.3 us | 1.784 us | 1.582 us | 1.00 | 0.00 | 26.3672 | - | - | 82.24 KB |
DeepJson_Sprache | 2,983.0 us | 42.512 us | 39.765 us | 7.46 | 0.09 | 761.7188 | 191.4063 | - | 2922.46 KB |
DeepJson_FParsec | 701.8 us | 1.665 us | 1.557 us | 1.76 | 0.01 | 112.3047 | - | - | 344.43 KB |
WideJson_Pidgin | 427.8 us | 1.619 us | 1.515 us | 1.00 | 0.00 | 15.6250 | - | - | 48.42 KB |
WideJson_Sprache | 1,704.2 us | 9.246 us | 8.196 us | 3.98 | 0.02 | 900.3906 | - | - | 2763.22 KB |
WideJson_Superpower | 1,494.6 us | 9.581 us | 8.962 us | 3.49 | 0.02 | 148.4375 | - | - | 459.74 KB |
WideJson_FParsec | 379.5 us | 1.597 us | 1.494 us | 0.89 | 0.00 | 41.9922 | - | - | 129.02 KB |
Product | Versions Compatible and additional computed target framework versions. |
---|---|
.NET | net5.0 is compatible. net5.0-windows was computed. net6.0 was computed. net6.0-android was computed. net6.0-ios was computed. net6.0-maccatalyst was computed. net6.0-macos was computed. net6.0-tvos was computed. net6.0-windows was computed. net7.0 was computed. net7.0-android was computed. net7.0-ios was computed. net7.0-maccatalyst was computed. net7.0-macos was computed. net7.0-tvos was computed. net7.0-windows was computed. net8.0 was computed. net8.0-android was computed. net8.0-browser was computed. net8.0-ios was computed. net8.0-maccatalyst was computed. net8.0-macos was computed. net8.0-tvos was computed. net8.0-windows was computed. |
-
net5.0
- No dependencies.
NuGet packages (16)
Showing the top 5 NuGet packages that depend on Pidgin:
Package | Downloads |
---|---|
ActualChat.Api
Package Description |
|
Blazor.ExtraDry.Core
Extensions to Blazor and DRY libraries to create Blazor client applications with a lower-code footprint. Use this Core library for server side and shared library common elements. |
|
ZingzeuData.Shared
ZingzeuData.Shared |
|
War3Net.CodeAnalysis
War3Net.CodeAnalysis contains additional parsers for the Pidgin parsing library. |
|
ODataQuery
Enables server-side filtering, sorting and pagination of any IQueryable<T> using OData syntax and without needing an EDM model. |
GitHub repositories (7)
Showing the top 5 popular GitHub repositories that depend on Pidgin:
Repository | Stars |
---|---|
unitystation/unitystation
The original unitystation
|
|
space-wizards/RobustToolbox
Robust multiplayer game engine, used by Space Station 14
|
|
Jcparkyn/nodexr
Graphical regular expression editor
|
|
sebastienros/parlot
Fast and lightweight parser creation tools
|
|
SnowflakePowered/snowflake
:snowflake: :video_game: Emulator Frontend and SDK
|
Version | Downloads | Last updated |
---|---|---|
3.3.0 | 16,689 | 7/31/2024 |
3.2.3 | 87,702 | 2/26/2024 |
3.2.2 | 745,505 | 7/13/2023 |
3.2.1 | 76,143 | 12/28/2022 |
3.1.0 | 41,509 | 4/13/2022 |
3.0.0 | 86,580 | 11/3/2021 |
2.5.0 | 1,872,119 | 6/23/2020 |
2.4.0 | 18,060 | 6/2/2020 |
2.3.0 | 39,994 | 2/28/2020 |
2.2.0 | 61,878 | 9/26/2019 |
2.1.0 | 44,044 | 2/15/2019 |
2.0.1 | 793 | 2/8/2019 |
2.0.0 | 1,257 | 1/22/2019 |
1.5.0 | 32,078 | 4/27/2018 |
1.4.1 | 1,081 | 2/19/2018 |
1.4.0 | 1,136 | 12/22/2017 |
1.3.0 | 13,848 | 10/17/2017 |
1.2.1 | 946 | 9/8/2017 |
1.2.0 | 994 | 8/1/2017 |
1.1.0 | 995 | 7/15/2017 |
1.0.5 | 973 | 5/24/2017 |
1.0.4 | 994 | 5/23/2017 |
1.0.3 | 1,007 | 4/11/2017 |