Majeure 2
Langages et Compilation
Cours 4


Analyse syntaxique,
Portée lexicale

jean-jacques.levy@inria.fr

9 février 1998

Les supports de cours sont en 

http://www.polytechnique.fr/poly/edu/informatique/
http://www.polytechnique.fr/poly/~levy/

Livres:

Introduction

Automates à pile

Un automate à pile (pushdown automata) est un n-uplet $(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ où

Q est un ensemble fini d'états,
$\Sigma$ est un alphabet (de terminaux ou tokens),
$\Gamma$ est un alphabet fini de symboles de pile,
$q_0 \in Q$ est l'état initial,
$Z_0 \in \Gamma$ est le symbole de pile initial,
$F \subset Q$ est l'ensemble des états finaux,
$\delta : Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \rightarrow2^{Q \times \Gamma^*}$est la fonction de transition

Déplacements élémentaires

$\delta(q,a,Z) = \{(q_1, \gamma_1), \cdots (q_n, \gamma_n)\}$ veut dire que, dans l'état q, si le sommet de pile est Z et si la tête de lecture voit la lettre a, alors l'automate déplace sa tête de lecture vers la droite et peut aller non déterministiquement dans un des états qi en remplaçant la lettre du sommet de pile Z par le mot $\gamma_i$. (Par convention, la pile est lue de la gauche vers la droite en allant du sommet à sa base).

$\delta(q,\epsilon,Z) = \{(q_1, \gamma_1), \cdots (q_n, \gamma_n)\}$veut dire qu'on fait de même sans regarder le symbole sous la tête de lecture. Alors la tête de lecture ne se déplace pas vers la droite.

(M.P.Schutzenberger, 1962)

Configurations et acceptation

Une configuration est une paire $(q,\gamma)$ où q est l'état courant et $\gamma$ est le contenu de la pile.

$(q,Z\gamma) \stackrel{a}{\longrightarrow} (p, \beta\gamma)$ si $(p,\beta) \in \delta(q,a,Z)$ où $a \in \Sigma \cup \epsilon$,

$(q,\gamma) \stackrel{w}{\longrightarrow} (p,\beta)$ si $w= a_1a_2\ldots a_n$ et $(q,\gamma) = (q_0, \gamma_0)$, $(p,\beta) = (q_n,\gamma_n)$ et $(q_i,\gamma_i) \stackrel{a_i}{\longrightarrow} (q_{i+1}, \gamma_{i+1})$ pour $0 \leq i < n$, $n \geq 0$.

L'automate M reconnait le langage T(M)

$T(M) = \{ w \mid (q_0,Z_0) \stackrel{w}{\longrightarrow} (q,\gamma),\; q \in F \}$

Acceptation

On peut aussi reconnaitre par pile vide, sans se servir de F.

$T'(M) = \{ w \mid (q_0,Z_0) \stackrel{w}{\longrightarrow} (q,\epsilon) \}$

Cela ne change pas la catégorie des langages reconnus.

Un automate à pile est déterministe si une seule transition est possible dans chaque configuration.

Théorème Les langages context-free sont les langages reconnus par les automates à pile.

Démonstration: évidente dans un sens. Légèrement plus compliquée dans l'autre sens. $\Box$

Propriété de fermetures des langages context-free

Les langages context-free sont fermés par union, mais pas par intersection. Par exemple, $L_1 = \{a ^n b^n c^p\}$ et $L_2 = \{a ^p b^n c^n\}$ sont context-free, mais pas $L_1 \cap L_2$.

L'intersection d'un langage régulier et d'un context-free est un langage context-free.

Appelons homomorphisme toute application $\Sigma_1 \rightarrow\Sigma_2^*$que l'on étend trivialement sur $\Sigma_1^*$. Alors les langages context-free sont clos par homomorphisme. Mieux:

Théorème[Chomsky-Schutzenberger] Tout langage context-free est l'image par homomorphisme de l'intersection d'un langage de parenthèses (langage de Dyck) et d'un langage régulier.

Automates déterministes

Pour analyser les langages de programmation en temps linéaire, on veut des automates déterministes (DPDA, deterministic pushdown automata).

Les langages context-free déterministes sont les langages reconnaissables par un automate déterministe. Par exemple, le langage $\{a ^n b ^n\} \cup \{a ^n b ^{2n}\}$ est context-free non déterministe.

[La conjecture sur l'équivalence des DPDA ne vient d'être résolue qu'en 1997 par Sénizergues de Bordeaux]

La programmation moderne utilise la récursion plutôt que les piles. Mais Yacc génère des analyseurs avec une pile. Le problème du déterminisme se retrouve aussi si on programme récursivement.

Analyse syntaxique

cf. le livre d'Andrew Appel















Récupération d'erreurs

En fait, on analyse syntaxiquement un langage et ses erreurs. Il est difficile de faire de bonnes récupérations d'erreurs. Typiquement on veut sauter au ;; suivant. Il faut donc savoir récupérer l'erreur soit grace à un token spécial error en yacc, soit en récupérant l'execption Parse_error en Caml, et en sautant manuellement les lexèmes jusqu'au ;; suivant, par exemple.

PCF: un petit langage fonctionnel

\begin{displaymath} \begin{array} {lclr} e,e',e'' & ::= & & \hbox{\rm expression... ...\mathrel{\mathtt{in}}e' & \hbox{\rm déf.\ récursive}\end{array}\end{displaymath}

Un interpréteur

On construit une fonction d'évaluation $\mathit{eval}$

$\mathit{eval}(\underline{n}) = n$
$\mathit{eval}(-e) = -\mathit{eval}(e)$
$\mathit{eval}(e+e') = \mathit{eval}(e) + \mathit{eval}(e')$
$\mathit{eval}(e-e') = \mathit{eval}(e) - \mathit{eval}(e')$
$\mathit{eval}(e+e') = \mathit{eval}(e) + \mathit{eval}(e')$
...
$\mathit{eval}(\mathop{\mathtt{ifz}}e \mathrel{\mathtt{then}}e' \mathrel{\mathtt... ...ox{si} \; \mathit{eval}(e)=0\\ \mathit{eval}(e '') & \mbox{sinon} \end{array}$

Déclarations locales et portées

Pour avoir des variables locales et des définitions locales, il faut donner un deuxième argument à la fonction d'évaluation, l'environnement $\rho$ qui décrit la liaison des variables locales.

$\rho$ est une liste d'association entre les noms des variables locales et leur valeur.

On redéfinit la fonction $\mathit{eval}$.

$\mathit{eval}(\underline{n}, \rho) = n$
$\mathit{eval}(-e, \rho) = -\mathit{eval}(e, \rho)$
$\mathit{eval}(e+e', \rho) = \mathit{eval}(e, \rho) + \mathit{eval}(e', \rho)$
...
$\mathit{eval}(\mathop{\mathtt{let}}x = e \mathrel{\mathtt{in}}e', \rho) = \mathit{eval}(e', (x,eval(e,\rho)) :: \rho)$$\mathit{eval}(x, (x,v):: \rho) = v$
$\mathit{eval}(x, (y,v):: \rho) = \mathit{eval}(x, \rho) \quad\quad x\neq y$

Valeurs fonctionnelles et application

Comment déclarer des fonctions et les appliquer? C'est simple dans PCF, il suffit de rajouter l'expression fonctionnelle $\mathop{\mathtt{fun}}x \rightarrow e$ et l'application e(e').

Les expressions pourront donner non seulement des valeurs scalaires, mais aussi des fermetures, i.e. un couple formé d'une expression et d'un environnement.

On ajoute simplement à l'évaluateur les règles:

$\mathit{eval}(\mathop{\mathtt{fun}}x \rightarrow e, \rho) = (\mathop{\mathtt{fun}}x \rightarrow e, \rho)$
$\mathit{eval}(e e', \rho) = \mathit{eval}(e'', (x, \mathit{eval}(e', \rho)):: \rho'')$
où $\mathit{eval}(e,\rho) = (\mathop{\mathtt{fun}}x \rightarrow e'', \rho'')$

Récursivité

Comme attendu, la récursivité introduite par $\mathop{\mathtt{letrec}}$ est une simple variation sur l'évaluation de $\mathop{\mathtt{let}}$.

$\mathit{eval}(\mathop{\mathtt{letrec}}x = e \mathrel{\mathtt{in}}e', \rho) = \mathit{eval}(e', (x,v)::\rho)$
où $v = \mathit{eval}(e, (x,v)::\rho)$

Exemples et exercices

On peut maintenant analyser et évaluer les petits programmes suivants: 

letrec fact = fun x -> ifz x then 1 else x * fact (x-1) in
fact(10);;

letrec fib = fun x -> ifz x then 0 else ifz x-1 then 0 else 
                      fib (x-1) + fib(x-2) in
fib(20);;

let x = let y = 20 in y+3*y in 
let y = let y = 20 in x-y in
x + y ;;

let twice = fun f -> fun x -> f (f x) in
let succ = fun x -> x+1 in
twice (succ) (0);;

2/8/1998