Languages and Parsers

antlr http://www.antlr.org/ Grammatik Parser mit definierten Grammatiken für viele Sprachen

Language

words or strings over an alphabet Σ
ε = emtpy word
concatenation, reflection: abc^R = cba, Repetition: a³ = aaa,
Language = set of words, lift string ops to Languages
L^* = {wⁱ | w ∈ L, i ∈ Nat}: Kleene Star: 0 - n concatenations, cross: L⁺: 1-n Concats

regular language

Regular Expression: terminal chars auf Alphabet, concat, union, star, empty set (+ Klammern)
derivation von regular expressions: e' ⇒ e" falls e' = e₁ ... e_k ... e_n, e" = e₁ ... e"_k ... e_n und e"_k eine choice von e'_k (d.h. eine Wahl aus einer Union, oder eine Anzahl für Repetition
Mehrschritt derivations

ContextFree (CF) oder BackusNaurForm Grammar:

nonterminal Alphabet mit einen Ziel Symbol (Axiom), terminal Alphabet, Rules: {X → α | X nonterminal, α Word aus terminals und nonterminals }
Rule mit gleicher linkerSeite stellen Wahl dar, und können auch mit | oder ∪ in ein Rule konzentriert werden
Derivations analog oben, derivation Tree
left(most) bzw. right(most) derivations: immer linkestes nonterminal ersetzen
ambigous: verschiedene derivation tree für selbes wort
links rekursive Regel A → Aβ | γ Aquivalente nicht links rekursiv: A → γA'; A'→ β A'
extended CF Grammar oder EBNF: rechte Seite mit regular expressions statt nur word ⇒ ergibt selbe Klasse von Sprachen

allgemeinere

allgemeine rewrite rules: linke und rechte Seite sind Wörter von terminals und nonterminal
context dependent z.B. mit Einschränkung: αBγ → αβγ

deterministic finite automata besteht aus

d.h. δ(q,a) = q': in zustand q liest Automat inputchar a und geht nach q'

input akzeptiert falls input zu ende gelesen und in F
stop oder error, falls q ∉ F und δ(q,a) undefiniert
clean automata: alle Zustände sind von q₀ aus erreichbar und haben einen Weg nach F
eindeutiger minimaler Automat für eine Sprache: äquivalente States mergen (äquivalent: ausgehende Kanten führen zu äquivalenten Zuständen)
erzeugt Sprache einer (rechts)Linear Grammatik (A → t^*B)

nondeterministic finite automata

aber wir können

spontane moves eliminieren (in dem wir die Kante bis zu einem nicht spontanen verlängern) und
δ in eine Funktion in die Potenzmenge umwandeln: δ: Q x Σ → 2^Q
also deterministisch oder nicht erzeugt dieselbe Sprachen

also lineare Sprachen entsprechen finiten Automaten

mit einem Stack (als secondary tape)

q states mit q₀ und F
Σ Input Alphabet
Γ Stack Alphabet mit Z₀ bottom of stack symbol
δ ⊆ (Q x (Σ ∪ {ε}) x Γ) x (Q x Γ^*) d.h. nicht deterministisch mit spontanen moves

move δ((q, a, γ) x (q' x &beta)): im state q, mit γ topOfStack liest input a (oder nichts ε) und neuer state q0 push't β (n StackSymbols)

CF Grammar entspricht non deterministic push down Automata:
- sponatan er move: nonTerminal auf TOS: pop und push rechte Seite, terminal:
- reading move pop falls read selbes terminal wie auf top of stack
- umgekehrt bekommt man aus Automat eine CF Grammatik
- aber Achtung EBNF Grammar braucht umFormung, sonst wird TransitionsFunktion unendlich
Grammar als Netz von Finite Automata: stack um call/return zu implementieren
Netz von Finite Automata entspricht Syntax Diagramm

liest input (von links nach rechts)
eine erkannte rechte Seite einer Regel, wird durch entsprechendes nonTerminal ersetzt und dann der modifizierte Input wieder analysiert
beste Beschreibung scheint immer noch Original von Knuth: On the Translation of Languages from Left to Right. INFORMATION AND CONTROL 8, 607-639 (1965) zu sein

als LR-Parser mit einem Stack

LR(k) Parser: wir lesen input von links nach rechts, und bauen so Parse Tree auf, reduzieren Handle (n Top of Stack Symbole) zu LHS Symbol der Rule, falls auch k readAhead Zeichen stimmen ⇒ dass das eindeutig ist, ist eben die LR(k) Bedingung
Stack enthält abwechselnd Symbol und State
State is eine Menge von Triples [p, j; α] mit p einer Rule j Position in Rule (0 = vor erstem Symbol), α eine Menge von Wörtern von Terminals der Länge k, die die erlaubten Nachfolger nach der ganze Rule p bezeichnen
Start Zustand ist [A, 0, ende] mit Axiom A
der Automat macht zwei Arten von Moves (muss durch State auf TOS und Preview eindeutig sein!)
1. shift: nächstes Input Zeichen wird auf den Stack gePush't
2. reduce: die die RHS einer Rule (d.h. n * Symbol und State) wird vom Stack gePop't, und das Symbol der LHS drauf gePush't
3. in beiden Fällen wird aus dem Symobl auf TOS und dem State auf TOS-1 ein neuer State abgeleitet und auf den Stack ge'Push't

Dieser Automat wird durch zwei Funktionen konstruiert

Closure: State → State: ein State wird um alle Rules [p, 0] erweitert, die durch Auflösung des nächsten Symbols entstehen können
lookahead: berechnet alles möglichen Wörter der Länge k, die nach einer abgeschlossenen Rule erlaubt sind (und als 3. Element der Triples eingefügt)

das wird ein pushDownAutomat, falls die States endlich bleiben und eindeutige Regeln ergeben ⇔ LR(k) Bedingung

Indem man die closure und lookAhead Berechnung vollständig im vor aus macht bekommt man eine zweiteilige Tabelle

CFG wird angereichert um

für jedes Symbol eine Menge von Attributen
jede Rule mit einer Menge von semantischen Funktionen, die aus Attributen der RHS, die Attribute der LHS berechnen

Z.B. Interpreter, Type Checker, Erstellung des AST

rules are general graphs

each graph rule represented as