Tutorium 12

Gruppe 2 und 4
Samuel Teuber
propa@teuber.dev
https://teuber.dev/propa

Heute: Evaluation

...gegen Ende des Tutoriums!

Übungsblatt

Aufgabe 1.1: Unifikation

Terme $$ X_1 = X_2\\ X_2 = X_3 $$ Substitutionen: $$ \sigma_1 = \left[X_1⇨X_2, X_2⇨X_3\right]\\ \sigma_2 = \left[X_2⇨X_3\right]\circ\left[X_1⇨X_2\right]\\ \sigma_3 = \left[X_1⇨a,X_2⇨a,X_3⇨a\right] $$

• $\sigma_2,\sigma_3$ sind Unifikatoren
• $\sigma_2$ ist mgu

Aufgabe 1.2: mgu berechnen

Aufgabe 1.3: mgu angeben

a([1,2,3],[3,4],L) = a([X|Xs], [Y|Ys], L2)

$$ \left[L⇨L2, X⇨1, Xs⇨[2,3], Y⇨3, Ys⇨[4]\right] $$

Aufgabe 2: Lambda Terme

Aufgabe 3: Typabstraktion

Lexikalische Analyse

Idee: String -> Folge von Tokens

• Basierend auf regulären Ausdrücken
• Konstruktion von endlichen Automaten zur Erkennung von Token

Ergebnis der Lexikalischen Analyse

id:X + id:Y * float:Z

Grammatiken und Parsing

Was ist eine Grammatik?

Grammatik $G = \left(\Sigma, V, P, S\right)$

• $\Sigma$: endliches Alphabet
• $V$: Nichtterminale
• $S \in V$ Startsymbol
• $P$ Produktionsregeln $l\rightarrow r$ mit $l\in \left(V\cup\Sigma\right)^+, r\in \left(V\cup\Sigma\right)^*$

$w \Rightarrow z$ Anwendung einer Produktion auf $w$ ergibt $z$
$w \Rightarrow^*z$ Anwendung einer, mehrer (oder keiner) Produktion verwandelt w in z
$w \Rightarrow^+ z$ Anwendung mind. einer Produktion

Weitere Begriffe

• Kontextfreie Grammatik

• Sprache $L(G)$ einer Grammatik $G$

• Linksableitung $\Rightarrow_L$
• Rechtsableitung $\Rightarrow_R$

Beispiel

$$ P = \{ E \rightarrow \textbf{id}, E \rightarrow E \mathbf{+} E, E \rightarrow E \mathbf{\ast} E \} $$

Abstrakter Syntaxbaum

(vs. konkreter Syntaxbaum)

Normalerweise konstruiert ein Parser den AST direkt

Top-Down Parsing

LL: Liest einmal von links nach rechts, baut dabei Linksableitung auf

$$ P = \{S \rightarrow AB\\ A \rightarrow a \mid aA\\ B \rightarrow ab \} $$

$k$-Lookahead

Indizmenge: Welche Terminale sieht der Parser, wenn er sich zwischen zwei Ableitungsregeln entscheiden muss?

$First$ and $Follow$

Für $\chi\in\Sigma^*$ ist der $k$-Anfang $k\colon\chi$ der Präfix der Länge $k$ von $\chi\#\#\dots$ ($\#\notin\Sigma$)

$$ First_k\left(\chi\right) = \{ \beta \mid \exists \tau \in \Sigma^*: \chi \Rightarrow^* \tau \land \beta = k \colon \tau \} $$

$$ Follow_k\left(\chi\right) = \{ \beta \mid \exists \alpha,\omega \in \left(V\cup\Sigma\right)^* \text{ mit } S \Rightarrow^* \alpha\chi\omega \land \beta \in First_k\left(\omega\right) \} $$

$$ P = \{S \rightarrow AB, A \rightarrow aA \mid a, B \rightarrow ab \mid cS\} $$

Aufgabe

$SLL$-Bedingung

Eine (kontextfreie) Grammatik ist genau dann eine $SLL(k)$-Grammatik, wenn für alle Paare von Produktionen $A \rightarrow \alpha \mid \beta$ ($\alpha \neq \beta$) gilt:

$$ First_k\left(\alpha\ Follow_k\left(A\right)\right) \cap First_k\left(\beta\ Follow_k\left(A\right)\right) = \emptyset $$

Spezialfall $k=1$

Für $\alpha \nRightarrow^* \varepsilon$ und $\beta \nRightarrow^* \varepsilon$: $$ SLL \iff First(\alpha) \cap First(\beta) = \emptyset $$

Für $\alpha \Rightarrow^* \varepsilon$ und $\beta \nRightarrow^* \varepsilon$: $$ SLL \iff First(\alpha) \cap First(\beta) = Follow(A) \cap First(\beta) = \emptyset $$

Umfrage

Linksfaktorisierung

Vermeiden von gemeinsamen Nichtterminal-Anfängen:

Parser Bau: Rekursiver Abstieg

• Eine parse-Funktion pro Grammatik-Symbol
• Jedes Symbol konsumiert seinen Teil der Eingabe

Parse-Funktion für Nichtterminal A:

• Für $SLL(1)$:

  switch (lexer.current) {...}
  

• In Zweig, der sich für Produktion $A \rightarrow aAB$ entscheidet:

  expect(TokenType.a);
  parseA();
  parseB();