Parser Grammar Engine

The Parrot Grammer Engine or PGE is a compiler and runtime for Perl 6 rules for the Parrot virtual machine. PGE translates these rules directly into Parrot bytecode for eventual execution, unlike most virtual machines and runtimes which store regular expressions in a secondary internal format that is then interpreted at runtime. PGE can express any regular expression or formal grammar, and as such it can be used to implement the behavior of all of Parrot's front-end languages.

History

Originally named P6GE and written in C, PGE was translated to native Parrot and re-named not long after its initial release in November of 2004. Its author is Patrick R. Michaud. PGE was written in order to reduce the amount of work required to implement a compiler on top of Parrot. It was also written to allow Perl 6 to easily self-host, though current Pugs development no longer uses PGE as its primary rules back-end in favor of a native engine called PCR.

Internals

PGE combines three styles of parsing:

• Perl 6 rules
• an operator precedence parser
• custom parse subroutines

The primary form is Perl 6 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 shift-reduce optable for expr and Perl 6 style rules for everything higher-level.

Code generation

The PGE compiler that comes with parrot compiles PGE grammars to Parrot Intermediate Representation (PIR) in which each rule is represented by a Parrot subroutine that performs the matches and builds the appropriate internal representation.

External links

• "Parsers, Perl 6 Rules, and the Parrot Grammar Engine". 2006-06-28.