Langages et Traducteurs – TD01 – Grammaires d'expressions
⊱ Calculs sur une syntaxe (dont évaluation),
⊱ preuves par récurrence structurelle,
⊱ prérequis pour exercice 2 : le if_then_else fonctionnel.
Exercice 1 : expressions arithmétiques
On donne la grammaire d'expressions suivante :
aexp ::= C | ⊕ | ⊖ | ⊗
| / \ / \ / \
nat aexp aexp aexp aexp aexp aexp
ou encore, avec plus de lettres :
aexp ::= Cst | Apl | Asub | Amu
| / \ / \ / \
nat aexp aexp aexp aexp aexp aexp
(La présentation directe en arbre évite les ambiguïtés de la forme textuelle gérées par l'analyse syntaxique).
1.1 Dessiner l'arbre correspondant à l'expression arithmétique
s'écrivant usuellement : exemple_ae = (2 + 3) × ((4 - 2) - 1)
[REPONDRE ICI]
1.2 Nombre d'éléments dans un AST
1.2.1 fonction nbf
On définit la fonction nbf qui compte le nombre d'entiers (ou de feuilles)
présents dans un AST d'expression arithmétique, au moyen des équations récursives suivantes :
nbf (C n) = 1 nbf (e1 ⊕ e2) = nbf e1 + nbf e2 nbf (e1 ⊖ e2) = nbf e1 + nbf e2 nbf (e1 ⊗ e2) = nbf e1 + nbf e2
Dans un premier temps on les visualise et utilise sous forme graphique :
C
nbf | = 1
n
⊕
nbf / \ = nbf e1 + nbf e2
e1 e2
⊖
nbf / \ = nbf e1 + nbf e2
e1 e2
⊗
nbf / \ = nbf e1 + nbf e2
e1 e2
Dérouler le calcul de nbf sur l'expression exemple_ae du 1.1 .
[REPONDRE ICI]
1.2.2 discussion sur les équations définissantes
- Que se passerait-il si la dernière équation était oubliée ?
[REPONDRE ICI]
- Que se passerait-il si l'on ajoutait l'équation :
nbf (e1 ⊖ (C n)) = nbf e1
[REPONDRE ICI]
- Que se passerait-il si l'on ajoutait l'équation :
nbf (e1 ⊖ (C n)) = nbf e1 + 1
[REPONDRE ICI]
- Conclure par la règle de conduite à tenir pour qu'un ensemble
d'équations puisse être considéré comme définissant une fonction.
[REPONDRE ICI]
1.2.3 fonction nbo
Définir la fonction récursive nbo qui compte le nombre d'opérateurs binaires
présents dans un AST d'expression arithmétique.
[REPONDRE ICI]
1.2.4 récurrence structurelle
Démontrer que pour tout AST e, nbf e = 1 + nbo e
[REPONDRE ICI]
1.3 Fonction d'évaluation eval
Définir une fonction récursive d'évaluation eval : aexp → ℕ
eval (C n) = n eval (e1 ⊕ e2) = eval e1 + eval e2 [COMPLETER ICI]
Dérouler le calcul de eval sur l'expression exemple_ae du 1.1
[REPONDRE ICI]
1.4 (À la maison) Compléter en ajoutant un opérateur de division
aexp' ::= C nat | ... [COMPLETER ICI]
Que faut-il ajouter à la fonction eval pour obtenir eval' : aexp' → ℕ ?
[REPONDRE ICI]
1.5 Simplification d'expressions arithmétiques
On considère une fonction simpl0 qui, étant donné une expression e,
rend e sauf dans deux cas :
- si
eest de la forme(0 ⊕ e2), alors elle rende2. - si
eest de la forme(0 ⊗ e2), alors elle rend0.
On peut l'écrire :
C C
simpl0 | = |
n n
⊕
simpl0 / \ = e2
C e2
|
0
⊕ ⊕ C
simpl0 / \ = / \ pour e1 <> |
e1 e2 e1 e2 0
⊖ ⊖
simpl0 / \ = / \
e1 e2 e1 e2
⊗ C
simpl0 / \ = |
C e2 0
|
0
⊗ ⊗ C
simpl0 / \ = / \ pour e1 <> |
e1 e2 e1 e2 0
Ou plus simplement :
⊕
simpl0 / \ = e2
C e2
|
0
⊗ C
simpl0 / \ = |
C e2 0
|
0
simpl0 e = e dans tous les autres cas
Définition de simpl
En utilisant simpl0, écrire les équations récursives d'une fonction
simpl qui, étant donné une expression e, rend une expression comme e mais dans laquelle les sous-arbres
⊕ / \ ont été remplacés par e2 C e2 | 0
et les sous-arbres
⊗ C / \ ont été remplacés par | . C e2 0 | 0
[REPONDRE ICI]
1.6 Montrer que l'optimisation est acceptable
c'est-à-dire la propriété P disant que l'évaluation de toute expression e de aexp
rend la même chose que l'évaluation de simpl e.
Commencer par démontrer une propriété similaire sur simpl0.
[REPONDRE ICI]
1.7 (*) (Suivant temps disponible) Montrer par récurrence structurelle
la propriété P disant que toute expression e de aexp ne contenant que des entiers pairs s'évalue dans un entier pair
[REPONDRE ICI]
1.8 (*) (À la maison) Montrer par récurrence structurelle
Soit k un entier.
la propriété P disant que toute expression e de aexp ne contenant que des entiers multiples de k s'évalue dans un multiple de k.
[REPONDRE ICI]
Exercice 2 : extension de aexp
On veut étendre les expressions arithmétiques aexp avec des conditionnelles
de la forme : si bexp alors … sinon …
2.1 Écrire une grammaire d'expressions booléennes
Dans un premier temps : expression purement booléennes
bexp ::= vrai | faux | [COMPLETER ICI]
Dans un second temps : expression booléennes avec comparaison (égalité) entre expressions arithmétiques aexp
bexp' ::= bexp | [COMPLETER ICI]
2.2 Étendre la définition de aexp avec des conditionnelles
aexp'' ::= (comme avant) | [COMPLETER ICI]
2.3 Étendre la définition de eval en eval'' : aexp'' → ℕ (pour les conditionnelles)
[REPONDRE ICI]
2.4 (À la maison) Montrer la propriété P de 1.6 pour cette nouvelle définition
[REPONDRE ICI]
∼∼∼
Made with Org-mode