TP 10 --- L3 -- Language et Compilation

Grammaires

Sommaire

  1. Grammophone
  2. Grammaires et analyse LL
  3. Grammaires et analyse LR
  4. Grammaires LL(*)
  5. Diverses propriétés des grammaires

Grammophone

Nous allons utiliser ici l'outil Grammophone développé à l'université de Calgary.

Les symboles terminaux commencent par une lettre minuscule, un chiffre ou une ponctuation (~ ! @ # * ( ) _ + ' ; : / ?). Les variables commencent par une majuscule. C'est facile, c'est presque la convention contraire d'ANTLR !

La variable de la partie gauche d'une règle est séparée de sa production en partie droite par une flèche ->, formée du signe moins suivi du signe supérieur. Une règle se termine par un point et on peut donner des parties droites alternatives en les séparant par une barre verticale. Les symboles sont séparés par un espace.

L'axiome apparaît toujours en partie gauche de la première règle.

On a même droit aux commentaires multi-lignes encadrés par /* et */.

Attention : le caractère '-' est interdit sauf pour le symbole de dérivation '->'. Bien respecter les espaces entre symboles, car seul l'espace est séparateur.

Premier test

  S -> a A B e.
  A -> A b c | b.
  B -> d.
Entrez la grammaire dans le formulaire de la page https://mdaines.github.io/grammophone et faites en l'analyse !
Que signifient les expressions suivantes : Traduisez les expressions suivantes :

Grammaires et analyse LL

Nous reprenons ici l'exemple du cours pour la construction de table d'analyse LL(1)

  S -> X Y.
  X -> a X b| .
  Y -> c Z | Z e.
  Z -> d c Z | .

Observez la table d'analyse LL(1) pour cette grammaire construite par l'outil.

Manipulation de grammaire. Rendre une grammaire LL(1)

Considérons la grammaire suivante qui n'est pas LL(1).

S -> a A B e.
A -> A b c | b.
B -> d.
Quel type de conflit observe-t-on dans la table d'analyse LL(1) ? Quelle en est la cause ? Utiliser l'outil pour transformer cette grammaire en une grammaire équivalente qui soit LL(1).
Même question pour la grammaire suivante : 
S -> ( L ) | ( ) | at.
L -> S | L S.
Même exercice avec : 
  S -> B b | C c.
  B -> a b.
  C -> a c.

On va reprendre maintenant des grammaires reconnaissant des expressions arithmétiques.

La grammaire suivante peut-elle être transformée en une grammaire équivalente qui soit LL(1) ? 
Expression -> Somme.
Somme -> Facteur plus Somme 
      |  Facteur moins Somme
      |  Facteur.
Facteur -> id | moins Facteur.
Même question en ajoutant des expressions booléennes : 
Booleen -> Disjonction.
Disjonction -> Conjonction ou Disjonction | Conjonction.
Conjonction -> Negation et Conjonction | Negation.
Negation -> Comparaison | non Negation.
Comparaison -> Expression OpComparaison Expression.
OpComparaison -> inf | sup | equ.

Expression -> Somme.
Somme -> Facteur plus Somme 
      |  Facteur moins Somme
      |  Facteur.
Facteur -> id | moins Facteur.
Peut-on encore obtenir une grammaire équivalente LL(1) en ajoutant la règle : 
Facteur -> ( Expression ) .
Ajoutez enfin les expressions booléennes parenthésées : 
Negation -> ( Booleen ).
D'où vient le problème ?
Vous pouvez toujours tenter de construire une table d'analyse LL(1).

Grammaires et analyse LR

Premier exemple

Reprenez le premier exemple de grammaire non LL(1)

S -> a A B e.
A -> A b c | b.
B -> d.
Cette grammaire est-elle SLR(1) ?

Analyse LR

Soit la grammaire suivante : 
S -> a S b | a b.
Cette grammaire est-elle LL(1) ? SLR(1) ?
Utiliser la table d'analyse SLR(1) pour réaliser l'analyse des entrées : ab et abb.
Note : Cette grammaire est LL(2).

Conflit shift/reduce

Soit la grammaire suivante : 
Instruction -> si condition alors Instruction
      |   si condition alors Instruction  sinon Instruction
      |   expression
      .
Observez les conflits dans les tables d'analyse LL et SLR. Comment les résoudre ?
Quel arbre d'analyse obtiendra-t-on lors de l'analyse de l'entrée suivante ? 
si condition alors si condition alors expression sinon expression

Conflit reduce/reduce

Soit la grammaire suivante : 
S ->	V assign E
  |     id.
V ->	id.
E ->	V
  |	num.
Observez les conflits dans les tables d'analyse LL et SLR. Comment les résoudre ?
Quel arbre d'analyse obtiendra-t-on lors de l'analyse des entrées suivantes ? 
id 
id assign num

Grammaires LL(*)

Reprenons la grammaire LL(2) précédente : 
S -> a S b | a b.
Cela donne en syntaxe ANTLR : 
grammar ll2;

start : s EOF;

s : 'a' s 'b'
  | 'a' 'b'
  ;
La grammaire ll2.g est-elle autorisée par ANTLR ?
Soit la grammaire suivante : 
A ->	C
  |	B.
C ->	a C a
  |	b.
B ->	a B
  |	c.
Est-elle LL(1) ? SLR(1) ? LL(k) ? LL(*) ?
Voir ci-dessous la grammaire réécrite en syntaxe ANTLR : 
grammar lr0;
a : c
  | b
  ;
c : 'a' c 'a'
  | 'b'
  ;
b : 'a' b
  | 'c'
  ;