Logo des Instituts  
 aufwärts

Laboraufgaben Compilerbau

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):

Sgeht über nachaSbS  |  ε

 

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 geht über nachterm (+ term | - term)*
    term geht über nachfactor (* factor | / factor)*
    term geht über nachnumber  |  ( expr )
    number geht über nachdigit+
    digit geht über nach0  |  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 geht über nachinteger fraction? exponent?
integer geht über nachdigit+
fraction geht über nach. integer
exponent geht über nach(e | E) sign integer
sign geht über nach(+ | -)?
digit geht über nach0  |  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

x
2
 + 
x
3
  =  
3x + 2x
6

soll in einer XML-Sprache wie folgt beschrieben werden:

 

<formel>
<bruch><oben>x</oben><unten>2</unten></bruch>
<normal> + </normal>
<bruch><oben>x</oben><unten>3</unten></bruch>
<gleich>auf den Hauptnenner bringen</gleich>
<bruch><oben>3x + 2x</oben><unten>6</unten></bruch>
</formel>

 

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­auszeichnungs­sprache 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 geht über nach(italic  |  bold  |  plain)*
italic geht über nach/* text */
bold geht über nach/+ text +/
plain geht über nachsymbol*
symbol geht über nach#

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 geht über nach[[ url | linktext ]]
url geht über nachplain
linktext geht über nachplain

Ferner kommt zu text noch die Alternative link hinzu:

text geht über nach(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://www.inf.fh-flensburg.de/lang/veranst/thi/parser.htm|Parser]]*/+/ enthaelt die Methoden /*lookahead*/ und /*isDigit*/.

 

 

 

 

 

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©  
Valid HTML 4.01 Transitional