Tutorium 13¶

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

Übungsblatt 12¶

Aufgabe 1.1¶

$$ S \to L \underline{=} R \mid R\\ L \to \underline{*} R \mid \underline{id}\\ R \to L $$

$$ First_1\left(L\right) = \left\{\underline{*},\underline{id}\right\}\\ First_1\left(R\right) = \left\{\underline{*},\underline{id}\right\}\\ First_1\left(S\right) = First_1\left(L\right) \cup First_1\left(R\right) = \left\{\underline{*},\underline{id}\right\}\\ $$

$$ Follow_1\left(L\right) = \left\{\#,\underline{=}\right\}\\ Follow_1\left(R\right) = \left\{\#,\underline{=}\right\}\\ Follow_1\left(S\right) = \left\{\#\right\}\\ $$

Aufgabe 1.2¶

$SLL(1)$-Grammatik:
$$ S \to L \underline{=} R \mid R\\ First_1\left(L\underline{=}R\right) \cap First_1\left(R\right) = \left\{\underline{*},\underline{=}\right\} \neq \emptyset $$

Aufgabe 2.1¶

Aufgabe 2.2¶

Aufgabe 3¶

$ Value\ \ \ \ \ \ \to \underline{string} \mid \underline{number} \mid Object\\ Object\ \ \ \ \ \to \underline{\{} Member \underline{\}}\\ Member\ \ \to Pair\ Members'\\ Members\ \to \underline{,} Members \mid \epsilon\\ Pair\ \ \ \ \ \ \ \ \ \to \underline{string} \underline{:} Value $

Linksrekursion¶

Alternative für $Member$: $$ Member \to Pair \mid Member Pair $$

Problem: $$ First_k\left(Pair\ Pair\ Pair \dots \right) \subseteq First_k\left(Pair\ Follow_k\left(Member\right)\right)\\ First_k\left(Pair\ Pair\ Pair \dots \right) \subseteq First_k\left(Member\ Pair\ Follow_k\left(Member\right)\right) $$

Aufgabe 3¶

$ Value\ \ \ \ \ \ \to \underline{string} \mid \underline{number} \mid Object\\ Object\ \ \ \ \ \to \underline{\{} Member \underline{\}}\\ Member\ \ \to Pair\ Members'\\ Members\ \to \underline{,} Members \mid \epsilon\\ Pair\ \ \ \ \ \ \ \ \ \to \underline{string} \underline{:} Value $

JSONValue parseValue() {
    String s;
    switch (lexer.current.type) {
        case STRING:
            s = lexer.current.text; lexer.lex();
            return new JSONString(s);
        case NUMBER:
            s = lexer.current.text; lexer.lex();
            return new JSONNumber(s);
        case LCURLY:
            return parseObject();
        default: throw error();
    }
}

Aufgabe 3¶

$ Value\ \ \ \ \ \ \to \underline{string} \mid \underline{number} \mid Object\\ Object\ \ \ \ \ \to \underline{\{} Member \underline{\}}\\ Member\ \ \to Pair\ Members'\\ Members\ \to \underline{,} Members \mid \epsilon\\ Pair\ \ \ \ \ \ \ \ \ \to \underline{string} \underline{:} Value $

JSONObject parseObject() {
    switch (lexer.current.type) {
        case LCURLY:
            lexer.lex();
            JSONObject o = new JSONObject(parseMembers());
            if (lexer.current.type != TokenType.RCURLY)
                error();
            lexer.lex();
            return o;
        default: throw error();
    }
}

Aufgabe 3¶

$ Value\ \ \ \ \ \ \to \underline{string} \mid \underline{number} \mid Object\\ Object\ \ \ \ \ \to \underline{\{} Member \underline{\}}\\ Member\ \ \to Pair\ Members'\\ Members\ \to \underline{,} Members \mid \epsilon\\ Pair\ \ \ \ \ \ \ \ \ \to \underline{string} \underline{:} Value $

List<Pair> parseMembers() {
    List<Pair> l = new LinkedList<Pair>();
    l.add(parsePair());
    while (true) {
        switch (lexer.current.type) {
            case COMMA:
                lexer.lex();
                l.add(parsePair());
                continue;
            case RCURLY: break;
            default: throw error();
        }
        break;
    }
    return l;
}

Aufgabe 3¶

$ Value\ \ \ \ \ \ \to \underline{string} \mid \underline{number} \mid Object\\ Object\ \ \ \ \ \to \underline{\{} Member \underline{\}}\\ Member\ \ \to Pair\ Members'\\ Members\ \to \underline{,} Members \mid \epsilon\\ Pair\ \ \ \ \ \ \ \ \ \to \underline{string} \underline{:} Value $

Pair parsePair() {
    if (lexer.current.type != TokenType.STRING) error();
    JSONString s = new JSONString(lexer.current.text);
    lexer.lex();

    if (lexer.current.type != TokenType.COLON) error();
    lexer.lex();

    JSONValue v = parseValue();
    return new Pair(s, v);
}

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 1.1¶

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 1.2¶

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

Benötigte Instruktionen: iload_n, if_icmpgt <label>, iconst_n, goto <label>,iload_n, aload_n, iconst_n, isub, imul, iadd, isub, invokevirtual, goto

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

Übungsaufgabe 2.1¶

Neg (Add (Const 1) (Add (Const 2) (Var 3)))

bipush 2
iload_3
iadd
bipush 1
iadd
ineg

vs

bipush 1
bipush 2
iload 3
iadd
iadd
ineg

Übungsaufgabe 2.2¶

Code Generation in Haskell

codegen :: Exp -> [String]
-- geg:
height :: Expr -> Int -- Gibt Höhe von Ausdrucksbaum zurück

codegen (Const value) = [ "bipush " ++ (show value) ]

Aufgabe 3¶

public void f(int a, int b):
    iconst_0
    istore_3
 2: iload_1
    iload_2
    if_icmplt 17
    iload_1
    iload_2
    isub
    istore_1
    iinc 3, 1
    goto 2
17: aload_0
    iload_3
    putfield x:I
    aload_0
    iload_1
    putfield y:I
    return

In [ ]: