---
# System prepended metadata

title: Compilerbau Notizen

---

# Compilerbau Notizen
## Parser
### VO 21.10.2021
    0.	((x))
    02.	(x))
    022.	x))
    0221.	))
    022.	E))
    0223.	))
    02234.	)
    02.	E)
    023.	)
    0234.	
    0.	E
    stop
----
    X = Yc | {a|b} d.
    Y = [Z|e].
    Z = f {"," f}.

    first(Z) = {f}
    first(Y) = {e,f}
    first(X) = {e,f,c,a,b,d} -> first(Yc) = {e,f,c0}, first({a|b} d) = {a,b,d}

    public static void Parse() {
        scan();
        X();
        check(eof);
    }

    private static void X() {
        if (sym == e || sym == f || sym == c) {
            Y(); check(c);
        } else if (sym == a || sym == b || sym == d) {
            while(sym == a || sym == b) { scan(); }
            check(d);
        } else error("invalid start of X");
    }

    private static void Y() {
        if (sym == f) Z();
        else if (sym == e) scan;
    }

    private static void Z() {
        for(;;) {
            check(f);
            if(sym == comma) scan; else break;
        }
    }

### UE 21.10.2021
    S = aAb | cAd.
    A = eB | f.
    B = gS.

Satz: aegcfdb

            S
    ________|________
    a       A       b eof
      ______|
      e     B
       _____|
       g    S
          __|__
          c A d


## LL(1) Grammatiken
### UE 28.10.2021

Eine Grammatik ist LL(1), wenn alle ihre Produktionen LL(1) sind.
Eine Produktion ist LL(1), wenn die First-Menge aller Alternativen disjunkt ist.

    X = [a]b. -> X = b | ab.
    First(b) = {b}
    First(ab) = {a}
-> Vereinigung muss leer sein für LL(1).

    X = [a]a. -> X = a | aa
nicht LL(1).

    X = A | Ab


## Fehlerbehandlung
### UE 04.11.2021
    _____|code compl v|  Runtime v |#gef. Fehler ^|
    PM   |      +     |      +     |       +      |
    Allg.|    + + +   |    + + +   |     + + +    |
    Spez.|     + +    |     + +    |      + +     |

Legende: 

    ___ = passt
    ... = erwarten wir
    --- = holpern
Bsp.:

    X = abYcd.
    Y = eee.

    abefecd
    ___________X...........
    a    b     |     c    d
          _____Y.....
          e   e(f)  e

    FS = {e, c, d, eof}

    ___________X___________
    a    b     |     c    d
          _____Y_____
          e   (f)   e
               WA geglückt.

    errordist = 3;
    scan() {...; errordist++;}

    error() {if(errordist >= 3) sout(...); errordist = 0;}

-----------------------------------------

    X = a | Y.
    Y = cdef | bY. <=> Y = {b}cdef

    bbmmef

               X
               |
    ___________Y____............
    b    b   bc(m)  c  d   e   f

    1. FS = {b, c, d, e, f, eof}

    2. wir lesen so lange bis sym \elementof FS 
-----------------------
    bbMMef

               X
               |
    ___________Y_-----------_____
    b    b   bc(m)  c   d   e   



## Codegenerierung
### VO 18.11.2021
In Microjava verwenden wir nur einen Interpreter.
Stack nur ein temporärer Speicher für Variablen und Konstanten.

            mstack
    fp -->  +----+
            |    |
    sp -->  +----+
    
    call:
    fp -->  +----+
            |    |
            +----+
            | ra |
    sp -->  +----+

    enter:
            +----+ <-+
            |    |   |
            +----+   | dynamic
            | ra |   | link
            +----+   |
            | dl | --+
    fp -->  +----+ -+
            |    |  |
            |    |  +- lsize
            |    |  |
    sp -->  +----+ -+
    
    exit:
    fp -->  +----+
            |    |
            +----+
            | ra |
    sp -->  +----+
    
    return:
    fp -->  +----+
            |    |
    sp -->  +----+

### UE 18.11.2021
Function Stack: locals
Data/Static Data: Globals
Heap: Objekte/Arrays

Code(Array)

Operands: Register, MJ: Expr.Stack

    IS = {Instructions}.                         <-- 1B ... b, Byte
    Instruction = OpCode {operand}.              <-- 2B ... s, Short
    OpCode = "load0", "add", "getstatic", ...    <-- 4B ... w, Word

    Addressierungsart    Operand    Opcodes    Example
    

