par , 08/12/2019 à 19h14 (352 Affichages)
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
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):
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:
1 2 3 4
| X -> ; C Z
X -> EPSILON
Z -> ; B
Z -> EPSILON |
ce qui donne:
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:
1 2 3 4 5 6
| A -> B X
A -> C Y
X -> ; C Y
X -> EPSILON
Y -> ; B
Y -> EPSILON |