Notion de barrière syntaxique

Nous avons vu que les différentes grammaires des expressions booléennes simples définissaient une classe de langages. Aussi les spécifications des reconnaisseurs, des accesseurs et des constructeurs seront exactement les mêmes dans tous les cas (si vous ne nous croyez pas -- ce qui serait plus que légitime --, redéfinissez-les pour les expressions préfixes).

D'autre part, nous avons vu que pour analyser un mot d'un langage des expressions booléennes simples, il fallait avoir

les reconnaisseurs ebs-atomique?, ebs-variable?, ebs-constante?, ebs-constante-vrai?, ebs-constante-faux?, ebs-unaire?, ebs-binaire?, ebs-operateur1?, ebs-non?, ebs-operateur2?, ebs-operateur2-et?, ebs-operateur2-ou?,
les accesseurs
- ebs-unaire-operande, ebs-unaire-operateur,
- ebs-binaire-operande-gauche, ebs-binaire-operande-droit et ebs-binaire-operateur.

et que pour construire des expressions booléennes simples, il fallait avoir

les constructeurs ebs-variable, ebs-constante-vrai, ebs-constante-faux, ebs-unaire, ebs-binaire, ebs-operateur1-non, ebs-operateur2-et et ebs-operateur2-ou.

Il est clair que l'implantation de ces différentes fonctions est interdépendante et dépend du choix que l'on fait pour implanter les expressions. On doit donc regrouper cet ensemble de fonctions dans une barrière d'abstraction, barrière d'abstraction pour une classe de grammaires, qu'on appelle la barrière syntaxique.

Nous allons donner la spécification précise de ces fonctions après quelques généralités.

Schéma des spécifications des fonctions ayant comme donnée un mot du langage Systématiquement, nous nommerons le type des mots qui dérivent d'un non-terminal par le nom de celui-ci (sans accents), avec la première lettre en majuscule. Par exemple, le type des expressions représentés par des mots dérivant de <expBoolSimple_infixe> sera noté ExpBoolSimple, le type des mots dérivant de <unaire> sera noté Unaire..., et la spécification des fonctions qui ont comme données un tel type est du genre:

;;; fn1: ExpBoolSimple -> ... ;;; (fn1 exp) rend ... ;;; fn2: Unaire -> ... ;;; (fn2 exp) rend ...

Rappelons qu'une telle spécification signifie que l'on garantit que la fonction rend bien ce qui est dit après « rend » lorsque la donnée appartient au type donné (ExpBoolSimple dans le cas de fn1, Unaire dans le cas de fn2) et que l'on ne sait pas ce qu'elle fait (signifie une erreur ou rend une valeur plus ou moins significative) dans le cas contraire. On pourra donner des précisions dans la spécification:

si nous savons qu'une erreur est signifiée sous certaines conditions, nous l'indiquerons dans la spécification comme d'habitude:

;;; fn3: ExpBoolSimple -> ... ;;; ERREUR lorsque ... ;;; (fn3 exp) rend ...
pour de nombreuses fonctions, nous saurons quelle valeur elles rendent lorsque la donnée n'appartient pas au type; nous l'indiquerons alors explicitement dans la spécification:

;;; fn4: ExpBoolSimple -> ... ;;; (fn4 exp) rend ... ;;; (elle rend ... lorsque ...)

(nous verrons des exemples concrets ci-après).

Remarque: ces précisions sont particulièrement utiles pour les reconnaisseurs car elles permettent de donner des messages d'erreur plus significatifs lorsque le mot à analyser n'appartient pas au langage.

Spécifications des reconnaisseurs
Noter que lorsqu'on applique les reconnaisseurs ebs-atomique?, ebs-unaire? et ebs-binaire?, on espère que le mot à analyser dérive du non-terminal <expBoolSimple_infixe>. Le type de la donnée de ces reconnaisseurs est donc ExpBoolSimple (et le type d'arrivée est bien sûr bool).

Pour ebs-atomique?, nous avons dit qu'il était aisé de savoir si un mot quelconque pouvait dériver ou non de <atomique>. On peut donc prendre comme spécification:

;;; ebs-atomique? : ExprBoolSimple -> bool ;;; (ebs-atomique? exp) rend #t ssi exp est une expression atomique ;;; (constante ou variable)

Pour ebs-unaire?, nous avons dit qu'il était difficile, voire impossible, de savoir si un mot quelconque pouvait dériver ou non de <unaire>. En revanche, il peut être aisé de savoir si on peut bien le décomposer en deux composants. D'où la spécification:

