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 convertir une parsing expression grammar en bytecode Parrot.

Il compile donc les règles en un programme, contrairement à la plupart des machines virtuelles, qui stockent les expressions rationnelles en un format interne secondaire qui est ensuite interprété au moteur d'exécution par un moteur de gestion d'expressions rationnelles en ce format. Le format des règles analysables par PGE peut exprimer toute expression rationnelle et beaucoup de grammaires formelles. Comme tel, PGE forme le premier maillon d'une chaîne de compilation de langages de haut niveau; chaîne dont parrot est le dorsal.

Lorsque exécuté, le bytecode généré par PGE analysera le texte comme spécifié par les règles d'entrée, générant un arbre d'analyse.
Celui-ci sera manipulé directement ou passé au maillon suivant de la chaîne de compilation de Parrot afin de générer un AST à partir duquel la génération de code peut être faite si la grammaire décrit un langage de programmation.

Histoire

Originellement nommé P6GE et écrit en langage C, PGE a été manuellement transcrit en source Parrot et renommé peu après sa release initiale en novembre 2004. Son auteur est Patrick R. Michaud^[2]. il a écrit PGE afin de réduire la quantité de travail nécessaire à la mise en œuvre d'un maillon compilateur au-dessus de Parrot. Il a aussi écrit PGE pour permettre l'autohébergement de Perl 6, bien que le développement de la version courante de Pugs n'utilise plus PGE mais un engin natif appelé PCR^[3].

Internes

PGE combines trois styles d'analyse :

• les règles Perl
• un analyseur à précédence d'opérateur
• des sous-routines spécialisées

Le style premier est celui des règles Perl 6, donc un règle PGE peut ressembler à ceci pour une grammaire qui décrit un langage qui supporte seulement l'opérateur d'addition :

rule term   { <number> | \( <expr> \) }
rule number { \d+ }
rule expr   { <term> ( '+' <term> )* }

L'analyseur à précédence d'opérateurs permet de construire une table d'opérateurs qui peut être utilisée dans un analyseur Perl 6. Ainsi :

rule expr is optable { ... }
rule term   { <number> | \( <expr> \) }
rule number { \d+ }
proto term: is precedence('=')
            is parsed(&term) {...}
proto infix:+ is looser('term:') {...}

Cela accomplit la même chose que la grammaire précédente. mais le fait en utilisant une combinaison de regex et de règles pour term et number et un automate shift-reduce pour tout le reste.

Génération de code

Bien que la sortie PGE génère du code Parrot qui analyse la grammaire décrite par une règle, et peut donc être utilisé pour traiter des grammaires simples et des expressions rationnelles, son but principal est l'analyse de langages de haut niveau.

La chaîne de compilation Parrot est divisée en plusieurs parties, dont PGE est la première. PGE convertit le code source en un arbre d'analyse. TGE, le Tree Grammar Engine le convertit ensuite en PAST (Parrot Abstract Syntax Tree, ou, en français, Arbre syntaxique d'analyse). Une seconde passe de TGE convertit le PAST en POST (Parrot Opcode Syntax Tree, ou, en français Arbre syntaxique d'opcodes) qui est directement transformé en bytecode exécutable.

Fichier:Pge-overview.svg

Références

1. ↑ Michaud, Patrick R., « Parrot Grammar Engine (PGE) », 22 novembre 2004
2. ↑ Michaud, Patrick R., « First public release of grammar engine », 8 novembre 2004
3. ↑ "Agent Zhang", « PCR replaces PGE in Pugs », 17 septembre 2006

Liens externes

• Parsers, Perl 6 Rules, and the Parrot Grammar Engine, 28 juin 2006