Exercices compilation luc brun Théorie des langages-tél...

Théorie des langages : Exercices compilation luc brun

Télécharger PDF

Qu'est-ce que la compilation ?

La compilation est l'analyse automatique d'un langage (avec un vocabulaire et une syntaxe). Elle inclut des actions telles que l'interprétation de langages comme JavaScript, Python, shell, SQL, ainsi que l'édition structurée et le contrôle statique.

Définition et synthèse

La compilation va au-delà de la génération de code exécutable à partir de langages sources. Elle pose également la question des langages compréhensibles sans ambiguïté.

Structure d'un compilateur

Un compilateur se compose de plusieurs étapes :

Analyse lexicale : vérifie et reconnaît le vocabulaire (identificateurs, mots-clés, etc.).
Analyse syntaxique : vérifie et reconnaît la grammaire.
Analyse sémantique : vérifie le sens du programme (par exemple, les types).

Un langage intermédiaire (RI) permet de factoriser des étapes pour plusieurs langages.

Analyse lexicale

L'analyse lexicale transforme un ensemble de caractères en concepts (nombres, identificateurs, mots-clés, etc.). Voici les principaux éléments :

Unité lexicale : correspond à une entité (un concept) reconnue par l'analyseur lexical. Par exemple, <, >, <=, >=, ==, et != sont des opérateurs relationnels.
Lexème : une instance d'une unité lexicale. Par exemple, le lexème 6.28 est une instance de l'unité lexicale nombre.
Modèle : associe des lexèmes à leur unité lexicale.

Éléments de théorie des langages

Un alphabet Σ est un ensemble fini de symboles. Par exemple, l'alphabet binaire {0, 1}, les codes ASCII, ou {A, G, C, T} pour l'ADN.

Une chaîne est une séquence finie de symboles. On utilise aussi le terme mot.

Préfixe : obtenu en supprimant un nombre quelconque de caractères en fin de chaîne.
Suffixe : obtenu en supprimant un nombre quelconque de caractères en début de chaîne.
Sous-chaîne : obtenue en supprimant un préfixe et/ou un suffixe.
Préfixe/suffixe propre : un préfixe, suffixe ou sous-chaîne qui n'est pas égal à la chaîne initiale.
Sous-suite : toute chaîne obtenue en supprimant des caractères de la chaîne initiale.

Langages et opérations

Un langage est un ensemble de chaînes construites sur un alphabet. Par exemple, les codes source en C, les nombres binaires ou les séquences ADN.

Union (L ∪ M) : L ∪ M = {s | s ∈ L ou s ∈ M}.
Concaténation (LM) : LM = {st | s ∈ L et t ∈ M}.
Fermeture de Kleene (L*) : L* = ∞⋃_i=0L_i.
Fermeture positive (L+) : L+ = ∞⋃_i=1L_i.

Exemples d'opérations sur les langages

Si B = {0, 1}, alors B+ est l'ensemble des nombres binaires d'au moins un chiffre.
Si C = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, alors C⁴ est l'ensemble des nombres de 4 chiffres.
Si K = {a,...,z, A,...,Z}, alors K(K ∪ C)* est l'ensemble des mots commençant par une lettre, suivis d'un nombre quelconque de lettres et chiffres.

Expressions régulières

Une expression régulière est construite récursivement à partir d'une union (notée |), de concaténation et de fermeture. Elle définit un langage L(r).

∅ est une expression régulière qui désigne L(∅) = {∅}.
a ∈ Σ est une expression régulière qui désigne L(a) = {a}.
(r) est une expression régulière désignant L(r).
(r)|(s) est une expression régulière désignant L(r) ∪ L(s).
(r)(s) est une expression régulière désignant L(r)L(s).
(r)* est une expression régulière désignant L(r)*.

Exemple d'expressions régulières

Soit Σ = {a, b} :

L(a|b) = {a, b}.
L((a|b)(a|b)) = {aa, ab, ba, bb}.
L(a*) = {∅, a, a², ...}.
{a, a², b, b², ab, ab², a²b², ...} ⊂ L((a|b)*).

Propriétés algébriques des expressions régulières

Axiome	Description
r\|s = s\|r	est commutatif
r\|(s\|t) = (r\|s)\|t	est associatif
(rs)t = r(st)	la concaténation est associative
r(s\|t) = rs\|rt	la concaténation est distributive vis-à-vis de \|
(s\|t)r = sr\|tr
∅r = r∅ = r	∅ est un élément neutre pour la concaténation
r* = (r\|∅)*	r* est idempotent
r** = r*	* est idempotent

Définitions régulières

Il est pratique de donner des noms à des expressions régulières et de s'en servir dans des expressions plus complexes. Pour cela, on utilise des définitions régulières.

Soit Σ un alphabet et un ensemble de couples d₁ → r₁, d₂ → r₂, ..., d_n → r_n où chaque r_i est une expression régulière et d_i son nom associé.