;;; ebs-unaire? : ExprBoolSimple -> bool ;;; (ebs-unaire? exp) rend #t ssi exp ne peut être qu'une expression dérivant ;;; de <unaire> ;;; (elle rend #f lorsque exp n'est pas composée de deux composants)

De même, pour ebs-binaire?, il est aisé de savoir si on peut bien le décomposer en trois composants. D'où la spécification:

;;; ebs-binaire? : ExprBoolSimple -> bool ;;; (ebs-binaire? exp) rend #t ssi exp ne peut être qu'une expression ;;; dérivant de <binaire> ;;; (elle rend #f lorsque exp n'est pas composée de trois composants)

Lorsqu'on applique les reconnaisseurs ebs-variable? et ebs-constante?, on espère que le mot à analyser dérive du non-terminal <atomique>. Le type de la donnée de ces reconnaisseurs est donc Atomique:

;;; ebs-variable? : Atomique -> bool ;;; (ebs-variable? exp) rend #t ssi exp est une variable

;;; ebs-constante? : Atomique -> bool ;;; (ebs-constante? exp) rend #t ssi exp est une constante ;;; (rend #f lorsque exp n'est pas une expression atomique)

Noter que la spécification de la fonction ebs-constante? que nous avons donnée indique qu'en fait ce reconnaisseur rend toujours (y compris lorsque l'on ne sait pas que le mot doit dériver de <atomique>) la bonne réponse.

Donnons les spécifications des autres reconnaisseurs sans autres commentaires:

;;; ebs-constante-vrai? : Constante -> bool ;;; (ebs-constante-vrai? exp) rend #t ssi exp est la constante @V ;;; (rend #f lorsque exp n'est pas une constante)

;;; ebs-constante-faux? : Constante -> bool ;;; (ebs-constante-faux? exp) rend #t ssi exp est la constante @F ;;; (rend #f lorsque exp n'est pas une constante)

;;; ebs-operateur1? : Symbole -> bool ;;; (ebs-operateur1? s) rend #t ssi s est un opérateur unaire

;;; ebs-operateur2? : Symbole -> bool ;;; (ebs-operateur2? s) rend #t ssi s est un opérateur binaire

;;; ebs-operateur1-non? : Symbole -> bool ;;; (ebs-operateur1-non? s) rend #t ssi s est l'opérteur (unaire) non

;;; ebs-operateur2-et? : Symbole -> bool ;;; (ebs-operateur2-et? s) rend #t ssi s est l'opérteur (binaire) et

;;; ebs-operateur2-ou? : Symbole -> bool ;;; (ebs-operateur2-ou? s) rend #t ssi s est l'opérteur (binaire) ou

Spécifications des accesseurs
Noter que lorqu'on applique les accesseurs ebs-unaire-operande et ebs-unaire-operateur, on espère que le mot à analyser dérive du non-terminal <unaire>. Le type de la donnée de ces reconnaisseurs est donc Unaire. Le type d'arrivée est le type qui correspond au non-terminal extrait. Par exemple, la règle étant

<unaire>	->	`(` <opérateur1> <expBoolSimple_infixe> `)`

ebs-unaire-operateur doit rendre un élément de Operateur1 et ebs-unaire-operande doit rendre un élément de expression. Noter aussi que l'on ne peut rien dire lorsque le mot donné ne dérive pas de <unaire>. Les spécifications sont donc:

;;; ebs-unaire-operateur : Unaire -> Operateur1 ;;; (ebs-unaire-operateur exp) rend l'opérateur (principal) de l'expression ;;; donnée ;;; ebs-unaire-operande : Unaire -> ExprBoolSimple ;;; (ebs-unaire-operande) rend l'expression, opérande de l'expression donnée

De même, les spécifications des accesseurs correspondant à la règle

<binaire>	->	`(` <expBoolSimple_infixe> <opérateur2> <expBoolSimple_infixe> `)`

sont:

;;; ebs-binaire-operande-gauche : Binaire -> ExprBoolSimple ;;; (ebs-binaire-operande-gauche exp) rend l'expression, opérande gauche de ;;; l'expression donnée ;;; ebs-binaire-operande-droit : Binaire -> ExprBoolSimple ;;; (ebs-binaire-operande-droit exp) rend l'expression, opérande droit de ;;; l'expression donnée ;;; ebs-binaire-operateur : Binaire -> Operateur2 ;;; (ebs-binaire-operateur exp) rend l'opérateur (principal) de l'expression ;;; donnée