| Adressierungsart | Operand       | Opcodes         | Example     |
| ---------------- | ------------- | --------------- | ----------- |
| Immediate        | Konstanten    | const_n 0..5    | const 17    |
|                  |               | const_m1        |             |
|                  |               | const w         |             |
| local            | loc-Var       | load b          | load 3      |
|                  | Parameter     | store b         |             |
|                  |               | load<n\> n 0..3 |             |
|                  |               | store<n\>       |             |
|                  |               | inc b1 b2       |             |
| static           | Globals       | getstatic s     | getstatic 3 |
|                  |               | putstatic s     |             |
| Relative         | Felder        | getfield s      | getfield 1  |
|                  |               | putfield s      |             |
| Indexed          | Arrays        |                 |             |
| Stack            | Werte(estack) | add             |             |
|                  |               | sub             |             |
|                  |               | mul             |             |

---
## Bottom-Up-Parsing
### UE 09.12.2021
#### LR Analyse

    S = xA|yBzB.
    A = [Au]. <-- LL(1) Konflikt
    B = y.
    \__________/
         \____________
                      |
                   (1) BNF
    0: S' = S#.    (2) S' einführen
    1: S = xA.     (3) Je NTS nach Länge sortieren
    2: S = yBzB.   (4) Nummerieren
    3: A = .
    4: A = Au.
    5: B = y.      
    
| Nr  | Zustand                                        | Op                                         | Anmerkungen               |
| --- | ---------------------------------------------- | ------------------------------------------ | ------------------------- |
| 0   | S' = .S#/<br>S = .xA/#<br>S = .yBzB/#          | shift S 1<br>shift x 2<br>shift y 3        |                           |
| 1   | S' = S.#/                                      | acc #                                      |                           |
| 2   | S = x.A/#, u <br> A = ./#, u <br> A = .Au/#, u | shift A 4 <br> red #, u (3) <br> shift A 4 | merging u wegen Rekursion |
| 3   | S = y.BzB/#<br>B = .y/z                        | shift B 5<br>shift y 6                     |                           |
| 4   | S = xA./# <br> A = A.u/#,u                     | red # (1) <br> shift u 7                   |                           |
| 5   | S = yB.zB/#                                    | shift z 8                                  |                           |
| 6   | B = y./z,#                                     | red z (5)                                  | Nachfolger # von 8        |
| 7   | A = Au./#,u                                    | red #,u (4)                                |                           |
| 8   | S = yBz.B/# <br> B = y./#                      | shift B 9 <br> shift y 6                   |                           |
| 9   | S = yBzB./#                                    |                                            |                           |


|     |  x  |  y  |   z   |   u   |   #   |  S  |  A  |  B  |
| --- |:---:|:---:|:-----:|:-----:|:-----:|:---:|:---:|:---:|
| 0   | s2  | s3  |   -   |   -   |   -   | s1  |  -  |  -  |
| 1   |  -  |  -  |   -   |   -   |  acc  |  -  |  -  |  -  |
| 2   |  -  |  -  |   -   | r (3) | r (3) |  -  | s 4 |  -  |
| 3   |  -  | s 6 |   -   |   -   |   -   |  -  |  -  | s 5 |
| 4   |  -  |  -  |   -   |  s 7  | r (1) |  -  |  -  |  -  |
| 5   |  -  |  -  |  s 8  |   -   |   -   |  -  |  -  |  -  |
| 6   |  -  |  -  | r (5) |   -   | r (5) |  -  |  -  |  -  |
| 7   |  -  |  -  |   -   | r (3) | r (3) |  -  |  -  |  -  |
| 8   |  -  | s 6 |   -   |   -   |   -   |  -  |  -  |  -  |
| 9   |  -  |  -  |   -   |   -   | r (2) |  -  |  -  | s 9 |

---

Input: yyzy
| Keller | Input     | Op   | Anmerkungen  |
| ------ | --------- | ---- | ------------ |
| 0      | **y**yzy# | s3   |              |
| 03     | **y**zy#  | s6   |              |
| 036    | **z**y#   | r(5) | (5) B=y.     |
| 03     | **B**zy#  | s5   |              |
| 035    | **z**y#   | s8   |              |
| 0358   | **y**#    | s6   |              |
| 03586  | **#**     | r(5) | (5)B=y       |
| 0358   | **B**#    | s9   |              |
| 03589  | **#**     | r(2) | (2) S = yBzB |
| 0      | **S**#    | s1   |              |
| 01     | **#**     | acc  |              |

---

Input: x
| Keller | Input  | Op   | Anmerkungen |
| ------ | ------ | ---- | ----------- |
| 0      | **x**# | s2   |             |
| 02     | **#**  | r(3) | (3) A=.     |
| 02     | **A**# | s4   |             |
| 024    | **#**  | r(1) | (1) S=xA.   |
| 0      | **S**# | s1   |             |
| 01     | **#**  | acc  |             |

---

