229 lines
7.1 KiB
Typst
229 lines
7.1 KiB
Typst
#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"),
|
||
)
|