#import "@preview/codly:1.3.0": *
#import "@preview/codly-languages:0.1.1": *
#import "@preview/catppuccin:1.0.1": catppuccin, flavors

#show: codly-init.with()
#show: catppuccin.with(flavors.latte)

#codly(languages: codly-languages)

= Exercise 01

#let question(body) = block(
  fill: luma(255),
  inset: 8pt,
  radius: 4pt
)[
	#body
]

== 01 Grundbegriffe

=== Task a

#question[
	Wie lang (in Terminalsymbolen) ist der kürzeste Satz in MicroJava, der mindestens ein Tilde (“∼”)
	enthält? Geben Sie ein Beispiel für einen Satz dieser Länge an. Der Satz muss nur syntaktisch korrekt
	(entspricht der Grammatik) sein, nicht semantisch (hält alle Kontextbedingungen der Sprache ein). Bei-
	spielsweise ist x = x + 1, ohne x zuvor zu definieren, eine syntaktisch korrekte Zuweisung, semantisch
	korrekt ist sie aber nicht.
]

```java
program MyProgram {
	void main() {
		x[~1]++;
	}
}
```

The statement above contains the following tokens:

- "program" (literal, terminal)
- MyProgram (ident, terminal)
- "{" (literal, terminal)
- "void" (literal, terminal)
- main (ident, terminal)
- "(" (literal, terminal)
- ")" (literal, terminal)
- "{" (literal, terminal)
- x (iden, terminal)
- "\[" (literal, terminal)
- "~" (literall, terminal)
- 1 (number, terminal)
- "\]" (literal, terminal)
- "++" (literal, terminal)
- ";" (literal, terminal)
- "}" (literal, terminal)
- "}" (literal, terminal)

To sum it up the statement has a `~` and has a terminal symbol count of 17.

=== Task b

#question[
Sind die Nonterminalsymbole Statement und ActPars rekursiv? Wenn ja, geben Sie alle Rekursionen-
arten an (Transitivität: direkt, indirekt; Orientierung: links, rechts, zentral). Beispiele für Rekursionsarten
sind direkt zentralrekursiv, indirekt linksrekursiv, . . . Pro NT kann es mehrere Rekursionsarten geben.
Geben Sie bei indirekten Rekursionen einen möglichen Pfad an (Beispiel: Factor ist indirekt zentralre-
kursiv über Factor -> Expr -> Term -> Factor).
]

==== Statement

The relevant Productions for the Statement Symbol are:

```
Statement = Designator ( Assignop Expr | ActPars | "++" | "--" ) ";"
| "if" "(" Condition ")" Statement [ "else" Statement ]
| "while" "(" Condition ")" Statement
| "break" ";"
| "return" [ Expr ] ";"
| "read" "(" Designator ")" ";"
| "print" "(" Expr [ "," number ] ")" ";"
| Block
| ";".

Block = "{" { Statement } "}".
```

We have the following Recursions:

- line 2: Statement is directly central recursive
- line 3: Statement is directly right recursive
- line 8: Block is indirectly central recursive


==== ActPars

The relevant Productions for the ActPars Symbol are:

```
ActPars = "(" [ Expr { "," Expr } ] ")".

Expr = [ "–" ] Term { Addop Term }.

Term = Factor { Mulop Factor }.

Factor = Designator [ ActPars ]
| number
| charConst
| "new" ident [ "[" Expr "]" ]
| "(" Expr ")".
```

We have the following Recursion:

- line 1: Factor is indirectly central recursive

=== Task c

#question[
	Wie sieht der konkrete Syntaxbaum für folgenden Satz aus? (Achtung, kann groß werden)

	```java
	program P int i; { void main(){ read(a[~i]); }}
	```

	- Geben Sie für Symbole der Terminalklassen ident und charConst im Baum auch die zugehörigen Werte an. Beispiel: ident (“main”)
	- Sie dürfen den Syntaxbaum auch handschriftlich erstellen und abfotografieren. Achten Sie dabei bitte darauf, dass die Diagramme sauber gezeichnet und gut lesbar sind.
	- Wenn Sie das Diagramm digital zeichnen wollen, dann bieten sich Zeichentools wie beispielsweise draw.io, LibreOffice Draw oder auch Microsoft PowerPoint an

]

Es gibt nur einen konkreten Syntaxbaum.

#figure(
	image("task1c.svg"),
)

=== Task d