Input: xuy
| Keller   | Input    | Op   | Anmerkungen |
| -------- | -------- | ---- | ----------- |
| 0        | **x**uy# | s2   |             |
| 02       | **u**y#  | r(3) | (3) A=.     |
| 02       | **A**uy# | s4   |             |
| 024      | **u**y#  | s7   |             |
| 024**7** | **y**#   | err  |             |

---

LR (k)  k..Anzahl der Vorgriffssymbole
LR (0)  BottumUp-Parser ohne Lookahead
        iff -> kein Zustand, wo sowohl shift als auch reduce möglich wäre
            -> nie mehr als ein reduce pro Zustand

LR(1)   iff -> mit 1 LA folgende Entscheidungen
            * ob shift oder reduce
            * zu welchem NTS reduziert wird
            
---
### UE 16.12.2021
#### LARL Fehlerbehandlung
    S = ab|aXb
    X = Xb|a

->

    0: S' = S#
    1: S = ab
    2: S = aXb
    3: X = a
    4: X = Xb

| Zustand   | Regel         | Übergang   | Guide   |
| --------- | ------------- | ---------- | ------- |
| 0         | S' = .S /     | s S 1      | a       |
|           | S = .ab /#    | s a 2      |         |
|           | S = .aXb /#   | s a 2      |         |
| 1         | S' = S.#      | acc #      | #       |
| 2         | S = a.b /#    | s b 3      | b       |
|           | S = a.Xb/#    | s X 4      |         |
|           | X = .a/b      | s a 5      |         |
|           | X = .Xb /b    | s X 4      |         |
| 3         | S = ab. /#    | r # 1      | #       |
| 4         | S = aX.b /#   | s b 6      | b       |
|           | X = X.b /b    | s b 6      |         |
| 5         | X = a. /b     | r b (3)    | b       |
| 6         | S = aXb. /#   | r # (2)    | #       |
|           | X = Xb. /b    | r b (4)    |         |


| | a  | b  | #  | S  | X  |
|-|----|----|----|----|----|
|0| s2 | -  | -  | s1 | -  |
|1| -  | -  |acc | -  | -  |
|2| s5 | s3 | -  | -  | s4 |
|3| -  | -  |r(1)| -  | -  |
|4| -  | s6 | -  | -  | -  |
|5| -  |r(3)| -  | -  | -  |
|6| -  |r(4)|r(2)| -  | -  |

    s_0...s_n	t_0...t_m #
    Keller		Verbleibender Input
	
Suche Fluchtweg

    t_0...t_m#	v_0...v_k#
	Guides
    Anker sammeln
    Alle Terminalsymbole die in den durchlaufenen Zuständen gültig sind.

Lösche Fehlerhafte Token.

    while t_b !e AS: del(t_b); b++;
Einfügen fehlender Token.

    	Lesen virtuelle Sym. bis t_j in s_i akzeptiert wird.

Beispiel:

    aaabb#
| Stack | Input  | Aktion |     |
| ----- | ------ | ------ | --- |
| 0     | aaabb# | s2     |     |
| 02    | aabb#  | s5     |     |
| 025   | abb#   | error  | **  |
| ...   |        |        |     |


Fluchtweg suchen

    Stack	Guide	Aktion		Anker	Op
    025*	b	r(3),s4		{b}	
    024	b	s6		{b}	b
    0246***	#	r(2),s1		{b,#}	
    01	#	acc		{#}	#

    AS = {b,#}

Lösche Fehlerhafte Token

    abb# -> a e AS? -> false -> delete
    bb#  -> b e AS? -> true  -> stop

Einfügen fehlender Token

    Wiederaufsatz geglückt bei *
    -> nichts eingefügt (keines der Virtuellen Sym. benötigt(Op-Spalte))
    **Fehlermeldung: deleted at pos 
| Stack | Input	 | Aktion |
|-------|--------|--------|
| ...   | ...    | ...    |
| 025   | bb#    | r(3)   |
| 02    | xbb#   |...     |
| ...   |        |        |

Beispiel :

    aaaa#
| Stack | Input | Aktion |      |
| ----- | ----- | ------ | ---- |
| 0     | aaaa# | s2     |      |
| 02    | aaa#  | s5     |      |
| 025   | aa#   | error  | **** |
| ...   |       |        |      |

Fluchtweg suchen

    selber wie im letzten Beispiel

Lösche Fehlerhafte Token

    aa# -> a e AS? -> false -> delete
    a#  -> a e AS? -> false -> delete
    #   -> # e AS? -> true  -> stop


Einfügen fehlender Token
    Wiederaufsatz geglückt bei ***
    ****Fehlermeldung: aa replaced by b at pos 3

| Stack | Input | Aktion         |
| ----- | ----- | -------------- |
| ...   | ...   | ...            |
| 0246  | #     | wie Fluchtweg. |


