Warpstone 3.0.0-preview04
dotnet add package Warpstone --version 3.0.0-preview04
NuGet\Install-Package Warpstone -Version 3.0.0-preview04
<PackageReference Include="Warpstone" Version="3.0.0-preview04" />
<PackageVersion Include="Warpstone" Version="3.0.0-preview04" />
<PackageReference Include="Warpstone" />
paket add Warpstone --version 3.0.0-preview04
#r "nuget: Warpstone, 3.0.0-preview04"
#:package Warpstone@3.0.0-preview04
#addin nuget:?package=Warpstone&version=3.0.0-preview04&prerelease
#tool nuget:?package=Warpstone&version=3.0.0-preview04&prerelease
| Package | Stable | Preview | Downloads |
|---|---|---|---|
| Warpstone | |||
| Warpstone.Sources |
<img src="https://raw.githubusercontent.com/CptWesley/Warpstone/main/logo_1024x1024.png" width="178" height="178">
Warpstone
Parser combinator forged deep within Ikit's forges in the Under-City from a shard of Morrslieb itself.
What is it?
Warpstone is a parser combinator library written in C# targetting .NET Standard 2.0, meaning that it can be used by any application running either .NET Framework >= 4.6.1, .NET Core >= 2.0 or Mono >= 5.4. The main focus of the library is to provide a powerful lightweight parser combinator framework for developers to create their own parsers with.
Why did you make it?
After following a course on compiler construction I was intrigued and wanted a way of parsing languages within code without requiring external tools to generate a parser for me first. During my quest I stumbled upon the concept of parser combinators and started looking for existing libraries for .NET. I soon stumbled upon Pidgin. After toying around with the library for a bit I felt dissatisfied with some of its syntax and I still felt like I didn't fully understand the concepts it was using behind the scenes. This led me to create my own parser combinator library, with syntax inspired by Pidgin.
Why the name? (Or: What are all those strange words in the description?!?!?)
Coming up with names is difficult, I wanted to get the project started and at the time I was consumed by the Warhammer Fantasy universe.
Where do the ideas come from?
Warpstone's implementation draws on the following work:
- Packrat Parsing: Simple, Powerful, Lazy, Linear Time (Bryan Ford, ICFP 2002): the original packrat paper. It shows how memoizing every rule result makes a backtracking recursive-descent parser run in linear time.
- Packrat Parsers Can Support Left Recursion (Alessandro Warth, James R. Douglass and Todd Millstein, PEPM 2008): the "seed growing" technique for left-recursive rules that Warpstone's
Growparser is based on. - Left-recursive PEG Grammars (Guido van Rossum, 2019): part of the blog series behind Python's pegen parser generator. Warpstone uses its approach of picking one "leader" rule per left-recursive cycle and growing only that rule. The leader selection itself is pegen's
compute_left_recursives. - Packrat Parsers Can Support Multiple Left-recursive Calls at the Same Position (Masaki Umeda and Atusi Maeda, Journal of Information Processing 29, 2021): handles several left-recursive calls at the same input position. Warpstone falls back to it for cycles that have no single leader.
How does it compare?
â supported, ðĄ partially supported, â not supported.
| Feature | Warpstone V1 | Warpstone V2 | Warpstone V3 | Pidgin | Parlot | ParsecSharp | Farkle |
|---|---|---|---|---|---|---|---|
| Left recursion | â | â | â | â | â | â | â |
| Packrat memoization | â | â | â | â | â | â | â<sup>1</sup> |
Backtracking choice (no Try needed) |
â | â | â | ðĄ<sup>2</sup> | â | â | â<sup>1</sup> |
| Lookahead (positive/negative) | â | â | â | â | â | â | â<sup>1</sup> |
| Deeply nested input | â | â | â | â | â | â | â |
| Cancellation | â | â | â | â | â | â | â |
| Step-wise execution | â | â | â | â | â | â | â |
| Regex parsers | â | â | â | â | â | â | â |
| Operator precedence helpers | â | â | â<sup>3</sup> | â | â | ðĄ<sup>4</sup> | â |
| Monadic bind (context-sensitive parsing) | â | â | ðĄ<sup>5</sup> | â | ðĄ<sup>6</sup> | â | â |
Non-char token input |
â | â | â | â | â | â | ðĄ<sup>7</sup> |
Streaming input (TextReader/Stream) |
â | â | â | â | â | â | â |
| Compiled / source-generated parsers | â | â | â | â | â | â | â |
| Source-only package (no assembly dependency) | â | â | â | â | â | â | â |
- Farkle is an LALR(1) parser generator, not a PEG/combinator library. It needs no memoization or backtracking and reports grammar conflicts when the grammar is built.
- A choice only backtracks over consumed input when the branch is wrapped in
Try. - Not needed: write expressions as left-recursive rules.
ChainLeft/ChainRightcombinators, no precedence table.- Via
Bind. Left recursion through the selected parser is not grown and fails with anInfiniteRecursionError; a selected parser that is not part of the grammar is prepared for parsing each time a new instance is returned. - Via
Switch. - Custom tokenizers, input is still text.
Third-party columns reflect each library's documentation and package API at the time of writing (Pidgin 3.5, Parlot 2.3, ParsecSharp 5.2, Farkle 7).
Performance
Every library parses the same MiniJava subset into the same AST (MiniJavaBenchmark). Inputs: small (619 chars), medium (7,286 chars) and large (73,241 chars). Lower is better.
Mean CPU time per parse:
| Library | Small | Medium | Large |
|---|---|---|---|
| Parlot (source-generated) | 8.1 Ξs | 92.7 Ξs | 1.00 ms |
| Parlot (runtime) | 10.4 Ξs | 124.3 Ξs | 1.37 ms |
| Farkle | 17.1 Ξs | 208.1 Ξs | 2.12 ms |
| Warpstone V3 | 24.7 Ξs | 297.1 Ξs | 2.86 ms |
| Warpstone V3 (left-recursive)<sup>7</sup> | 40.6 Ξs | 524.0 Ξs | 5.29 ms |
| Pidgin | 101.2 Ξs | 1.27 ms | 13.52 ms |
| Warpstone V1 | 487.5 Ξs | 6.21 ms | 60.29 ms |
| ParsecSharp | 549.1 Ξs | 6.84 ms | 67.45 ms |
| Warpstone V2 | 3.39 ms | 79.51 ms | 805.98 ms |
Memory allocated per parse:
| Library | Small | Medium | Large |
|---|---|---|---|
| Farkle | 6.5 KB | 65.0 KB | 650 KB |
| Parlot (source-generated) | 6.5 KB | 67.5 KB | 673 KB |
| Parlot (runtime) | 6.6 KB | 67.5 KB | 673 KB |
| Warpstone V3 | 14.7 KB | 93.9 KB | 866 KB |
| Warpstone V3 (left-recursive)<sup>7</sup> | 22.1 KB | 179.2 KB | 1,696 KB |
| Pidgin | 21.8 KB | 252.0 KB | 2,523 KB |
| Warpstone V1 | 1,578 KB | 19,116 KB | 191,131 KB |
| ParsecSharp | 1,956 KB | 24,179 KB | 242,814 KB |
| Warpstone V2 | 9,069 KB | 109,981 KB | 1,104,776 KB |
- Binary operators written as left-recursive rules instead of repetitions.
Measured with BenchmarkDotNet 0.16.0-preview.2 (InProcessEmitToolchain) on .NET 11.0, AMD Ryzen 9 7950X3D, Windows 11. Reproduce from src/ with dotnet run -c Release --project Warpstone.Benchmarks -- --filter "*MiniJavaBenchmark*" --inProcess.
Usage
Install the package. V3 is in preview, so include prereleases:
dotnet add package Warpstone --prerelease
Or install Warpstone.Sources instead, which compiles the library's source code into your project, so your build output has no Warpstone.dll dependency.
Example: a calculator
The program below parses and evaluates arithmetic such as (1 + 2) * 3. It's a complete console app: paste it into Program.cs and run it.
using System;
using Warpstone;
using Warpstone.Errors;
using static Warpstone.Parsers;
// Parse() returns the value and throws if the input is invalid.
Console.WriteLine(Calculator.Expression.Parse("1 + 2 * 3")); // 7
Console.WriteLine(Calculator.Expression.Parse("(1 + 2) * 3")); // 9
Console.WriteLine(Calculator.Expression.Parse("10 - 4 - 3")); // 3: '-' groups to the left
// TryParse() doesn't throw. The result holds either a value or the errors.
var result = Calculator.Expression.TryParse("1 + * 2");
if (result.Success)
{
Console.WriteLine(result.Value);
}
else
{
foreach (var error in result.Errors)
{
Console.WriteLine($"Error at {error.InputStartPosition}");
if (error is UnexpectedTokenError unexpected)
{
Console.WriteLine($"Expected {string.Join(" or ", unexpected.Expected)} but found {unexpected.Found}");
}
}
}
public static class Calculator
{
// A number is one or more digits. Regex() matches the text, Transform() converts it to an int.
// WithName() sets the name used in error messages instead of the regex pattern.
private static readonly IParser<int> Number
= Regex("[0-9]+").Transform(int.Parse).WithName("number");
// An atom is a number or a sum between parentheses.
// Sum is declared further down, so Lazy() postpones reading the field until parsing starts.
// The '!' tells the compiler the field will be set by then.
// Then() keeps only the right-hand result, ThenSkip() keeps only the left-hand result.
private static readonly IParser<int> Atom
= Or(
Number,
Char('(').Then(Lazy(() => Sum!)).ThenSkip(Char(')')));
// A term is atoms joined by '*' or '/'.
// The rule starts with itself (left recursion). Warpstone detects and supports this, so
// operators group to the left: 8 / 4 / 2 means (8 / 4) / 2.
// ThenAdd() keeps both results as a tuple, which Transform() unpacks into two arguments.
// Or() tries each alternative in order and returns the first that succeeds.
private static readonly IParser<int> Term
= Or(
Lazy(() => Term!).ThenSkip(Operator("*")).ThenAdd(Atom).Transform((left, right) => left * right),
Lazy(() => Term!).ThenSkip(Operator("/")).ThenAdd(Atom).Transform((left, right) => left / right),
Atom);
// A sum is terms joined by '+' or '-'. Because a sum is built from terms,
// '*' and '/' bind tighter than '+' and '-'.
private static readonly IParser<int> Sum
= Or(
Lazy(() => Sum!).ThenSkip(Operator("+")).ThenAdd(Term).Transform((left, right) => left + right),
Lazy(() => Sum!).ThenSkip(Operator("-")).ThenAdd(Term).Transform((left, right) => left - right),
Term);
// The entry point. ThenEnd() fails if any input is left over, so "1 + 2 abc" is rejected.
public static readonly IParser<int> Expression
= Sum.ThenEnd();
// An operator symbol with optional whitespace on both sides.
private static IParser<string> Operator(string symbol)
=> OptionalWhitespaces.Then(String(symbol)).ThenSkip(OptionalWhitespaces);
}
Output:
7
9
3
Error at Index 4 Line 1 Column 5
Expected number or '(' but found '*'
| Product | Versions Compatible and additional computed target framework versions. |
|---|---|
| .NET | net5.0 is compatible. net5.0-windows was computed. net6.0 is compatible. 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 is compatible. 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 is compatible. 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. net9.0 is compatible. net9.0-android was computed. net9.0-browser was computed. net9.0-ios was computed. net9.0-maccatalyst was computed. net9.0-macos was computed. net9.0-tvos was computed. net9.0-windows was computed. net10.0 is compatible. net10.0-android was computed. net10.0-browser was computed. net10.0-ios was computed. net10.0-maccatalyst was computed. net10.0-macos was computed. net10.0-tvos was computed. net10.0-windows was computed. net11.0 is compatible. |
| .NET Core | netcoreapp2.0 was computed. netcoreapp2.1 was computed. netcoreapp2.2 was computed. netcoreapp3.0 is compatible. netcoreapp3.1 was computed. |
| .NET Standard | netstandard2.0 is compatible. netstandard2.1 was computed. |
| .NET Framework | net461 was computed. net462 was computed. net463 was computed. net47 was computed. net471 was computed. net472 was computed. net48 was computed. net481 was computed. |
| MonoAndroid | monoandroid was computed. |
| MonoMac | monomac was computed. |
| MonoTouch | monotouch was computed. |
| Tizen | tizen40 was computed. tizen60 was computed. |
| Xamarin.iOS | xamarinios was computed. |
| Xamarin.Mac | xamarinmac was computed. |
| Xamarin.TVOS | xamarintvos was computed. |
| Xamarin.WatchOS | xamarinwatchos was computed. |
-
.NETCoreApp 3.0
- No dependencies.
-
.NETStandard 2.0
- No dependencies.
-
net10.0
- No dependencies.
-
net11.0
- No dependencies.
-
net5.0
- No dependencies.
-
net6.0
- No dependencies.
-
net7.0
- No dependencies.
-
net8.0
- No dependencies.
-
net9.0
- No dependencies.
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.
| Version | Downloads | Last Updated |
|---|---|---|
| 3.0.0-preview04 | 0 | 11/20/2026 |
| 3.0.0-preview03 | 473 | 6/11/2025 |
| 3.0.0-preview02 | 379 | 6/11/2025 |
| 3.0.0-preview01 | 412 | 6/10/2025 |
| 2.0.0-preview3 | 256 | 3/13/2025 |
| 2.0.0-preview2 | 3,473 | 1/9/2025 |
| 2.0.0-preview1 | 258 | 11/30/2023 |
| 1.1.0-preview5 | 384 | 8/2/2022 |
| 1.1.0-preview4 | 477 | 7/11/2021 |
| 1.1.0-preview3 | 487 | 7/11/2021 |
| 1.1.0-preview2 | 487 | 7/9/2021 |
| 1.1.0-preview1 | 437 | 7/9/2021 |
| 1.0.8.2-preview2 | 467 | 6/29/2021 |
| 1.0.8.2-alpha | 510 | 6/18/2021 |
| 1.0.8.1 | 776 | 5/25/2021 |
| 1.0.8 | 564 | 5/25/2021 |
| 1.0.7.1 | 732 | 11/26/2020 |
| 1.0.7 | 640 | 11/24/2020 |
| 1.0.6.1 | 728 | 10/17/2020 |
| 1.0.6 | 627 | 10/17/2020 |
### v3.0.0
- Significantly improved performance.
- Reworked API interface.
### v2.0.0
- Reworked library from scratch.
- Changed to Packrat parsing.
- Added support for left-recursion.