Home

Awesome

Parakeet

NuGet Version

Parakeet is a text parsing library written in C#. Parakeet is the parsing library being used by the Plato programming language project to Parse both Plato and C# source code.

Parakeet1

Image by Hugo Wai

Overview

Parakeet is a recursive descent (RD) parsing library based on the parsing expression grammar (PEG) formalization introduced by Bryan Ford. Parakeet parsers are defined directly in C# using operator overloading. Parakeet combines both lexical analysis (aka tokenization) and syntactic analysis in a single pass.

See this CodeProject article for an introduction to the core concepts of Parakeet.

More Details and Features

Parakeet was designed primarily for the challenge of parsing programming languages. It can be used in different contexts of course.

Parakeet supports:

Steps

  1. Define a grammar in code: a class with a set of properties that map to rules
  2. Convert the input text into a parser input object
  3. Choose the starting rule of the grammar
  4. Call the match function of the starting rule
  5. Examine the resulting ParserState object
  6. If the result is null the parser failed to match, and failed to recover
    • Consider adding OnError to your grammar
  7. Convert

Primary Classes

Grammar

A Grammar is the base class for collections of parsing rules. Usually each parse rule in a grammar is defined as a computed property that either returns a NodeRule or a TokenRule. By using the functions Node and Token to wrap rule definitions, names are automatically assigned to each rule.

The GrammarExtensions.cs file contains a number of helper functions for outputting the definitions of grammars or to simplify parsing rules.

When defining rules it is important that any cyclical reference from a rule to itself uses at least one RecursiveRule in the relationship chain. This prevents stack overflow errors from occuring.

Rules

A Parakeet parser is defined by a class deriving from Rule. Some rules are defined by combining rules. Those combining rules are called "combinators".

Ever rule has a single function:

public ParserState Match(ParserState state, ParserCache cache)

The Match will return null if the Rule failed to match, or a ParserState object if successful.

Fluent Syntax for Rules

Rules can be combined using a fluent syntax (aka method chaining).

Overloaded Operators for Rules

Rules can be combined using the following overloaded operators.

Implicit Casts

The following implicit casts are defined for Rules:

Primitive Rules

Rule Combinators

Rule combinators combine zero or more rules.

Assertion Rules

Several rules never advance the parser state:

Error Handling Rules

Parse Trees

Parse trees generated from Parakeet are untyped. A parse node is created whenever a NodeRule rule successfully matches its child rule against the input. After parsing the list of parse nodes is converted into a tree structure.

Typed Parse Tree (CST)

A set of classes representing a strongly typed parse tree can be created automatically from a Parakeet grammar. This is called the Concrete Syntax Tree. Concrete syntax trees are generated from the Ara3D.Parakeet.Grammars project using one of the functions in the Ara3d.Parakeet.Tests project.

Examples of Using Parakeet

The following projects use Parakeet:

History

Parakeet evolved from the Jigsaw parser and applies lessons learned when writing the Myna parsing library in TypeScript as well as my first parsing library [YARD](https://www.codeproject.com/Articles/9121/Parsing-XML-in-C-using-the-YARD-Parser Parakeet is designed to be as fast as possible while retaining a clean and elegant grammar description.

Related Work

C# and F# Parsing Libraries

Parser Generator Tools

References

FAQ

Q: Isn't a parse tree and concrete syntax tree (CST) the same thing?

Yes. Parakeet uses the term parse tree to refer to untyped parse tree, and CST to refer to the typed parse tree.

Q: What is the difference between a CST and an AST?

The CST is generated from parsing the input text as is. An AST is the result of transforming the CST into a form that has the same semantic meaning but is presumably simpler and easier.

Q: Why isn't Parakeet a code generator from the beginning

I find it easier to learn, understand, use, and debug libraries that aren't generated. Writing an extension to Parakeet that generates parser code would not be very hard.

Q: So why is the CST code generated?

Having a strongly typed CST is very beneficial when writing analysis and transformation tools especially for non-trivial grammars like those of programming languages. I don't know of any other way in C# to generate strongly typed libraries other than generating code.

Q: Isn't parsing library X faster?

Maybe. I designed Parakeet to be fast enough for my needs, but I prioritized making it robust and (hopefully) easy to use. See the related work section for other parsing libraries to consider.

Q: Can you provide some benchmarks? Or implement grammar X?

I'm kind of busy getting work done. If you are willing to fund this project, then we should talk: email me at cdiggins@gmail.com.