fr Symboles terminaux et non terminaux

En informatique, et notamment en théorie des langages, 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.

Symboles terminaux

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 :

x peut devenir xa
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 deux règles pour être modifié). Un langage formel défini (ou engendré) par une grammaire particulière est l'ensemble des chaînes ou mots 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^[1] :

« 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^[2]. »

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

Symboles non terminaux

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 ou variables. 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

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 engendrer des chaînes de caractères ou pour les analyser. 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 tête → 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^[3]^,^[4], 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)^{*}

où

{}^{*}

est l'étoile 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

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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Terminal and nonterminal symbols » (voir la liste des auteurs).

↑ Le Dragon book est un ouvrage de référence en informatique dans le domaine de la compilation.
↑ Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, second edition; Pearson/Addison-Wesley, 2006. Box, p. 43. (traduction pour l'article)
↑ Chomsky, Noam, « Three Models for the Description of Language », IRE Transactions on Information Theory, vol. 2, n^o 2,‎ 1956, p. 113–123 (DOI 10.1109/TIT.1956.1056813)
↑ Chomsky, Noam, Syntactic Structures, La Haye, Mouton, 1957

[1] Le Dragon book est un ouvrage de référence en informatique dans le domaine de la compilation.

[2] Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, second edition; Pearson/Addison-Wesley, 2006. Box, p. 43. (traduction pour l'article)

[Chomsky1956-3] Chomsky, Noam, « Three Models for the Description of Language », IRE Transactions on Information Theory, vol. 2, n^o 2,‎ 1956, p. 113–123 (DOI 10.1109/TIT.1956.1056813)

[Chomsky1957-4] Chomsky, Noam, Syntactic Structures, La Haye, Mouton, 1957

[1]

[2]

[3]

[4]