[Mission Impossible] CSS Parser erstellen...

[Daniel G]

Ihr,

Nachdem ich mich durch eine mehrere hundert Zeilen kleine CSS - Datei kämpfen musste, kam mir die großartige Idee, ich könnte ja einen CSS - Parser schreiben, der als Grundlage für einen CSS - Editor dienen soll. Die Kernfrage, die man sich natürlich stellt, lautet:

Wie stelle ich das am elegantesten an?

Also habe ich hier im Forum a bissel gesucht und bin dabei immer wieder auf die Begriffe "Scanner" und "Token" gestoßen. Auch von DEA war die Rede, und nachdem ich Wikipedia endlich klar gemacht hatte, dass ich nichts mit einer Tankstelle zu tun haben will, sondern etwas über "deterministische endliche Automaten" wissen wil, fiel ich ob der vielen mathematischen Symbole in dem Artikel glatt vom Hocker. Sofort schloss ich die Seite wieder und setzte meinen gesunden Menschenverstand ein.

Was muss ich eigentlich beachten?

Im Prinzip brauch ich erstmal eine Definition der Sprache, also quasi deren Grammatik. Die soll, laut Wikipedia, so aussehen:

Code:

Selektor { Eigenschaft-A: Wert-A; Eigenschaft-B: Wert-B; } /* Kommentar */

Prinzipiell also doch gar nicht so schwer: "{" leitet einen neuen Block ein, ergo ist das Wort davor der Selektor. Dann kommen die Eigenschaften. Links vom ":" steht die Eigenschaft, rechts davon der Wert, dessen Ende durch ein ";" gekennzeichnet ist. Der Block wird durch ein "}" wieder geschlossen.

Es klingt vielleicht jetzt sehr naiv, aber könnte man mit dieser Vorgehensweise und der aktuellen CSS2 - Definition (über CSS3 reden wir nochmal) einen halbwegs vernünftigen Parser schreiben? Und wie würde ich sowas programmiertechnisch geschickt umsetzten können? Evtl. über eine baum - ähnliche Struktur?

P.S.: Wer sich jetzt fragt: "Wat will der Kerl eigentlich von mir?": Im Prinzip will ich nur wissen, ob der eingeschlagene Weg der richtige ist, oder ob ich damit mit meiner typischen "so schwer kann das ja nicht sein" - Naivität evtl. gehörig auf die Schnauze fliegen kann.

[alzaimar]

Hi Daniel,

So schwer ist das auch nicht. Wie Du schon richtig erkannt hast, besteht ein Parser aus zwei Teilen: Dem Tokenizer und dem 'Spracherkenner', dem Parser. Der Tokenizer überführt die Eingabe (meist eine Zeichenkette) in eine Token-Kette. Aus
Procedure Foobar (Param1 : Integer); Wird

Code:

Keyword PROCEDURE
Identifier FooBar
Symbol (
Identifier Param1
Symbol :
Identifier Integer
Symbol )
Symbol ;

Der Tokenizer ('Scanner') erkennt die Symbole, aus denen die zu parsende Sprache besteht. Die Delphi-Sprache basiert ja auf Symbolen ('Token') wie 'Procedure', 'Identifier','Number'. 'String' etc.

Ein Kommentar ist ein Sonderfall und wird i.A. vom Scanner verschluckt.

Wenn dein Tokenizer diese Routinen zur Verfügung stellt, dann kannst Du damit alle Sprachen erkennen.

Delphi-Quellcode:

Function GetNextToken : TToken; // liefert das nächste Token und bewegt den Eingabezeiger
Function UngetToken (aToken : TToken); // Bewegt den Eingabezeiger zurück, sodaß der nächste Aufruf von GetNextToken das aToken liefert.
Function PeepNextToken : TToken; // Liefert das nächste Token, ohne den Eingabezeiger zu bewegen.

Ein spezielles Token ist das 'EOF'-Token, das das Ende der Eingabe bezeichnet.

Der Parser überführt nun widerum die Eingabe (hier eine Token-Liste) in einen Syntax-Baum.
Der Compiler überführt den Syntax-Baum in die Übersetzung (meist ASM, kann aber auch z.B. 'C' sein. Oder formatierter Delphi-Code. Oder ein Manual, Crossref etc.).
Der Interpreter überführt den Syntax-Baum in eine E/A-Relation, führt also das Programm aus.

Für einen einfachen Parser musst Du nicht studiert haben, aber bei Sprachen wie Delphi sollte man schon mal etwas von 'formalen Sprachen' gehört haben. Bei deinem Beispiel würde ich die Grammatik der Sprache direkt in Delphi überführen:

Code:

Selektor { Eigenschaft-A: Wert-A; Eigenschaft-B: Wert-B; } /* Kommentar */

Code:

CSS-Code ::= <CSS-Statement> [ <CSS-Code> ]
                | Epsilon

Das ist die sog. Backus-Naur-Notation. Es bedeutet:

Zitat von Backus-Naur:

Ein CSS-Code besteht aus einem CSS-Statement gefolgt von CSS-Code (oder auch nicht, das sind die [...]). CSS-Code darf auch leer sein (das beduetet das Epsilon).

Code:

