mibeon
/ Compilerbau & Formale Sprachen

LL(1) Parsertabelle Größe

Anzahl der Felder in einer LL(1)-Parsertabelle: Einträge = Nichtterminale · Terminale (|M| = |N|·|T+$|).

LL(1) Parsertabelle Größe
01 · Eingabe

LL(1) Parsertabelle Größe berechnen

Anzahl der Felder in einer LL(1)-Parsertabelle: Einträge = Nichtterminale · Terminale (|M| = |N|·|T+$|).

Lösen für
Einträge = Nichtterminale · Terminale

Worum geht es?

Ein LL(1)-Parser wählt seine nächste Produktion über eine zweidimensionale Tabelle M[A, a], indiziert mit dem aktuellen Nichtterminal A und dem Lookahead-Terminal a (einschließlich $/EOF). Die Tabelle hat damit immer genau |N| · |T| Felder, unabhängig davon, wie viele davon belegt sind — leere Zellen sind Fehlereinträge.

Diese Größe bestimmt den Speicherbedarf der erzeugten Parsertabelle eines Generators und ist die Grundgröße für Kollisionsanalysen: Trägt der Generator in dieselbe Zelle mehr als eine Produktion ein, ist die Grammatik nicht LL(1).

Die Formel

Formel Tabellengröße 
Einträge = Nichtterminale · Terminale

Umstellungen:
    Nichtterminale = Einträge / Terminale
    Terminale      = Einträge / Nichtterminale

Die Variablen

SymbolBedeutungEinheitErklärung
NichtterminaleNichtterminale—Anzahl Nichtterminalsymbole |N|.
TerminaleTerminale—Anzahl Terminalsymbole inkl. EOF (|T| + 1).
EinträgeTabelleneinträge—Felder der LL(1)-Tabelle M[A, a].

Minimal-Beispiel

Ein Mini-Parser mit |N| = 4 Nichtterminalen und |T| = 6 Terminalen (inkl. $):

Rechnung Mini-Parser 
Einträge = 4 · 6
         = 24

Praxis-Beispiele

Beispiel 1 — Ausdrucks-Grammatik

|N| = 6, |T| = 8 (inkl. EOF):

Rechnung Ausdrücke 
Einträge = 6 · 8
         = 48

Beispiel 2 — Nichtterminale aus Tabellenausgabe

Eine generierte Tabelle hat 168 Einträge bei 14 Terminalen:

Rechnung Rückwärts 
Nichtterminale = 168 / 14
               = 12

Beispiel 3 — JSON-Subset

|N| = 7 (Value, Object, Members, Pair, Array, Elements, Element), |T| = 12 (inkl. $):

Rechnung JSON-Subset 
Einträge = 7 · 12
         = 84