Compilerbau

Lexikalische Analyse

Damit der Parser es leichter hat wird der Eingabetext zerlegt in einen Stream von Tokens. Diese haben zwei Attribute: Typ und ggf. Wert.

Zum erkennen der Tokens werden Reguläre Ausdrücke verwendet.

Zur Implementierung von Regulären Ausdrücken werden Endliche Automaten verwendet.

Man kann Übersetzen: RegExp -> NFA (nicht deterministisch, Epsilon) -> DFA (deterministisch)

Es gibt Algorithmen zur Minimierung von Automaten.

Ein bekanntes Tool für die Lexikalische Analyse ist Lex

Es hat das Prinzip Maximal Munch oder auch Longest Match, das besagt es soll so viel wie möglich vom Eingabestrom konsumiert werden.

Syntaktische Analyse / Parsing

Parser liest Token-Stream und erzeugt Baumstruktur

Eine Grammatik besteht aus terminal symbols, nonterminal symbols, production rules und start symbol

Man benutzt Kontext-freie Grammatiken, wo auf der linken Seite der Produktion nur ein Symbol stehen darf.

Es gibt mehrdeutige Grammatiken, die für einen String verschiedene Parsebäume zulassen. So eine ambiguous grammar kann nicht verwendet werden. Siehe auch: https://en.wikipedia.org/wiki/Dangling_else

Grammar Flowchart von Niklaus Wirth

Top-down Parsing

Man fängt beim Startsymbol an und versucht den String abzuleiten.

Im compilerbau immer den Eingabestring left-to-right untersuchen.

recursive descent parsing

Backtracking ist einfacher zu implementieren, aber langsam. Predictive dagegen in linear time.

LL Grammar wird geparsed left-to-right und mit Linksableitung

LL(1) kann geparsed werden mit 1 symbol im vorraus angeschaut (look ahead).

Da geht aber nicht für Linksrekursive Grammatiken. Diese können aber transformiert werden.

Bei der First-Menge sucht man für eine Produktion die möglichen Terminalsymbole welche zuerst auftreten.

Eine Grammatik gehört genau dann zur Klasse LL(1), wenn für zwei unterschiedliche Produktionen A –> α und A –> β folgende Bedingungen gelten:

1. FIRST(α) und FIRST(β) sind disjunkt, dh. sie haben keine gemeinsamen Elemente.

2. Wenn λ ∈ FIRST(α) gilt, dann sind FIRST(β) und FOLLOW(A) disjunkt. Wenn λ ∈ FIRST(β) gilt, dann sind FIRST(α) und FOLLOW(A) disjunkt.

Bottom-up Parsing

Man fängt mit dem String an und versucht das Startsymbol zu erzeugen.

Der Parsebaum wird also von unten, von dern Blättern her aufgebaut, bis man oben beim Startsymbol angelangt ist.

Meistens wird ein shift-reduce parser verwendet in Form von LALR Also Look Ahead Left-to-right Rightmost derivation.

Dieser arbeitet mit einem Stack, einem Handle und dem Look Ahead.

Bottom-up parsing ist relativ kompliziert, und diese Art von Parser wird oft generiert, z.B. vom Yacc bzw. Bison