CSS-Statement ::= <Selektor> '{' <Propertylist> '}'
Selektor ::= Identifier
PropertyList ::= <PropertyDesc> [<PropertyList>] | Epsilon
PropertyDesc ::=  <Property> ':' <Value> ';'
Property := Identifier
Value ::= Identifier | Integer-Number | Floating-Point-Number

Ein '|' steht für: Alternative.
Ein Identifier ist unsere übliche Definition eines Bezeichners. Das kann man zwar auch noch backusnaurnotationstechnisch beschreiben, aber das schenken wir uns, oder doch nicht:

Code:

Identififer ::= <Letter> [ <Letter-Or-Digit> ]
Letter ::= 'A' | 'B' | 'C' ... 'Z' | 'a' | ... | 'z'
Digit ::= '0' | ... '9'
Letter-Or-Digit ::= <Letter> | <Digit>

Soooo, jetzt das Programm:

Delphi-Quellcode:

Function CSSCode : Boolean;
Begin
  Result := False;
  If CSSStatement Then
     While CSSCode Do;
End;

Function CSSStatement : Boolean;
Var
  Selector : TToken;

Begin
  Result := False;
  If IsIdentifier (Selector) Then
    If IsSymbol ('{') Then
     If IsPropertyList Then
       If IsSymbol ('}') Then
         Result := True;
End;
...

Klar? Die Backus-Naur-Form wird einfach 1:1 in Delphi-Code umgesetzt. Natürlich fehlen im o.g. Beispiel geeignete Rückgabewerte, denn irgendwie muss der erkannte Code ja in einen Syntax-Baum. Nebenbei klappt das mit dieser Art der Parserprogrammierung nur, weil die CSS-Sprachdefinition so einfach ist, ich glaube das betrifft die LL(0)-Sprachen, weil sie von Links nach Rechts geparst werden können und keinen '(0)' Look-Ahead benötigen, aber das ist schon bald 15 Jahre her, also nagt der Zahn der Zeit an diesem Teil des Hirns.

EDIT: Oder kukstu hier

[Daniel G]

Hey,

vielen Dank für die ausführliche Erklärung.

War ich ja doch nicht so schlecht davor

[marabu]

Hallo Daniel,

CSS kann mit einem LL(1) Parser verarbeitet werden, aber alleine die Grammatik von CSS Level 1 umfasst schon 22 Produktionen. Vielleicht solltest du CSS2 auch erstmal außen vor lassen ...

Grüße vom marabu

[Daniel G]

Zitat von marabu:

aber alleine die Grammatik von CSS Level 1 umfasst schon 22 Produktionen.

*räusper*

Was ...äh... sind Produktionen in diesem Zusammenhang?

[Tubos]

"in der Informatik eine Ersetzungsregel in einer formalen Grammatik, siehe Produktion (formale Sprache)". Wikipedia.

[Sergej]

Zitat von Daniel G:

Zitat von marabu:

aber alleine die Grammatik von CSS Level 1 umfasst schon 22 Produktionen.

*räusper*

Was ...äh... sind Produktionen in diesem Zusammenhang?

Hey. Produktionen sind einfach folgendes:

Code:

Identififer ::= <Letter> [ <Letter-Or-Digit> ]
Letter ::= 'A' | 'B' | 'C' ... 'Z' | 'a' | ... | 'z'
Digit ::= '0' | ... '9'
Letter-Or-Digit ::= <Letter> | <Digit>

Das bedeutet z.B., dass <Identifier> nach <Letter> und optional <Letter-Or-Digit> ableitbar ist. <letter> widerum kann man nach allen Buchstaben ableiten, <digit> nach allen Zahlen und so weiter. Wenn du mit ableiten nichts anfangen kannst, dann denk dir statt dessen sowas wie "lässt sich aus [...] erzeugen". Hat zumindest mir am Anfang geholfen

[Edit] Zusammenfassend kann man also sagen, dass Produktionen Ersetzungsregeln sind... [/Edit]

[Daniel G]

Zitat von Sergej:

Wenn du mit ableiten nichts anfangen kannst, dann denk dir statt dessen sowas wie "lässt sich aus [...] erzeugen".

Doch, doch. Ableitungen sind mir ein Begriff, wenigstens etwas, was ich in der Schule ordentlich konnte.

Zitat von Sergej:

[Edit] Zusammenfassend kann man also sagen, dass Produktionen Ersetzungsregeln sind... [/Edit]

Ah, ok. Und davon gibt das bei CSS 1 22 Stück? Hm..

@Tubos: Danke auch dir

//Edit: Die Frage wäre ja prinzipiell, inwiefern CSS1 und CSS2 genutzt werden, und ob sich eine Implementierung von CSS2 nachträglich lohnen würde.

[Sergej]

Naja wenn du einen Parser/Lexer für CSS1 hast dürfte der sich ohne größere Probleme auf CSS2 erweitern lassen. Du kannst dir ja mal die Unterschiede der beiden Grammatiken anschaun...

CSS1
CSS2

[Florian H]

gibt ja auch so sachen wie mehrere (sub-)eigenschaften, die einer eigenschaft untergeordnet sind..
also es ginge ja sowohl

Code:

border-style:solid;
border-color:red;
border-width:1px;

also auch

Code:

border:solid red 1px;

Aber das sind wohl Feinheiten ^^