Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Livret – 14 Programmer avec des grammaires automate à pile de mémoire, automate

Livret – 14 Programmer avec des grammaires automate à pile de mémoire, automate d’états finis, construction d’un interpréteur Outil utilisé : C# RM di scala Cours informatique programmation Rm di Scala - http://www.discala.net rm di Scala - 2006 Livret 14 : Programmer avec des grammaires - ( rév. 07.12.2005 ) page 1 SOMMAIRE 14.1 Programmation avec les grammaires de type 2 3 • programmation par les grammaires • C-grammaire et automate à pile de mémoire 14.2 Automates et grammaires de type 3 23 • automates pour les grammaires de type 3 • implantation d'un automate d'état fini en C# • déterministe à partir des règles • déterministe à partir de sa table des transitions • non-déterministe à partir des règles • automate pour les identificateurs • automate pour les constantes numériques 14.3 Projet d'interpréteur de micro-langage 44 • la grammaire du micro-langage • construction de l'analyseur • construction de l'interpréteur Livret 14 : Programmer avec des grammaires - ( rév. 07.12.2005 ) page 2 14.1 : Programmation avec des C-grammaires Plan du chapitre: 1. Programmation par les grammaires 1.1 Méthode pratique de programmation avec un langage récursif 1.2 Application de la méthode : un mini-français 2. C-grammaire et automate à pile de mémoire 2.1 Définition d’un automate à pile 2.2 Algorithme de fonctionnement d’un automate à pile 2.3 Programme C# d’un automate à pile rm di Scala - 2006 Livret 14 : Programmer avec des grammaires - ( rév. 07.12.2005 ) page 3 1. Programmation par les grammaires ( programme en C# ) D’un point de vue pratique, les grammaires sont un outil abstrait puissant. Nous avons vu qu’elles permettaient de décrire des langages de quatre catégories. Elles servent aussi : q soit à générer des phrases dans le langage engendré par la grammaire (en ce sens elles permettent la programmation), q soit à analyser un énoncé quelconque pour savoir s’il appartient ou non au langage engendré par la grammaire (en ce sens elles permettent la construction des analyseurs et des compilateurs). Nous adoptons ici le point de vue " mode génération " d’une grammaire afin de s’en servir comme d’un outil de spécification sur les mots du langage engendré par cette grammaire. On appelle aussi cette démarche programmation par la syntaxe. Nous nous restreindrons au C-grammaires et aux grammaires d’états finis. Soit G = (VN,VT,S,R), une telle grammaire et L(G) le langage engendré par G. Objectif : Nous voulons construire un programme qui nous exhibe sur l’écran des mots du langage L(G). 1.1 Méthode pratique de programmation avec un langage récursif G = (VN,VT,S,R) à traduction en programme pratique en langage X générateur de mots. La grammaire G est supposée ne pas contenir de règle récursive gauche ( du genre Α → Αα ), sinon il faut essayer de la changer ou abandonner. 1° Tous les éléments du vocabulaire auxiliaire VN deviennent les noms d’un bloc-procédure du programme. 2° Le vocabulaire terminal VT est décrit soit par un type prédéfini du langage X s’il est simple, sinon par une structure de donnée et un TAD. 3° Toutes les règles de G sont traduites de cette manière : 3.1° le symbole de VN de la partie Gauche de la règle indique le nom du bloc-procédure que l’on va implanter. 3.2° la partie droite d’une règle correspond à l’implémentation du corps du bloc-procédure, pour chaque symbole α de cette partie droite si c’est : q un élément de VT, il est traduit par une écriture immédiate de sa valeur (généralement un écrire(α) traduit dans le langage X). q un élément de VN, il est traduit par un appel au bloc-procédure du même nom que lui. 4° Le bloc-procédure représentant l’axiome S est appelé dans le programme principal. Chaque appel de S fournira un mot du langage L(G). Livret 14 : Programmer avec des grammaires - ( rév. 07.12.2005 ) page 4 Afin de bien persuader le lecteur de la non dépendance de la méthode vis à vis du langage nous construisons l'exemple en Delphi et en C#. Exemple fictif : grammaire Traduction en Delphi Traduction en C# G = ( VN,VT,S, R ) VN = { S, A, B } VT = { a, b } Axiome : S Règles : ...... k : S → aAbBb VN →procedure S ; VT →Type Vt = char ; procedure A ; procedure B ; VN →void S( ) ; VT →char ; void A( ) ; void B( ) ; La règle k est traduite par l’implantation du corps du bloc-procédure associé à l’axiome S (partie gauche): règle Traduction en Delphi Traduction en C# k : S → aAbBb procedure S ; begin writeln(‘a’) ; A ; writeln(‘b’) ; B ; writeln(‘b’) ; end; void S ( ) { System.out.println('a'); A( ) ; System.out.println('b'); B( ) ; } Le lecteur comprend ici le pourquoi de la contrainte de règles non récursives gauches (du genre A → A α ), le bloc-procédure s’écrirait alors : règle Traduction en Delphi Traduction en C# A → A α procedure A ; begin A ; ... end ; void A ( ) { A( ) ; ... } Ce qui conduirait le programme à un empilement récursif infini du bloc-procédure A (limité par la saturation de la pile d’exécution de la machine avec production d'une exception de débordement de pile). 1.2 Application de la méthode : un mini-français Etant donné G une grammaire d’un sous-ensemble du français dénommé mini-fr. G = (VN,VT,S,R) VT ={le, un, chat, chien, aime, poursuit, malicieusement, joyeusement, gentil, noir, blanc, beau, '.'} VN = { 〈phrase〉, 〈GN〉, 〈GV〉, 〈Art〉, 〈Nom〉, 〈Adj〉, 〈Adv〉, 〈verbe〉} Axiome : 〈phrase 〉 rm di Scala - 2006 Livret 14 : Programmer avec des grammaires - ( rév. 07.12.2005 ) page 5 Règles : 1 : 〈phrase 〉 → 〈GN 〉 〈GV 〉 〈GN 〉. 2 : 〈GN 〉 → 〈Art 〉 〈Adj 〉 〈Nom 〉 3 : 〈GN 〉 → 〈Art 〉 〈Nom 〉 〈Adj 〉 4 : 〈GV 〉 → 〈verbe 〉 | 〈verbe 〉 〈Adv 〉 5 : 〈Art 〉 →le | un 6 : 〈Nom 〉 →chien | chat 7 : 〈verbe 〉 →aime | poursuit 8 : 〈Adj 〉 →blanc | noir | gentil | beau 9 : 〈Adv 〉 →malicieusement | joyeusement Traduisons à l’aide de la méthode précédente, cette grammaire G en un programme C# générant des phrases de L(G). A) les procédures du programme Chaque élément de VN est associé à une procédure : VN = {〈phrase〉, 〈GN〉, 〈GV〉, 〈Art〉, 〈Nom〉, 〈Adj〉, 〈Adv〉, 〈verbe〉} VN Traduction en Delphi Traduction en C# VN = {〈phrase〉, 〈GN〉, 〈GV〉, 〈Art〉, 〈Nom〉, 〈Adj〉, 〈Adv〉, 〈verbe〉} procedure phrase; procedure GN; procedure GV; procedure Art; procedure Nom; procedure Adj; procedure Adv; procedure verbe; void phrase() void GN() void GV() void Art() void Nom() void Adj() void Adv() void verbe() B) les types de données associés à VT Nous utilisons la structure de tableau de chaînes, commode à cause de sa capacité d’accès direct pour stocker les éléments de VT. Toutefois, au lieu de ne prendre qu’un seul tableau de chaînes pour VT tout entier, nous partitionnons VT en 5 sous-ensembles disjoints : VT = tnom ∪ tadjectif ∪ tarticle ∪ tverbe ∪ tadverbe où : tnom={ chat, chien } tadjectif={ blanc, noir, gentil, beau } tarticle ={ le, un } tverbe ={ aime, poursuit } tadverbe={ malicieusement, joyeusement } Spécification d’implantation en C# : Ces cinq ensembles sont donc représentés en C# chacun par un tableau de chaînes. Const int Maxnbmot=4; // nombre maximal de mots dans un tableau Livret 14 : Programmer avec des grammaires - ( rév. 07.12.2005 ) page 6 champs private String[ ] tnom ; private String[ ] tadjectif ; private String[ ] tarticle ; private String[ ] tverbe ; private String[ ] tadverbe ; Nous construisons une classe que nous nommons Gener_fr qui est chargée de construire et d'afficher une phrase du langage mini-fr : Tous les champs seront privés la seule méthode publique est la méthode phrase qui traduit l'axiome de la grammaire et qui lance le processus de génération et bienentendu le constructeur d'objet de la classe qui est obligatoirement publique. Etat de la classe C# à ce niveau de construction : class Gener_fr { const int Maxnbmot=4; // nombre maximal de mots dans un tableau private String[ ] tnom ; private String[ ] tadjectif ; private String[ ] tarticle ; private String[ ] tverbe ; private String[ ] tadverbe ; private void GN ( ) { } private void GV ( ) { } private void Art ( ) { } private void Nom ( ) { } private void Adj ( ) { } private void Adv ( ) { } private void verbe ( ) { } public void phrase ( ) { } // axiome de la grammaire } C) Initialisation des données associées à VT Un ensemble de méthodes de chargement est élaboré afin d’initialiser les contenus des différents tableaux, ce qui permet de changer aisément leur contenu, voici dans la classe Gener_fr les uploads/Ingenierie_Lourd/ livret-14-grammaireautomatecsharp.pdf