Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


21. Syntaxanalyse (Parsing)



Übungen

  1. Wie findet der rekursiv absteigende Parser einen Fehler in einem unvollständigen regulären Ausdruck der Art (A+B)*BC?
  2. Geben Sie den Syntaxbaum für den regulären Ausdruck ((A+B)+(C+D)*)* an.
  3. Erweitern Sie die Grammatik für arithmetische Ausdrücke dahingehend, daß auch Potenzieren, div und mod erfaßt werden.
  4. Geben Sie eine kontextfreie Grammatik zur Beschreibung aller Zeichenfolgen mit nicht mehr als zwei aufeinanderfolgenden Einsen an.
  5. Wie viele Prozeduraufrufe verwendet der rekursiv absteigende Parser zum Erkennen eines regulären Ausdrucks, ausgedrückt über die Anzahl der Verkettungen, oder-Operationen und Hüllenbildungen und die Anzahl der Klammern?
  6. Geben Sie die Felder ch, next1 und next2 an, die sich aus der Herstellung des Pattern Matching-Automaten für das Muster ((A+B)+(C+D)*)* ergeben.
  7. Modifizieren Sie die Grammatik für reguläre Ausdrücke dahingehend, daß sie die Funktion »nicht« und Joker behandelt.
  8. Erstellen Sie ein allgemeines Pattern Matching-Programm für reguläre Ausdrücke, das auf der verbesserten Grammatik aus Ihrer Lösung für die vorige Aufgabe beruht.
  9. Beseitigen Sie die Rekursion aus dem rekursiv absteigenden Compiler und vereinfachen Sie den resultierenden Code so weit wie möglich. Vergleichen Sie die Laufzeit der nichtrekursiven und der rekursiven Methode.
  10. Erstellen Sie einen Compiler für einfache arithmetische Ausdrücke, die durch die im vorliegenden Kapitel angegebene Grammatik beschrieben werden. Er soll eine Liste von »Anweisungen« für einen Automaten erzeugen, der in der Lage ist, drei Operationen auszuführen: Ablegen (push) des Wertes einer Variablen in einem Stapel; Addieren (add) der beiden obersten Werte im Stapel, indem diese aus dem Stapel entnommen werden und danach das Ergebnis dort abgelegt wird; Multiplizieren (multiply) der beiden obersten Werte im Stapel in der gleichen Weise.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]