Construction d'un compilateur

Prérequis pour la construction d'un compilateur

• La compilation est la traduction d'un code source de haut niveau en code de bas niveau compréhensible par une machine.

Les étapes de la compilation

• Le processus de compilation est divisé en plusieurs étapes distinctes, chacune ayant un rôle spécifique.

Analyse Lexicale (Scanning)

• Le rôle est de convertir le code source en une séquence de lexèmes.
• Un lexème représente une unité lexicale de base telle qu'un mot-clé, un identificateur ou un opérateur.
• Par exemple, le code int x = 5; est transformé en INT, IDENTIFIER (x), EQUAL, INTEGER (5), SEMICOLON.

Analyse Syntaxique (Parsing)

• Le rôle est de vérifier la structure grammaticale du code source.
• Un arbre de syntaxe abstrait (AST) est une représentation hiérarchique du code.
• Par exemple, x = 5 + 2; est converti en un arbre représentant l'expression d'affectation.

Analyse Sémantique

• Le rôle est de vérifier la cohérence sémantique du code.
• Plusieurs vérifications sont effectuées, comme les types et la portée des variables.
• La table des symboles contient des informations sur les identificateurs.
• Par exemple, il est vérifié que x est déclaré avant d'être utilisé et que son type est compatible avec la valeur 5 + 2.

Génération de Code Intermédiaire

• Le rôle est de traduire l'AST en une représentation intermédiaire.
• L'avantage de cette étape est de faciliter l'optimisation et la génération du code cible.
• Par exemple, l'AST est traduit en code à trois adresses.

Optimisation du Code

• Le rôle est d'améliorer le code intermédiaire pour réduire son temps d'exécution ou sa taille.
• Les techniques utilisées sont la suppression du code mort, la propagation des constantes (loop unrolling), etc.

Génération de Code Cible

• Le rôle est de traduire le code intermédiaire optimisé en code machine ou assembleur.
• Les spécificités dépendent de l'architecture cible.
• Par exemple, génération de code assembleur pour une architecture x86.

Structure d'un compilateur

Front-End

• Le rôle est d'effectuer l'analyse du code source (lexicale, syntaxique et sémantique).
• Le front-end est indépendant de l'architecture cible.

Back-End

• Le rôle est d'effectuer la génération de code intermédiaire, l'optimisation et la génération de code cible.
• Le back-end dépend de l'architecture cible.

Outils pour la construction d'un compilateur

• Lex/Flex sont utilisés comme analyseurs lexicaux.
• Yacc/Bison sont utilisés comme analyseurs syntaxiques.
• Les langages de programmation utilisés sont C/C++, Java etc.
• Les frameworks comme LLVM sont utilisés pour l'optimisation et la génération de code.

Représentation intermédiaire

Intérêt

• La portabilité permet de cibler différentes architectures sans modifier le front-end.
• L'optimisation facilite l'application des techniques d'optimisation.

Formes courantes

• Le code à trois adresses contient des instructions simples avec au plus trois opérandes.
• L'arbre de syntaxe abstrait (AST) est une autre forme courante de représentation intermédiaire.

Gestion des erreurs

Importance

• Il est important de détecter et de signaler les erreurs de manière précise et informative.
• Les types d'erreurs incluent les erreurs lexicales, syntaxiques et sémantiques.
• La gestion des erreurs comprend l'affichage de messages d'erreur clairs et la reprise après erreur pour analyser le reste du code.

Table des symboles

Contenu

• La table des symboles contient les identificateurs, les noms des variables et les fonctions.
• Les attributs sont le type, la portée, l'adresse mémoire, etc.

Rôle

• Le rôle est de stocker et de retrouver les informations sur les identificateurs.
• La table des symboles est utilisée lors de l'analyse sémantique et de la génération de code.

Théorème de Bayes

• En théorie des probabilités et en statistique, le théorème de Bayes décrit la probabilité d'un événement, en se basant sur la connaissance préalable de conditions qui peuvent être liées à cet événement.
• La formule du théorème de Bayes est exprimée comme : $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$

Définitions

• $P(A|B)$ est la probabilité conditionnelle de $A$, sachant que $B$ est vrai.
• $P(B|A)$ est la probabilité conditionnelle de $B$, sachant que $A$ est vrai.
• $P(A)$ et $P(B)$ sont les probabilités que $A$ et $B$ soient vrais indépendamment.

Déduction du Théorème

• La compréhension du théorème de Bayes nécessite la connaissance de concepts de base en probabilité.

Probabilité Conditionnelle

• La probabilité conditionnelle d'un événement $A$, sachant qu'un événement $B$ s'est produit, est définie comme $P(A|B) = \frac{P(A \cap B)}{P(B)}$.
• $P(A \cap B)$ est la probabilité que les deux événements $A$ et $B$ se produisent.

Démonstration

• Définition de la probabilité conditionnelle :
  • $P(A|B) = \frac{P(A \cap B)}{P(B)}$
  • $P(B|A) = \frac{P(B \cap A)}{P(A)}$
• Isolation de l'intersection :
  • $P(A \cap B) = P(A|B) \cdot P(B)$
  • $P(B \cap A) = P(B|A) \cdot P(A)$
• Égalisation des intersections (car $P(A \cap B) = P(B \cap A)$):
  • $P(A|B) \cdot P(B) = P(B|A) \cdot P(A)$
• Résolution pour $P(A|B)$:
  • $P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$

Exemple Pratique

• Une entreprise a deux usines produisant des ampoules. L'usine A produit 60% des ampoules avec un taux de défaut de 3%, tandis que l'usine B produit 40% avec un taux de défaut de 5%. Si une ampoule est sélectionnée au hasard et est défectueuse, la probabilité qu'elle ait été produite à l'usine A est calculée comme suit.

Définition des Événements

• $A$: Ampoule produite à l'usine A
• $B$: Ampoule produite à l'usine B
• $D$: Ampoule défectueuse

Probabilités Connues

• $P(A) = 0.60$ (Probabilité qu'une ampoule provienne de l'usine A)
• $P(B) = 0.40$ (Probabilité qu'une ampoule provienne de l'usine B)
• $P(D|A) = 0.03$ (Probabilité qu'une ampoule soit défectueuse, sachant qu'elle provient de l'usine A)
• $P(D|B) = 0.05$ (Probabilité qu'une ampoule soit défectueuse, sachant qu'elle provient de l'usine B)

Calcul de $P(D)$

• La probabilité totale qu'une ampoule soit défectueuse, $P(D)$, est calculée en utilisant la loi de la probabilité totale : $P(D) = P(D|A) \cdot P(A) + P(D|B) \cdot P(B)$
• $P(D) = (0.03 \cdot 0.60) + (0.05 \cdot 0.40) = 0.018 + 0.02 = 0.038$

Application du Théorème de Bayes

• La probabilité que l'ampoule défectueuse ait été produite à l'usine A est calculée en utilisant le théorème de Bayes :

  • $P(A|D) = \frac{P(D|A) \cdot P(A)}{P(D)}$
  • $P(A|D) = \frac{0.03 \cdot 0.60}{0.038} = \frac{0.018}{0.038} \approx 0.4737$

• La probabilité qu'une ampoule défectueuse ait été produite à l'usine A est d'environ 47.37%.