Éd. 1971-1976

langage formel (suite)

Une séquence de mots v dans V* est une phrase de la grammaire si et seulement si σ v et v dans T* (itéré du vocabulaire terminal) : le langage engendré par la grammaire G est L(G) = {v|v dans T* et σ v}. Un langage L est à structure de phrase s’il existe une grammaire G telle que L = L(G).

Chomsky* a défini trois sous-classes progressivement plus restreintes parmi les grammaires à structure de phrase.

• Une grammaire est sensible au contexte si chaque production x : : = v satisfait la relation des longueurs l(x) ≤ l(v), dans laquelle L est le nombre de lettres d’un mot d’automate, c’est-à-dire le nombre de mots d’une phrase de langage.

• Une grammaire est libre du contexte si chaque production satisfait l(x) = 1. Elle peut être formalisée par un automate à pile.

• Une grammaire est régulière si chaque production est soit du type x : : = t, soit du type x : : = αt avec t dans T et x ou α dans X = V — T peut être formalisée par un automate fini.

Exemple. Soit la grammaire
G = {0, 1, σ}, P, σ, {0, 1},
dans laquelle la variable métalinguistique unique est {σ} = X et les productions ont au nombre de deux :
σ : : = 1σ011,
σ : : = 01.

Le langage correspondant peut alors être représenté comme l’ensemble de séquences suivant :

où tⁿ indique la séquence obtenue par concaténation de n copies de t.

Quelques arbres de génération et leurs descriptions structurales dans L(G) permettent de vérifier que toute séquence n’appartient pas au langage :

Les principaux systèmes formels élaborés ou utilisés pour l’étude des langages sont la machine de Turing, le système de Post, les algorithmes de Markov, le calcul Lambda, le système de Semi-Thué, la notation polonaise, la forme normale de Backus, les automates à piles, la théorie des catégories, etc. L’exemple le plus représentatif et le plus fructueux d’emploi d’une grammaire formelle pour la définition d’un langage de programmation est celui d’ALGOL, où une grammaire à structure de phrase a permis dès 1960 de spécifier la plupart des règles syntaxiques.

M. D.

➙ Automates (théorie des) / Générative (grammaire) / Langage informatique / Modèle.

F. de Saussure, Cours de linguistique générale (Payot, 1916 ; nouv. éd., 1969). / H. B. Curry et R. Feys, Combinatory Logic, vol. I (Amsterdam, 1958 ; 2^e éd., 1968). / N. Chomsky et G. A. Miller, « Introduction to the Formal Analysis of Natural Languages », dans Handbook of Mathematical Psychology, sous la dir. de R. D. Luce, vol. II (New York, 1963 ; trad. fr. l’Analyse formelle des langues naturelles, Gauthier-Villars et Mouton, 1968). / R. Martin, Logique contemporaine et formalisation (P. U. F., 1964). / J. Porte, Recherches sur la théorie générale des systèmes formels et sur les systèmes connectifs (Gauthier-Villars et Nauwelaerts, Louvain, 1965). / M. Gross et A. Lentin, Notions sur les grammaires formelles (Gauthier-Villars, 1967). / A. Culioli, C. Fuchs et M. Pêcheux, Considérations théoriques à propos du traitement formel du langage (Dunod, 1970). / B. A. Galler et A. J. Perlis, A View of Programming Languages (Reading, Mass., 1970).

langage informatique

Mode d’expression permettant de communiquer avec un ordinateur à l’aide de séquences de caractères combinés selon un ensemble de règles pour former des mots, des expressions, des phrases et des programmes.

Du code-machine au langage d’assemblage

De même que la pratique de l’arithmétique est fondée sur la compréhension de signes, +, —, ×, ..., représentant des opérations, et de séquences de chiffres, 0, 1, ..., représentant des nombres, de même le fonctionnement d’un ordinateur est fondé sur l’interprétation de séquences de caractères pris dans un alphabet particulier. Ainsi, 27182 peut signifier la valeur arithmétique « vingt-sept mille cent quatre-vingt-deux », mais, décomposée en 2,7182, cette même séquence représente la valeur entière suivie des quatre premières décimales du nombre irrationnel e, tandis que, décomposée en 27/1/82, elle évoque la date du 27 janvier 1882. Plus généralement, toute séquence de caractère comme A ou MUL ou 27 JAN 82 peut tenir lieu de nom pour une variable.

L’unité de traitement d’un calculateur pourrait interpréter la séquence 2 : 7182 comme suit : effectuer l’opération numéro 2 à l’aide du contenu de la cellule de mémoire d’adresse 7182. Par exemple, l’opération est la multiplication et 7182 est l’adresse du multiplicateur, de sorte qu’une cellule référencée implicitement, l’accumulateur A, contient initialement le multiplicande et finalement le produit.

Un langage peut ainsi être formé au moyen d’un ensemble de noms avec un certain nombre de règles permettant d’attribuer à ces noms une valeur finale (opération ou opérande).

Un programme est une séquence de noms de variables et de noms d’opérations à effectuer dans un ordre prescrit à partir de valeurs connues des variables données. Cet ordre est généralement séquentiel, mais il existe des instructions de rupture de séquence permettant de « brancher » sous certaines conditions vers une instruction autre que la suivante. Un résultat est la valeur finale d’un programme.

Or, un calculateur ne peut interpréter que des noms codés généralement en chiffres binaires (0 ou 1) et ne peut exécuter que des instructions de format simple, soit du type impératif comme (2 ; 7182), c’est-à-dire (nom d’opération : nom d’opérande), soit du type conditionnel (branchement ; étiquette), qui signifie que, selon le contenu de l’accumulateur A référencé implicitement, l’instruction à exécuter est non la suivante, mais celle qui est indiquée par l’étiquette. Ces instructions, exprimant des étapes de traitement élémentaires, ne permettent de composer que des programmes dits en langage-machine, car ils ne sont adaptés qu’à un calculateur spécifique. Ils sont cependant universels, en ce sens qu’ils permettent de résoudre algorithmiquement n’importe quel problème, mais ils s’avèrent d’emploi fastidieux pour exprimer « sans erreur » une solution. Ainsi, la multiplication (instruction numéro 2 codée 001 en binaire) par le contenu de la cellule 7182 doit être spécifiée sous la forme (0011110000001110) pour un calculateur doté d’une mémoire de 8192 cellules ayant chacune seize positions binaires. Cette instruction est contenue dans une cellule de mémoire, par exemple à l’adresse 0054.