Skip to content
Parser
Quiz letzte Woche
- Lexer liefert nur den regulären Anteil
- Keine rekursive Syntax-Elemente, bzw. Elemente, die _nur rekursiv ausdruckbar sind
Top-Down Parser
- Input: Terminalsymbole, Output: Syntaxbaum
- Kann nur kontextfreie Sprache
- z.B. nicht, ob Variable deklariert ist, oder Parameter auf Argumente passen, type checking
- Diese sind kontextabhängig
- Der Parser muss eine Ableitung der Syntaxregeln finden, um einen gegebenen Input herzuleiten
- Quasi eine Ableitung rückwärts, von Token zu einer Regel
- Diese Woche: Syntax-Check, nächste Woche Syntaxbaum
Syntax-Baum
- Konkreter Syntax-Baum (Parse Tree) befolgt die Syntax genau
- Abstract Syntax-Tree (AST) kann unwichtige Details auslassen
- AST kann nicht automatisch erzeugt werden, "nach Gusto" des Entwicklers
- Selber implementierte Parser können direkt AST liefern
Top-Down vs. Bottom-Up
- Top-Down: Zuerst "linke Seite" der Regel anwenden, bis Eingabetext rauskommt
- Immer von links her auflösen
- Bottom-Up: Mit Eingabetext beginnen, und Regeln darauf anwenden, bis man zum "Startsymbol" kommt
- Umgekehrt zum Top-Down Parsing
Recursive Decent
- Wir nutzen den Stack der Methodenaufrufe als "Push-Down Automat"
- Pro Nicht-terminalsymbol eine Methode
- Wenn ein Nicht-Terminalsymbol in Syntax (rechte Seite) vorkommt, wird die entsprechende Methode aufgerufen
- Methoden können sich gegenseitig rekursiv aufrufen
- Gibt keine Entscheidungsprobleme bei Top-Down (zielorientiert)
- Anderer Ansatz, wenn das nicht geht: Produktion ausprobieren und bei Fehler "backtracken" (exponentielle Laufzeit)
- One Token lookahead reicht aus
- Momentan geben die Methoden
void
zurück, wo später ein Syntaxbaum erstellt wird
- Für nicht-terminal-Symbole braucht es z.T. ein weiteres Lookahead
- Mögliche Terminalsymbole erfassen, die in einem nicht-terminal-symbol als erstes vorkommen können:
FIRST
Set
- FIRST-Sets können Vereinigungen von "untergeordneten" NT-Symbolen haben
- Wenn zwei NT-Symbole nicht-disjunkte FIRST-Mengen haben, reicht ein One-Token-Lookahead nicht mehr aus, da nicht entschieden werden kann
- Braucht weiteres Lookahead, dann irgendwann drei, etc.
- Stattdessen Syntax "umformen" für Parser
- Für beide Regeln eine eigene Regeln erfassen und das Gemeinsame zusammen ziehen
Linksrekursion
- z.B.
Sequence = Sequence [ Statement ]
- Gibt bei Implementation bei Recursive Decent endlose Rekursion
- Bottom-Up Parser können damit umgehen
- Umschreiben nach
Sequence = { Statement }
Syntaxbaum
- Statement-Block ist ein Spezialfall von Statement, in anderen Sprachen ist ein Statement-Block auch ein Statement
- Achten auf Assoziativität bei Expressions
Fehlerbehandlung
- Nur häufige Fehler korrigieren
- Basiert immer auf Hypothese, es können leicht Folgefehler entstehen
- Andere Fehler wie inkompatible Typen, falsche Argumentliste, etc. werden im Semantic Checker behandelt
Attributierte Grammatiken
- EBNF-Grammatiken mit kontext-sensitiven Attributen ergänzen
- Semantische Checks oder Erzeugen des AST
Write()
ist eine Aktion und gibt lediglich etwas auf die Konsole aus
- Ausgabe Folie 22: `1 2 - 3 4 - +
- Postfix-Notation wie bei HP Taschenrechner
- Die Aktionen werden immer zum Schluss "der Parse-Methode" ausgeführt
- Der Parser kann auch direkt statische Ausdrücke evaluieren
- Direkt Syntaxbaum erzeugen mit
new BinaryExpression(...)
etc. direkt im Attribut
- S-attributiert (synthetisiert): Attribute lesen nur Parameter von Teilregeln (rechte Seite)
- L-attributiert (Ererbt): Attribut kann auch "linke" Seite lesen
- Es kann alles in Grammatik beschrieben werden, in der Praxis ist dies aber unübersichtlich und kompliziert
Bottom-Up Parser (LR-Parser)
- Ansatz: Tokenstream nehmen und "zusammenfalten" zu Syntaxbaum
- Nach jedem gelesenen Symbol prüfen, ob die Folge einer Regel entspricht
- Wenn ja, "Reduce"
- Wenn nein, das nächste Zeichen auslesen (shift)
- Am Schluss muss das Startsymbol übrig bleiben, sonst Syntaxfehler
- Es kann zu Entscheidungsschwierigkeiten kommen: "Shift-reduce" / "Reduce-Reduce" Probleme
- Grammatik anpassen oder "von Hand"
- LR ist "mächtiger" als LL-Parser