Algorithmes de fermeture

LL(1)

Définitions

  • ensembles appelés FIRST pour tous les symboles (terminaux, non-terminaux, alternatives) dans G.
  • Un ensemble appelé FIRST pour chaque queue alternative en G; où une queue alternative est une suite de zéro ou plus symboles \alpha si A\alpha est une alternative ou queue alternative en G.

Initialisations

  • Pour tout terminal T, FIRST(T) = {T}.
  • Pour tout non-terminal N, FIRST(N) = \emptyset
  • Pour toute alternative et queue alternative non-vide \alpha, FIRST(\alpha)=\emptyset .
  • Pour toute alternative et queue alternative vide, FIRST = {\epsilon }

Règles d'inférence

  • Pour chaque règle N\rightarrow\alpha dans G, FIRST(N) doit contenir tous les symboles dans FIRST(\alpha), y compris \epsilon si FIRST(\alpha) le contient.
  • Pour chaque alternative ou queue alternative \alpha de la forme A\beta , FIRST(\alpha) doit contenir tous les symboles dans FIRST(A), hormis \epsilon si tant est que FIRST(A) le contient.
  • Pour chaque alternative ou queue alternative \alpha de la forme A\beta telle que FIRST(A) contient \epsilon, FIRST(\alpha) doit contenir tous les symboles de FIRST(\beta), y compris \epsilon si tant est que FIRST(\beta) le contient.

LR(0)

Définitions

Initialisations

Règles d'inférence

SLR(1)

Définitions

Initialisations

Règles d'inférence

LR(1)

Définitions

Initialisations

Règles d'inférence

LALR(1)

Définitions

Initialisations

Règles d'inférence

 
m1ilc/compil_fermetures.txt · Dernière modification: 2010/01/04 15:26 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki