Pliant 0.11.0
dotnet add package Pliant --version 0.11.0
NuGet\Install-Package Pliant -Version 0.11.0
<PackageReference Include="Pliant" Version="0.11.0" />
paket add Pliant --version 0.11.0
#r "nuget: Pliant, 0.11.0"
// Install Pliant as a Cake Addin #addin nuget:?package=Pliant&version=0.11.0 // Install Pliant as a Cake Tool #tool nuget:?package=Pliant&version=0.11.0
Pliant
Implementation of a modified Earley parser in C# inspired by the Marpa Parser project.
Build Status
Gitter Chat
Description
Pliant is a table driven parser that implements the Earley algorithm. Two optimizations are added to handle issues with the original Earley implementation:
- Optimization from Joop Leo to efficiently handle right recursions.
- Bug fix from Aycock and Horspool to handle nullable predictions
Using the Code
Getting Started
Add a reference to the Pliant libarary using NuGet
PM> Install-Package Pliant
Creating Grammars
Using the Grammar Expression classes
using Pliant.Builders;
using Pliant.Builders.Expressions;
using Pliant.Grammars;
using Pliant.Automata;
public static int Main(string[] args)
{
var digits = CreateDigitLexerRule();
var whitespace = CreateWhitespaceLexerRule();
ProductionExpression
Calculator = "Calculator",
Factor = "Factor",
Term = "Term",
Expression = "Expression",
Number = "Number";
Calculator.Rule
= Expression ;
Expression.Rule
= Expression + '+' + Term
| Term ;
Term.Rule
= Term + '*' + Factor
| Factor ;
Factor.Rule
= Number ;
Number.Rule
= digits;
var grammar = new GrammarExpression(
Calculator,
new []{ Calculator, Factor, Term, Expression, Number },
new []{ new LexerRuleModel(whitespace) })
.ToGrammar();
// TODO: Use the grammar in a parse.
}
private static BaseLexerRule CreateDigitLexerRule()
{
var startState = new DfaState();
var finalState = new DfaState(true);
var digitTransition = new DfaTransition(new DigitTerminal(), finalState);
startState.AddTransition(digitTransition);
finalState.AddTransition(digitTransition);
return new DfaLexerRule(startState, "[\\d]+");
}
private static ILexerRule CreateWhitespaceLexerRule()
{
var whitespaceTerminal = new WhitespaceTerminal();
var startState = new DfaState();
var finalState = new DfaState(true);
var whitespaceTransition = new DfaTransition(whitespaceTerminal, finalState);
startState.AddTransition(whitespaceTransition);
finalState.AddTransition(whitespaceTransition);
return new DfaLexerRule(startState, new TokenType("[\\s]+"));
}
Using Pliant Definition Language (PDL)
calculator.pdl
Calculator
= Expression;
Expression
= Expression '+' Term
| Term;
Term
= Term '*' Factor
| Factor;
Factor
= Number ;
Number
= Digits;
Digits ~ /[0-9]+/ ;
Whitespace ~ /[\s]+/ ;
:start = Calculator;
:ignore = Whitespace;
Program.cs
using Pliant.Languages.Pdl;
using Pliant.Runtime;
using System;
using System.IO;
namespace PdlExample
{
public static int Main (string[] args)
{
// load the grammar definition file (make sure to copy it to output directory if debugging)
var path = Path.Combine(Directory.GetCurrentDirectory(), "calculator.pdl");
var content = File.ReadAllText(path);
// parse the grammar definition file
var pdlParser = new PdlParser();
var definition = pdlParser.Parse(content);
// create the grammar, parser and scanner for our calculator language
var grammar = new PdlGrammarGenerator().Generate(definition);
var parser = new ParseEngine(grammar);
var calculatorInput = "5+30 * 2 + 1";
var scanner = new ParseRunner(parser, calculatorInput);
// run the scanner
if(!scanner.RunToEnd())
{
Console.WriteLine($"error parsing at line {scanner.Line + 1} column {scanner.Column}");
}
// parse the calculator input
var rootNode = parser.GetParseForestRootNode();
// TODO: use the parse node in the calculator interpreter
}
}
Recognizing and Parse Trees
Using ParseEngine, ParseRunner and Grammars to Recognize Input
Using the calculator grammar from above, we can parse input by constructing a parse engine and parse runner instance.
var input = "1 + 1 * 3 + 2";
// use the calculator grammar from above
var parseEngine = new ParseEngine(grammar);
// use the parse runner to query the parse engine for state
// and use that state to select lexer rules.
var parseRunner = new ParseRunner(parseEngine, input);
// when a parse is recognized, the parse engine is allowed to move
// forward and continues to accept symbols.
var recognized = false;
var errorPosition = 0;
while(!parseRunner.EndOfStream())
{
recognized = parseRunner.Read();
if(!recognized)
{
errorPosition = parseRunner.Position;
break;
}
}
// For a parse to be accepted, all parse rules are completed and a trace
// has been made back to the parse root.
// A parse must be recognized in order for acceptance to have meaning.
var accepted = false;
if(recognized)
{
accepted = parseRunner.ParseEngine.IsAccepted();
if(!accepted)
errorPosition = parseRunner.Position;
}
Console.WriteLine($"Recognized: {recognized}, Accepted: {accepted}");
if(!recognized || !accepted)
Console.Error.WriteLine($"Error at position {errorPosition}");
Using ParseEngine, ParseRunner, Forest API and Grammars to build a parse tree.
The process for creating a parse tree is the same as recognizing input. In fact, when running the ParseEngine, a Sparsley Packed Parse Forest (SPPF) is created in the background. The parse forest is presented in a specialized format to promote density and allow for computational complexity similar to that of running the recognizer alone.
The easiest way to use the parse forest is use a internal node tree visitor on the parse forest root with a SelectFirstChildDisambiguationAlgorithm instance controling disambiguation of thet forest.
If the parse is ambiguous, you may want to supply a custom IForestDisambiguationAlgorithm.
// get the parse forest root from the parse engine
var parseForestRoot = parseEngine.GetParseForestRootNode();
// create a internal tree node and supply the disambiguation algorithm for tree traversal.
var parseTree = new InternalTreeNode(
parseForestRoot,
new SelectFirstChildDisambiguationAlgorithm());
References
- berkeley earley cs164
- washington edu ling571
- unt cse earley
- wikipedia
- optimizing right recursion
- marpa parser
- joop leo - optimizing right recursions
- parsing techniques - a practical guide
- practical earley parsing
- detailed description of leo optimizations and internals of marpa
- theory of Marpa Algorithm
- parse tree forest creation
- cs theory stackexchange, leo optimization parse tree creation
- insights on lexer creation
- incremental reparsing
- An extension of Earley's Algorithm for extended grammars
- Finding nullable productions in a grammar
- Directly-Executable Earley Parsing (Aycock and Horspool, 2001)
- Context Senitive Earley Parsing
- stack overflow question on parse forests
- stack overflow question on nullable non terminals
Product | Versions Compatible and additional computed target framework versions. |
---|---|
.NET | net5.0 was computed. 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. |
.NET Core | netcoreapp1.0 was computed. netcoreapp1.1 was computed. netcoreapp2.0 was computed. netcoreapp2.1 was computed. netcoreapp2.2 was computed. netcoreapp3.0 was computed. netcoreapp3.1 was computed. |
.NET Standard | netstandard1.0 is compatible. netstandard1.1 was computed. netstandard1.2 was computed. netstandard1.3 was computed. netstandard1.4 was computed. netstandard1.5 was computed. netstandard1.6 was computed. netstandard2.0 was computed. netstandard2.1 was computed. |
.NET Framework | net45 was computed. net451 was computed. net452 was computed. net46 was computed. 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 | tizen30 was computed. tizen40 was computed. tizen60 was computed. |
Universal Windows Platform | uap was computed. uap10.0 was computed. |
Windows Phone | wp8 was computed. wp81 was computed. wpa81 was computed. |
Windows Store | netcore was computed. netcore45 was computed. netcore451 was computed. |
Xamarin.iOS | xamarinios was computed. |
Xamarin.Mac | xamarinmac was computed. |
Xamarin.TVOS | xamarintvos was computed. |
Xamarin.WatchOS | xamarinwatchos was computed. |
-
.NETStandard 1.0
- ClrHeapAllocationAnalyzer (>= 3.0.0)
- NETStandard.Library (>= 1.6.1)
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 |
---|---|---|
0.11.0 | 196 | 10/2/2023 |
0.10.0 | 4,920 | 6/13/2022 |
0.9.1 | 464 | 8/4/2021 |
0.9.0 | 510 | 1/21/2021 |
0.8.0 | 1,214 | 11/14/2017 |
0.7.0 | 1,147 | 11/7/2017 |
0.6.0 | 1,147 | 10/28/2017 |
0.5.2 | 1,134 | 10/9/2017 |
0.5.1 | 1,030 | 5/9/2017 |
0.5.0 | 1,013 | 5/3/2017 |
0.4.3 | 1,003 | 4/2/2017 |
0.4.2 | 1,108 | 12/13/2016 |
0.4.1 | 1,260 | 8/19/2016 |
0.4.0 | 1,280 | 8/8/2016 |
0.3.0 | 1,394 | 7/13/2016 |
0.2.1 | 1,273 | 6/29/2016 |
0.1.0 | 1,497 | 6/21/2016 |
0.0.1 | 1,317 | 5/22/2016 |