Remarque: noter la règle de nommage des fonctions que nous utilisons (un préfixe correspondant au non-terminal analysé, un suffixe correspondant à l'unité syntaxique extraite).

Spécifications des constructeurs

;;;; Constructeurs:

;;; ebs-variable : Symbole -> ExprBoolSimple ;;; (ebs-variable s) rend l'expression booléenne simple réduite à la variable s

;;; ebs-constante-vrai : -> Constante ;;; (ebs-constante-vrai) rend la constante « vrai »

;;; ebs-constante-faux : -> Constante ;;; (ebs-constante-faux) rend la constante « faux »

;;; ebs-unaire : Operateur1 * ExprBoolSimple -> ExprBoolSimple ;;; (ebs-unaire op exp) rend l'expression composée unaire ayant comme ;;; opérateur op et comme opérande exp

;;; ebs-binaire : ExprBoolSimple * Operateur2 * ExprBoolSimple -> ExprBoolSimple ;;; (ebs-binaire exp1 op exp2) rend l'expression composée ayant comme ;;; opérande gauche exp1, comme opérateur op et comme opérande droit ;;; exp2

;;; ebs-operateur1-non : -> Operateur1 ;;; (ebs-operateur1-non) rend l'opérateur de négation

;;; ebs-operateur2-et : -> Operateur2 ;;; (ebs-operateur2-et) rend l'opérateur de conjonction

;;; ebs-operateur2-ou : -> Operateur2 ;;; (ebs-operateur2-ou) rend l'opérateur de disjonction

Exemple: pour construire l'expression booléenne, représentée en notation infixée, complètement parenthésée, par:

( (@non (@v @et @v) ) @et (@v @ou @f) )

on peut écrire:

(ebs-binaire (ebs-unaire (ebs-operateur1-non) (ebs-binaire (ebs-constante-vrai) (ebs-operateur2-et) (ebs-constante-vrai))) (ebs-operateur2-et) (ebs-binaire (ebs-constante-vrai) (ebs-operateur2-ou) (ebs-constante-faux)))

Premier exemple d'utilisation de la barrière syntaxique
Écrivons la définition d'une fonction qui teste si une expression booléenne simple est une expression constante (i.e. qui ne comporte pas de variable).

Spécification

La spécification de cette fonction est:

;;; ebs-exp-cste? : ExprBoolSimple -> bool ;;; (ebs-exp-cste? exp) rend #t ssi exp est une expression constante ;;; (c'est-à-dire qui n'a pas d'occurrence de variable)

Exemple d'application

(let ((expression (ebs-binaire (ebs-unaire (ebs-operateur1-non) (ebs-constante-faux)) (ebs-operateur2-et) (ebs-binaire (ebs-variable 'a) (ebs-operateur2-ou) (ebs-variable 'b))))) (ebs-exp-cste? expression))

-> #f

Implantation

Comme pour toutes les fonctions dont la donnée est un mot du langage, la forme générale de la définition de ebs-exp-cste? est une conditionnelle qui passe en revue toutes les branches de la règle donnée pour l'axiome (rappelons que c'est la première règle):

(define (ebs-exp-cste? exp) (cond ((ebs-atomique? exp) ... à faire ((ebs-unaire? exp) ... à faire ((ebs-binaire? exp) ... à faire ... à faire (else (erreur 'ebs-exp-cste? "expression mal formée"))))

et il n'y a plus qu'à remplir les trous. Lorsque l'expression est une expression atomique, elle est constante si, et seulement si, le reconnaisseur ebs-constante? rend #t:

(define (ebs-exp-cste? exp) (cond ((ebs-atomique? exp) (ebs-constante? exp)) ((ebs-unaire? exp) ... à faire ((ebs-binaire? exp) ... à faire ... à faire (else (erreur 'ebs-exp-cste? "expression mal formée"))))

lorsque l'expression donnée est une expression unaire, elle est constante si, et seulement si, son opérande est une expression constante:

(define (ebs-exp-cste? exp) (cond ((ebs-atomique? exp) (ebs-constante? exp)) ((ebs-unaire? exp) (ebs-exp-cste? (ebs-unaire-operande exp))) ((ebs-binaire? exp) (else (erreur 'ebs-exp-cste? "expression mal formée"))))

lorsque l'expression donnée est une expression binaire, elle est constante si, et seulement si, ses deux opérandes sont des expressions constantes:

(define (ebs-exp-cste? exp) (cond ((ebs-atomique? exp) (ebs-constante? exp)) ((ebs-unaire? exp) (ebs-exp-cste? (ebs-unaire-operande exp))) ((ebs-binaire? exp) (and (ebs-exp-cste? (ebs-binaire-operande-gauche exp)) (ebs-exp-cste? (ebs-binaire-operande-droit exp)))) (else (erreur 'ebs-exp-cste? "expression mal formée"))))