# Compielerbauexekution

1.
a) Was ist die Aufgabe eines Scanners oder Lexers?

>Antwort: Lesen des Eingabetextes und zerteilen des Eingabestroms in Tokens/Lexeme der Grammatik, Überlesen von Leerzeichen und Kommentaren, Berechnung der Token-Attribute

b) Mit welchem Typ von Grammatik arbeitet ein Scanner oder Lexer mindestens?

> Antwort: Typ-3-Grammatik

c) Was ist die Eingabe für eine Lexer?
> Antwort: Quelltext = Folge von (ASCII) Zeichen

d) Was ist die Aufgabe eines Parsers?

>Tokenstream prüfen ob eine Ableitung möglich ist und dabei einen AST erzeugen.

e) Mit welchem Typ von Grammatik arbeitet ein Parser mindestens?

>Typ 2

f) Was ist die Eingabe für einen Parser?

>Tokenstream

g) Was ist die Aufgabe der semantischen Analyse?

>Überprüfung der Kontextabhängigkeiten im erzeugten AST

h) Nennen sie ein Beispiel für die Aufgabe der semantischen Analyse anhand der in der Vorlesung verwendeten Programmiersprache X.

>Es wird überprüft ob die variablen Dekleration richtig vorgenommen wurde

i) Was ist die Aufgabe der Optimierung in einem Übersetzer?

>Vereinfachen des gegebenen AST
>Reduktion der nötigen Ressourcen (Zeit, Speicherplatz, ...) für die Ausführung des übersetzten Programms

j) Nennen sie ein Beispiel für die Optimierung bei der Übersetzung einer Programmiersprache in ausführbaren Code.

>Constant Propagation
>Dead Code Elimination
>If Optimization
>

2. Gegeben sei eine Sprache L, für die ein Scanner die folgenden Token erkennen und unterscheiden soll.

* hans: Das Wort "hans" bestehend aus den Zeichen h, a, n & s
* haus: Das Wort "haus" bestehend aus den Zeichen h, a, u & s
* nix: Das Wort "nix" bestehend aus n, i & x

Leerräume und Zeilenumbrüche seien in der Menge W. Geben sie für einen tabellengesteuerten Scanner die Steuertabelle an.

>| Zustand | Eingabe | Folgezustand | Ausgaben | Token |
>| ------- | ------- | -------- |--------- |------ |
>| WS | WS | WS | - | - |
>| WS | h | h | - | - |
>| WS | n | n | - | - |
>| h | a | ha | - | - |
>| ha | n | han | - | - |
>| han | s | hans | - | hans |
>| ha | u | hau | - | - |
>| hau | s | haus | - | haus |
>| WS | n | n | - | - |
>| n | i | ni | - | - |
>| ni | x | nix | - | nix |
>|hans, haus, nix | WS | WS | X | - |
>|hans, haus, nix | h | h | X | - |
>|hans, haus, nix | n | n | X | - |
3. Gegeben sei die Grammatik G = (N,T,S,P) mit N = {A,B,S}, T = {a,b,c,d} und P = {S -> A|B, A -> Bcd|aAb, B -> ad|ε}

a) G erfüllt die LL(1)-Eigenschaft nicht. Begründen sie dies.

> FIRST(Bcd FOLLOW(A)) = {a,c}
> FIRST(aAb FOLLOW(A)) = {a}
> Zur Vollständigkeit halber [ FIRST(ad FOLLOW(B)) = {a}
> FIRST($\epsilon$ FOLLOW(B)) = {c} ]
> Da FIRST(Bcd FOLLOW(A)) vereinigt mit FIRST(aAb FOLLOW(A)) != {} ( gemeinsame Menge {a} )

b) Geben sie eine Grammatik G' an, die die LL(1)-Eigenschaft erfüllt und für die gillt L(G) = L(G').

> G -> G´ => LL(1)
> B inkludieren
> S -> A | ad | $\epsilon$ .
> A -> adcd | cd | aAb.
> Linksgleichheit für A ausfakturieren
> S -> A | ad | $\epsilon$ .
> A -> aA´| cd.
> A´ -> dcd | Ab.
> A einsetzen
> S -> aA´ | cd | ad | $\epsilon$ .
> A´ -> dcd | Ab.
> A -> aA´ | cd.
> Linksgleichheit für S ausfakturieren
> S -> aS´ | cd | $\epsilon$ .
> S´ -> A´ | d.
> A´ -> dcd | Ab.
> A -> aA´ | cd.
> Linksgleichheit für S´ sichtbar ( A´ einsetzen)
> S -> aS´ | cd | $\epsilon$ .
> S´ -> dcd | d | Ab.
> A -> adcd | cd.
> A´ -> dcd | Ab.
> Linksgleichheit für S´ ausfakturieren
> S -> aS´ | cd | $\epsilon$ .
> S´ -> dS´´ | Ab.
> S´´ -> cd | $\epsilon$ .
> A -> aA´ | cd.
> A´ -> dcd | Ab.
> => FIRST(aA´ FOLLOW(A)) = {a}
> => FIRST(cd FOLLOW(A)) = {c}
> => vereinigt = leere Menge {}.