Exemple de définitions régulières

Identificateurs de variables :

lettre → a|b|c|...|z|A|B|...|Z
chiffre → 0|1|2|3|4|5|6|7|8|9
id → lettre(lettre|chiffre)*

Nombres :

pm → (+|−)
chiffre → 0|1|2|3|4|5|6|7|8|9
frac → .chiffre+
exp → E(pm|∅)chiffre+
nb → (pm|∅)(chiffre+(frac|∅)|frac)(exp|∅)

Notations abrégées et limites des expressions régulières

Notations abrégées :

L'expression (r|∅) se note également r?. Par exemple, exp → E(pm|∅)chiffre+ se note exp → Epm?chiffre+.
(a|b|c) se note également [abc].
L'ensemble des identificateurs se note : [a-zA-Z][a-zA-Z0-9]*.

Limites des expressions régulières :

Les expressions régulières ne permettent pas de coder tous les langages, notamment celles nécessitant une opération de comptage. Par exemple, le langage L = {wcw | w ∈ L({a, b}*)} n'est pas régulier.

Unités lexicales et diagrammes de transition

Un diagramme de transition est une représentation graphique du processus de reconnaissance d'une unité lexicale. Il montre les actions réalisées par l'analyseur lexical sur le tampon d'entrée lorsqu'il est appelé par l'analyseur syntaxique.

Un diagramme de transition est constitué d'états : internes et finaux. Les états finaux peuvent être sans ou avec recul de tampon. Les arcs indiquent les transitions entre états avec des étiquettes précisant les entrées.

Exemple de diagramme de transition

oprel → (<|>|<=|>=|==|!=)
id → lettre(lettre|chiffre)*

Automates finis non déterministes (AFN)

Un AFN est un modèle mathématique défini par :

Un ensemble d'états E.
Un ensemble de symboles d'entrée Σ.
Une fonction de transition Transiter qui associe des couples (état, symbole) à des ensembles d'états.
Un état initial e₀.
Un ensemble d'états finaux F.

Le langage défini par un AFN est l'ensemble des chaînes menant à un état d'acceptation.

Exemple d'AFN

Unité lexicale : (a|b)*abb.
Table de transition :

Transiter :

Etat : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Symbole d'entrée : a, b
Transitions : 0 → {0, 1} sur a, 1 → {2} sur b, etc.

Construction récursive d'un AFN à partir d'une expression régulière

Pour ∅, construire un AFN avec un état de départ et un état final sans transition.
Pour a ∈ Σ, construire un AFN avec un état de départ, un état final et une transition sur a.
Pour N(s|t), l'AFN est défini par :

Un état initial commun.
Deux états finaux distincts.

Pour N(st), l'AFN est défini par :

L'état final de N(s) est relié à l'état initial de N(t).

Pour N(s*), l'AFN est défini par :

L'état final de N(s) est relié à l'état initial de N(s) via une boucle.

Propriétés de l'AFN construit

N(r) a au plus deux fois plus d'états que le nombre de symboles dans r.
N(r) a exactement un état de départ et un état d'acceptation, sans transition sortante.
Chaque état de N(r) a soit une transition sortante sur un symbole de Σ, soit au plus deux transitions sortantes sur ∅.

Exemple de construction d'AFN

Construction de l'AFN pour (a|b)*abb.

Transformation d'un AFN en Automate fini déterministe (AFD)

Un AFD est un automate où aucun état n'a de transition sur ∅ et où chaque état et chaque symbole a au plus une transition.

Reconnaissance d'un lexème par un AFD

La reconnaissance d'un lexème par un AFD calcule une suite d'états. L'algorithme est le suivant :

Début avec l'état initial e₀.
Lire le caractère suivant.
Tant que le caractère n'est pas une fin de fichier, faire :

Transiter vers l'état suivant.
Lire le caractère suivant.

Retourner vrai si l'état final est atteint.

Exemple de transformation d'AFN en AFD

Transformation de l'AFN pour (a|b)*abb en AFD.

Discussion sur les automates

La reconnaissance d'un lexème par un AFD est plus rapide qu'avec un AFN, mais le nombre d'états peut être exponentiel par rapport à l'AFN.

Automate	Place	Temps
AFN	O(\|r\|)	O(\|r\|*\|x\|)
AFD	O(2^\|r\|)	O(\|x\|)

Un outil d'analyse lexicale : Lex

Lex est un analyseur lexical combiné avec Yacc pour produire des compilateurs en C. Ses cousins pour le C++ sont Flex et Bison.

Syntaxe des expressions régulières en Lex

x : le caractère "x".
. : n'importe quel caractère sauf \n.
[xyz] : soit x, soit y, soit z.
[^bz] : tous les caractères sauf b et z.
[a-z] : n'importe quel caractère entre a et z.
[^a-z] : tous les caractères sauf ceux compris entre a et z.
r* : zéro ou plus r.