Parser Grammar Engine

Parser Grammar Engine

The Parser Grammar Engine (originally Parrot Grammar Engine) or PGE is a compiler and runtime for a Perl 6 rules for the Parrot virtual machine. [cite web | url=http://search.cpan.org/~ltoetsch/parrot-0.2.2/compilers/pge/README | title=Parrot Grammar Engine (PGE) | author=Michaud, Patrick R. | date=2004-11-22] PGE uses these "rules" to convert a parsing expression grammar into Parrot 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 and most formal grammars, 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 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 re-named not long after its initial release in November 2004. Its author is Patrick R. Michaud. [cite web | url=http://www.nntp.perl.org/group/perl.perl6.compiler/96 | title=First public release of grammar engine | author=Michaud, Patrick R. | date=2004-11-08] 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. [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]

Internals

PGE combines three styles of parsing:
* Perl 6 rules
* an operator precedence parser
* custom parse subroutinesThe primary form is Perl 6 rules, so a PGE rule might look like this for an addition-only grammar: rule term { | ( ) } rule number { d+ } rule expr { ( '+' )* }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 { | ( ) } 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 Perl 6 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 runtime to handle simple grammars and regular expressions found in code, its primary purpose is for the parsing of high level languages.

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

External links

*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
*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Parser Grammar Engine — Moteur d analyse de grammaire Pour les articles homonymes, voir PGE. Le Parser Grammar Engine (PGE ou en français, moteur d analyse de grammaire) est un compilateur et un moteur d exécution pour les regex Perl 6 pour la machine virtuelle… …   Wikipédia en Français

  • Operator-precedence parser — An operator precedence parser is a bottom up parser that interprets an operator precedence grammar. For example, most calculators use operator precedence parsers to convert from the human readable infix notation with order of operations format… …   Wikipedia

  • Comparison of parser generators — This is a list of notable lexer generators and parser generators for various language classes. Contents 1 Regular languages 2 Deterministic context free languages 3 Parsing expression grammars, deterministic boolean grammars …   Wikipedia

  • Parser — Ein Parser [ˈpɑːʁzɐ] (engl. to parse, „analysieren“, bzw. lateinisch pars, „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Computertechnik für die Zerlegung und Umwandlung einer beliebigen Eingabe in ein für …   Deutsch Wikipedia

  • Irrlicht Engine Extentions — Being the open ended project it is, the Irrlicht Engine has various first party and third party extensions to even further power up the engine.VideoThere are no known extensions for the video rendering capabilities of Irrlicht.AudioirrKlangAudio… …   Wikipedia

  • GOLD (parser) — Infobox Software name = GOLD Parsing System caption = developer = Devin Cook [http://www.devincook.com/goldparser/contributors Multiple Contributors] latest release date = 2007 07 29 latest release version = 3.4.4 operating system = Windows… …   Wikipedia

  • Lemon Parser — Lemon is an LALR parser generator for C or C++. It does the same job as GNU bison and yacc; however, Lemon is not another bison or yacc clone. It uses a different grammar syntax which is designed to reduce the number of coding errors. Lemon also… …   Wikipedia

  • Parrot virtual machine — Developer(s) Parrot Foundation Stable release 3.10.0[1] / November 16, 2011; 7 days ago …   Wikipedia

  • Moteur D'analyse De Grammaire — Pour les articles homonymes, voir PGE. Le Parser Grammar Engine (PGE ou en français, moteur d analyse de grammaire) est un compilateur et un moteur d exécution pour les regex Perl 6 pour la machine virtuelle Parrot.[1] PGE utilise ses règles pour …   Wikipédia en Français

  • Moteur d'analyse de grammaire — Pour les articles homonymes, voir PGE. Le Parser Grammar Engine (PGE ou en français, moteur d analyse de grammaire) est un compilateur et un moteur d exécution pour les regex Perl 6 pour la machine virtuelle Parrot[1]. PGE utilise ses règles pour …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”