Remerciez-le!

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

Expression régulière et automates finis Automates finis Passage de l’AF (D ou

Expression régulière et automates finis Automates finis Passage de l’AF (D ou N) vers l’ER Expression régulière et automates finis Automates finis Passage de l’AF (D ou N) vers l’ER Expression régulière et automates finis Automates finis Passage de l’AF (D ou N) vers l’ER Exemple: Expression régulière et automates finis  Automates finis Passage de l’AF (D ou N) vers l’ER  L'algorithme des équations linéaires en utilisant le lemme d'Arden SoitA=(Q,V ,δ,q0,F) un automate à états fini quelconque. On note par Li le langage reconnu par l’automate si son état initial était qi. Par conséquent, trouver le langage reconnu par l’automate revient à trouver L0 étant donné que la reconnaissance commence à partir de q0. commence à partir de q0. L’automate permet d’établir un système d’équations aux langages de la manière suivante: - Si δ(qi,a)=qj alors on écrit: Li=aLj - Si qi∈F, alors on écrit: Li=ε. - Si Li=α et Li=β alors on écrit Li= α| β Il suffit ensuite de résoudre le système en précédant à des substitutions et en utilisant la règle du lemme d’Arden suivante: La solution de l’équation L= αL|β est le langage L=α*β. Expression régulière et automates finis Automates finis Passage de l’AF (D ou N) vers l’ER Expression régulière et automates finis Automates finis Passage de l’AF (D ou N) vers l’ER Expression régulière et automates finis Automates finis Passage de l’ER vers l’AFN Soit E une expression régulière sur un alphabet Ω, on décompose d’abord E en ses sous expression élémentaires puis on applique les règles suivantes: Regle1: Si E est la chaîne vide ε, l’AFN correspondant est: Regle2: Si E=a Ω, l’AFN correspondant est: q2 q1 ε  q1 a q2 Regle2: Si E=a , l’AFN correspondant est: Regle3: Les AFN des expressions régulières E1|E2, E1.E2, (E1)+ et (E2)* (où E1 et E2 sont deux expressions régulières d’AFN correspondantsAFN(E1) etAFN(E2), ) sont: q2 101 AFN(E1) AFN(E1) AFN(E1|E2) AFN(E1) AFN(E2) AFN(E1.E2) AFN((E1)+) AFN((E2)*) Expression régulière et automates finis Automates finis Passage de l’ER vers l’AFD La stratégie la plus utilisée consiste à construire tout d’abord l’AFN correspondant ensuite on l’a convertit en un AFD ou on utilise la méthode de Gluskov Exercice à rendre le 30/12/2020 On utilisant la méthode de Gluskov, déterminer AFD de cette expression 1. On utilisant la méthode de Gluskov, déterminer AFD de cette expression régulière 00(0|1)*. 2. Déterminer AFN puis AFD de même expression 00(0|1)*. Email: fsdmtpinfo@gmail.com . Analyse lexical Définition À partir du programme source, qui se présente comme un flot de caractères, l'analyse lexicale permet de reconnaitre des unités lexicales, qui sont les mots que l'analyseur syntaxique va ensuite les utiliser. Analyseur Analyseur Unité lexicale Programme Analyseur lexical Analyseur syntaxique Table des symboles Prochaine unité lexicale? Programme source Remarques: 1-Les unités lexicales seront stockées au fur et à mesure dans la table de symboles. 2-L’opération du lecture du texte source doit s’accompagner avec des tâches supplémentaires: Eliminer les blancs, les commentaires, fin de lignes, gérer les numéros des lignes pour l’utiliser dans le cas d’une erreur rencontrée, ….. 3-L’analyseur lexical doit signaler chaque présence d’erreur dans le texte d’entrée. Analyse lexical Lexème, unité lexicale Lexème (ouToken): est une chaîne de caractères qui constitue une seule entité tirée à partir du texte source. Par exemple dans l’instruction suivante: aire:=base * hauteur / 2, l’analyseur lexical reconnaît les lexèmes suivants Unité lexicale: est un type de lexème qui est un symbole terminal qui rentre dans la construction du langage source. Unité lexicale: est un type de lexème qui est un symbole terminal qui rentre dans la construction du langage source. Pour l’exemple précédent, on trouve: 104 Lexèmes Unité lexicale aire , base , hauteur identificateur := op-affectation * , / op-arithmétique Analyse lexical Modèle Modèle: est une règle décrivant les lexèmes qui correspondent à une unité lexicale particulière. Nous utilisons les expressions régulières ou les automates finis pour représenter les modèles des unités lexicales. Exemple: - Modèle identificateur: - Modèle identificateur: 105 0 lettre lettre | _ | chiffre 1 Analyse lexical Spécification des unités lexicales Un identificateur: lettre(lettre|chiffre)* = [a-zA-Z][a-zA-Z0-9]* Un entier signé ou non: (+|-)? (chiffre)+ = [+-]?[0-9]+ Un nombre décimal: (+|-)? (chiffre)+ (.(chiffre)+)? Un réel: (+|-)?(chiffre)+(.(chiffre)+)?((e|E)(+|-)?(chiffre)+)? = [+-]?[0-9]+(.[0-9]+)?((e|E)(+|-)?[0-9]+)? Analyse lexical Spécification des unités lexicales Une définition régulière est une suite de définitions de la forme: d1 r1 Chaque di est un nom distinct d2 r2 et chaque ri est une expression d2 r2 et chaque ri est une expression . . ……… régulière. dn rn Nous allons voir quelques exemples de définitions régulières. Analyse lexical Spécification des unités lexicales Exemples: 1- Définition régulière d'un identificateur: 2- Définition régulière des entiers signés et non signés: Analyse lexical Spécification des unités lexicales 3- Définition régulière d'un réel: Analyse lexical Reconnaitre un mot par un automate: Exemple: Analyse lexical Exercice 1 1- Écrire une grammaire pour générer les identificateurs d’un langage comme Pascal ou C. On considérera qu’un identificateur est valide s’il commence par une lettre (majuscule ou minuscule) suivi d'un nombre quelconque (éventuellement aucun) de symboles. Ces symboles sont constitués par des lettres, des chiffres, et du caractère '_'. 2- Une constante de type chaîne de caractères est délimitée par des apostrophes et constituée d'un nombre quelconque de caractères. Pour permettre à une apostrophe de 2- Une constante de type chaîne de caractères est délimitée par des apostrophes et constituée d'un nombre quelconque de caractères. Pour permettre à une apostrophe de faire partie d'une chaîne de caractères, on double celle-ci. 2-1- Écrire la grammaire qui permet de générer cette unité lexicale. 2-2- Construire l’automate qui permet de reconnaitre cette unité lexicale. 2-3- Donner quelques lexèmes qui sont définis par cette unité lexicale. 2-4-Trouver des constantes qui ne sont pas reconnues par cette unité lexicale. 111 Analyse lexical Construction de l’analyseur lexical I- Implémenter tous les modèles (automates) représentant les unités lexicales du langage traité. Exemples: Identificateurs, Mots clés, Nombres, Opérations relationnelles, Opérations logiques, opérations arithmétiques, ……. II- Traiter le programme source caractère par caractère pour: - Extraire les lexèmes reconnus par leur automates et les enregistrer dans une table des symboles avec d’autre attributs attributs - Gérer les erreurs pour les lexèmes non reconnus. Exemples: x:=y+30 112 Lexèmes Unités lexicales Attributs x , y identificateur Adresse de x et y: Pour le GC Type de x et y: Pour l’AS := op-affectation + op-arithmétique 30 nombre Type: Pour l’AS uploads/Litterature/ diapo7-td-3.pdf