Raincode PEG Grammar

PEG, short for Parsing Expression Grammars, is a relatively novel approach to develop top-down parsers by relying on recognition and prioritized choice ^[2]. Technically a PEG represents a straight forward recursive descent parser with backtracking ^[3], which implies easier maintenance due to its understandable semantics compared to over-engineered bottom-up parsers. On the other hand, PEGs are better than pure regular expressions for parsing due to extended expressiveness and reliable deterministic behaviour ^[4].

There are known ways to address problems typical for all top-down parsers, such as support for left recursion ^[5] , ^[6], and together with techniques like highly configurable memoization ^[7], they allow efficient implementations that work in linear time ^[8] and nearly constant space ^[9].

Raincode PegGrammar implements PEG extended with several additional features to be discussed later in the document.

The PegGrammar framework helps an engineer to develop a parser by modeling some easily automated yet error-prone parts. Still, it is not meant to be an out of the box fully automated solution. The user of PegGrammar will need to program the abstract syntax (the target representation of the parser) manually in C# and then write a grammar that serves as a specification of how to recognize correct concrete programs and how to map them into this abstract representation. The PegGrammar generator produces a C# class that implements this specification and build a complete solution together with manually written code fragments. The grammar may contain explicit references to some of those code fragments.

Create a new C# project in Visual Studio. Go to Project > Manage NuGet Packages…​ Make sure the right `Package source is selected, then Browse for Raincode.Peg.Generator and Install it into your project. Add a new item to the project and call it FicTool.peg, then, in the Properties of that file, make sure that the Build Action is set to GenPeg.

A new, generated, C# file named FicTool.peg.g.cs will appear nested under FicTool.peg in the project. Do not edit this file by hand. It will be rebuilt when you build the project. If you want to rebuild it immediately, simply delete it from the project.

Below is a simple parser for this source. Copy this in FicTool.peg as described above.

The generated file has the following content.

This parser can be used in your program. Of course, this parser only recognizes the single example and not any other potential input. We can already see that literal strings are written with the C# syntax and parse a constant text.

Here is a slightly more reasonable grammar.

Since this grammar defines six non-terminals, the generated parser will have six corresponding methods to parse them: ParseCommands, ParseCommand, ParseWhen, ParseCondition, ParseIndex, and ParseBuild. There is no specified root non-terminal, so a single grammar can be used to parse different (but related) kinds of input.

The Commands non-terminal is now defined as a repetition (with a minimum of one) of sequences of a Command and a newline. The repetition is indicated by the +, and the sequence is implicit when parsing expressions are juxtaposed. The parentheses are used for precedence. Without them, we would only parse a single Command followed by any number (greater than one) of newlines.

A Command is in turn defined as either a sequence of INPUT, blanks, and a When clause or OUTPUT, blanks, a When clause, a comma, and a Build clause.

Similarly, the When and Condition non-terminals are defined with known concepts. Note that definitions can be recursive (as is the case for Condition) but be careful that, as with a typical hand-written parser, immediate recursion (without progressing in the input) will result in an infinite loop. Ordering of the cases is meaningful as they are tried in order, and the first matching branch is taken, even if it makes the parsing fail later on and that taking a different branch would have allowed it to succeed.

The Index non-terminal introduces a new concept: regular expressions. It uses the .NET regular expressions defined in System.Text.RegularExpressions and is very useful to parse non-constant terminals.

Finally, Build is defined as a sequence, one element of which is a repetition of one or more indexes separated by commas. Alternatively, we could have defined Build as Build ::= "BUILD(" Index ("," Index)* ")" with a repetition of zero or more sequences of comma and Index, but the option we choose is more specific and will give a better parse tree later on.

The parser generator only generates a parser. It does not create classes for an abstract syntax tree (AST). This gives you a lot of controls on how the classes are implemented and their inheritance hierarchy. The only things the parser needs is that instances of the classes can be constructed without giving arguments to the constructor (see below for more details) and that fields (or properties) are accessible, defined with compatible types, and (in the case of lists) initialized.

Let’s now add the following as an Ast.cs file to the project.

We can now write the following grammar that will generate a more useful parser.

The only change to the definition of Commands is that we removed void from the front as it now as a semantic type (also known as return type) which, if unspecified, defaults to the same as the non-terminal name. Since it has to receive potentially several Commands, it has to inherit from List<Command>. (More specifically, it has to have an Add method that can take an argument with the semantic type of the Command non-terminal.)

The non-terminal Command had more changes. We now see what class to instantiate (Input := and Output :=) and what field or property to set (WhenClause = and BuildClause =).

