Compilation: Historique Au début de l’informatique, on programmait directement les ordinateurs en langage machine. Cela s’est vite avéré fastidieux. On a très vite essayé d’utiliser les possibilités de l’informatique pour faciliter le travail de programmation. En premier lieu on a donné des informations symboliques, ce que l’on appelle aussi des mnémoniques, aux instructions machines. Cela a été l’assembleur. Par exemple on a codé MOV A0, A1 une instruction qui était notée auparavant 0A43 en hexadécimal.

     Ensuite on a utilisé des étiquettes pour exprimer les branchements. Cela a donné des instructions de la forme : BRANCH boucle ; à la place d’une instruction de la forme BRANCH -24 où -24 est le déplacement qu’il faut effectuer dans le programme. Enfin, on a exprimé directement des places mémoires en leur donnant un nom symbolique à la place de l’adresse en hexadécimal.

     L’étape suivante a consisté à s’affranchir complètement de la machine en élaborant ce que l’on appelle des langages de haut niveau. Ces langages ont introduit un certaine nombre de constructions qui n’existent pas dans le langage de la machine : expressions arithmétiques, variables locales, procédures et fonctions avec des paramètres qui retournent un résultat, structures de données (tableaux, énumération, record, objet,..), etc.

     Pour cela il a fallu construire des programmes qui traduisent des énoncés exprimés dans le langage de haut niveau utilisé par les programmeurs, ce que l’on appelle le langage source, en instructions pour la machine cible. Les programmes effectuant ce genre d’opération s’appellent des compilateurs (ou des interprètes, nous verrons la différence par la suite, mais pour l’instant elle n’est pas fondamentale).

Grammaire: Une grammaire est un ensemble de règles permettant de dire si une phrase, c'est-à-dire une suite de mots ou lexèmes (cf. l’analyse lexicale), est correcte ou non. Les règles qui nous intéressent en informatique sont celles qui donnent une description générative du langage, en indiquant comment précisément construire de telles phrase.

Par exemple une définition générative est la suivante : Une phrase se compose d’une proposition sujet, d’un verbe et d’une proposition complément.

     Alors qu’une définition de la forme : La subordonnée relative complète un nom ou un groupe nominal appartenant à la proposition principale n’est pas générative : elle ne nous dit pas comment effectivement construire une subordonnée relative.