Tutorium 13

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

TODO

Lexikalische Analyse

Idee: String -> Folge von Tokens

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

grafik.png

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();

Evaluation

https://onlineumfrage.kit.edu/evasys/online.php?p=NS7W1

In [ ]: