Automates finis et analyse lexicale

Automates finis et expressions régulières

Une machine à états finis est un modèle mathématique d'un système qui prend une chaîne constituée de symboles d'un alphabet et détermine si cette chaîne appartient au langage reconnu par le contrôleur.

Formellement, une machine à états finis peut être décrite comme un quintuple (S, Σ, T, s, A) où :

• S : ensemble d'états
• Σ : alphabet
• T : fonction de transition
• s : état initial
• A : ensemble des états finals (ou d'acceptation)

Formes de représentation des automates finis

En plus de sa définition formelle, une machine à états finis peut être représentée par d'autres notations plus pratiques, telles que les tables de transition, les diagrammes de transition et les expressions régulières.

Analyseur lexical

L'analyseur a pour fonction principale de prendre une séquence de caractères ou de symboles de l'alphabet de la langue et de les classer dans des catégories appelées unités lexicales. Ces unités sont utilisées par l'analyseur syntaxique pour déterminer si le programme source est grammaticalement correct. Certaines unités lexicales sont filtrées (comme les commentaires ou les espaces) et ne sont pas transmises à l'analyseur syntaxique.

La terminologie utilisée dans la construction d'un analyseur est la suivante :

• Motif : représente la règle définissant une séquence de caractères comme une unité lexicale.
• Lexème : est la valeur réelle d'une séquence de caractères satisfaisant un motif.
• Token : est la valeur associée à une unité lexicale, souvent représentée par un entier.
• Caractères : symboles alphabétiques valides pour une langue donnée.
• Unités lexicales : catégories classant les chaînes valides dans une langue.

Rôle de l'analyseur lexical

Bien que l'analyseur lexical soit la première étape du processus de compilation, il ne démarre pas de lui-même. C'est l'analyseur syntaxique qui initie le processus en demandant un token à l'analyseur lexical. Au cours de ces étapes, une communication étroite est maintenue avec la table des symboles, qui centralise les informations sur les entités utilisées dans les programmes.

Description de motif

Il existe trois façons de décrire les motifs : la description informelle (langage naturel), les expressions régulières et les automates finis sous forme de diagrammes de transition.

Diagrammes de transition

Un diagramme de transition est la représentation graphique d'un ensemble d'états (initiaux, intermédiaires ou finaux) pouvant avoir une ou plusieurs sorties vers d'autres états.

Les états initiaux sont représentés par un cercle, les intermédiaires par un cercle numéroté, et les états finaux par un double cercle. Les états sont reliés entre eux par des transitions étiquetées avec le caractère ou l'ensemble de caractères provoquant le passage d'un état à un autre.

Caractéristiques des diagrammes de transition

• Chaque état doit être atteint avec le même jeu de caractères à chaque transition.
• Chaque modèle possède un sélecteur de caractère permettant de reconnaître le modèle à appliquer de manière unique.
• Pour atteindre un état d'acceptation, il doit y avoir une transition sur le caractère qui termine l'unité lexicale.

Descriptions informelles des unités lexicales

• Identifiant : une lettre suivie ou non par d'autres lettres, chiffres ou caractères de soulignement.
• Commentaires : commencent par /* et se terminent par */.
• EOF : indique la fin du fichier.
• Erreur : tout symbole ne se conformant pas aux règles précédentes.