4. Gegeben sei die Grammatik G = (N,T,S,P) mit N = {A,B,S, D}, T = {a,c,d} und P = {S -> Aa, A -> BD, B -> b| $\epsilon$, D -> d| $\epsilon$}

a) Berechnen sie die First-Follow-Mengen für alle Produktionen von G.

> FIRST(Aa FOLLOW(S)) = {b,d,a}
> FIRST(b FOLLOW(B)) = {b}
> FIRST($\epsilon$ FOLLOW(B)) = {d,a}
> FIRST(d FOLLOW(D)) = {d}
> FIRST($\epsilon$ FOLLOW(D)) = {a}
> FIRST(BD FOLLOW(A)) = {b,d,a}

b) Erfüllt G die LL(1)-Eigenschaft? Bitte begründen Sie dies kurz.
>Ja, da die Vereinigungen der Produktionen B | D jeweils die leere Menge {} vorweisen.

5.

a) Welche Eigenschaft sollte ein abstrakter Syntaxbaum im allgemeinen haben? Erläutern sie die Einschaften Stichwortartig.
>1. dicht -> keine für die Bedeutung unnötige Knoten
>2. geeignet -> geeignet für die weitere Verarbeitung
>3. hinreichend -> alle nötigen Informationen vorhanden

b) Gegeben sei folgende EBNF:
condition ::= expression "==" expression
expression ::= variable | boolean | expression "and" expression | "(" expression "or" expression ")" | "(" expression ")"
boolean ::= "true"| "false"
variable ::= "a" | "b" | "c" | "d"

Geben sie für die EIngabe "(b and (a or c)) == (true and a) or ( c )" einen abstrakten Syntaxbaum an.

