On souhaite faire une analyse descendante réalisant des dérivations gauches.

On souhaite faire une analyse ascendante réalisant des dérivations droites.

La grammaire comporte une récursivité gauche.

On souhaite avoir un analyseur déterministe.

La grammaire est ambigüe.

S → A | Ac

S → cSd | deA

S → Scd | Se | d | e

S → AB

On peut supprimer les récursivités gauches indirectes pour n'importe quelle grammaire non-contextuelle.

On peut factoriser n'importe quelle grammaire non-contextuelle, même quand elle comporte plusieurs facteurs gauches en commun.

Il est possible de supprimer les récursivités gauches dans une grammaire ambigüe.

On peut supprimer les récursivités gauches directes pour n'importe quelle grammaire non-contextuelle.

Il est possible de factoriser, si besoin, une grammaire ambigüe.

NUL(U)

NUL(S)

NUL(T)

Les langages engendrés par ce type de grammaires peuvent être reconnus par un automate à états finis.

Tous les langages engendrés par ce type de grammaire sont non-ambigus.

Il existe un algorithme permettant de construire la grammaire minimale reconnaissant un langage engendré par ce type de grammaires.

Tous les langages rationnels (autres que le langage vide ou restreint au mot vide) sont reconnaissables par des grammaires de ce type.

xS → xTx (où x, y sont des terminaux et S,T des non-terminaux) est une règle de production autorisée.

Toute grammaire de type 2 peut être utilisée sans risque pour définir un langage de programmation informatique.

Il est possible d'écrire un programme efficace pour reconnaitre tout langage engendré par ce type de grammaires.

Tout langage engendré par ce type de grammaires peut être reconnaissable par un automate à états finis.

Il existe un algorithme permettant de savoir si deux grammaires de ce type sont équivalentes.

S → xyS (où x, y sont des terminaux et S un non-terminal) est une règle de production autorisée.

On peut écrire un compilateur efficace pour tout langage exprimé par ce type de grammaires.

xSTy → xxyy (où x, y sont des terminaux et S,T des non-terminaux) est une règle de production autorisée.

xSy → Tx (où x, y sont des terminaux et S,T des non-terminaux) est une règle de production autorisée.

xSTy → xSSTy (où x, y sont des terminaux et S,T des non-terminaux) est une règle de production autorisée.

On peut écrire un programme sur un ordinateur permettant de savoir si une chaine est reconnue par la grammaire.

Il existe un algorithme permettant de savoir si 2 grammaires de ce type sont équivalentes.

xSy → Tx (où x, y sont des terminaux et S,T des non-terminaux) est une règle de production autorisée.

On peut écrire un programme sur un ordinateur permettant de savoir si une chaine est reconnue par la grammaire.

Une grammaire de ce type ne peut jamais être réécrite sous la forme d'une grammaire régulière.

On peut écrire un compilateur pour tout langage exprimé par ce type de grammaires.

0+0

0+1+2

0+1*

1*1*2*2

0+1*0