Créer son propre langage de programmation de A à Z

<< Introduction | Notion de grammaire et langage formel | Syntaxe du langage Simple >>

Théorie des langages

Je ne vais pas m'étendre très longtemps sur cette partie. D'autant que je ne suis pas expert sur ce point. Néanmoins c'est une partie primordiale pour la suite. Il faut savoir que tout les langages informatiques sont des langages formels. Leur particularité est d'avoir des règles grammaticales strictes. C'est ce qui les différencie des langages naturels qui sont les langages parlés des êtres humains (oui nos langues en fait). Même si la langue française par exemple, a une grammaire qu'il faut respecter, quelques petites fautes de français ne vont pas forcément impacter la compréhension du destinataire qui est logiquement humain. En revanche pour un compilateur, qui n'est qu'autre qu'un programme informatique, il est certain qu'il ne comprendra pas et donc ne fera aucune traduction. Juste parce qu'il peut manquer un point à une phrase ou que la majuscule du début de la phrase a été oubliée. Un compilateur est très stricte et n'est pas du tout subtil. Aucune possibilité donc de déformer des mots pour donner un certain ton humoristique à une phrase ou faire des jeux de mots. Si c'est pas dans la grammaire du langage, le compilateur ne comprend pas. Alors qu'un humain possède une intelligence et va chercher à comprendre le message, le compilateur non. Il n'est pas fait pour comprendre mais pour traduire (sauf si le compilateur est doté d'une intelligence artificielle, on peut dans ce cas imaginer qu'il puisse déduire et suggérer des traductions). C'est pourquoi tout les langages informatiques sont des langages formels.

Les traducteurs de langues comme Google Traduction sont bien des compilateurs. Bien qu'ils soient complets, on peut toujours voir des erreurs au résultat produit. En effet comme tout compilateur, les traducteurs automatiques de langues traduisent des langages formels. Or une langue est un langage naturel. Les développeurs ont donc dû essayer de formaliser le plus possible nos langues, c'est à dire les transformer en langage formel. Mais la formalisation d'un langage naturel est assez compliquée car une langue évolue constamment (presque quotidiennement). De même, il n'existe pas toujours de traduction possible d'un langage à l'autre. On ne peut donc pas avoir une formalisation parfaite et aboutie d'un langage naturel. De ce fait la plupart des traducteurs en ligne disposent d'algorithmes d'intelligence artificielle. Tout est alors fondé dans ce cas-là sur de la déduction à partir de faits et de règles stockées dans des bases de connaissances. Ces bases de connaissances (contenant en fait des règles grammaticales) sont alimentées au fur et à mesure que des utilisateurs font des suggestions au programme. Ce dernier les retient et les proposera au moment venu, quand un autre utilisateur lui demandera la traduction de la même phrase. Il apprend donc de ses utilisateurs, comme nous nous apprenons de notre environnement. C'est un peu un compilateur qui évolue tout le temps. C'est de l'apprentissage automatique, une des disciplines fondamentales de l'intelligence artificielle, et l'ordinateur est bien plus fort que nous pour stocker des données rapidement et en grande quantité. D'ailleurs lorsque l'ordinateur pourra apprendre automatiquement de son environnement extérieur et pas seulement que de nous, c'est à dire lorsqu'il pourra constituer et enrichir à lui seul de manière totalement autonome sa base de connaissances, alors il est fort possible qu'il sera au même niveau intellectuel que l'Homme voir le dépassera.

Rassurons-nous, cela ne le fera quand même pas disposer du libre arbitre et par conséquent ne lui donnera aucun pouvoir à prendre des initiatives. Autrement dit, Chappie, iRobot, Skynet et compagnie ne verrons jamais le jour tant que l'on aura pas perçé le mystérieux secret du libre arbitre. Plutôt difficile quand on a déjà bien du mal à le définir ou que l'on remet même en question l'existence du notre...

Réaction de Bender (le robot) après que le Pr. Hubert Farnsworth lui annonce qu'il n'a pas de libre arbitre - Episode 7 de la saison 9 de Futurama

Réaction de Bender (le robot) après que le Pr. Hubert Farnsworth lui annonce qu'il n'a pas de libre arbitre - Episode 9 de la saison 7 de Futurama. Ce qui est assez amusant dans cet épisode, c'est qu'avant que Bender connaisse la vérité, on voyait en lui un robot humanoïde assez libre de ses choix. Le pire c'est qu'il en ait persuadé de cette liberté. Ce n'est qu'au moment où il apprend que ses choix étaient tous programmés qui perd confiance en lui, n'étant finalement plus maître de son destin. C'est assez philosophique car la même question peut se poser pour nous finalement. - © MTV Networks / Futurama

Bon je m'éloigne pas mal du sujet mais j'aime bien ces petites réflexions... Bref, dans le cas d'un traducteur en ligne comme celui de Google par exemple, plus il y a de personnes qui l'utilisent et lui proposent des traductions équivalentes, plus le programme s'améliore. Il s'améliore de son expérience de traduction ! Et pour les moteurs de recherche en ligne, cela fonctionne aussi sur le même principe. Le moteur de recherche en ligne Google s'adapte à la personne au fur et à mesure qu'elle l'utilise. Selon les résultats qui intéressent l'utilisateur, le moteur est capable de construire un profil d'intérêt et va lui fournir de meilleurs résultats en lui mettant en premiere liste que ceux qui correspondent le plus au profil. Pour un même mot recherché sur le moteur de recherche Google, on n'aura pas forcément les mêmes résultats si on a bien sûr pas effacé nos données de navigation (historique, cookies... etc).

Petite parenthèse à propos des traducteurs : j'ai trouvé sur YouTube cette vidéo de Linguisticae qui présente avec humour le fonctionnement de Google Traduction dans ses grandes lignes. Si vous avez le temps de la visionner, je ne peux que vous conseiller de la regarder car c'est plutôt intéressant (et ça vous fait une pause dans le cours, c'est bien aussi !) :

Il faut savoir qu'un langage formel est un objet mathématique. Plus précisément ce n'est qu'un simple ensemble de mots. En mathématiques, les mots sont des suites d'éléments, les lettres, compris eux-même dans un autre ensemble appelé alphabet. Il est tout à fait légitime de voir le langage comme un concept mathématique et la théorie des langages a pour objectif de décrire les langages formels c'est à dire des ensembles de mots (ou suites de lettres d'un alphabet) appelé aussi grammaire ou encore syntaxe. Quand on parle ou que l'on écrit, on fait inconsciemment et sans cesse des mathématiques discrètes assez poussées et difficiles. Les langages formels sont décrits par une grammaire. Toujours de manière formelle, une grammaire est un groupe de 4 éléments :

un ensemble de terminaux, qui sont les lexèmes du langage formel
un ensemble de non terminaux
un élément dans l'ensemble des non terminaux, que l'on appelle axiome et qui est conventionnellement noté S. C'est le point de départ du langage.
un ensemble de règles de forme, ces règles font l'association d'un non terminal à une ou plusieurs séries généralement ordonnée de terminaux et/ou de non terminaux. Ce sont les règles grammaticales du langage.

On écrit généralement une grammaire sous cette forme en mathématique : G=(terminaux, non terminaux, axiome, règles grammaticales)

Exemple d'un langage formel L1 définit par la grammaire G suivante :

G=({a,b},{R,S,T},S,{S->abR,R->aT,T->b})

La grammaire dit que le langage L1 a 2 terminaux : 'a' et 'b'

Le langage possède 4 non terminaux : R, S et T avec S l'axiome

Par les règles grammaticales du langage, il n'y a qu'une seule phrase de possible : 'abab'

On commence par S : on a abR

On regarde le non terminal R et on voit qu'il donne aT : on a donc abaT

De même on regarde ensuite le non terminal T qui donne 'b' : on a au final 'abab'

On ne peut pas aller plus loin. Et nous n'avons qu'un seul mot "abab".

On dit que ce langage est borné, il fait partie des langages de type 1 (les langages contextuels) dans la hiérarchie de Chomsky - La hiérarchie de Chomsky est une hiérarchie qui classe les langages par leur grammaires. Il existe 4 types de langages (4 types de grammaire donc) dans la hiérarchie de Chomsky allant de 0 à 3.

Changeons maintenant les règles de notre grammaire G (ce qui va changer le langage L1, on va le noter L2) :

G=({a,b},{R,S,T},S,{S->abR,R->aT,T->bS,S->ԑ})

ԑ est l'ensemble vide (pas de mots)

On commence par S : on a abR ou ԑ

On regarde le non terminal R et on voit qu'il donne aT : on a donc abaT ou ԑ

De même on regarde ensuite le non terminal T qui donne bS : on a au final ababS ou ԑ

Et récursivement comme S donne abR ou ԑ on a alors une infinité de mots acceptables : {ԑ,abab,abababab,abababababab,...}

Bref le langage accepte par ses règles grammaticales tout les mots de la forme 'abab'ⁿ avec n>0 ou aucun mot (ԑ).

On dit que la grammaire de ce langage est algébrique ou context-free ou non contextuelle ou encore hors contexte. La grammaire définit le langage comme un langage algébrique qui sont des langages de type 2 dans la hiérarchie de Chomsky.

Un langage de langage

Vous vous souvenez que l'on va utiliser un compilateur de compilateur pour compiler notre compilateur. Il va falloir que je transmette le langage Simple pour que le compilateur puisse connaître sa grammaire (et vous aussi par la même occasion). Comme il s'agit d'un langage informatique, il est donc formel. Je vais alors utiliser un langage qui permet de décrire un langage formel. On appelle ce type de langage un métalangage. Le BNF ou la forme de Backus-Naur permet de décrire une grammaire. Rappelons-nous, une grammaire est constituée d'un ensemble de terminaux, de non terminaux, de règles et d'un axiome.

Forme de Backus-Naur

En BNF, on écrit les règles grammaticales de cette manière :

Les non terminaux sont entre '<>'

'::=' signifie "est défini par", c'est l'équivalent de la flèche '->' des règles grammaticales vues plus haut

Afin d'éviter toute confusion, les terminaux sont entre guillemets si ils ne font qu'un seul caractère ou si ils contiennent des caractères alphanumériques

Exemples :

Soit la grammaire G=({a,b},{S},S,{S->a,S->b})

Les règles S->a et S->b s'écriront en BNF par <S> ::= "a" | "b" - (Le '|' est utilisé dans le cas où un non terminal peut avoir plusieurs règles, il signifie le OU)

Soit la grammaire G=({a,b},{S},S,{S->ab,S->aa})

Les règles S->ab et S->aa s'écriront en BNF par <S> ::= "a" ("a" | "b") - (Les parenthèses sont admis en BNF)

Soit la grammaire G=({a,b},{S},S,{S->ab,S->a})

Les règles S->ab et S->a s'écriront en EBNF (EBNF est une forme étendue du BNF facilitant sa lecture et son écriture) par <S> ::= "a" ["b"] - (Les crochets indiquent que le terminal "b" est optionnel à la fin de la phrase, c'est l'équivalent de <S> ::= ("a" "b") | "a" )