Remerciez-le!

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

Info theo LesMathématiques net LANGAGES - GRAMMAIRES - AUTOMATES Marie- Paule Muller Version du juillet Ce cours présente et met en oeuvre quelques méthodes mathématiques pour l ? informatique théorique Ces notions de base pourront servir d'entrée en mati

LesMathématiques net LANGAGES - GRAMMAIRES - AUTOMATES Marie- Paule Muller Version du juillet Ce cours présente et met en oeuvre quelques méthodes mathématiques pour l ? informatique théorique Ces notions de base pourront servir d'entrée en matière avant d'aborder un cours de compilation Elles sont introduites ici sans aucun prérequis a ?n d ? être accessibles à tout lecteur débutant sur ce sujet Table des matières INTRODUCTION Les t? ches d ? analyse d ? un compilateur La notion de grammaire et d ? analyse syntaxique LANGAGES ?? LANGAGES REGULIERS Dé ?nitions Opérations sur les langages Langages réguliers Kleene GRAMMAIRES ALGEBRIQUES dites aussi hors contexte ? Dé ?nition d ? une grammaire algébrique Dérivations Langage engendré Arbre de dérivation Dérivations à gauche Grammaires régulières Ambigu? té Graphe orienté d ? une grammaire algébrique LE LEMME DE L ? ETOILE en anglais pumping lemma ? Le lemme de l ? Etoile pour les grammaires régulières Un exemple d ? application du lemme de l ? Etoile ANALYSE SYNTAXIQUE en anglais parsing ? Test sur le pré ?xe terminal dans les analyses syntaxiques descendantes Analyse syntaxique descendante en largeur d'abord Analyse syntaxique descendante en profondeur d'abord Note sur les analyses ascendantes AUTOMATES Dé ?nitions Langage reconnu par un automate Automates déterministes automates déterministes complets Automates et grammaires régulières Les ? ??automates Preuve du théorème TRANSFORMATION DES GRAMMAIRES ALGEBRIQUES Suppression de la récursivité de l ? axiome Suppression des règles vides Suppression des encha? nements de variables Suppression des variables et symboles inutiles Forme normale de Chomsky Forme normale de Greibach NETOGRAPHIE M P Muller - LANGAGES - GRAMMAIRES - AUTOMATES page CINTRODUCTION LesMathématiques net Un compilateur est un utilitaire de traduction permettant à partir d'un programme écrit dans un langage de haut niveau ou du moins compréhensible par un programmeur humain C C Pascal Algol FORTRAN assembleur de véri ?er la syntaxe du programme de départ puis de produire un ?chier en un langage de niveau plus bas par exemple un ?chier en code objet exécutable par le système d'exploitation Le premier langage de haut niveau qui a été écrit est le FORTRAN Mathematical FORmula TRANslating System ? son compilateur a été conçu et écrit dans les années - par une équipe de pionniers super-programmeurs conduite par John W Backus Son écriture soit lignes de code machine enregistrées sur bande magnétique a nécessité un travail équivalent à hommes-années bien plus important que ce que le projet initial prévoyait mais la direction d'IBM dont dépendait ce projet a eu l'intelligence de laisser le groupe libre de poursuivre son e ?ort comme il l'entendait Coup d'essai coup de ma? tre le langage FORTRAN I a eu un succès énorme et son compilateur a gardé durant vingt ans le record d'optimisation du code objet produit Plus tard le compilateur du PASCAL a été écrit en auto-amorçage conçu à la main ? pour environ du langage le reste a été produit par ce qui était déjà compilé De nombreux autres compilateurs ont suivi par exemple YACC