Parser Grammar Engine
This article needs to be updated.(April 2010) |
The Parser Grammar Engine (PGE, originally the Parrot Grammar Engine) is a
When executed, the bytecode generated by PGE will parse text as described in the input rules, generating a parse tree. The parse tree can be manipulated directly, or fed into the next stage of the Parrot compiler toolchain in order to generate an AST from which code generation can occur (if the grammar describes a programming language).
History
Originally named P6GE and written in C, PGE was translated to native Parrot and renamed not long after its initial release in November 2004. Its author is Patrick R. Michaud.
Internals
PGE combines three styles of parsing:
- Raku rules
- an operator precedence parser
- custom parse subroutines
The primary form is Raku rules, so a PGE rule might look like this for an addition-only grammar:
rule term { <number> | \( <expr> \) }
rule number { \d+ }
rule expr { <term> ( '+' <term> )* }
The operator precedence parser allows an operator table to be built and used directly in a Perl 6 rule style parser like so:
rule expr is optable { ... }
rule term { <number> | \( <expr> \) }
rule number { \d+ }
proto term: is precedence('=')
is parsed(&term) {...}
proto infix:+ is looser('term:') {...}
This accomplishes the same goal of defining a simple, addition-only grammar, but does so using a combination of a Raku style regex/rules for term
and number
and a shift-reduce optable for everything else.
Code generation
Though PGE outputs code which will parse the grammar described by a rule, and can be used at
The Parrot compiler toolchain is broken into several parts, of which PGE is the first. PGE converts source code to parse trees. The Tree Grammar Engine (TGE) then converts these into Parrot Abstract Syntax Trees (PAST). A second TGE pass then converts a PAST into Parrot Opcode Syntax Trees (POST) which can be directly transformed into executable bytecode.
References
- ^ Michaud, Patrick R. (2004-11-22). "Parrot Grammar Engine (PGE)". Archived from the original on 2005-12-20.
- ^ Michaud, Patrick R. (2004-11-08). "First public release of grammar engine".
- ^ Agent Zhang (2006-09-17). "PCR replaces PGE in Pugs".