Symboles terminaux et non terminaux

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, on appelle symboles terminaux et non terminaux les symboles utilisés dans les règles de production d'une grammaire formelle. Les symboles terminaux et les symboles non-terminaux font partie d'ensembles disjoints.

Symbole terminaux[modifier | modifier le code]

Les symboles terminaux sont des caractères littéraux qui peuvent apparaître dans les règles de production (en entrée ou sortie) d'une grammaire formelle et ne peuvent pas être subdivisés en éléments plus petits. Ce sont plus précisément des éléments qui ne peuvent pas être changés via les règles de la grammaire. Par exemple, une grammaire définie par les deux règles :

  1. x peut devenir xa
  2. x peut devenir ax

présente a comme symbole terminal parce qu'aucune règle n'existe pour le changer en autre chose (cependant x est non-terminal puisqu'il accepte 2 règles pour être modifié). Un langage formel défini (ou généré) par une grammaire particulière est l'ensemble des chaînes de caractères terminaux produites par la grammaire ; les non-terminaux n'étant pas construits entièrement de terminaux ne peuvent pas apparaître comme lexèmes appartenant au langage. Dans un contexte d'analyse syntaxique, étant opposé à la théorie des langages de programmation et des compilateurs, les termes symbole terminal et jeton sont souvent considérés synonymes. Selon le Dragon Book (référence standard) :

« Dans un compilateur, l'analyseur lexical lit les caractères du programme source, les groupe en unités sémantiques appelées lexèmes, et produit des jetons représentant ces lexèmes. Un jeton est constitué de deux éléments, un nom de jeton et une valeur d'attribut. Les noms de jeton sont des symboles abstraits qui sont utilisés par le parser pour l'analyse syntaxique. On appellera souvent ces noms de jetons terminaux, dans la mesure où ils apparaissent en symboles terminaux dans la grammaire d'un langage de programmation. La valeur de l'attribut, si elle est présente, est un pointeur vers la table des symboles où plus d'informations sur le jeton est contenue. Ces informations ne font pas partie de la grammaire, donc sur le sujet de l'analyse syntaxique, on fera référence aux jetons et aux terminaux de façon synonyme[1]. »

Les symboles terminaux, ou juste terminaux, sont les symboles élémentaires du langage défini par une grammaire formelle.

Symboles non-terminaux[modifier | modifier le code]

Les symboles non-terminaux, ou non-terminaux, sont les symboles qui peuvent être remplacés ; il y a donc des chaînes composées de symboles terminaux et non-terminaux. Ils peuvent également être appelés variables syntactiques. Une grammaire formelle inclut un symbole de départ, membre désigné de l'ensemble des non-terminaux à partir duquel toutes les chaînes de caractères du langage peuvent être dérivées par des applications ou des règles de production successives. En fait, le langage défini par une grammaire est précisément l'ensemble des chaînes terminales qui peuvent être ainsi dérivés.

Une grammaire non contextuelle est une grammaire dans laquelle le membre gauche de chaque règle de production est un seul symbole non-terminal. Cette restriction est non-triviale, tous les langages ne peuvent pas être générés par des grammaires non contextuelles. Ceux-là sont appelés langages non contextuels. Ce sont ces langages-là qui sont reconnus par des automates à pile non-déterministes. Les langages non-contextuels constituent la base théorique de la syntaxe de la plupart des langages de programmation.

Règles de production[modifier | modifier le code]

Une grammaire est définie par des règles de production qui spécifient quels lexèmes remplacent quels autres lexèmes ; ces règles peuvent être utilisées pour générer des chaînes de caractères ou pour les parser. Toute règle de production a une tête, ou membre gauche, qui représente la chaîne à remplacer, et un corps ou membre droit qui représente la chaîne qui va la remplacer. Les règles sont souvent écrites sous la forme <tete \rarr corps> ; par exemple la règle z0 → z1 spécifie que z0 peut être remplacé par z1.

Dans la formalisation classique des grammaires génératives proposée par Noam Chomsky dans les années 1950[2],[3], une grammaire G est constituée de :

  • Un ensemble fini N de symboles non-terminaux.
  • Un ensemble fini \Sigma de symboles terminaux disjoints de N.
  • Un ensemble fini P de règles de production, chaque règle étant de la forme
(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*}
{}^{*} est la Fermeture de Kleene, tel que (\Sigma \cup N)^{*} représente zéro ou plus symboles, et N correspond à un symbole non-terminal. Cela veut dire que chaque règle de production produit une chaîne à partir d'une autre, celle-ci contenant au moins un symbole non-terminal. Dans le cas où le corps est constitué uniquement de la chaîne vide (aucun symbole), on peut utiliser une notation spéciale (souvent \Lambda, e ou \epsilon) pour éviter toute confusion.
  • Un symbole distingué S \in N qui est le symbole de départ.

Une grammaire est définie formellement comme le quadruple ordonné <N, \Sigma, P, S>.

Exemple[modifier | modifier le code]

Par exemple, pour représenter un nombre éventuellement signé, on peut proposer la grammaire suivante (exprimée en notation pseudo-BNF) :

<entier> ::= ['-'] <chiffre> {<chiffre>}
<chiffre> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Dans cette grammaire, les symboles (-,0,1,2,3,4,5,6,7,8,9) sont terminaux ; les symboles <chiffre> et <entier> sont non terminaux.

Références[modifier | modifier le code]

  1. Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, second edition; Pearson/Addison-Wesley, 2006. Box, p. 43. (traduction pour l'article)
  2. Chomsky, Noam, « Three Models for the Description of Language », IRE Transactions on Information Theory, vol. 2, no 2,‎ 1956, p. 113–123 (lien DOI?)
  3. (en) Chomsky, Noam, Syntactic Structures, The Hague, Mouton,‎ 1957