Skip to content

Latest commit

 

History

History
138 lines (97 loc) · 8.21 KB

PEGGED.md

File metadata and controls

138 lines (97 loc) · 8.21 KB
Raw

PEGGED

Pegged is a parsing expression grammar (PEG) generator implemented in the D programming language.

The idea is to give the generator a PEG, with the syntax presented in the reference article . From this grammar definition a set of related parsers will be created, to be used at runtime or compile time.

Usage

To use Pegged, just call the grammar function with a PEG and mix it in. For example:

import pegged.grammar;

mixin(grammar(`
Arithmetic:
    Expr     <  Factor AddExpr*
    AddExpr  <  ^('+'/'-') Factor
    Factor   <  Primary MulExpr*
    MulExpr  <  ^('*'/'/') Primary
    Primary  <  '(' Expr ')' / Number / Variable / ^'-' Primary

    Number   <~ [0-9]+
    Variable <- Identifier
`));

This creates the Arithmetic grammar, with the Expr, AddExpr, Factor (and so on) rules for basic arithmetic expressions with operator precedence ('*' and '/' bind stronger than '+' or '-'). Identifier is a pre-defined parser recognizing your basic C-style identifier (first a letter or underscore, then digits, letters or underscores). In the rest of this document, I'll call 'rule' a Parser <- Parsing Expression expression and I'll use 'grammar' to designate the entire group of rules given to grammar.

To use a grammar, use the .parse method. It will return a parse tree containing the calls to the different rules:

// Parsing at compile-time:
enum parseTree1 = Expr.parse("1 + 2 - (3*x-5)*6");

pragma(msg, parseTree1.capture);
writeln(parseTree1);

// And at runtime too:
auto parseTree2 = Expr.parse(" 0 + 123 - 456 ");
assert(parseTree2.capture == ["0", "+", "123", "-", "456"]);

Even for such a simple grammar and such a simple expression, the resulting parse tree is a bit long to be shown here. See the result here

By default, the grammars are space-sensitive (spaces are not silently consumed), because doing otherwise introduced lots of subtle bugs everywhere in my grammars. Use the 'space-arrow' (< ) to create a space-consuming rule (see [[Extended PEG Syntax]])

Tutorial

Here is a [[Pegged Tutorial]]. It's about 15 lessons gradually introducing Pegged features.

As a Library

The only modules you need are pegged.peg, pegged.grammar and pegged.utils.associative. To compile Pegged as a library, do:

>  dmd -lib -oflibpegged.a pegged/peg.d pegged/grammar.d pegged/utils/associative.d

(FWIW, I use rdmd personally)

Features

  • The complete set of operators described here are implemented, with the 'traditional' PEG syntax. See [[PEG Basics]].
  • Pegged can parse its input at compile time and generate a complete parse tree at compile time. See [[Generating Code]] for the power that gives you. In a word: compile-time string (read: D code) transformation and generation.
  • You can parse at runtime also, you lucky you ([[Using the Parse Tree]])
  • Pegged accepts strings, wstrings and dstrings as inputs. Grammar can also be written as strings, wstrings or dstrings, allowing accented characters or Unicode characters to be used.
  • Use a standard and readable PEG syntax as a DSL ([[PEG Basics]]), not a bunch of templates that hide the parser in noise.
  • But you can use expression templates if you want, as parsers are all available as such. Pegged is implemented as an expression template, and what's good for the library writer is sure OK for the user too ([[Behind the Curtain: How Pegged Works]]).
  • Some useful additional operators are there too: a way to discard matches (thus dumping them from the parse tree), to push captures on a stack, to accept matches that are equal to another match: see [[Extended PEG Syntax]].
  • Adding new parsers is easy. See [[User-Defined Parsers]] to see how to do that. Pegged comes with a bunch of [[Predefined Parsers]].
  • Grammars are composable: you can put different mixin(grammar(rules)); in a module and then grammars and rules can refer to one another. That way, you can have utility grammars providing their functionalities to other grammars. [[Grammar Composition]]
  • That's why Pegged comes with some pre-defined grammars (JSON, etc). See [[Grammar Examples]].

More advanced features, outside the standard PEG perimeter are there to bring more power in the mix:

  • Parametrized rules: "List(E, Sep) <- E (Sep E)*" is possible. The previous rule defines a parametrized parser taking two other parsers (namely, E and Sep) to match a Sep-separated list of E's. Entire grammars can be parametrized, too. See [[Parametrized Rules]] to see what's possible.
  • Named captures: any parser can be named with the = operator. The parse tree generated by the parser (so, also its matches) is delivered to the user in the output. Other parsers in the grammar see the named captures too. See [[Named Captures]] for more explanations on this.
  • Semantic actions: can be added to any rule in a grammar. Once a rule has matched, its associated action is called on the rule output and passed as final result to other parsers further up the grammar. Do what you want to the parse tree. If the passed actions are delegates, they can access external variables. See [[Semantic Actions]].

Limitations

  • No effort was done to accelerate the parsing or reduce the memory consumption. The main goal was to 1) use the PEG syntax 2) parse at compile-time. Packrat parsing could be done, maybe. Pegged does some basic optimization, though: one-element sequences and choices are replaced by their only element and sequences of sequences are flattened (the same is done for ordered choices).
  • No left-factorization because this doesn't work well with PEGs. But you can do recursive grammars, of course.
  • Error reporting is the same as for any in-my-own-free-time / just-one-guy parsing project (read: awful). You'll know when it crashes. I ave plans to put an error stack in the mix, to unwind when a grammar cannot parse the provided input.
  • I couldn't find a way to use anonymous function templates as actions (o => o). Too bad.
  • The entire grammar is defined at compile-time: no user input for actions and such. That was a design decision from the very beginning.

Future features (aka, my todo list)

See [[TODO]]

Long-Term Goals (the Right to Dream)

  • As a long-term goal, parsing structures, as presented in OMeta. Yeah, I know, but I find that wonderfully interesting. Rules could match not only strings by any D type inner structure (matching a struct if it contains an int member named foo and a bar method, etc).
  • Hence, a pattern-matcher. if you used Haskell or ML, you know what I'm talking about.
  • As a longer-term goal: implementing the complete D grammar and see if that flies.
  • As an even longer-term goal: macros in D. Think Lisp and talking to God.

References

Articles:

D Code:

Other languages:

License

Pegged is released with the Boost license (like most D projects). See here for more details.

Author: Philippe Sigaud.