#question[
	Welche terminalen Anfänge und Nachfolger haben die Regeln MethodDecl, AssignOp und Cond- Term? Bitte die finalen Antworten komplett ausschreiben (i.e., jeweils ein Set an TS)
]

==== First Sets

- MethodDecl: { "void", Type, "}" } = #text(weight: "bold")[{ "void", ident, "}" }]
- AsignOp: #text(weight: "bold")[{ "=" , "+=" , "-=" , "\*=" , "/=" , "%=" }]
- CondTerm: { CondFact } = { Expr } = { Term, '-' } \
	\= { Factor, '-' } = { Designator, number, charConst, "new", "(", "-" } \
	\= #text(weight: "bold")[{ iden, number, charConst, "new", "(", "-" }]

==== Follow Sets

- MethodDecl: { "}", "void", Follow(Type) } = #text(weight: "bold")[{ "}", "void", ident }]
- AsignOp: { Expr } = { "-", Term } = { "-", Factor } \
	\= { "-", Designator, number, charConst, "new", "(", "-" } \
	\= { "-", ident, number, charConst, "new", "(", "-" } \
	\= #text(weight: "bold")[{ "-", ident, number, charConst, "new", "(" }]
- CondTerm: { "||", Follow(Condition)  } = #text(weight: "bold")[{ "||", ")" }]

== 02 Konstruktion einer Grammatik

#question[
Geben Sie eine EBNF-Grammatik an, die folgende Beschreibung abdeckt. Es handelt sich dabei um eine fiktive
Schachnotation. Bilden Sie dabei beliebig viele Non-Terminalklassen, mindestens jedoch eine für jedes fett
geschriebene Wort.
Ein Spiel setzt sich aus mindestens einem Zug zusammen, wobei Züge durch Beistriche (“,”) getrennt sind.
Nach dem letzten Zug steht ein Strichpunkt (“;”).
Ein Zug beginnt mit einer Figur, gefolgt von einer Position (Startposition). Darauf folgt ein Bindestrich (“-”),
gefolgt von einer weiteren Position (Zielposition). Sollte durch den Zug eine Figur geschlagen worden sein,
folgt ein “x”. Unabhängig davon, ob eine Figur geschlagen wurde, folgt gegebenenfalls die Information, ob der
Gegner Schach ( + ) oder Schach-Matt ( \# ) steht. Ein Spieler kann nicht gleichzeitig Schach und Schach-Matt
stehen.
Beispielzüge: Ka1-a2, Qf5-h7x\#, Pb2-c3x, Rh1-h6+, Bb5-d7x+
Eine Figur ist entweder ein König (“K”), eine Königin (“Q”), ein Turm (“R”), ein Läufer (“B”), ein Springer
(“N”), oder ein Bauer (“P”).
Eine Position ist eine Spalte, gefolgt von einer Zeile.
Eine Spalte ist ein Buchstabe zwischen a und h (a, b, c, d, e, f, g, h).
Eine Zeile ist eine Zahl zwischen 1 und 8 (1, 2, 3, 4, 5, 6, 7, 8).

]

```ebnf
Game = Turn { "," Turn} ";".
Turn = Character Position "-" Position ["x"] ["+" | "#"].
Character = “K” | “Q” | “R” | “B” | “N” | “P”.
Position = Column Row.
Column = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h".
Row = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8".
```

== 03 Beseitigung von Linksrekursionen

#question[
	+ Wo befinden sich in der folgenden Grammatik Linksrekursionen? Geben Sie die Produktionen an.
	+ Wie könnte man die Linksrekursionen entfernen? Geben Sie eine umgeformte EBNF Grammatik ohne Linksrekursionen an. Ersetzten Sie die Linksrekursionen dabei durch Iterationen.

	```ebnf
		Object = ident ":" "{" Props "}" ";".
		Props = ident ":" Value | Props "," ident ":" Value .
		Value = "’" text "’" | Value "+" "’" text "’" | ε .
	```

	Beispielsätze:
	```
		alice : { name: ’Alice’, greeting: ’welcome’ + ’alice’ };
		bob: { name: ’Bob’, greeting: ’hello’ + ’to’ + ’bob’ };
		test: { noValue: , emptyValue: ’empty’, plusValue: + ’plus’ };
	```
]

=== Task 1

- line 2: Props is left recursive
- line 3: Value is left recursive

=== Task 2

```ebnf
Props = ident ":" Value { "," ident ":" Value }.
Value = (ε | "’" text "’") {"+" "’" text "’"}.
```

#figure(
	image("task3.2.svg"),
)