# 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. |