Langage et Syntaxe
Tous les langages, que ce soit les langages de programmation ou les langages naturels, ont une structure appelée grammaire ou syntaxe. On peut dire, par exemple, qu’une phrase correcte (c’est à dire bien formée) doit toujours se composer d’un sujet suivi d’un prédicat1. Ce fait peut être décrit par la formule suivante:
Ajoutons maintenant deux nouvelles formules à notre grammaire:
Nous définissons ainsi quatre phrases possibles, à savoir :
- \(\mathsf{«Robert\ mange»}\).
- \(\mathsf{«Robert\ parle»}\).
- \(\mathsf{«Marie\ mange»}\).
- \(\mathsf{«Marie\ parle»}\).
Note
Pour être tout à fait précis, il faudrait considérer les espaces comme des symboles terminaux à part entière, mais nous les avons omis pour plus de clarté. Vous verrez par la suite que les espaces sont généralement traités de manière spéciale dans les langages de programmation.
Dans nos formules, le symbole \(|\) signifie “ou”. Nous appelons ces formules des règles syntaxiques, des productions ou simplement des équations syntaxiques. Le \(sujet\) et le \(prédicat\) sont des classes syntaxiques. On peut remplacer des identifiants par quelque chose de plus compacts et on obtient:
L’ensemble de phrases \(L\) qui peut être généré par ces règles est appelé langage. Ces phrases sont produites en remplaçant les classes syntaxiques (ce qui est à gauche du symbole \(=\)) par les éléments qu’elles définissent (ce qui est à droite du symbole \(=\)).
Nous utiliserons cette notation pour la suite du cours.
L’exemple ci-dessus définit un langage composé de seulement quatre phrases, mais dans la pratique, les langages contiennent un nombre infini de phrases. Par exemple:
Note
Le symbole \(\varnothing\) représente la séquence vide.
Ces règles syntaxiques permettent de générer un langage \(L\) comprenant un nombre infini de phrases:
Vous remarquerez que le moyen de parvenir à un langage avec une infinité de phrases fait appel à la récursivité qui permet de répéter une substitution (ici de \(A\) par \(\mathsf{«a»}A\)).
Notre troisième exemple est à nouveau basé sur l’utilisation de la récursivité. Il ne génère plus de phrases constituées d’une séquence de longueur arbitraire du même symbole, mais des phrases imbriquées:
Le langage \(L\) généré par ces règles comprend, entre autres, les phrases suivantes:
L’imbrication des classes syntaxiques, à des profondeurs différentes, permet de générer des phrases de plus en plus complexes.
Le quatrième et dernier exemple illustre la structure d’une expression mathématique simple. Les symboles \(E\), \(T\), \(F\) et \(V\) représentent l’expression, le terme, le facteur et la variable:
Cet exemple montre qu’une syntaxe ne se contente pas de définir l’ensemble des phrases d’un langage, mais qu’elle leur fournit également une structure. La syntaxe décompose les phrases en leurs constituants, comme le montre l’exemple de la figure ci-dessous. Les représentations graphiques sont appelées arbres structurels ou arbres syntaxiques.
Formulons maintenant les concepts présentés ci-dessus de manière plus rigoureuse :
Un langage est défini par les éléments suivants
- L’ensemble des symboles terminaux. Il s’agit des symboles qui apparaissent dans les phrases du langage. Ils sont dits terminaux parce qu’ils ne peuvent être remplacés par aucun autre symbole. Le processus de substitution s’arrête aux symboles terminaux. Dans notre premier exemple, cet ensemble est constitué des éléments \(\mathsf{«a»}\), \(\mathsf{«b»}\), \(\mathsf{«c»}\) et \(\mathsf{«d»}\). Cet ensemble est également appelé vocabulaire.
- L’ensemble des symboles non terminaux. Ils désignent des classes syntaxiques et peuvent être substitués. Dans notre premier exemple, cet ensemble est constitué des éléments \(S\), \(A\) et \(B\).
- L’ensemble des équations syntaxiques (également appelées productions). Elles définissent les substitutions possibles des symboles non terminaux. Une équation est spécifiée pour chaque symbole non terminal.
- Le symbole de départ. Il s’agit d’un symbole non terminal, dénoté par \(S\) dans les premiers exemples ci-dessus et par \(E\) pour les expressions.
Résumé
Un langage est donc l’ensemble des séquences de symboles terminaux qui, à partir du symbole de départ, peuvent être générées par l’application répétée d’équations syntaxiques, c’est-à-dire de substitutions.
Nous souhaitons également définir de manière rigoureuse et précise la notation dans laquelle les équations syntaxiques sont spécifiées.
- Les symboles non terminaux sont des identificateurs tels que nous les connaissons dans les langages de programmation,
c’est-à-dire des séquences de lettres (et éventuellement de chiffres). par exemple expression,
terme. - Les symboles terminaux sont des séquences de caractères entre guillemets (chaînes de caractères). Par exemple “=” ou “|”.
Pour définir la structure de ces équations, il est opportun d’utiliser l’outil que nous venons de définir :
syntax = production syntax | ∅.
production = identifier "=" expression ".".
expression = term | expression "|" term.
term = factor | term factor.
factor = identifier | string.
identifier = letter | identifier letter | identifier digit.
string = stringhead """.
stringhead = """ | stringhead character.
letter = "a"|...|"z".
digit = "0"|...|"9".
Cette notation a été introduite en 1960 par John Backus et Peter Naur sous une forme presque identique pour la description formelle de la syntaxe du langage Algol 60. Elle est appelée Backus Naur Form (BNF).
Comme on peut le voir dans l’exemple ci-dessus, l’utilisation de la récursivité pour exprimer de simples répétitions n’est pas des plus lisible.
C’est pourquoi nous ajoutons à cette notation deux constructions pour exprimer la répétition ({}) et l’optionnalité ([]).
En outre, nous permettons aux expressions d’être placées entre parenthèses (()).
Cette extension de BNF a été proposée par Niklaus Wirth en 1977 et s’appelle EBNF pour Extended Backus Naur Form.
Utilisons sans tarder cette nouvelle notation pour sa propre définition :
syntax = { production }.
production = identifier "=" expression ".".
expression = term { "|" term }.
term = factor { factor }.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".
identifier = letter { letter | digit }.
string = """ { character } """.
letter = "a"|...|"z".
digit = "0"|...|"9".
Un facteur de la forme {x} est équivalent à une séquence arbitrairement longue de x, y compris la séquence vide.
Une production de la forme A = AB | ∅ peut maintenant être formulée plus brièvement (et plus lisiblement) comme A = {B}.
Un facteur de la forme [x] est équivalent à « x ou rien », c’est-à-dire qu’il exprime une option.
Par conséquent, le symbole spécial ∅ pour la séquence vide n’est plus nécessaire.
L’idée de définir les langues et leur grammaire avec une précision mathématique remonte à Noam Chomsky. Il est toutefois apparu clairement que le schéma simple des règles de substitution était insuffisant pour représenter la complexité des langues parlées. En revanche, ce travail s’est avéré extrêmement fructueux pour la théorie des langages de programmation et des formalismes mathématiques. Avec lui, Algol 60 est devenu le premier langage de programmation dont la syntaxe était définie de manière formelle et précise.
L’utilisation du formalisme de Chomsky est également à l’origine du terme langage de programmation, car les langages de programmation semblaient présenter une structure similaire à celle des langues parlées. Nous pensons que ce terme n’est pas vraiment approprié, car un langage de programmation n’est pas parlé, et n’est donc pas un langage au sens propre du terme. Formalisme ou notation formelle auraient été des termes plus appropriés.
Une grammaire permet de savoir si une phrase est bien formée ou non. En plus, elle doit nous permettre de comprendre la signification de la phrase. Illustrons ce point avec un exemple simple.
E = N | E "-" E.
N = "1" | "2" | "3" | "4".
La phrase 4 - 2 - 1 est bien formée. Nous pouvons la dériver de la manière suivante :
Lors de l’évaluation, nous commençons par faire “4 - 2” et obtenons 2. Ensuite, nous soustrayons 1 et obtenons 1.
Le problème avec cette grammaire, c’est qu’elle nous permet aussi de dériver la phrase d’une autre manière :
Lors de l’évaluation de cette dernière, nous commençons par faire “2 - 1” et obtenons 1. Ensuite, nous soustrayons ce résultat à 4 et obtenons 3.
Cet exemple illustre deux faits :
- L’interprétation des phrases repose toujours sur la reconnaissance de leur structure syntaxique.
- Toute phrase doit avoir une structure unique pour ne pas être ambiguë.
Si la deuxième condition n’est pas remplie, des phrases ambiguës apparaissent. Elles peuvent enrichir les langues parlées, mais elles sont tout simplement inutiles avec les langages de programmation.
Définition
Nous appelons une classe syntaxique ambiguë si plusieurs structures peuvent lui être attribuées. Un langage est ambigu s’il contient au moins une classe syntaxique ambiguë.