La grammaire comporte une récursivité gauche.

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

La grammaire est ambigüe.

On souhaite avoir un analyseur déterministe.

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

S → cSd | deA

S → A | Ac

S → AB

S → Scd | Se | d | e

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

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

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

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.

NUL(U)

NUL(T)

NUL(S)

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.

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

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

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

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

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

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

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

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

xSTy → xxyy (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 compilateur efficace pour tout langage exprimé par ce type de grammaires.

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.

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

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

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.

0+1*

0+0

0+1+2

0+1*0

1*1*2*2