Übersetzerbau	WS 98/99 Heckmann Pape
6. Übungsblatt

 

Aufgabe 1 (2 + 6 + 1 Punkte)

Gegeben seien die folgenden Zeichenklassen

bu = a-z A-Z
zi = 0-9
hz = A-F

und Symbolklassendefinitionen

hex = H (zi | hz)+
id  = bu (bu | zi)*

(Die Sprache von r+ ist gleich der Sprache von r* ohne epsilon.)

1. Gib die vom Scannergenerator zu berechnende Einteilung in disjunkte Zeichenklassen an. Definiere die Symbolklassen mithilfe dieser Zeichenklassen neu.
2. Generiere mithilfe der Algorithmen aus der Vorlesung den minimalen DEA für die Symbolklassen aus a. (Dazu muß ein geeigneter NEA für reguläre Ausdrücke der Form r+ definiert werden.)
3. Als was erkennt der DEA aus b. die folgenden Wörter:

   *H, HA, HAUBE, HABE.

   (Diese Frage kann auch aufgrund der Definition der regulären Ausdrücke beantwortet werden, ohne den DEA aus b. zu kennen.)

Aufgabe 2 (3 Punkte)

Gegeben sei die folgende kontextfreie Grammatik:

VN = {A, B}, VT = {a, b}, Startsymbol A,
Produktionen A -> ABA | a, B -> b.

Gib zwei Linksableitungen, zwei Rechtsableitungen und zwei Syntaxbäume für das Wort ababa aus A an. Welche der Ableitungen gehören zu welchem Syntaxbaum?

Aufgabe 3 (3 Punkte)

Gegeben sei die folgende kontextfreie Grammatik:

VN = {A, B}, VT = {a, b}, Startsymbol A,
Produktionen A -> AB | a, B -> epsilon.

Gib drei Linksableitungen und drei Syntaxbäume für das Wort a aus S an.