Aufgabe Vorschlag C2 - Aufgabe 2 · Abitur Hessen Informatik LK 2022

Auszeichnungssprache YAML

YAML ist eine Auszeichnungssprache zur Darstellung strukturierter Daten in einfach lesbarer Textform. Die Sprache zeichnet sich dadurch aus, dass sie jede Datenstruktur allein durch Verwendung von Konstanten, Listen und assoziativen Listen darstellen kann. Elemente von Listen und assoziativen Listen werden durch Zeilenumbrüche (<CR> <LF>) getrennt dargestellt. Dabei besitzen diese Elemente in aufeinanderfolgenden Zeilen die gleiche Einrückung. Elemente einer Liste beginnen mit dem Zeichen „-“ und Elemente einer assoziativen Liste bestehen aus einem Schlüssel:Wert-Paar. Listen und assoziative Listen enthalten jeweils nur gleichartige Listenelemente (Material 1).

Alle Elemente einer Liste und alle Werte einer assoziativen Liste können entweder Konstanten oder auch wieder Listen oder assoziative Listen sein. In den beiden letztgenannten Fällen spricht man dann von geschachtelten Listen. Die Schachtelung wird durch einen Zeilenumbruch und eine Einrückung mit Leerzeichen (<SP>) dargestellt (Material 1).

Material 1

Beispiel von Listen und assoziativen Listen in YAML

Liste

assoziative Liste

- Apfel

- Banane

- Karotte

Name: Frank

Alter: 19

Sport: Fußball

geschachtelte Liste

geschachtelte assoziative Liste

assoziative Liste mit einer Liste als Wert

- HTML

-

- Überschrift H1

- Absatz p

- CSS

- JavaScript

Datum: 2021 05 17

Name: Lisa

Adresse:

Straße: Allee 17

PLZ: 64646

Ort: Heppenheim

Datum: 2021 05 17

Name: Frank

Interessen:

- Sport

- Politik

Alter: 19

Material 2

YAML-Texte

a

b

Datum: 2021 04 05

RechnungNr: 7266

Produkt:

-

Beschreibung: Basketball

Preis: 86

Menge: 4

-

Beschreibung: Hantel

Preis: 48

Menge: 2

-

Name: Martin Schmidt

Anstellung: Entwickler

Fachkompetenz:

- Python

- Java

- Pascal

-

Name: Tabitha Bitumen

Anstellung: Entwicklerin

Fachkompetenzen:

- Lisp

- Fortran

- Erlang

Material 3

Text in einer Konfigurationsdatei

packages:

yum:

mod_ssl: false

files:

servercrt:

mod: 000400

owner: admin

- group root

script:

- cd tools

- tox ecover

Material 4

Unvollständige Grammatik G zur Sprache YAML

$T = \{<\text{CR}>, <\text{LF}>, <\text{SP}>, <\text{INDENT}>, <\text{DEDENT}>, \text{-,:, true, false, null}, 0, \dots, 9, a, \dots, z, A, \dots, Z\}$

$N = \{\text{YAML}, \text{Liste}, \text{Element}, \text{AssoziativeListe}, \text{Schlüssel}, \text{Wert}, \text{Konstante}, \text{Zeichenkette}, \text{Zeichenketten}, \text{Zahl}\}$

$\text{Startsymbol} = \text{YAML}$

$\begin{aligned}

P = \{ & \text{YAML} & \to & \ \text{Liste} \mid \text{AssoziativeListe}, \\

& \text{Liste} & \to & \ \text{Element } <\text{CR}> <\text{LF}> \mid \text{Element } <\text{CR}> <\text{LF}> \text{Liste}, \\

& \text{AssoziativeListe} & \to & \ \text{Schlüssel}: <\text{SP}> \text{Wert } <\text{CR}> <\text{LF}> \mid \\

& & & \ \text{Schlüssel}: <\text{SP}> \text{Wert } <\text{CR}> <\text{LF}> \text{AssoziativeListe}, \\

& \text{Element} & \to & \ \text{- } <\text{SP}> \text{Wert}, \\

& \text{Schlüssel} & \to & \ \text{Zeichenkette}, \\

& \text{Wert} & \to & \ \text{Konstante} \mid <\text{CR}> <\text{LF}> <\text{INDENT}> \text{Liste } <\text{DEDENT}> \mid \\

& & & \ <\text{CR}> <\text{LF}> <\text{INDENT}> \text{AssoziativeListe } <\text{DEDENT}>, \\

& \text{Konstante} & \to & \ \text{Zeichenketten} \mid \text{Zahl} \mid \text{true} \mid \text{false} \mid \text{null}, \\

& \text{Zeichenketten} & \to & \ \text{Zeichenkette} \mid \text{Zeichenkette } <\text{SP}> \text{Zeichenketten}, \\

& \dots \\

\} & & &

\end{aligned}$

Hinweis: Die Terminale <INDENT> und <DEDENT> stehen für eine Ein- bzw. Ausrückung.

Aufgabe 2

Eine Registermaschine soll die maximale Einrücktiefe in einem YAML-Text ermitteln. Die einzelnen Zeichen des Textes werden mit dem ASCII-Zeichensatz kodiert (Zahlenwerte von 0 bis 127) und in aufeinanderfolgenden Registern ab Register R10 gespeichert. Das Leerzeichen <SP> wird in diesem Zeichensatz mit der Dezimalzahl 32 kodiert, das Steuerzeichen <LF> (LineFeed) mit der Dezimalzahl 10. Das Ende des YAML-Textes wird durch den Wert 128 markiert.

2.1

Implementieren Sie ein kommentiertes Registermaschinenprogramm, das die maximale Einrücktiefe eines YAML-Textes bestimmt und in den Akkumulator schreibt. [10 BE]

2.2

Bestimmen Sie die asymptotische Laufzeit Ihres Registermaschinenprogramms in Abhängigkeit von der Länge der Eingabe. [4 BE]