# Parser Grammar Engine

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Parser_Grammar_Engine
> Markdown URL: https://mediated.wiki/source/Parser_Grammar_Engine.md
> Source: https://en.wikipedia.org/wiki/Parser_Grammar_Engine
> Source revision: 1335357758
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Update|date=April 2010}}
The '''Parser Grammar Engine''' ('''PGE''', originally the '''Parrot Grammar Engine''') is a [compiler](/source/compiler) and [runtime system](/source/runtime_system) for [Raku rules](/source/Raku_rules) for the discontinued [Parrot virtual machine](/source/Parrot_virtual_machine).<ref>{{Cite web |title=Parrot - Grammar Engine |url=http://docs.parrot.org/parrot/latest/html/docs/book/pct/ch04_pge.pod.html |access-date=2026-01-28 |website=docs.parrot.org}}</ref> PGE uses these ''rules'' to convert a [parsing expression grammar](/source/parsing_expression_grammar) into Parrot [bytecode](/source/bytecode). It is therefore compiling rules into a program, unlike most virtual machines and runtimes, which store regular expressions in a secondary internal format that is then interpreted at runtime by a regular expression engine. The rules format used by PGE can express any [regular expression](/source/regular_expression) and most [formal grammar](/source/formal_grammar)s, and as such it forms the first link in the compiler chain for all of Parrot's front-end languages.

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'' to generate an [abstract syntax tree](/source/abstract_syntax_tree) (AST) from which code can be  generated; 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.<ref>{{cite web |url=http://www.nntp.perl.org/group/perl.perl6.compiler/96 |title=First public release of grammar engine |last1=Michaud |first1=Patrick R. |date=2004-11-08}}</ref> PGE was written to reduce the amount of work needed to implement a compiler on Parrot. It was also written to allow Perl 6 to easily self-host, though current [Pugs](/source/Pugs_(compiler)) development no longer uses PGE as its main rules back-end in favor of a native engine named PCR.<ref>{{cite web |url=http://pugs.blogs.com/pugs/2006/09/pcr_replaces_pg.html |title=PCR replaces PGE in Pugs |author=Agent Zhang |date=2006-09-17}}</ref>

==Internals==
PGE combines three styles of parsing:
* Raku rules
* an [operator-precedence parser](/source/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:
<syntaxhighlight lang="raku">
 rule term   { <number> | \( <expr> \) }
 rule number { \d+ }
 rule expr   { <term> ( '+' <term> )* }
</syntaxhighlight>

The operator precedence parser allows an operator table to be built and used directly in a Perl 6 rule style parser like so:
<syntaxhighlight lang="raku">
 rule expr is optable { ... }
 rule term   { <number> | \( <expr> \) }
 rule number { \d+ }
 proto term: is precedence('=')
             is parsed(&term) {...}
 proto infix:+ is looser('term:') {...}
</syntaxhighlight>

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 <code>term</code> and <code>number</code> 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 [runtime](/source/Execution_(computing)) to handle simple grammars and regular expressions found in code, its main purpose is to parse [high-level programming language](/source/high-level_programming_language)s.

The Parrot compiler toolchain is broken into several parts, of which PGE is the first. PGE converts source code to [parse tree](/source/parse_tree)s. The ''tree grammar engine'' (TGE) then converts these into a ''Parrot abstract syntax trees'' (PAST). A second TGE pass then converts a PAST into ''Parrot [opcode](/source/opcode) syntax trees'' (POST) which can be directly transformed into executable bytecode.

File:Pge-overview.svg

==References==
{{Reflist}}

==External links==
*[http://docs.parrot.org/parrot/latest/html/docs/book/pct/ch04_pge.pod.html Official documentation]
*{{cite web |url=http://www.pmichaud.com/2006/pres/yapc-parsers/start.html |title=Parsers, Perl 6 Rules, and the Parrot Grammar Engine |date=2006-06-28}}

Category:Perl
Category:Formal languages
Category:Pattern matching
Category:Beta software
Category:Compilers
Category:Interpreters (computing)

---
Adapted from the Wikipedia article [Parser Grammar Engine](https://en.wikipedia.org/wiki/Parser_Grammar_Engine) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Parser_Grammar_Engine?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.