The When non-terminal had just a change of semantic type from void to ICondition.

The Condition non-terminal is changed in a way very similar to the changes made to Command.

For Index, the regular expression was changed from a rei: prefix to a re: prefix. This has a semantic type of string and gives access to the matched text. We then transform that string into an int using the .NET static method int.Parse.

Finally, for Build, we added an assignment to the Indexes field. Because of the repetition, the parser will infer that Indexes is a list in which elements have to be added and not just a field or property to be assigned. We didn’t have to explicitly write anything to instantiate the class Build. We could have written more explicitly Build ::= Build := "BUILD(" Indexes = Index,"," ")";+ but the creation of an instance of the semantic type is implicit with the definition of a non-terminal.

Simple expressions are simple in that they are not made by the application of an operator to one or more sub-expressions. Some of the most advanced parsing expressions are in this category and may be skipped on a first reading.

Terminals are formed by a string between double-quotes and potentially a prefix (lit:, re:, or rei:). With no prefix or a lit: prefix, the terminal recognizes the exact string (up to C# escapes). The difference is that without prefix, the semantic type is void, and with the lit: prefix, it is string with a semantic value equal to the parsed string (or the literal itself as they are the same). With a re: or rei: prefix, the terminal is interpreted as a .NET regular expression encoded in a C# string. Be careful about the needed escaping for special characters, in particular backslashes. The difference between the two prefixes is again that rei: has a void semantic and re: a string semantic where the semantic value is the text matched by the regular expression.

Non-terminals are formed of an identifier and potentially a prefix (i: or extent:). With no prefix, the semantic type is the one declared when defining the non-terminal. With an i: prefix, it is void and with an extent: prefix, it is string with a semantic value equal to the part of the input parsed by the non-terminal.

Values can be used as parsing expressions that match the empty string. They are used only for their semantic value. The possible values are $true and $false of bool type, $left, which has the type of the non-terminal being defined (See later left-recursive rules), integers in decimal notation (with an optional negative sign) of type int and arbitrary C# values written as @= T { code } where the C# code must have balanced braces ({ and }) and must be an expression compatible with type T.

A permutation scope is enclosed in square brackets ([ and ]). Permutations will be described with the permutation operator ^.

Any simple or complex parsing expression can be enclosed in parentheses (( and )) to force the precedence of operators.

The remaining cases are considerably more advanced concepts.

External parsers are written @ T { code } where the C# code must have balanced braces and must be a method or delegate that returns a T and takes two parameters of type ref int, and out bool.

This construction allows manually writing parts of the parser. The boolean output argument indicates if the parsing was successful or not. The integer argument is the current parsing position (which must be updated if the parsing is successful), and the return is the semantic value.

A function call is an identifier followed by a colon and, between parentheses, a list of arguments. Functions will be described in more details later.

An expression variable reference is written $$:xxx where xxx is any identifier. It can only be used in the body of a function and will be described with them.

As postfixes, these complex expressions are made by writing an operator after a simpler expression.

Repetitions can be done with + or * for, respectively, at least one or any repetitions of the element.

These are actually shortcuts for {1} and {0} respectively. In general, {n} can be used for at least n repetitions, and {n, m} can be used for between n and m repetitions (bounds included).

An expression can be made optional with ?.

A semantic transformation can be applied to an expression by => T { code } where the C# code must have balanced braces and must be a method or delegate that takes the semantic value of the sub-expression and return a value of type T.

A separation can be applied to either a repetition or a permutation scope by following it with a comma and a simple expression. This is, therefore, not strictly a postfix, but it has the same priority as the other postfixes. For example, "a",":" will parse a:a:a:aa:a:aa but not a::a whereas "a",(":") will match the second example but not the first.

The last case is considerably more advanced.

An external transformation is applied to an expression by @=> TR (T1 P1, …​, Tn Pn) { code } where the C# code must have balanced braces and must be a method or delegate that returns a TR and takes n + 2 parameters of types T1 up to Tn, ref int, and out bool. This construction allows to write manually parts of the parser dependent on previously parsed values and/or to transform multiple values. The boolean output argument indicates if the parsing was successful or not. The integer argument is the current parsing position (which must be updated if the parsing is successful), and the return is the semantic value. The input arguments are the semantic values assigned to properties P1 to Pn in the expression. These properties need not be defined in any AST class.

The prefix operators are written in front of the simpler expression they modify.

An assignment is written as the name of a property followed by an equal sign.

A lookahead is written & (positive) or ! (negative). It saves the current parsing position, parses its sub-expression, and resets the parsing position. If the sub-expression parsed successfully, a positive lookahead succeeds, and a negative lookahead fails, and the opposite if the sub-expression fails to parse.

Sequences are written by simple concatenation of simpler expressions without an explicit operator.

The construction operation is written by prefixing a simpler expression with a typename and a := operator. While this makes it technically a prefix operator, it doesn’t share the precedence of the other prefix operators described above.

Alternatives are written by separating simpler expressions with the / operator.

Permutations are written by separating simpler expressions with the ^ operator. Permutations are only meaningful in a permutation scope delimited by [ and ]. Repetitions and optional expressions have a different interpretation when they are (directly) sub-expressions of a permutation. Let us consider the permutation scope [ A ^ B? ^ C{7,42} ^ D+ ]. It is parsed very similarly to ( A / B / C / D )* but with the added constraints that branches are not entered if they have already had their maximum number of occurrences (here 1, 1, 42, and infinite) and, at the end, there is a check that all branches have had at least their minimum number of occurrences (here 1, 0, 7, and 1). If the final check fails, the parsing of the whole permutation fails. Another slight difference is that from a semantic point of view, non-repeated sub-expressions of a permutation don’t have a list semantic.

This concludes the parsing expressions themselves.

A rule defines a non-terminal. The syntax for a rule is T NT ::= E ; where NT is the non-terminal to define, T its semantic type, and E is a parsing expression. The semantic type can be omitted if it has the same name as the non-terminal itself (which is a common case).

Because the generated parser is close to a hand-written recursive descent parser, left-recursion is problematic. However, left-recursion is the natural way to express left-associative operations, which are fairly common even in mainframe tool input languages. Here is an example of a left-recursive rule.

The generic way to remove the left-recursion is to transform it as in the following rule. The idea is to define a base case and a repetition of addends to it.

This solves the parsing problem, but we cannot easily get the same semantic value as before. We can do it with the following definitions.

The standard rule for Expr only gives the base, non-recursive, case. The other cases are defined with special left-recursion rules. They define the addends that would have been used in the previous block, but they have access to $left, which is the semantic value of the previously matched base case and addends. Notice how close the structure of the final grammar is to the initial one. Because the standard rule gives the semantic type, left-recursion rules are always of the form NT <<+ E; where NT is a non-terminal and E is a parsing expression.

The [version 1] directive defines how the grammar will be produced. It can only be the first element of the file (except for comments). If not present, the grammar is produced as with preceding versions (version 0).

The [using NS] directive where NS is a .NET namespace can be used to add a corresponding using directive to the generated parser. This is useful to use members of that namespace in inlined C# code blocks. Note also that as the generated class is marked partial, it is easy to define, in the parser class itself, a small private method in another file to which one can then directly refer in the grammar.

The [namespace NS] directive defines the .NET namespace NS into which the generated parser class will be placed.

The [class Vis C ] directive defines the name C of the generated parser class and, optionally, its visibility Vis (public or internal).

The [errorHandling Kind ( NT1, …​, NTn)] directive specifies the error handling method used for the named non-terminals. Without the parenthesis and list of non-terminals, set the default handling method for non-terminals. The possible values of Kind are none (the default) or simple.

The [custom textGetter = { tgCode } exceptionBuilder = { excCode }] If specified, tgCode must have balanced braces and must be an expression of type string that returns the text to parse. When specified, no constructors are generated for the parser. If specified, excCode must have balanced braces and must be a method or delegate that returns a throwable type. If all non-terminals use the none error-handling method, it takes four parameters of type string (the name of the failing root non-terminal), bool (true if it only fails due to trailing text), object (semantic value, only valid if preceding argument is true), and int (current position, only well-defined if the boolean argument is true). If any non-terminal use the simple error-handling method, it takes six parameters, the extra two being the furthest position at which it failed to parse any non-terminal with simple error-handling and the last a list of such non-terminal names. This will be called (and the result will be thrown) when the text to parse doesn’t fully correspond to the invoked parsing method. The first two arguments are the name of the non-terminal, and whether the non-terminal was successfully parsed (but then not up to the end of the text to parse). The last two arguments only have a meaningful value if the second argument is true and are the semantic value of the non-terminal and the final position.

The [compatibilityV0 static external] directive permits a smoother transition of old grammars to version1. The optional static parameter restores the generation of static parsing methods. The optional external parameter restores the old signature for external parsers (i.e. @ constructs).

The [default T { code }] directive where the C# code must have balanced braces and must be an expression of type compatible with the type T can be used if T is used in the grammar but code should be used to construct instances of T rather than new T().

The [root Vis ( NT1, …​, NTn)] directive specifies that the parsing method for the named non-terminals has to have the specified visibility (e.g. private or public override). If that directive is used at least once, only named non-terminals will have parsing methods generated.

The [export Vis ( NT1, …​, NTn)] directive specifies that a parsing method for the named non-terminals with the specified visibility (e.g. private or public override) must be generated. That parsing method has a signature compatible with external parsers.

A macro looks a lot like a non-terminal. The differences at the definition are that it has no type and uses a === rather than ::= defining operator. It is used as a non-terminal but shouldn’t have any prefix. Before the code is generated, the references to the macro are replaced with its definition. This can be useful to avoid repetition in the grammar in cases that cannot be made into proper non-terminals, such as parts of a permutation scope containing ^ operators or assignment to fields (or properties) found in different types.

Functions are executed at the same time as macros. They differ from macros by taking arguments and having a syntax closer to the prefixes used with terminals and non-terminals. Here is an example of a function definition and usage.

This is expanded to the following rule.

There can be multiple arguments separated by ;, both in the definition and usage.

The arguments can be:

Each can be used in the body where the corresponding element can be used.

Comments can only appear between rules, directives, macro definitions, or function definitions. They start with # and extend to the end of the line.

We define a function fromType that takes a .NET type and return a PEG expression type in the following way:

fromType(void) = [false] which indicates that there is no guaranteed primary value and that all names (including the empty name) map to the empty set of types.

fromType(T) = [true, ''→{T}] for any other .NET type T which indicates that the primary value can only be of type T and is guaranteed to be present.

We define a unary function list on PEG expression types in the following way:

list([g, a1 → { t11, t12, *t13, …​}, …​]) = [false, a1 → {*t11, *t12, *t13, …​}, …​] which forces all the types to be repetitions and does not guarantee the presence of a primary value.

We define a function def taking a non-empty name n and a PEG expression type and returning a PEG expression type in this way:

def(n, [g, '' → { t1, t2, *t3, …​}]) = [false, 'n'→ { t1, t2, *t3, …​}]

It is an error for def to be applied on a PEG expression type that maps non-empty names to anything else than the empty set.

We define a binary function disjunct on PEG expression types by:

disjunct([gL, a1 → s1L, a2 → s2L, …​], [gR, a1 → s1R, a2 → s2R, …​])=[gL and gR, a1 → s1L union s1R, a2 → s2L union s2R, …​]

and finally a binary function conjunct on PEG expression types by:

conjunct([gL, a1 → s1L, a2 → s2L, …​], [gR, a1 → s1R, a2 → s2R, …​])=[gL or gR, a1 → s1L union s1R, a2 → s2L union s2R, …​]

It is an error to apply conjunct on types where a name (possibly empty) is mapped by one argument to a set that contains a non-repeated type and to a non-empty set by the other argument.

These last two functions will also be used as n-ary functions as they can easily be shown to be associative.

With the preceding definitions, we can now define the expression typing function exprType taking a PEG expression and returning its type. The definition is given by cases depending on the structure of the expression.

exprType("some string") = exprType(rei:"some regexp") = exprType(i:_SomeNonTerminal_) = exprType(!expr) = fromType(void)

exprType(lit:"some string") = exprType(re:"some regexp") = exprType(extent:_SomeNonTerminal_) = fromType(string)

exprType($true) = exprType($false) = fromType(bool)

exprType(n) = fromType(int) when n is a number.

exprType(T { code }) = exprType(expr ⇒ T {code}) = exprType(@ T {code}) = exprType(expr @=> T (…​) {code}) = exprType(T := expr) = fromType(T)

exprType(SomeNonTerminal) = fromType(T) where T is the declared semantic type of non-terminal SomeNonTerminal.

exprType($left) = fromType(T) where T is the declared semantic type of the non-terminal in which the expression is used.

exprType( (expr) ) = exprType(&_expr_) = exprType(expr)

exprType( a = expr) = def(a, exprType(expr))

exprType(expr1 expr2 …​ exprN) = conjunct(exprType(expr1), exprType(expr2), …​, exprType(exprN))

exprType(expr1/expr2/…​/exprN) = disjunct(exprType(expr1), exprType(expr2), …​, exprType(exprN))

exprType([expr1^expr2^…​^exprN]) = conjunct(exprType(expr1), exprType(expr2), …​, exprType(exprN))

exprType(expr+) = exprType(expr*) = exprType(expr{n}) = exprType(expr{n,m}) = list(exprType(expr))

exprType(expr1,expr2) = conjunct(exprType(expr1), list(exprType(expr2))) as separators can normally occur several times.