Interrogation écrite [SuitableStuff]

- Interrogation écrite
  - Exercice 1
    - 1.
    - 2.
    - 3.
    - 4.
    - 5.
  - Exercice 2
    - 1.
    - 2.
    - 3.

Interrogation écrite

du 7 décembre 2007, documents non autorisés.

On modélise par une grammaire G un sous-ensemble du français. Les classes des unités lexicales sont {verbe, nom, qui, et, . }. Ces classes sont aussi les symboles terminaux de la grammaire G. L'unité lexicale verbe peut prendre les valeurs: dérange, suit, aime, frappe, et écoute. L'unité lexicale nom peut prendre les valeurs Alphonse, Bastien, Yannick et Hélène. Les unités lexicales qui, et, et . ont une seule valeur (eux-mêmes).

P →	S verbe C .
S →	nom
C →	nom \| nom R
R →	qui verbe C \| R et R

1.

On veut analyser la phrase : Alphonse suit Bastien qui écoute Hélène qui dérange Yannick et qui aime Alphonse.

La suite de terminaux de la grammaire correspondant à cette phrase : nom verbe (nom ['qui' verbe (nom 'qui' verbe nom 'et' 'qui' verbe nom )])'.'
un arbre de dérivation syntaxique pour cette phrase :

P →	nom
+	verbe
+	C1 →	nom
	+	R1 →	'qui'
		+	verbe
		+	C2 →	nom
			+	R2 →	R3 →	'qui'
					+	verbe
					+	C3 →	nom
				+	'et'
				+	R4 →	'qui'
					+	verbe
					+	C4 →	nom
+	'.'

2.

la grammaire proposée n'est pas LL(1) : la règle “R → R et R” est récursive gauche.
la grammaire est ambiguë : deux arbres sont possibles pour certaines phrases. exemple

3.

Supprimons la récursivité gauche dans la production R → 'qui' verbe C | R 'et' R :

R → 'qui' verbe C R'
R' → 'et' R
R' → epsilon

Calculer la table de transitions LL(1) pour les productions R et R':

	FIRST	FOLLOW
R	'qui'	'.', 'et'
R'	'et', epsilon	'et', '.'

	verbe	nom	qui	et	'.'	$
R			r1
R'				r2, r3	r3

Il y a un conflit lorsqu'on rencontre 'et'. FIXME : Quelle explication peut-on donner?

4.

On considère la grammaire G2 obtenue à partir de la grammaire initiale G en supprimant la production R → R et R. Transformer la grammaire G2 pour la rendre LL(1). Calculer la table de transitions LL(1) de G2.

n°.	G “allégée”	G2
1	P→ S verbe C .	P→ S verbe C .
2	S → nom	S → nom
3	C → nom	C → nom C'
4	C → nom R	C' → R
5	R → qui verbe C	C' → epsilon
6		R → qui verbe C

Puisque deux productions de C commençaient par nom, il faut désambiguer.

	P	S	C	C'	R
FIRST	nom¹⁾	nom	nom	epsilon, qui²⁾)	qui
FOLLOW	$	verbe	.	.	.

	nom	'qui'	'.'
P	r1
S	r2
C	r3
C'		r5	r4
R		r6

5.

En suivant la table de transitions calculée à la question précédente, donner les étapes de l'analyse descendante de la phrase Hélène frappe Bastien qui dérange Yannick.

Pile	Entrée	Action
$P	nom verbe nom 'qui' verbe nom '.' $	Prod 1
$ . C verbe S	nom verbe nom 'qui' verbe nom '.' $	Prod 2
$ . C verbe nom	nom verbe nom 'qui' verbe nom '.' $	pop
$ . C verbe	verbe nom 'qui' verbe nom '.' $	pop
$ . C	nom 'qui' verbe nom '.' $	Prod 3
$ . C' nom	nom 'qui' verbe nom '.' $	pop
$ . C'	'qui' verbe nom '.' $	Prod 5
$ . R	'qui' verbe nom '.' $	Prod 6
$ . C verbe 'qui'	'qui' verbe nom '.' $	pop
$ . C verbe	verbe nom '.' $	pop
$ . C	nom '.' $	prod 3
$ . C' nom	nom . $	pop
$ . C'	. $	prod 4
$ .	. $	pop
$	$	acc

Exercice 2

On se donne la grammaire suivante pour reconnaitre des expression arithmétiques écrites de manière post-fixée. L'ensemble des terminaux est {num, op } et la grammaire possède un seul non-terminal E et les règles suivantes

E	→	num
E	→	E E op

1.

Les expressions suivantes appartiennent-elles au langage engendré par cette grammaire?

Expression	Réponse
num num num op op	oui : E [E E op] op
num num op num op op	non : ([E E op] E op) E manquant op (ou op en trop)

Autrement dit, dans la deuxième expression, il faudrait trouver une dérivation de num num op num op à partir de E E. On peut tout essayer, on n'y arrivera pas

E1	E2
num	num op num op	Faux, E2 n'est pas ainsi dérivable
num num op	num op	Faux, E2 n'est pas ainsi dérivable

2.

Cette grammaire est-ell LL(1)? LR(0)? SLR(1)? Dans le cas de réponse positive, construire la table de transitions correspondante.

LL(1) : certainement pas, encore à cause de la récursivité gauche.
LR(0) : construisons la table de transitions pour voir s'il y a conflit(s).

Fixons notre grammaire:

0	E' → E
1	E → num
2	E → E E num

\begin{eqnarray} . & = & \left\{ E\prime \rightarrow \cdot E, E \rightarrow \cdot num, E\rightarrow \cdot E\; E\; op \right\} & = & s_0 \\ goto \left(s_0,num \right) & = & \left\{ E \rightarrow num \cdot \right\} & = & s_1 \\ goto \left( s_0,E \right) & = & \left\{ E\prime \rightarrow num\cdot , E\rightarrow E\;\cdot\;E\;op \right\} & = & s_2 \\ goto\left( s_2 , E \right) & = & \left\{ E \rightarrow E\;\;E\cdot\;op \right\} & = & S_3 \\ goto\left( s_3, op \right) & = & \left\{ E \rightarrow E\;\;E\;op\cdot \right\} & = & S_4 \end{eqnarray}

	num	op	$		E
0	s2			:	1
1	s2			:	3
2	r1	r1	r1	:
3	s2	s4		:	3
4	r2	r2	r2	:

3.

On suppose que l'on veut traiter également des opérations unaires. Pour cela on ajoute la règle : E → E op. La nouvelle grammaire ainsi obtenue est-elle LL(1)? SLR(1)? LR(1)?

règle	Production
1	E' → E
2	E → num
3	E → E E op
4	E → E op

Pour la table LR(), d'abord les états:

goto	fermeture	LA	état
s₀ =	E' → . E	$
	E → . num	$
	E → . E E op	$
	E → . E op	$
goto(s₀,E) =	E' → E.	$
	E → E . E op	$
	E → . num	op
	E → . E E op	op
	E → . E op	op
	E → E . op	op
	E → E . op	$	= s₁
goto(s₀, num) =	E → num .	$	= s₂
goto(s₁, E ) =	E → E E . op	$
	E → E . E op	op
	E → . num	op
	E → . E E op	op
	E → . E op	op
	E → E . op	$	= s₃
goto(s₁, num) =	E → num .	$	= s₄
goto(s₁, op) =	E → E E op .	$	= s₅
goto(s₃, op) =	E → E op .	$
	E → E E op .	op	= s₆
goto(s₃, E ) =	E → E E . op	op
	E → E . E op	op
	E → . E E op	op
	E → . E op	op
	E → E . op	op
	E → . num	op	= s₇
goto(s₃, num) =	E → num .	$	= s₄
goto(s₇, op ) =	E → E E op .	op
	E → E op .	op	= s₈
goto(s₇, E ) =	E → E E . op	op
	E → E . E op	op
	E → . E E op	op
	E → . E op	op
	E → E . op	op
	E → . num	op	= s₇
goto(s₇, num) =	E → num .	$	= s₄

état	num	op	$	:	E
0	s2			:	1
1	s4	s5	acc	:	3
2	r2	r2	r2	:
3	s4	s6		:	7
4	r2	r2	r2	:
5	r4	r4	r4	:
6	r3/r4	r3/r4		:
7	s4			:	7
8	r3/r4	r3/r4	r3/r4	:

Il y a des conflits (reduce/reduce), ce n'est donc pas LR(1).

Note: pour passer de LR(1) à LALR(1), on regroupe les état s₆ et s₈, s₂ et s₄

¹⁾ = FIRST(S)

²⁾ = FIRST(R