Chap 1 Grammaires et dérivations.

Une grammaire algébrique (context free) est donnée par :

un alphabet terminal A un alphabet de variables (non terminal V) un ensemble de règles de production R de la forme

avec V et (VA)*On a donc RVx(VA)*

On note la grammaire G = (V.A.R)

1

La grammaire algébrique est utilisée pour engendrer un langage formel en utilisant des dérivations.

Définition

Soit ,(VA)*On dit que dérive ( )

ssi =12, =12et que est une règle de la grammaire (.)R.

2

Pourquoi grammaire ? Chaque langage a des règles.

Grammaire donne une spécification syntaxique précise facile à comprendre

A partir de grammaire on peut facilement construire un analyseur syntaxique qui pourra déterminer si le programme source est correct.

Grammaire bien définie donne une structure au langage de programmation très utile pour la traduction et

pour détection des erreurs.

Si le langage évolue c'est bien plus facile d'ajouter des nouvelles constructions si l'implémentation existante est basée sur la description grammaticale du langage.

3

La dérivation commence toujours par le symbole de début (start symbol ou axiome en français) et on remplace de façon répétée le non-terminal à gauche d'une règle par la partie droite de cette règle de production.

4

Ex. (*) expr expr op exprexpr (expr)expr -exprexpr idop +op -op *op /

A={id, +, -, *, /, (, )}V={expr, op}expr est start symbol

5

La signification :

expr -expr signifie qu'une expression précédée par - est aussi une expression. Cette production permet de générer des expressions plus complexes à partir d'expressions plus simples. On peut remplacer expr par -expr. On peut décrire ça en écrivant expr - expr, c.a.d. expr dérive -expr.

La production expr (expr) nous montre qu'on peut remplacer une

occurrence de expr dans n'importe quelle chaîne des symboles de grammaire par (expr).

Par exemple, E*E (E)*E ou E*EE*(E). On peut prendre E et appliquer des productions dans n'importe quel

ordre pour obtenir une séquence de remplacements.

6

Ex. E -E-(E) -(id). Une séquence comme ça s'appelle une dérivation de -(id) de E. Cette dérivation montre qu'une chaîne –(id) est une expression

valide.

7

Manière plus abstraiteA si A est une production de grammaire et et sont des chaînes

arbitraires. Si on a 1 2 …n. On dit que 1 dérive n. Symbole signifie dérive immédiatement (dans un seul étape).

*Si on veut dire dérive en 0 ou plus étapes on utilise Alors :1) pour

+ 2) Si et alors + dérive en un ou plus étapes

8

Définition de L(G) : langage généré par G.

Chaînes contenues dans L(G) peuvent contenir seulement des symboles terminaux de G.

La chaîne de terminaux wL(G) ssi Sw. w est une phrase de G;Le langage qui peut être généré par G est un langage

algébrique. Si 2 grammaires génèrent le même langage elles sont équivalentes.

9

Ex 1. -(id+id) est une phrase du langage engendré par G parce qu'il y a une dérivation : E-E-(E) -(id+E)-(id+id).

10

Ex 2. G’ :

a b

ou pour simplifier a + b avec A={a, b} et V = {}. Le langage engendré par est l'ensemble des expressions arithmétiques

en notation polonaise préfixe. a : unique symbole d'opérateurs et b : unique symbole de variable. LG() ={b, abb, aabbb, ababb, …}

11

Ex 3. H :

ab

A={a, b} V={} Le langage engendré par H est l'ensemble des expressions bien

parenthésées avec a : parenthèse ouvrante, b : parenthèse fermante.

12

Les automates finis correspondent à une classe particulière de grammaires algèbriques : ce sont les grammaires linéaires dont toutes les règles sont de la forme a avec V, aA ou bien .

Considerons un automate fini A=(Q, I, T, F) et la grammaire G ayant comme

ensemble de variables l'ensemble Q des états de A et comme règles p aq pour toutes les flèches (p.a.q) de A et des règles t pour tout tT.

Le langage engendré par la grammaire G à partir des variables de I est égal

au langage reconnu par l'automate. On a une dérivation p wq dans G ssi un chemin p q, étiquetté par w

dans A. (par recurrence sur la longueur de w).

13

Réciproquement, si G = (V, A, R) est une grammaire linéaire on

construit A=(Q,i,T,F) qui reconnaît le langage engendré par G en prenant Q=V, i=start, F={(.a.)| a}

et T={V| }

a b ba

reconnaît le langage a + b

b + a +

14

