Parser und Übersetzer

Aufgabe 1:  

Schreiben Sie einen Parser für korrekt aufgebaute Klammer­strukturen. Legen Sie folgende Grammatik zugrunde (a entspricht einer öffnenden, b einer schließenden Klammer):

S

aSbS  |  ε

Aufgabe 2:  

1. Schreiben Sie einen Parser, der arithmetische Ausdrücke der Art

   (123*(30-5))-16+32

   auf korrekten syntaktischen Aufbau überprüft, und benutzen Sie dabei die unten­stehende Grammatik in erweiterter Backus-Naur-Form.

   Die Grammatik hat folgende Produktionen:

   expr		term (+ term | - term)*
   term		factor (* factor | / factor)*
   term		number  |  ( expr )
   number		digit+
   digit		0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9

    

2. Wandeln Sie den Parser in einen Compiler um, der den arithmetischen Ausdruck in seinen Zahlenwert übersetzt (ganzzahlige Division mit dem Zeichen /).

Aufgabe 3:  

Schreiben Sie einen Übersetzer, der eine Zahl auswertet. Mögliche Zahlen sollen z.B. sein:

17, 0, 1024, 13.5, 0.005, 5.5e-2, 6e+2, 1.00E3, 0e0, 000.000e000

Eingabewort soll eine als String dargestellte Zahl sein, Ergebnis der Übersetzung soll eine double-Zahl sein.

Die Grammatik für Zahlen hat folgenden Produktionen:

number		integer fraction? exponent?
integer		digit+
fraction		. integer
exponent		(e | E) sign integer
sign		(+ | -)?
digit		0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9

Schreiben Sie eine Klasse NumberCompiler und leiten Sie diese von der Basisklasse Compiler ab.

Aufgabe 4:  Schreiben Sie einen Compiler, der römische Zahlen in ihren Zahlenwert übersetzt.

Entwickeln Sie zunächst eine Grammatik in erweiterter Backus-Naur-Form (EBNF) für römische Zahlen, die sich für einen Recursive-Descent-Parser eignet. Programmieren Sie anschließend ein Modul RomanNumberCompiler, in dem Sie schulmäßig die Produktionen Ihrer Grammatik in ent­sprechende Funktionen umsetzen.

Testen Sie den Compiler mit den (zulässigen) Eingabe­wörtern DVI, XL, MIX, MCMLII.

Hinweis: Römische Zahlen bestehen aus einer Folge von Tausendern, Hundertern, Zehnern und Einern, wobei jede dieser Gruppen auch fehlen kann.

Die folgenden Zeichen­ketten sind die Einer, mit den zugehörigen Zahlenwerten 1, 2, ..., 9:

I, II, III, IV, V, VI, VII, VIII, IX

Die folgenden Zeichen­ketten sind die Zehner, mit den zugehörigen Zahlenwerten 10, 20, ..., 90:

X, XX, XXX, XL, L, LX, LXX, LXXX, XC

Die folgenden Zeichen­ketten sind die Hunderter, mit den zugehörigen Zahlenwerten 100, 200, ..., 900:

C, CC, CCC, CD, D, DC, DCC, DCCC, CM

Die folgenden Zeichen­ketten sind die Tausender, mit den zugehörigen Zahlenwerten 1000, 2000, 3000:

M, MM, MMM

Aufgabe 5:  

Eine mathe­matische Formel der Art

soll in einer XML-Sprache wie folgt beschrieben werden:

Entwerfen Sie eine kontextfreie Grammatik für diese XML-Sprache. Möglich sein soll innerhalb eines formel-Elements eine beliebige Folge von bruch-, normal- und gleich-Elementen.

Schreiben Sie zunächst einen Recursive-Descent-Parser auf Grundlage dieser Grammatik.

Schreiben Sie dann einen Recursive-Descent-Übersetzer, der die Formel in HTML übersetzt, derart dass die Formel im Browser wie oben dargestellt wird.

Aufgabe 6:  

In Wikipedia wird beim Bearbeiten der Beiträge eine spezielle Form der Text­auszeichnung (markup) verwendet, z.B. ''kursiv'' für kursiv. Es soll ein Übersetzer für eine ähnliche, einfache Text­auszeichnungssprache geschrieben werden.

Zunächst werden nur die Aus­zeichnungen für kursiv (engl.: italic) und für fett (engl.: bold) innerhalb einer einfachen Textzeile behandelt, später kommen weitere Auszeichnungs­möglichkeiten hinzu.

Die zugrunde liegende Grammatik hat folgende Produktionen; Startsymbol ist text:

text		(italic  |  bold  |  plain)*
italic		/* text */
bold		/+ text +/
plain		symbol*
symbol		#

Das Zeichen # steht für ein beliebiges Zeichen. Innerhalb von text dürfen allerdings nicht die schließenden Zeichen­folgen */ und +/ vorkommen, innerhalb von plain weder die öffnenden Zeichen­folgen /* und /+ noch die schließenden Zeichen­folgen */ und +/.

Schreiben Sie ein Python-Modul SimpleMarkupCompiler zur Übersetzung eines entsprechend ausge­zeichneten Textes in HTML.

Testen Sie den Übersetzer mit dem Text

Die /+Klasse /*Parser*/+/ enthaelt die Methoden /*lookahead*/ und /*isDigit*/.

Aufgabe 7:  Es soll jetzt die Auszeichnung für einen Link innerhalb einer einfachen Textzeile behandelt werden.

Die Grammatik wird um folgende Produktionen erweitert:

link		[[ url | linktext ]]
url		plain
linktext		plain

Ferner kommt zu text noch die Alternative link hinzu:

text

(italic  |  bold  |  link  |  plain)*

Nun darf innerhalb von text auch nicht die Zeichenfolge ]] vorkommen; innerhalb von plain darf weder [[ noch ]] und auch nicht das Zeichen | vorkommen.

Fügen Sie zur Klasse SimpleMarkupParser die ent­sprechenden neuen Funktionen hinzu.

Testen Sie den SimpleMarkupParser mit dem Text

Die /+Klasse /*[[http://hwlang.de/theor/parser-py/parser.htm|Parser]]*/+/ enthaelt die Methoden /*lookahead*/ und /*isDigit*/.