In HTML (Hypertext Markup Language) gibt es Konstrukte, um
verschachtelte Listen zu definieren. Das Kommando
<OL> (ordered list) leitet eine numerierte Liste
ein, <UL> (unordered list) eine Liste mit
*. Ein Listeneintrag beginnt mit <LI>
(list item) und eine ganze Liste wird mit </OL>
bzw. </UL> beendet. Auf dem Bildschirm wird der
Text entsprechend seiner logischen Struktur eingerückt dargestellt.
Die Eingabe von
Das sind Listen: <OL><LI> Text eins <LI> Text zwei <UL> <LI> erste Zeile <LI> zweite Zeile </UL> <LI> Text drei </OL> Hier geht's weiter.
bewirkt die Bildschirmdarstellung
Das sind Listen:
Hier geht's weiter.
Anmerkung: Diese Darstellung hängt natürlich von ihrem Browser
ab. Bei der Lösung wird jedoch bei jedem Listenelement das
Zeichen * verwendet. Jede Liste ist um
tabs(1) eingerückt.
Erweitern Sie die nachfolgend gezeigte Grammatik um Attribute für die
Darstellung von Listen in einem HTML-Text. Unterscheiden Sie
numerierte von nicht numerierten Items (Is). Der Text
soll im synthetisierten Attribut
S.x geliefert werden.
Die Funktion
tabs(n) liefert n Tabulatoren. Ein
newline wird durch "\n" dargestellt. Das
Attribut chars.x enthält die Textstücke zwischen den
Kommandos. Verwenden Sie den Operator ||, um Zeichenketten
zusammenzuhängen.
S -> Html Html -> Text Html | Text Text -> chars | List List -> <UL> Is </UL> | <OL> Is </OL> Is -> Item Is | Item Item -> <LI> Html
S -> Html S.x := Html.x
Html.i := 0 /* noch keine Einrückung */
Html -> Text Html1 Html.x := Text.x || "\n" || Html1.x
Text.i := Html.i
Html1.i := Html.i
Html -> Text Html.x := Text.x
Text.i := Html.i
Text -> chars Text.x := chars.x
Text -> List Text.x := List.x
List.i := Text.i + 1 /* einrücken */
List -> <UL> Is </UL> Is.i := List.i; List.x := Is.x
Is.n := 1
Is.o := false /* keine Numerierung */
List -> <OL> Is </OL> Is.i := List.i; List.x := Is.x
Is.n := 1
Is.o := true /* mit Numerierung */
Is -> Item Is1 Item.i := Is.i
Is1.i := Is.i
Is1.n := Is.n + 1 /* nächste Nummer */
Item.n := Is.n
Item.o := Is.o
Is1.o := Is.o
Is.x := Item.x || "\n" || Is1.x
Is -> Item Item.i := Is.i
Item.n := Is.n
Item.o := Is.o
Is.x := Item.x
Item -> <LI> Html Html.i := Item.i
IF Item.o = true /* d.h., numerierte Liste */
THEN Item.x := tabs(Item.i) || Item.n || ". " || Html.x
ELSE Item.x := tabs(Item.i) || "* " || Html.x
Erklärungen von attributierten Grammatiken sind immer schwierig, weil es beliebig viele Möglichkeiten gibt, eine Grammatik zu attributieren. In diesem Zusammenhang verweise ich zuallererst auf den Appendix des letzten Skriptums.
Was ist eigentlich zu tun? Wo liegt das (eigentliche) Problem?
Es macht einen großen Unterschied aus, ob man eine bestehende Grammatik attributieren oder eine ganz neue Grammatik erstellen soll. Im ersten Fall muß man unbedingt das Gesamtkonzept erfassen und die Intention der Grammatik begreifen.
Folgende Anforderungen stellen sich:
x
synthetisiert werden.
Sehen wir uns die Grammatik einmal ganz genau an. Die ersten beiden Produktionen
S -> Html Html -> Text Html | Text
sind noch sehr einfach zu verstehen. Das Startsymbol
S ist ein HTML-Text und ein HTML-Text ist eine Liste von
Textelementen.
Anmerkung: Die Produktion
List -> Item List | Item
ist sehr häufig bei Listen zu sehen. Äquivalent wäre die Produktion
List -> List Item | Item
die ist aber linksrekursiv. Bitte beachten Sie dazu die Ableitungsbäume der Abbildung 4.3 in Kapitel 4.1 des Skriptums.
Aus der nächsten Produktion sehen wir, daß ein Textelement aus
Textstücken (chars) oder aus Listen
(List) bestehen kann.
Text -> chars | List
Irgendwo hier muß also die Einrückung passieren weil ja die ganze Liste eingerückt dargestellt werden soll.
Eine Liste wiederum besteht aus Listeneinträgen
(Is für Items) und kann entweder numeriert sein oder auch nicht.
List -> <UL> Is </UL> | <OL> Is </OL>
Hier ist eine gute Stelle, um die beiden Listentypen voneinander zu unterscheiden. Wo sich diese Unterscheidung später vielleicht auswirken wird ist hier egal.
Die Listeneinträge sind einfach aneinandergereiht und bestehen selbst wieder aus HTML-Text.
Is -> Item Is | Item Item -> <LI> Html
Das heißt aber auch, daß alle bis dahin angesammelten
Einrückungen an den HTML-Text weitergegeben werden
müssen. An dieser Stelle wird sich auch die Unterscheidung der
Listentypen auswirken, ob ein * oder eine Nummer erzeugt
wird.
Die Synthetisierung des Ergebnistextes im Attribut x hat
in unserer Liste zwar die niedrigste Priorität, sie zieht sich
jedoch naturgemäß durch alle Attributierungsregeln
hindurch. Wir nehmen also an, daß jedes Nichtterminal ein
synthetisiertes Attribut x hat in das wir (hemmungslos)
Zeichen hineinschreiben bzw. den schon erzeugten Text daraus lesen.
Anmerkung: Im weiteren werden alle Attributierungsregeln die nur "Durchreichefunktion" haben weggelassen.
Gehen wir systematisch an Hand unserer Anforderungsliste vor.
Wir brauchen offensichtlich ein Attribut, daß die derzeitige
Einrückung anzeigt. Der Name des Attributs ist i
(der Buchstabe i steht für indent). Bei jeder neuen
Liste wird sein Wert um eins erhöht. Die Stelle, wo das passiert haben wir schon bei
der Analyse der Grammatik gesehen.
Die zweite Regel von
Text -> chars | List
erhält die Attributierungsregel
List.i := Text.i + 1
d.h., eine Liste wird um eine Tabulatorposition mehr eingerückt als der restliche Text.
An dieser Stelle wollen wir kurz innehalten, um uns das Wesen der Attributierung vor Augen zu halten. Jede einzelne Grammatikproduktion wird unabhängig von den anderen attributiert. Uns interessiert also nicht der globale Zusammenhang - den sollten wir zumindest im Hinterkopf behalten - sondern nur die lokale Auswirkung. Wir erzeugen nur Information, die an anderer Stelle gebraucht wird. Die Daten, die wir dafür brauchen, müssen wir also woanders erzeugen.
In unserem Fall ist die neue Tabulatorposition die erzeugte
Information. Dabei müssen wir auf die alte Tabulatorposition
zurückgreifen. Alleine durch diese Definition sehen wir,
daß das Attribut i vererbt wird.
Irgendwo müssen wir das Attribut i auch
initialisieren. Das geschieht zweckmäßigerweise gleich am
Beginn, nämlich in der Grammatikregel
S -> Html
durch die Attributierungsregel Html.i := 0,
d.h., die Einrückung jedes Html-Textes wird auf die nullte
Tabulatorposition gesetzt.
Anmerkung: Es ist nicht notwendig, den Text wieder "auszurücken", d.h., die Einrückung rückgängig zu machen. Die Attribute sind lokale Größen die durch die Grammatik automatisch die richtigen Werte zugewiesen bekommen.
Die Unterscheidung von numerierten und nicht numerierte Listen ist sehr einfach. Schon bei der Analyse der Grammatik haben wir die entsprechenden Grammatikregeln lokalisiert.
List -> <UL> Is </UL> List -> <OL> Is </OL>
Wir müssen den Items der Listen irgendwie anzeigen,
daß sie zu einer numerierten bzw. nicht numerierten Liste
gehören. Diese Unterscheidung wird später gebraucht, weil ja
entweder eine Zahl oder ein * ausgegeben werden soll. Wir
verwenden dazu ein Flag, das entweder auf true oder
auf false gesetzt wird.
List -> <UL> Is </UL> Is.o := false List -> <OL> Is </OL> Is.o := true
Das Flag wirkt sich dann aus wenn wir zu einem Listeneintrag kommen, also erst in der Grammatikregel
Item -> <LI> Html
An dieser Stelle müssen wir, abhängig vom Wert des Flags,
entweder eine Nummer oder einen * ausgeben. Damit auch
alles am richtigen Platz steht erzeugen wir noch die richtige
Einrückung und geben außerdem den entsprechenden Text aus.
IF Item.o = true THEN Item.x := tabs(Item.i) || >Nummer< || ". " || Html.x ELSE Item.x := tabs(Item.i) || "* " || Html.x
Das Attribut i muß demnach mindestens bis zu dieser
Stelle in der Grammatik vererbt werden. (Auf das Attribut
x wollen wir nicht näher eingehen. Es enthält
den auszugebenden Text und wird auch dementsprechend verwendet.)
Für Nummer fehlen uns jedoch noch die entsprechenden Regeln.
Bei der Analyse der Grammatik haben wir schon gesehen, wie eine Liste aufgebaut ist. Die Listeneinträge sind einfach aneinander gereiht.
Is -> Item Is Is -> Item
Eine Liste von Items besteht also aus einem
Item gefolgt von weiteren Items oder aus einem
einzigen Item. Wir verwenden das Attribut n, um
die Position in der Liste anzuzeigen. Dieser Zähler muß
also bei jedem weiteren Element um eins erhöht werden. Die
Attributierungsregeln sind daher
Is -> Item Is1 Item.n := Is.n
Is1.n := Is.n + 1
Is -> Item Item.n := Is.n
Auch in diesem Fall greifen wir auf vererbte Information
zurück. Irgendwo "vorher" (weiter oben im Ableitungsbaum)
müssen wir das Attribut Is.n initialisieren. Das
geschieht, wenn wir zum ersten Mal auf eine Liste stoßen, in
List -> <UL> Is </UL> | <OL> Is </OL>
Die Attributierungsregel lautet ganz einfach Is.n := 1.
Zuerst müssen wir uns überlegen, welche Elemente eigentlich von welchen Elementen getrennt werden. Nocheinmal zur Erinnerung: Ein HTML-Text besteht aus einer Liste von Textelementen. Ein Textelement ist entweder ein Textstück oder eine Liste.
Html -> Text Html | Text Text -> chars | List
Das ergibt folgende Kombinationsmöglichkeiten:
Sowohl ein Text als auch eine Liste fängt immer in einer neuen
Zeile an, d.h. hier müssen wir das Trennzeichen einfügen.
Die Variante ein Text gefolgt von einem Text gibt es nicht,
weil chars den gesamten Text zwischen zwei Listen beinhaltet.
Die obige Überlegung führt sofort zu
Html -> Text Html1 Html.x := Text.x || "\n" || Html1.x
Jetzt fehlt nur noch die Trennung der Listeneinträge. Jeder Listeneintrag fängt in einer neuen Zeile an. Aufgrund unserer früheren Attributierungsregel wissen wir, daß die Tabulatorposition stimmt, nur das Trennzeichen fehlt noch. Wir wenden das gleiche Schema an und erhalten
Is -> Item Is1 Is.x := Item.x || "\n" || Is1.x
Nach dem Zusammensetzen der einzelnen Bausteine und dem Hinzufügen der Durchreicheregeln erhalten wir die endgültige Lösung.