Pourquoi utiliser les expressions rationnelles pour définir le syntaxe lexicale d'un langage ?

Les règles lexicales sont souvent très simples, et alors pour les décrire on n'a pas besoin d'une notation aussi puissante que grammaires

Expressions rationnelles donnent une notation

pour décrire les lexèmes plus facile à comprendre que des grammaires.

15

Les analyseurs lexicales plus efficaces peuvent être construits automatiquement des expressions rationnelles que des grammaires arbitraires.

Quand on sépare la structure syntaxique d'un langage dans les

parties lexicales et non-lexicales on obtient un moyen efficace pour modulariser un compilateur. On obtient deux modules de taille possible à gérer.

16

• Un langage formel L est un langage algébrique (context-free) si une grammaire algébrique G telle que L=LG().

• beaucoup de langages algébriques qui ne sont pas reconnaissables par des automates finis.

• Ex. ab + • Supposons que P soit reconnu par un automate A=(Q, I, R, F).• Pour n0 le mot anbn est bien parenthesé, donc un chemin • in pntn.

• pn est un état ou on arrive après la lecture de an. • Si n<>m, pn <> pm puisque ambn n'est pas bien parenthesé et si pn = pm on

ait un chemin • in pn= pmtn. • D'ou la contradiction, car A doit avoir le nombre fini d'états par définition.

17

• Revenons à dérivation permettant à reconnaître une phrase • -(id+id) dans la grammaire des expressions arithmétiques. • Gauche : E-E-(E) -(E+E) -(id+E) -(id+id) (1)

• Droite : à partir de -(E+E) -(E+id) -(id+id).(2)

• L'ordre de remplacement est différent. • Pour comprendre certains analyseurs il faut considérer des dérivations

ou à chaque moment de dérivation on remplace juste le non-terminal le plus à gauche.

• On appelle une dérivation comme ça – dérivation gauche. • En utilisant des conventions de notation on peut marquer chaque étape

wAw ou w consiste juste de terminaux A est une production et est une chaîne des symboles de grammaire.

• Dérivation droite est définie de façon analogue.

18

Arbres de dérivation (parse trees)

• C'est une représentation graphique pour une dérivation qui filtre le choix de remplacement.

• A chaque étape de dérivation il y a 2 choix à faire. Il faut

choisir quel non-terminal on veut remplacer et après avoir fait ce choix, il faut choisir quelle alternative on veut utiliser.

19

Les étapes de construction pour -(id+id).

E E E- E - E - E

( E ) ( E )

E + E

E E En lisant la frontière on obtient la phrase.- E - E Les feuilles sont étiquetées par des terminaux.

( E ) ( E )

E + E E + E

id id id

20

Quand même il ne faut pas penser que chaque phrase donne nécessairement un seul arbre ou une seule gauche ou droite dérivation.

On prend une phrase id + id*id.Il y a 2 dérivations gauches distinctes.EE+E E E*E E

id+E E + E E+E*E E * Eid+E*E id E * E id+E*E E + E idid+id*E id id id idid+id*E id+id*Eid+id*id id+id*id

La première reflète la précédence normale des opérateurs.

21

Ambiguité :

• Une grammaire qui produit plus qu'un seul arbre de dérivation pour une phrase quelconque s'appelle une grammaire ambiguë.

• Pour beaucoup d'analyseurs c'est préférable de pouvoir

transformer une grammaire ambiguë dans une grammaire non-ambiguë.

22

• Exemple de transformation – élimination d'ambiguité.

• "dangling else". • stmt if expr then stmt• | if expr then stmt else stmt• |other • other – toute autre instruction.

23

• if E1 then S1 else if E2 then S2 else S3.stmt

if expr then stmt else stmt

E1 S1 if expr then stmt else stmt

E2 S2 S3

24

• if E1 then if E2 then S1 else S2. (*)a) stmt

if expr then stmt E1 if expr then stmt else stmt

E2 S1 S2

25

b)stmt

if expr then stmt else stmt

E1 E2

if expr then stmt

E2 S1

26

Dans tous les langages on préfère (a).

27

Règle : Faites correspondre chaque else avec le plus proche "unmatched" then. On peut incorporer cette règle directement dans la grammaire.

stmt matched_stmt

| unmatched_stmt matched_stmt if expr then matched_stmt else

matched_stmt| other

unmatched_stmt if expr then stmt

| if expr then matched_stmt else unmatched_stmt

28

stmt

unmatched_stmt

if expr then stmt

E1 matched_stmt

if expr then matched_stmtelse matched_stmt

E2 other other

S1 S2

29