Grammaire LL

Cet article est une ébauche concernant la linguistique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

La grammaire C [1] n’est pas LL (1): la partie inférieure montre un analyseur qui a digéré les jetons " int v ;main(){ " et qui concerne le choix d’une règle pour dériver le non-terminal " Stmt ". En regardant uniquement le premier jeton d'anticipation " v ", il ne peut pas choisir laquelle des deux alternatives pour " Stmt " choisir, étant donné que deux suites d'entrées sont possibles. Ils peuvent être distingués en jetant un coup d'œil sur le deuxième jeton d'anticipation (fond jaune).

Dans la théorie des langages formels, une grammaire LL est une grammaire non contextuelle qui peut être analysée par un analyseur LL, c'est-à-dire qui analyse l'entrée de gauche à droite, et construit une dérivation gauche de la phrase (d'où LL: Left-to-right parsing with Leftmost derivation en anglais, par rapport à l'analyseur LR qui construit une dérivation droite, Rightmost derivation).

Un langage qui a une grammaire LL est appelé un langage LL. Ceux-ci forment des sous-ensembles de grammaires déterministes non-contextuelles (DCFG) et de langages déterministes non-contextuels (DCFL), respectivement.

On dit qu'une grammaire ou un langue donnée "est une grammaire / langue LL" ou simplement "est LL" pour indiquer qu'elle se trouve dans cette classe.

Notes et références

  1. ↑ (en) Brian W. Kernighan et Dennis M. Ritchie, The C Programming Language, Englewood Cliffs/NJ, Prentice Hall, coll. « Prentice Hall Software Series », , 272 p. (ISBN 0-13-110362-8)