Tutorium 14

Gruppen 5 und 7
Samuel Teuber
propa@teuber.dev
https://teuber.dev/propa

Übungsblätter

diesmal im Laufe des Tutoriums...

Davor 3 Bemerkungen:

  • wait und notify/notifyAll benötigen einen aktiven Monitor!
  • Bei der Barriere auf Ãœbungsblatt 10: 
    curThreads++;
if (curThreads == maxThreads) freeAll();
else wait()
    Wo ist der Fehler?
  • Ich habe 10 schlafende Threads. Wie oft muss ich notifyAll aufrufen, um alle aufzuwecken?

Lexikalische Analyse

Idee: String -> Folge von Tokens

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

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

$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 \in \Sigma^k \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\} $$

Übungsaufgabe 1

$$ S \rightarrow L \mathbf{=} R \mid R\\ L \rightarrow \mathbf{*}R \mid \mathbf{id}\\ R \rightarrow L $$

Bestimme Menge $First_1$ und $Follow_1$ für alle Nichtterminale

$SLL$-Bedingung

Eine (kontextfreie) Grammatik ist genau dann eine $SSL(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 $$

Übungsaufgabe 1 (Teil 2)

$$ S \rightarrow L \mathbf{=} R \mid R\\ L \rightarrow \mathbf{*}R \mid \mathbf{id}\\ R \rightarrow L $$

Ist $G$ eine $SLL(1)$-Grammatik?

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

Übungsaufgabe 3

Grammatik: $$ \textit{Value} \rightarrow \textbf{string} \mid \textbf{number} \mid \textit{Object}\\ \textit{Object} \rightarrow \textbf{\{} \textit{Members} \textbf{\}}\\ \textit{Members} \rightarrow \textit{Pair } \textit{Members'}\\ \textit{Members'} \rightarrow \textbf{, } \textit{Members} \mid \varepsilon\\ \textit{Pair} \rightarrow \textbf{string} \textbf{ : } \textit{Value} $$

Übungsaufgabe 3

Grammatik: $$ \textit{Value} \rightarrow \textbf{string} \mid \textbf{number} \mid \textit{Object}\\ \textit{Object} \rightarrow \textbf{\{} \textit{Members} \textbf{\}}\\ \textit{Members} \rightarrow \textit{Pair } \textit{Members'}\\ \textit{Members'} \rightarrow \textbf{, } \textit{Members} \mid \varepsilon\\ \textit{Pair} \rightarrow \textbf{string} \textbf{ : } \textit{Value} $$

JSONValue parseValue() {
    String s;
    switch (token.getType()) {
        case STRING: s = token.getSymbol();
            nextToken(); return new JSONString(s);
        case NUMBER: s = token.getSymbol();
            nextToken(); return new JSONNumber(s);
        case LCURLY: return parseObject();
        default: error();
    }
}

JSONObject parseObject() {
    switch (token.getType()) {
        case LCURLY:
            nextToken();
            JSONObject o = new JSONObject(parseMembers());
            if (token.getType() != RCURLY) error();
            nextToken();
            return o;
            break;
        default: error();
    }
}

Übungsaufgabe 3

Grammatik: $$ \textit{Value} \rightarrow \textbf{string} \mid \textbf{number} \mid \textit{Object}\\ \textit{Object} \rightarrow \textbf{\{} \textit{Members} \textbf{\}}\\ \textit{Members} \rightarrow \textit{Pair } \textit{Members'}\\ \textit{Members'} \rightarrow \textbf{, } \textit{Members} \mid \varepsilon\\ \textit{Pair} \rightarrow \textbf{string} \textbf{ : } \textit{Value} $$

Pair parsePair() {
    if (token.getType() != TokenType.STRING) error();
    JSONString s = new JSONString(token.getSymbol());
    nextToken();
    if (token.getType() != TokenType.COLON) error();
    nextToken();
    JSONValue v = parseValue();
    return new Pair(s, v);
}

Übungsaufgabe 3

Grammatik: $$ \textit{Value} \rightarrow \textbf{string} \mid \textbf{number} \mid \textit{Object}\\ \textit{Object} \rightarrow \textbf{\{} \textit{Members} \textbf{\}}\\ \textit{Members} \rightarrow \textit{Pair } \textit{Members'}\\ \textit{Members'} \rightarrow \textbf{, } \textit{Members} \mid \varepsilon\\ \textit{Pair} \rightarrow \textbf{string} \textbf{ : } \textit{Value} $$

List<Pair> parseMembers() {
    List<Pair> l = new LinkedList<Pair>();
    l.add(parsePair());
    while (true) {
        if (token.getType() == COMMA) {
            nextToken();
            l.add(parsePair());
        } else {
            break;
        }
    }
    return l;
}

Codegeneration

JVM Bytecode

  • Heap: Speicher für Objektinstanzen etc.
  • Method Area: Nur für Methoden
  • Runtime Constant Pool
  • Threads:
    • PC
    • JVM Stack
    • Native Method Stack (Laufzeitsystem)

Umgekehrte polnische Notation

  • Infix Notation:
    (x + (y * z))-7
  • Polnische Notation:
    - + x * y z 7
  • Umgekehrte polnische Notation:
    x y z * + 7 -
    Wozu?

Übung

$$ (((4 * x) + 5) / 3) - 2 $$
$$ 4\ x\ *\ 5\ +\ 3\ /\ \ 2\ - $$ 
iconst_4
iload_1
imul
iconst_5
iadd
iconst_3
idiv
iconst_2
isub

Übungsaufgabe 2

a * (x - 1) + c
  • Umgekehrte polnische Notation
  • Bytecode
    • a -> 1; x -> 2; c -> 3
    • Befehle: iload_n, iconst_n, isub, imul, iadd

Methodenaufruf

  • Setze Paramter $p_1,\dots,p_n$ auf Operandenstack
  • Wenn nicht static: $p_0$ ist this
  • Aufruf mittels invokevirtual/invokestatic

Beispiel

public classTest {
    int bar() {
        return foo(42);
    }
    int foo(int i) {
        return i;
    }
}

int bar();
    aload_0
    bipush 42
    invokevirtual #2
    ireturn
int foo(int);
    iload_1
    ireturn

Übungsaufgabe 2 (Teil 1)

if ((a > c) || (c > 0))
    a = a - this.f(a * (x - 1) + c);
  • this in Variable 0
  • a -> 1; b -> 2; c->3
  • Konstantenpool enthält an zweiter Stelle Information zur nicht-statischen Methode f

Erstmal nur if
Benötigte Instruktionen: iload_n, if_icmpgt <label>, iconst_n, goto <label>

    ???
no_shortcut:
    ???
then:
    ...
else:
finish:

Übungsaufgabe 2 (Teil 2)

a = a - this.f(a * (x - 1) + c);
  • this in Variable 0
  • a -> 1; x -> 2; c->3
  • Konstantenpool enthält an zweiter Stelle Information zur nicht-statischen Methode f

Benötigte Instruktionen:
iload_n, aload_n, iconst_n, isub, imul, iadd, isub, invokevirtual, goto

then:
    ???
else:
finish:

grafik.png

grafik.png

grafik.png

Fragen?

Feedback?

...zum Tooling?

Viel Erfolg bei der Klausur!