Grammaire comme Structure de Graphe
Un compilateur traduit le code source en construisant un arbre d'analyse syntaxique — un arbre enraciné où chaque nœud représente une règle de grammaire appliquée, & chaque feuille représente un symbole terminal (nom de variable, littéral, opérateur).
Géométrie de l'Arbre
Un arbre avec n nœuds & n−1 arêtes. Profondeur d : la distance maximale de la racine à une feuille quelconque. Pour un arbre binaire équilibré de profondeur d : jusqu'à 2^d feuilles & 2^(d+1)−1 nœuds au total.
Les arbres d'analyse syntaxique pour les expressions typiques ne sont pas équilibrés : la précédence des opérateurs crée des arbres asymétriques à droite ou à gauche. A + B C produit un arbre où est plus profond que +, codant que * se lie plus fortement.
BNF & ALGOL
La forme de Backus-Naur (BNF), inventée pour spécifier ALGOL, formalise la grammaire en tant que règles de production :
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Chaque règle de production définit un niveau de l'arbre. La grammaire est un graphe dirigé sur les symboles non-terminaux ; l'analyse syntaxique d'une phrase trace un chemin à travers ce graphe du symbole de départ aux feuilles.
Profondeur de l'Arbre d'Analyse & Complexité des Expressions
Pour l'expression (A + B) * (C + D), l'arbre d'analyse syntaxique a une structure spécifique sous la précédence standard des opérateurs.
La profondeur d'un arbre d'analyse syntaxique affecte les performances du compilateur : les arbres plus profonds nécessitent plus de cadres de pile lors de l'analyse par descente récursive.
Entropie de Shannon & Redondance
Hamming a noté que la langue parlée est ~60% redondante, la langue écrite ~40%. Cela a un sens précis d'un point de vue théorique de l'information.
Entropie de Shannon
Pour une source générant des symboles d'un alphabet A avec les probabilités {p₁, p₂, ..., pₙ} :
H = −Σ pᵢ log₂(pᵢ) (bits par symbole)
Entropie maximale : distribution uniforme (tous les symboles également probables). H_max = log₂(n) pour n symboles.
Redondance R : fraction des bits qui ne portent pas d'information (pourrait être supprimée sans perdre le contenu) :
R = 1 − H / H_max
Si R = 0.4 (40% redondant) : 40% des bits peuvent être prédits à partir du contexte. Un canal véhiculant du texte anglais à 8 bits/caractère utilise seulement 60% de sa capacité pour l'information ; 40% est une structure que le récepteur connaît déjà.
La détection d'erreurs utilise la redondance : si 40% des bits sont prédictibles, une erreur de transmission peut produire une séquence qui viole la structure de redondance — détectable même sans codes de correction d'erreur.
La redondance quasi nulle d'APL : un changement d'un seul caractère est presque jamais détectable à partir du contexte seul. La redondance de 60% de l'anglais : vous pouvez souvent reconstruire un mot à partir du contexte environnant même si une lettre manque ou est erronée.
Calcul de la Redondance
Fréquence des lettres en anglais (approximatif) : 'e' apparaît ~12.7% du temps ; 'z' apparaît ~0.07%. L'entropie réelle de l'anglais est approximativement H ≈ 1.0 bit/caractère (en tenant compte du contexte au niveau des mots). Entropie maximale pour un alphabet de 26 lettres : H_max = log₂(26) ≈ 4.70 bits/caractère.
Courbes de Croissance en tant que Géométrie
Les algorithmes de compilation traitent des programmes de taille n (tokens, lignes ou nœuds). Le choix de l'algorithme détermine comment le temps de compilation augmente avec la taille du programme.
Classes de Complexité Courantes
| Classe | Temps d'Exécution | Exemple | |---|---|---| | O(n) | linéaire | analyse lexicale | | O(n log n) | quasi-linéaire | tri optimal | | O(n²) | quadratique | détection naïve de doublons | | O(n³) | cubique | multiplication matricielle, analyse CYK | | O(2ⁿ) | exponentielle | preuve de théorème naïve |
L'image géométrique : tracez le temps d'exécution en fonction de n. O(n) est une ligne. O(n²) est une parabole. O(2ⁿ) est une courbe exponentielle qui semble plate près de n=0 et presque verticale près de n=50.
L'analyse générale de la grammaire sans contexte (algorithme CYK) s'exécute en O(n³). Pour la plupart des langages de programmation pratiques, la grammaire est conçue pour être LR(1)-analysable, permettant une analyse O(n). La grammaire d'ALGOL était plus complexe que celle de FORTRAN, contribuant à des compilateurs plus lents — un frottement pratique qui importait en 1958 quand la compilation prenait des heures.
Points de Croisement
Une recherche naïve dans la table des symboles utilise O(n²) opérations totales pour un programme de n identificateurs (scan linéaire pour chacune des n recherches). Une table de symboles de table de hachage utilise O(n) opérations totales attendues.
Supposez : l'algorithme O(n²) s'exécute à 10⁶ opérations/sec sur le matériel de 1958. L'algorithme O(n) s'exécute à la même vitesse mais nécessite 100n opérations de configuration (construction de la table de hachage).