Zum Inhaltsverzeichnis
Algorithmus zur Firstmengenbestimmung
Trennlinie

Algorithmus zur Firstmengenbestimmung

 
 

Berechnung von FIRST für Grammatiksymbole
Für alle Grammatiksymbole X wird FIRST(X) berechnet, indem die folgenden Regeln solange angewendet werden, bis zu keiner FIRST-Menge mehr ein neues Terminal oder hinzukommt:

  1. Wenn X ein Terminal ist, dann ist FIRST(X)={X}
  2. Wenn X eine Produktion ist, füge zu FIRST(X) hinzu.
  3. Wenn X Nichtterminal und X Y 1 Y 2 ... Y k eine Produktion ist, dann nimm zu FIRST(X) hinzu, falls für irgendein i in FIRST(Yi) und in allen FIRST(Y1), ..., FIRST(Yi-1) enthalten ist, d.h. FIRST(Y1), ..., FIRST(Yi-1) .
    Wenn für alle j=1,2,...,k in FIRST(Yj)enthalten ist, nimm zu FIRST(X) hinzu.

Berechnung von FIRST für eine Folge von Symbolen
Für X1 X2 ...Xn läßt sich FIRST nun folgendermaßen berechnen:
In FIRST (X1 X2 ...Xn) werden alle Symbole aus FIRST(X1) aufgenommen, die ungleich sind.
Ebenso werden alle Symbole ungleich aus FIRST(X2) hinzugenommen, falls FIRST(X1) enthält.
Entsprechend werden alle Symbole ungleich aus FIRST(X3) hinzugenommen, falls sowohl FIRST(X1)als auch FIRST(X2) enthalten usw. Falls für alle i mit 0 < i <= n in allen FIRST(Xi) enthalten ist, wird auch selbst zu FIRST (X1 X2 ...Xn) hinzugefügt.  

Trennlinie
Zum Seitenanfang

Letzte Änderung 2. Juni 1999 © Copyright Thomas App