>```graphviz
>digraph {
> rankdir=UD
> condition -> and
> and -> b
> and -> or
> or -> a
> or -> c
> condition -> Or
> Or -> And
> And -> true
> And -> A
> Or -> C
> "" [shape=none]
>}

6. Grammatikprobleme

a) Gegeben sei die Grammatik G = (N,T,S,P) mit N = {S}, T = {multi,1,0,+} und P = {S -> S*S|S+S|1|0} für einfache Ausrücke. Der *-Operator habe höhrere Prioritöt als der +-Operator. Geben sie eine Grammatik G' mit L(G) = L(G') an, bei der durch die Produktion die Beachtung der Priorität der Operatoren im Ableitungsbaum sichergestellt wird.

> Vorrang bei Operatoren
>S -> S*S | S+S | 1 | 0. => S -> 1S´ | 0S´.
>S´ -> *SS´ | +SS´ | $\epsilon$ .
>
> Vorschlag:
>S -> 1S´ | 0S´
>S´-> +SS´| Y | $\epsilon$
>Y -> *SS´| $\epsilon$
>
>Korrekturvorschlag:
>S -> S\+S|B
>B -> B\*B|C
>C -> 1|0
>Evtl Assoziativität auflösen??
>S -> B+S|B
>B -> C*B|C
>C -> 1|0

b) Gegeben sei die Grammatik G = (N,T,S,P) mit N = {A,B,S}, T = {a,b,c,d} für die P = { S -> aA|aB, A -> cAb|B, B -> cBb|(grich. E)}. Welches Grammaitikproblem für eine nicht rücksetzenden rekursiven Abstiegsparser liegt hier vor? Geben sie eine Grammatik G' mit L(G) = L(G') an, in der sie das Problem beseitigen.

>Redundante Grammatikregel = Nicht-Eindeutigkeit laut Eisenbiegler´s E-Mail
>S -> aB.
>B -> cBb | $\epsilon$

c) Gegeben sei die Grammatik G = (N,T,S,P) mit N = {A,B,S}, T = {a,b,c,d} für die P = {S -> aAbB|aAcC, A -> aAa|$\epsilon$, B -> bB|$\epsilon$, C -> cC|$\epsilon$}. Welches Grammatikproblem für einen nicht rücksetzenden rekursiven Abstiegsparser liegt hier vor? Geben sie eine Grammatik G' mit L(G) = L(G') an, in der sie das Problem beseitigen.
>Implizite Kontextabhängigkeit
> G' = $(\{$A,B,C,D,$\epsilon\}$,$\{$a,b,c,d$\}$,S,P$)$ für
P =$\{$
S -> aAD,
D -> bB|cC,
A -> aaA|$\epsilon$,
B -> bB|$\epsilon$,
C -> cC|$\epsilon$ $\}$

7. Eine E-Mail-Adresse sei (vereinfacht) wie folgt definiert: Eine E-Mail-Adresse beginnt mit einem Namen bestehend aus einer Folge von Kleinbuchstaben (a-z), Großbuchstaben (A-Z) oder Punkten. Danach folgt das Zeichen "@". Danach folgt eine beliebige Anzahl von Buchstabenfolgen aus Kleinbuchstaben oder Großbuchstaben, die jeweils durch einen Punkt getrennt sind. Nach dem "@" müssen mindestens zwei solcher Buchstabenfolgen auftreten.

a)Geben sie eine Regel für JFlex an, das ein URL(E-Mail)-Token erkennt und dabei ein Token der Klasse EmailToken erzeugt.
>LETTER = [a-zA-Z]
>EMAIL = ({LETTER}|\\\.)+ \\\@ ({LETTER}+ \\\.)+ {LETTER}+
>
>%%
>
>{EMAIL} { return new Token(Token.EMAIL, yytext(), yyline+1, yycolumn+1); }
>
>Überlegung ->
>EMAIL-TOKEN:
>([a-zA-Z] | \\\. )+ { yybegin(EMAIL); textValue = new StringBuffer();}
><EMAIL> {
\@ { textValue.append(yytext());}
(([a-zA-Z]+ \\\. )+)+ { yybegin(YYINITIAL); textValue.append(yytext()); return new emailToken(Token.EMAIL, textValue.toString(), yyline+1, yycolumn+1-textValue.length(), textValue.toString();}
>}
>

>Korrekturvorschlag:
>[a-zA-Z\.]+@([(([a-zA-Z]+)\.)][a-zA-Z]+)+ {return newToken (EMAIL)}
Eventuell noch Ausgabe von Position und Textvalue

b) Geben Sie eine Lexer-Regel für ANTLR (Version 3.5) an, das ein Email-Token erkennt.
> fragment LETTER: ('a'..'z' | 'A'..'Z');
> EMAIL: (LETTER | '.')+ '@'(LETTER+ '.')+ LETTER+;

c) Erweitern sie ihre ANTLR-Lexer-Regel so, dass beim Scannen die Anzahl der Buchstabenfolgen nach dem "@" gezählt wird. Dazu sei berets eine Variable c definiert.
>EMAIL: (LETTER | '.')+ '@'(LETTER {c++;}+ '.')+ LETTER{c++;}+;

8. Gegeben sei eine Regel für einen Parser in erweiterter Backus-Naur-Form:
x = "?1" COND ":" EXPR | "?2" COND ":" EXPR "," EXPR

a) Skizieren sie die Parsing Methode für X für einen nicht rücksetzenden rekursiven Abstiegsparser. Die Parsing-Methode für COND (parseCond()) und EXPR (parseExpr()) sowie zum Parsen eines Tokens (parseToken(string Token)) seien gegeben. Das nächste Token kann über lookAheadToken() abgefragt werden. Der Parser liefert einen Wahrheitswert (boolean) zurück, der angibt, ob die Eingabe korrekt ist oder nicht.
> boolean parseX() {
> >myPosition = getTokenStremPosition();
> >if( parseToken("?1") && parseCond() && parseToken(":") && parseExpr()) {
>>>return true;
>
>}
>>setTokenStreamPosition(myPosition);
>
>>if(parseToken("?2") && parseCond() && parseToken(":") && parseExpr() && parseToken(",") && parseExpr()) {
>>>return true;
>
>>}
>>setTokenStreamPosition(myPosition);
>>return false;
>}

> bei rekursivem Abstiegsparser über LL(1) zum Vergleich: 

b) Geben sie für die Regel X eine ANTLR-Parser-Regel an. Dabei soll eine AST erzeugt werden, der "?1" oder "?2" als Wurzel und ausschließlich COND- oder EXPR-Knoten als Kinder hat.
>mX:'?1' COND ':' EXPR -> ^('?1' COND EXPR) | '?2' COND ':' EXPR ',' EXPR -> ^('?2' COND EXPR EXPR);
>
>mX: '?1'^ COND ':'! EXPR |'?2'^ COND ':'! EXPR ','! EXPR

>Korrekturvorschlag:
>xRule: 'S1'^ COND ':'! EXPR | 'S2'^ COND ':'! EXPR ','! EXPR