/ Compilerbau & Formale Sprachen

FIRST/FOLLOW-Menge Größe

Maximale Größe einer FIRST- bzw. FOLLOW-Menge einer kontextfreien Grammatik: MaxGröße = Terminale + 1 (inklusive ε bzw. $/EOF).

01 · Eingabe

FIRST/FOLLOW-Menge Größe berechnen

Maximale Größe einer FIRST- bzw. FOLLOW-Menge einer kontextfreien Grammatik: MaxGröße = Terminale + 1 (inklusive ε bzw. $/EOF).

Lösen für

MaxGröße = Terminale + 1

Terminale Terminalanzahl

Worum geht es?

Für eine kontextfreie Grammatik berechnet ein LL-Parser-Generator für jedes Nichtterminal A die Mengen FIRST(A) und FOLLOW(A) — die möglichen Anfangs- bzw. Folgesymbole.

FIRST(A) enthält maximal alle Terminale T plus das leere Wort ε.
FOLLOW(A) enthält maximal alle Terminale T plus das Endemarker-Symbol $ (EOF).

In beiden Fällen ist die maximale Mengengröße also |T| + 1. Diese Schranke bestimmt den Speicherbedarf einer FIRST/FOLLOW-Tabelle und wird in Lehrbüchern (z. B. Aho, Sethi, Ullman) als Obergrenze für statisch dimensionierte Bitmaps verwendet.

Die Formel

Formel Mengengröße

MaxGröße = Terminale + 1

Umstellung:
    Terminale = MaxGröße - 1

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
Terminale	Terminalanzahl	—	Anzahl Terminalsymbole \|T\| der Grammatik.
MaxGröße	Max. Mengengröße	—	Maximale Größe von FIRST(A) oder FOLLOW(A).

Minimal-Beispiel

Eine arithmetische Grammatik hat 5 Terminale (+, *, (, ), id):

Rechnung Arithmetik

MaxGröße = 5 + 1
         = 6

Praxis-Beispiele

Beispiel 1 — Mini-JSON-Grammatik

Terminale: {, }, [, ], :, ,, string, number, true, false, null (|T| = 11):

Rechnung JSON-Grammatik

MaxGröße = 11 + 1
         = 12

Beispiel 2 — Terminale aus Mengengröße

Eine Werkzeug-Ausgabe zeigt FOLLOW(A) mit 18 Elementen:

Rechnung Rückwärts

Terminale = 18 - 1
          = 17

Beispiel 3 — Speicher für FIRST-Bitmap

|T| = 64. Jede FIRST-Menge passt in ein 65-Bit-Wort:

Rechnung Bitmap

MaxGröße = 64 + 1
         = 65 Bit pro Nichtterminal