matser

bonjour,

Nous allons voir ici une grammaire hors-contexte LL d'une liste où C apparraît au plus une fois.
On a le non-terminal A qui est une liste B avec un C qui apparaît zéro ou une fois. Ici, le point virgule n'est pas la fin de ligne de code mais la séquentialité entre deux lignes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
A -> B
A -> B ; C
A -> C ; B
A -> B ; C ; B
A -> C

en factorisant à gauche (EPSILON est la production vide):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
A -> B X
A -> C Y
X -> ; C
X -> ; C ; B
X -> EPSILON
Y -> ; B
Y -> EPSILON

X se factorise à gauche comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
X -> ; C Z
X -> EPSILON
Z -> ; B
Z -> EPSILON

ce qui donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
A -> B X
A -> C Y
X -> ; C Z
X -> EPSILON
Z -> ; B
Z -> EPSILON
Y -> ; B
Y -> EPSILON

comme Z et Y sont pareils, on peut simplifier ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
A -> B X
A -> C Y
X -> ; C Y
X -> EPSILON
Y -> ; B
Y -> EPSILON