:: Enseignements :: ESIPE :: E4INFO :: 2007-2008 :: Compilation ::
[LOGO]

Analyse LR

Dans ce TD, nous allons voir comment construire l'automate des items LR d'une grammaire, ainsi que la table d'analyse correspondante qui permet de tester si un mot appartient ou non au langage reconnu par la grammaire.

Exercice 1 - Analyses LR(0) et SLR(1)

Soit les grammaires suivantes :
G0: (p0) S ::= E '$'
(p1) E ::= E 'a'
(p2) E ::= 'a'
G'0: (p0) S ::= E '$'
(p1) E ::= 'a' E
(p2) E ::= 'a'

Pour ces deux grammaires :
  • Quels sont les langages reconnus ?
  • Calculer les ensembles annulable, premier et suivant. Sont-elles LL(1)?
  • Construire les automates des items LR(0). Ces grammaires sont-elles LR(0) ?
  • Construire la table d'analyse SLR(1). Ces grammaires sont-elles SLR(1)?
  • Décrire l'analyse du mot aaaa. Que remarquez-vous ? Qu'en déduisez-vous ?
  • Dessiner les arbres de dérivation correspondants.

Exercice 2 - Plus d'analyses LR(0) et SLR(1)

Soit la grammaire :
G1 : (p0) S ::= E '$' (p3) T ::= 'id'
(p1) E ::= E '+' T (p4) T ::= '(' E ')'
(p2) E ::= T (p5) T ::= 'id' '(' E ')'
  • Calculer les ensembles annulable, premier et suivant. Sont-elles LL(1)?
  • Construire l'automate des items LR(0). Cette grammaire est-elle LR(0) ?
  • Construire la table d'analyse SLR(1) correspondante. Cette grammaire est-elle SLR(1) ?
  • Décrire l'analyse du mot id(id+id)$
  • Dessiner l'arbre de dérivation correspondant.

Exercice 3 - Encore plus d'analyses LR(0) et SLR(1)

Soit la grammaire G2 :
(p0) S ::= T '$' (p3) X ::= ε
(p1) T ::= X B (p4) B ::= 'b' B
(p2) X ::= 'a' X 'b' (p5) B ::= 'b'
  • Construire l'automate des items LR(0).
  • Construire la table d'analyse SLR(1). Cette grammaire est-elle SLR(1) ?
  • Quel est le langage engendré par la grammaire ?
  • Utiliser la table pour faire l'analyse du mot abb$.

Exercice 4 - Analyses LR(1) et LALR(1)

Soit la grammaire G3 suivante :
G3 (p0) S ::= T '$' (p3) E ::= V
(p1) T ::= V '=' E (p4) V ::= 'id'
(p2) T ::= E (p5) V ::= '*' E
  • Calculer les ensembles annulable, premier et suivant. Sont-elles LL(1) ?
  • Construire l'automate des items LR(0). Cette grammaire est-elle LR(0) ?
  • Cette grammaire est-elle SLR(1) ?
  • Construire l'automate et la table LR(1) de la grammaire G3. La grammaire est-elle LR(1) ?
  • Construire la table LALR(1). La grammaire G3 est-elle LALR(1) ?

© Université de Marne-la-Vallée