Introduction aux langages et compilateurs

Langues naturelles

Dans les langues, une phrase est une séquence de mots et un mot, aussi appelé lexème (unité lexicale), est une séquence de caractères (possiblement d'un seul). L'ensemble des caractères utilisés par une langue est un ensemble fini. Des phrases, il y en a une infinité (pas de limite sur leur longueur). On utilise un dictionnaire pour lister tous les mots. Les lexèmes sont habituellement classé en différentes catégories lexicales, comme verbes, noms, pronoms, prépositions, etc. On utilise une grammaire (aussi appelée ensemble des règles syntaxiques) pour déterminer quelle séquence de mots est une phrase bien formée (seulement de telles séquences font partie de la langue). Les phrases bien formées ont normalement un certain sens ou signification que les humains peuvent comprendre.

Exemples de phrases françaises

• le lapin voit le renard.
• la mouche sent le fromage.
• le lapin est gris.
• la mouche est grise.
• le lapin voit le renard rouge.
• le lapin gris voit le renard.
• le lapin voit le renard qui regarde la souris.
• la mouche sent le fromage qui émet une odeur.
• le lapin voit le renard qui regarde la souris qui mange une noix.
• le lapin voit le renard qui regarde la souris qui est grise.
• le lapin voit le renard qui est gris.
• le lapin qui est réveillé voit le renard.
• le lapin qui voit le renard est réveillé.
• le lapin qui voit le renard qui voit la souris est réveillé.
• le garçon donne le livre à la fille.
• le garçon donne le livre qui transmet la tradition qui est importante à la génération future à la fille.

Analyse des phrases à trois niveaux:

• Analyse lexicale: identification des mots à partir des caractères
  • les mots sont groupés en catégories: articles, noms, verbes, adjectifs, prépositions, pronoms, mots spéciales (est, et, si, etc.)
  • Lexique: liste des mots dans chaque catégorie
  • Chaque catégorie a des attributs: e.g. genre d'un article, d'un nom; verbe peut être transitif, etc.
  • règles de déclinaison et de conjugaison
• Analyse syntaxique: comment les mots peuvent être combinés pour obtenir une phrase valide
  • régles syntaxiques: ordres possibles des catégories lexicales, e.g. article - nom - verbe - article - nom
    • on utilise des règles récursives: e.g. le lapin qui voit le renard qui voit le chien qui ...
  • règles contextuelles: contraintes supplémentaires en relation avec les attributs des catégories lexicales. E.g. le genre de l'article ou de l'adjectif doit suivre le genre du nom
• Analyse du sens: difficile à formaliser

Exemples de phrases françaises avec des problèmes

• voit lapin.
• le lapin mange gris.
• la lapin est gris.
• le lapin est grise.
• le garçon donne le livre qui transmet la tradition qui est important à la génération future à la fille.
• la mouche sent le fromage qui regarde la souris.

Vision orientée objet de l'analyse de phrases

• Analyse lexicale: Chaque catégorie de mots correspond à une classe d'objets avec certains attributs. Toutes ces classes sont une spécialisation de la class Mot avec l'attribut Épélation (la chaîne de caractères le représentant). Voici des examples:
  • Nom : avec les attributs Gendre (avec valeur masculin ou feminain), Pluriel (booléen).
  • Article : avec les mêmes attributs.
  • Verbe : avec les attributs Personne (avec valeur 1 à 3), Pluriel (booléen), Temps (...), etc.
    • Note: les attributs sont importants pour vérifier des contraintes grammaticales dans une phrase.
• Analyse syntaxique: On distingue différents "catégories syntaxiques", c'est-à-dire des composantes de phrases. On peut aussi les considérer comme des classes d'objets. Chaque catégorie a certains règles qui déterminent comment une objet de cette nature est composé de mots et d'autres objets syntaxiques. Toutes ces catégories sont des spécialisation de la classe Composante qui a un attribut Épélation qui contient le contenu de la phrase comme il est épélé. Voici des examples:
  • Phrase-simple : Il y a différentes règles alternatives pour former une phrase simple, tel que:
    • Elle contient, dans l'ordre de gauche à droite, les éléments suivants: Article, Nom, Verbe, Complément-d-objet
  • Complément-d-objet : Il est construit d'aprés une des alternatives suivantes:
    • vide (non existant)
    • Article, Nom
    • Article, Nom, Adjectif
  • Phrase-composée : Elle peut être formée d'après les règles suivantes:
    • Phrase-simple, Conjonction, Phrase-simple (par exemple, la phrase: "le lapin regarde le renard mais le renard dort")
    • Phrase-simple, Conjonction, Phrase-composée (Note: cette règle récursive - Phrase-composée apparait dans sa définition -  permet de former des phrases arbitrairement longues.)
    • Exercise: Donnez des règles syntaxiques supplémentaires qui pouraient s'appliquer pour les phrases françaises données en exemple ci-haut, comme par exemple "le lapin qui est réveillé voit le renard".
• On peut former des structures d'arbres pour représenter comment une phrase est composée de catégories syntaxiques et de mots de certain catégories. On appelle cela des arbres syntaxiques. Voici l'arbre syntaxique pour "le lapin regarde le renard mais le renard dort":
  •                                                            Phrase-composée
  •                                            /                               |                \
  •                       Phrase-simple                       Conjunction        Phrase-simple
  •          /          /        |             \                             mais                  /          |         \ 
  • Article   Nom   Verbe   Complément-d-objet                     Article     Nom     Verbe 
  •     le     lapin   regarde         /            \                                 le        renard     dort
  •                                         Article    Nom                          
  •                                           le         renard
• On appele  les objets qui se trouvent comme feuilles dans l'arbre syntaxique des "terminaux", et les autres objets dans l'arbre des "non-terminaux".

Langages informatiques

Similairement, dans les langages informatiques, un parle d'un programme (correspondant à une phrase) qui est une séquence d'unités lexicales, et une unité lexicale (ou lexème) est une séquence de caractères.

• Ce sont les règles lexicales qui déterminent quels sont les lexèmes valables du langage; on distingues normalement différentes catégories lexicales, comme identificateurs, nombres, chaînes de caractères, opérateurs, séparateurs, etc... (Note: certains livres utilisent le nom "token" pour désigner une catégorie lexicale) [voir examples].
• Ce sont les règles syntaxiques qui déterminent quelle séquence de lexèmes est un programme bien formé.
• Le sens d'un programme bien formé est aussi appelé sa sémantique. Dépendant de la nature du langage, le sens pourrait être la fonction de calcul que le programme représente, ou le comportement du système temps réel qui est réalisé quand il s'exécute, ou bien d'autres choses.

Le traitement de langages

Un compilateur traduit un programme bien formé dans le langage source en programme objet (dans un autre langage, appelé langage cible). On veut normalement que la sémantique du programme (comme définie dans le langage source) soit le même que la sémantique du programme objet (comme définie dans le langage cible); cela veut dire que le programme objet, quand il est exécuté, réalise le sens du programme source. Des fois, on dit aussi que la sémantique du programme source est le programme objet; cela dépend de la nature du problème.

Normalement, un compilateur réalise la traduction en plusieurs étapes; correspondemment, il contient plusieurs composantes. Cela peut être représenté de différentes manières, comme par exemple par les diagrammes suivants: Version-1 , Version-2.

Comme indiqué ci-haut, la définition de ce qui est une phrase valide dans une langue, ou un programme valide, se fait à deux niveaux:

• Les règles lexicales déterminent quelle séquences de caractères sont des lexèmes valables, et
• Les règles synaxiques déterminent quelle séquences de lexèmes sont des programmes valables. Les règles syntaxiques sont normalement définies en deux étapes:
  • les règles d'une syntaxe hors-contexte définies par une grammaire hors-contexte (voir chapitre sur l'analyse syntaxique), et
  • les contraintes sémantiques qui donnent des contraintes supplémentaires qui doivent être satisfaites par un programme valide (par exemple, les règles de typage en Java).

Ces règles peuvent être exprimées de différentes manières et en utilisant différents formalismes. En général, les règles syntaxiques sont plus complexes que les règles lexicales. Donc, les formalismes utilisés pour exprimer les règles syntaxique d'une langue ou d'un langage sont normalement plus puissant que les formalismes utilisés pour décrire les règles lexicales. Certains formalismes peuvent être utilisés pour décrire les deux, comme par exemple les grammaires formels (voir le chapitre 2.3 de ce cours).

En général, il y a deux problèmes à résoudre en relation avec de langages informatique (et aussi avec les langues naturelles quand elles sont traitées par ordinateur):

• La génération de toutes les programmes valides (ou leur génération dans ordre de leur longueur, dans le cas qu'il y en a une infinité)
• La reconnaissance (ou analyse), c'est-à-dire, déterminer si un programme donné (séquence de caractères donnée) est un programme valide.

Certains formalismes de définition sont plus apte à résoudre le problème de génération, tandis que d'autres sont plus aptes à résoudre le problème de reconnaissance. Le compilateur, évidemment, doit résoudre le problème de reconnaissance.

Dans ce qui suit, nous allons étudier les problèmes associés à l'analyse lexicale et syntaxique des languages.

Dernière mise à jour: le 3 février,  2015