Scribd
Importer
10 vues48 pages

Analyse Lexicale et Automates Finis

Le document décrit la technique d'analyse lexicale. Il définit les notions de lexème et de jeton, et explique le processus d'analyse lexicale. Il présente ensuite les expressions régulières, les automates à états finis, et les méthodes de construction de Thompson et de déterminisation d'automates. Un exemple détaillé illustre ces concepts.

Transféré par

chaimaabaoub09
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
10 vues48 pages

Analyse Lexicale et Automates Finis

Le document décrit la technique d'analyse lexicale. Il définit les notions de lexème et de jeton, et explique le processus d'analyse lexicale. Il présente ensuite les expressions régulières, les automates à états finis, et les méthodes de construction de Thompson et de déterminisation d'automates. Un exemple détaillé illustre ces concepts.

Transféré par

chaimaabaoub09
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TECHNIQUE DE COMPILATION

ANALYSE LEXICALE

Hager MERDASSI

2023/2024
Plan

 Définitions

 Analyse Lexicale

 Automates et Expression régulière

 Construction Thompson

 Déterminisation d’un automate


Définition
Définition

.

 .

 .
Lexème

• While
• (
• ip
• <
• z
• )
• ++
• Ip
• ;
Analyse Lexicale

 Première étape:
Jeton (Token)

 .

 .
Jeton (Token)

 .
Analyse Lexicale

 .

 .
Expressions Régulières

.
Expressions Régulières

.
Expressions Régulières
Expressions Régulières
Automates à états finis
Automates à états finis
Représentation d’un automate
Notation
Notation
Champs d’application
Utilité des Automates
Utilité des Automates
Utilité des Automates
Types d ’Automates
Automate fini et expressions régulières
Automate fini et expressions régulières

Construction Thompson
Méthode de construction
Méthode de construction (rs)
Méthode de construction (r)|(s)
Méthode de construction (r)*
Automate fini et expressions régulières
De AFN ->AFD
Réduction
Exemple
Exemple
Exemple
Exemple
Exemple
De ER ->AFN (Construction de Thompson)
De ER ->AFN (Construction de Thompson)

Exemple:

R= 1*+0
De AFN ->AFD (Déterminisation)
De AFN ->AFD (Déterminisation)
Exercice (Thompson)

De l’expression régulière à l’automate fini déterministe


Sur l’alphabet {a, b}, donner l’automate fini déterministe
optimal reconnaissant le langage défini par l’expression
régulière suivante : (ab*)|(ab)*
Utiliser les algorithmes de Thompson, de déterminisation et
de minimisation.
Exercice (Thompson)
Solution
Exercice (Thompson)
Solution
Exercice (Thompson)
Solution
Déterminisation
Ɛ-fermeture (S0) = q0 = { S0 , S1 , S7 , S8 , S12 , S13 } q0 est un état initial et final.

Trans(q0, a)={ S2 , S9} ; Ɛ-fermeture (S2) = { S2 , S3 , S4 , S6 , S13 } ; Ɛ-fermeture (S9) = { S9 , S10};


Trans(q0, a)= q1 = { S2 , S3 , S4 , S6 , S9 , S10 , S13 } q1 est un état final.
Trans(q0, b)= Ø

Trans(q1, a)= Ø
Trans(q1, b)={ S5 , S11} ; Ɛ-fermeture (S5) = { S4 , S5 , S6 , S13 } ; Ɛ-fermeture (S11) = { S8 , S11 , S12, S13};
Trans(q1, b)= q2 = { S4 , S5 , S6 , S8 , S11 , S12 , S13 } q2 est un état final.
Exercice (Thompson)
Solution
Trans(q2, a)={ S9} ; Ɛ-fermeture (S9) = { S9 , S10} ; Trans(q2, a)= q3 = { S9 , S10} .
Trans(q2, b)={ S5} ; Ɛ-fermeture (S5) = { S4 , S5 , S6 , S13 } ; Trans(q2, b)= q4 = { S4 , S5 , S6 , S13 } q4 est un état
final.

Trans(q3, a)= Ø.
Trans(q3, b)={ S11} ; Ɛ-fermeture (S11) = { S8 , S11 , S12 , S13 } ; Trans(q3, b)= q5 = { S8 , S11 , S12 , S13 } q5 est un
état final.

Trans(q4, a)= Ø.
Trans(q4, b)={ S5} ; donc Trans(q4, b)= q4.

Trans(q5, a)={ S9} ; donc Trans(q5, a)= q3.


Trans(q5, b)= Ø.
Exercice (Thompson)
Solution

Le AFD correspondant est donc le suivant:


Exercice (Thompson)
Solution

Le AFD correspondant est donc le suivant:

En appliquant l’algorithme de Moore (algo de minimisation), on se rend


compte que cet automate est déjà minimal.

Vous aimerez peut-être aussi