[Mission Impossible] CSS Parser erstellen...

[Daniel G]

:hi: 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. :wink:

[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

Delphi-Quellcode:

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:

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. :thumb:

War ich ja doch nicht so schlecht davor :wink:

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

Zitat von marabu

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

*räusper*

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

[Tubos]

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

[Sergej]

Zitat:

Zitat von Daniel G

Zitat:

Zitat von marabu

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

*räusper*

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

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:

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. :mrgreen:

Zitat:

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

//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 ^^

[Daniel G]

Igitt :shock:

Aber wenn man's weiß, kann man das glaube ich auch handeln....

[mael]

Um einen Parser zu schreiben mit den Sachen die man im Netz findet ist etwas schwierig ohne theoretische Informatik zu verstehen.
Hauptsächlich wegen den Begriffen und weil viele Details angesprochen werden.
Z.B. ob LL, LR, LALR, ... Parser ist erst einmal egal.

Das gibt nur die Ausdruckstärke an (also welche Sprache so beschreibbar ist) und damit auch die mögliche Geschwindigkeit des Parsers. Übliche Werkzeuge wie Yacc/Bison sollten aber die meisten Programmiersprachen beschreiben können, und im besonderen sollte CSS kein Problem sein.

Wenn man es von Hand schreibt, also direkt Delphi, hat man aber sowieso die vollständige Mächtigkeit einer Programmiersprache und kann alles parsen.
Dazu kannst Du Dir mal den SynEdit-Quelltext des CSS-Highlighters anschauen. Der kann die einzelnen Tokens erkennen und entspricht einem Lexer mit etwas Zusatz. Das könnte eventuell schon ausreichen, falls Du nur eine bestimme Stelle im Quelltext finden willst.

Falls Du trotzdem kurz über die Theorie drüberschauen möchtest, schaue nach Kontextfreie Grammatiken (Produktionen, Ableitungen, akzeptieren) und reguläre Sprachen.
Kellerautomaten bzw. DEAs entsprechen den oben genannten Grammatiken und sind zu ihnen äquivalent, in der Praxis wirst Du aber Grammatiken schreiben.

Delphi Parser Generator: Delphi Yacc und Lex

Hier ist noch eine gute Einführung in Lex und Yacc mit kurzer Erklärung der Theorie:
http://epaperpress.com/lexandyacc/

Hoffe das hilft ein wenig.

[Daniel G]

Zitat:

Zitat von mael

Dazu kannst Du Dir mal den SynEdit-Quelltext des CSS-Highlighters anschauen. Der kann die einzelnen Tokens erkennen und entspricht einem Lexer mit etwas Zusatz.

Hmm, stimmt, an SynEdit habe ich gar nicht gedacht, man muss das Rad ja auch nicht immer neu erfinden.

Zitat:

Zitat von mael

Das könnte eventuell schon ausreichen, falls Du nur eine bestimme Stelle im Quelltext finden willst.

Hehe, ich sach mal so: Wenn ich das komplette CSS - Dokument in einer Baumstruktur vorliegen habe, bin ich glücklich. :wink:

Zitat:

Zitat von mael

Falls Du trotzdem kurz über die Theorie drüberschauen möchtest [...]

Jabb, interessieren würde es mich schon, zumindest in Grundzügen...

Zitat:

Zitat von mael

Hoffe das hilft ein wenig.

Bestimmt, danke dir. ;)

Über den Begriff "Lexer" bin ich schon gestolpert, allerdings produzierten die alle C - Code...

//Edit: "Quote" - Tag repariert
//Edit2: "Edit" - Tag repariert. Ich hasse Opera :wall:

[mael]

Zitat:

Zitat von Daniel G

Hehe, ich sach mal so: Wenn ich das komplette CSS - Dokument in einer Baumstruktur vorliegen habe, bin ich glücklich. :wink:

Hmm, du kannst natürlich darauf aufbauen, aber eine Baumstruktur erfordert da schon noch ein gutes Stück arbeit, d.h. die Syntax wird vom Highlighter nicht verarbeitet.
In diesem Fall ist vielleicht doch Yacc einfacher, muß man sich aber auch ne Weile reindenken.

Zitat:

Zitat von Daniel G

Über den Begriff "Lexer" bin ich schon gestolpert, allerdings produzierten die alle C - Code...

Der Link in meinem obigen Beitrag (bzw. das Programm dahinter) erzeugt Delphi-Code.

[Daniel G]

Zitat:

Zitat von mael

Zitat:

Zitat von Daniel G

Über den Begriff "Lexer" bin ich schon gestolpert, allerdings produzierten die alle C - Code...

Der Link in meinem obigen Beitrag (bzw. das Programm dahinter) erzeugt Delphi-Code.

"...also danke für den Link" hatte ich vergessen dazu zu schreiben. :wink:

Ich werde mich dann mal durch die vorhanden Sourcen, Specs und what ever wühlen...

[marabu]

Hallo Daniel,

ich will dich nicht davon abhalten einen neuen CSS-Editor zu erschaffen, aber wenn du dir einen Überblick über dein CSS-Monster verschaffen möchtest, dann hilft dir vielleicht TopStyle Lite (1.8 MB).

marabu

[Daniel G]

Zitat:

Zitat von marabu

ich will dich nicht davon abhalten einen neuen CSS-Editor zu erschaffen [..]

Das nehme ich mit Freude zur Kenntnis. :lol:

TopStyle kannte ich schon, auch ein paar andere Freeware - Editoren habe ich mir angesehen (selbst hier in der DP), nur hatte der eine ein Feature, das ich gerne gehabt hätte, der andere ein Feature, das ich gerne gehabt hätte. Also habe ich beschlossen, einen Editor zu schreiben, der das kann, was ich gerne an Features hätte.

Und vllt. kann ich dann ganz nebenbei auch endlich CSS mal vernünftig lernen... :wink: