exercice 1 deuxième session année 2011

[amina mamat]

bonjour,

on a la grammaire suivante 

S-> E$

E->EBE|n

B->+|*

pour la question trouver une grammaire équivalente G' est ce qu'on peut donner cette grammaire  

S->E$

E->nE'

E'->BEE'|ε

B->+|*

merci d'avance 

cordialement 

[Hai NGUYEN VAN]

C'est ce que je me demande aussi. Faut-il juste eliminer la recursion gauche ou bien faut-il aussi eliminer la recursion droite sur le non-terminal E ?

2012/5/18 amina mamat <amina.m...@gmail.com>

[Yann Régis-Gianas]

Bonjour,

le problème de cettez

--
Yann Régis-Gianas
New email : y...@pps.univ-paris-diderot.fr


2012/5/19 Hai NGUYEN VAN <hai.nguy...@gmail.com>:

[Yann Régis-Gianas]

Oups. Mauvaise manip'. On reprend :

Lisez bien la question! Pourquoi cette grammaire est-elle ambiguë?

Si vous comprenez pourquoi elle est ambiguë, alors vous aurez une
piste pour déterminer G'. (Corollaire : vos propositions ne sont pas
les bonnes.)

--
Yann Régis-Gianas
New email : y...@pps.univ-paris-diderot.fr

2012/5/19 Yann Régis-Gianas <y...@pps.univ-paris-diderot.fr>:

[Sandra Naboulet]

Pour ma part, j'ai supprimé la récursion gauche :

S -> E$

E -> nE' | n

E' -> BEE' | BE

B -> + | *

Puis j'ai factorisé :

S -> E$

E -> nE''

E' -> BEE''

E''  -> E' | Ꜫ

B -> + | *

est- ce correct ?

[Sandra Naboulet]

Le carré qui passe mal c'est un epsilon pour désigner le mot vide.

[Sandra Naboulet]

Par contre on obtient des règles de production vide...

On ne doit pas en avoir pour construire un automate LR(1) ? donc si je supprime les regles de production vide, on revient a l'état de la grammaire avant la factorisation..

Donc pas besoin de factoriser ?

[Yann Régis-Gianas]

Hum.

Quelques rappels :
- On supprime la récursion à gauche pour essayer de rendre LL(1) une grammaire.
- LR(1) n'a aucun problème avec les règles epsilon et la récursion (à
gauche comme à droite).

Pour cet exercice :
Pour montrer qu'une grammaire est ambigue, il suffit d'expliciter un
mot qui est reconnue de deux façons différentes...

--
Yann Régis-Gianas
New email : y...@pps.univ-paris-diderot.fr

2012/5/20 Sandra Naboulet <s.nab...@gmail.com>:

[Jean-Marc HAING]

- LR(1) n'a aucun problème avec les règles epsilon et la récursion (à
gauche comme à droite).

Pour créer un automate déterministe LR(1) ne doit on pas supprimer la récursion à gauche ?

Jean-Marc HAING

[fatima-zahra louidadi]

Pour créer un automate déterministe LR(1) ne doit on pas supprimer la récursion à gauche ?

Pour cette exercice je pense que la recursion gauche n'est pas vraiment le probleme, mais que c'est plutot la priorité entre le + et le *,  pour l'expression n+n*n on a deux arbres differents (n+n)*n et n+(n*n)
C'est comme le probleme du if then else.
La grammaire que je trouve pour regler ce probleme est donc :

S->E$
E->E+T | T
T->T*F | F
F->n

Et la du coup la grammaire est plus ambigue(normalement)

[Jean-Marc HAING]

je suis d'accord pr la grammaire, on peut meme mettre le n directement.

mais pour creer l'automate a partir de G

comment fait on lorsqu'on a une boucle?

par exemple si on lit un E dans E->.E+T on a un nouvel etat qui contient E->E.+T 

mais on devrait pouvoir lire un E de nouveau non? 

[fatima-zahra louidadi]

oui normalement on peut lire un nouveau E mais je sais pas comment le mettre sur l'automate..

[Jean-Marc HAING]

En fait, quand on a une boucle ça créé forcément un problème de R/R ?

Jean-Marc HAING

[Yann Régis-Gianas]

Bonne réponse Fatima!

--
Yann Régis-Gianas
New email : y...@pps.univ-paris-diderot.fr

2012/5/20 fatima-zahra louidadi <fatima....@gmail.com>:

[Yann Régis-Gianas]

A propos de la récursion à gauche (ou à droite) et LR(1).

Il n'y a vraiment aucun problème. (Cela a été dit et redit en cours!)
Pour vous en convaincre, regardez ce que produit menhir quand on a une
grammaire avec une récursion à gauche :

/tmp % zed g.mly
Err 1 pangolin
%token S EOF
%start<unit> s
%%

s: mylist EOF {}

mylist: /* empty */ {}
| mylist S {}
/tmp % menhir --dump g.mly
15:47 pangolin
/tmp % cat g.automaton
15:47 pangolin
State 0:
s' -> . s [ # ]
-- On s shift to state 1
-- On mylist shift to state 2
-- On S reduce production mylist ->
-- On EOF reduce production mylist ->

State 1:
s' -> s . [ # ]
-- On # accept s

State 2:
mylist -> mylist . S [ S EOF ]
s -> mylist . EOF [ # ]
-- On S shift to state 3
-- On EOF shift to state 4

State 3:
mylist -> mylist S . [ S EOF ]
-- On S reduce production mylist -> mylist S
-- On EOF reduce production mylist -> mylist S

State 4:
s -> mylist EOF . [ # ]
-- On # reduce production s -> mylist EOF

--
Yann Régis-Gianas
New email : y...@pps.univ-paris-diderot.fr

2012/5/20 Yann Régis-Gianas <y...@pps.univ-paris-diderot.fr>:

[Iyari Rojas]

mais avec la grammaire de fatima on peut pas lire (n+n)*n+n

c'est pas plutot

S -> E$

E -> T+E | T

T -> n | E*T

?

[Iyari Rojas]

a non c'est bon j'ai compris