Suche Informationen über -- Text - lexer - parser --

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Suche Informationen über -- Text - lexer - parser --

Beitragvon EnTeQuAk » Mittwoch 31. Januar 2007, 04:15

So.

ich benutze im Moment zum erstellen einer WikiSyntax die joa... unfertige Version von Tekisuto (hier)

So... doch... ich bastel ja an meinen Projekten, weil ich gerne lernen möchte. Nun versuche ich mich in Tekisuto reinzuarbeiten... um zu verstehen, wie es arbeitet und um eventuell eine besser an die Bedürfnisse von dauCMS angepasste Version zu schreiben.


Jedoch fehlt mir immo einfach eine Vorstellung, wie solch ein Lexer (geht ja noch gar nicht ums parsen der Ergebnisse) wirklich arbeitet.

Ich habe schon auf Wikipedia Verfahren wie LR-Parsing RL-Parsing etc. gefunden. jedoch klingt mir das dort so "wissenschaftlich".

Habt ihr da gute Informationen? -- Was benötigt man genau -- bzw. Wie kann man so etwas bewerkstelligen?


MfG EnTeQuAk
Benutzeravatar
sunmountain
User
Beiträge: 89
Registriert: Montag 13. März 2006, 17:18

Lexer

Beitragvon sunmountain » Mittwoch 31. Januar 2007, 07:39

Lexer, oder besser lexikalische Scanner, sind Programme
die bei einer gegebenen Syntax, z.B. in der erweiterten Backus-Naur Form (EBNF),
einen übergebenen Text in seine syntaktisch zusammengehörenden Einheiten
zerlegt.

Beispiel (sehr Einfach !)

ADDITION := SUMMAND '+' SUMMAND.
SUMMAND := ZAHL.
ZAHL := {ZIFFER}.
ZIFFER := 0 .. 9.

Wenn man nun einen Ausdruck wie den hat:

4 + 5

würde der Lexer daraus z.B. eine Baum erstellen, der die einzelnen
Bestandteile zusammenfasst.

Sowas schreibt man in den seltensten Fällen selbst - dafür gibt es
so Programme wie (F)Lex, Bison, YACC etc.

Oft werden solche Programme rekursiv aufgebaut, was dazu führt,
das man dann keine Bäume braucht, sondern direkt über die Rekursion
zu den richtigen Ergebnissen kommt.

Vielleicht schaust Du dir das mal an: http://www.dabeaz.com/ply/

Python bringt selbst aber auch Code mit, um in dieser Richtung
zu arbeiten: http://docs.python.org/lib/module-parser.html

Hoffe geholfen zu haben.
BlackJack

Beitragvon BlackJack » Mittwoch 31. Januar 2007, 11:19

Sunmountain geht schon etwas zu weit, was er beschreibt ist ein Parser und kein Lexer. Ein Lexer zerlegt die Eingabe erst einmal nur in einen Strom von Token oder Lexemen. Es wird noch kein Baum erzeugt, das macht dann erst der Parser, der als Eingabe einen Token-Strom bekommt. So ein Token kann man im einfachsten Fall als Tupel von einem symbolischem Bezeichner und einem Wert auffassen, wobei nicht jedes Token einen Wert haben muss. Das ``4 + 5``-Beispiel könnte beispielsweise dieses Ergebnis haben:

[(INTEGER, 4), (PLUS, None), (INTEGER, 5)]

Wie ein Token aussieht, beschreibt man meistens als regulären Ausdruck.

Mein Lieblings-Parsergenerator in Python ist PyParsing.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Beitragvon EnTeQuAk » Mittwoch 31. Januar 2007, 11:37

Mir ging es eigentlich eher darum... etwas sehr simples selber zu schreiben. Die Lösungen oben sind alle "HighLevel"... Ich brauch einfach etwas simples, kleines...

Es steht in keinem Verhältnis, wenn der Lexer fast drei mal So groß ist, wie das Programm ansich.

Wir wollen lediglich eine kleine Wiki-Syntax implementieren.

Immo nutzen wir wie oben gesagt Tekisuto als Lexer... aber mich interessiert das, was solch ein Lexer macht. Das Parsen... das haben wir immo auch selber implementiert... da wir dort einige Sachen benötigen... Tekisuto hat zZ so oder so keinen integrierten Parser... von daher.

So... jedenfalls interessiere ich mich weniger für existierende Lösungen.. sondern eher für deren "Suchalgorithmus". Denn... wie finden die so zuferlässig Sachen, wie in ein ander verschachtelte BBCodes.

Code: Alles auswählen

[b][u]dadada[/u][/b]
--- mit einfachen Regular Expressions wird das schwierig... da muss ein einhaltlicher Lexer her, der das Suchen anhand der Regex übernimmt.

MfG EnTeQuAk
BlackJack

Beitragvon BlackJack » Mittwoch 31. Januar 2007, 12:10

Also willst Du doch einen Parser, denn Lexer haben mit verschachteln nix zu tun.

Von Hand lassen sich rekursiv absteigende Parser (recursive descent parser) am einfachsten schreiben. Dort wiederum sind solche für LL(1)-Grammatiken am simpelsten. Das sind welche bei denen nur jeweils ein Token vorausgeschaut werden muss, um zu entscheiden welche Regel aus der Grammatik angewendet werden muss. Ansonsten muss man einen Parser verwenden, der die Eingabe zurücksetzen kann, wenn er den falschen Regeln gefolgt ist.

So etwas wie BBCode oder XML/HTML ist recht einfach, weil man bei einem Start-Tag rekursiv absteigen kann und bei einem Ende-Tag wieder eine Ebene höher gehen kann.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 31. Januar 2007, 12:13

Zu den ganzen Lexing-Parsing-Sachen gibt es übrigens im PythonInfo-Wiki die Seite LanguageParsing, wo auch auf ZestyParser verlinkt wird, welcher womöglich auch in den Bereicht von PyParsing kommt.

Für einen richtig genauen Einstieg wird in der Regel das sogenannte Dragon Book als ultimative Wissensquelle zitiert - vielleicht wäre das was für dich.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Beitragvon EnTeQuAk » Mittwoch 31. Januar 2007, 12:44

Sehr interessante Links Leonidas -- Danke!

Das Buch ist wirklich genial :D Das werde ich mir mal ausdrucken (sind ja net sooo viele Seiten )


MfG EnTeQuAk
BlackJack

Beitragvon BlackJack » Mittwoch 31. Januar 2007, 13:19

Reden wir von dem selben Buch!? Die erste Ausgabe hat ungefähr 900 Seiten und in der deutschen Übersetzung ist sie auf zwei Bände aufgeteilt.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Beitragvon EnTeQuAk » Mittwoch 31. Januar 2007, 13:37

:D -- hi hi nee ich hab nur die Wikipediaseite gesehen sorry :D

Sehe ich das richtiug, das es dort mehr um den Compilerbau geht?

Ich meine... ich will Wiki-Syntax parsen :D

Wobei das Gebiet ansich sehr interessant ist, muss ich sagen. Mal schaun. vllt. steige ich mal etwas näher ein, wenn ich mich mehr mit Python auskenne.


MfG EnTeQuAk
Benutzeravatar
sunmountain
User
Beiträge: 89
Registriert: Montag 13. März 2006, 17:18

Tokenizer

Beitragvon sunmountain » Mittwoch 31. Januar 2007, 13:39

BlackJack hat geschrieben:Sunmountain geht schon etwas zu weit, was er beschreibt ist ein Parser und kein Lexer. Ein Lexer zerlegt die Eingabe erst einmal nur in einen Strom von Token oder Lexemen.

Das war für mich immer ein Tokenizer.
BlackJack

Beitragvon BlackJack » Mittwoch 31. Januar 2007, 14:20

EnTeQuAk hat geschrieben:Sehe ich das richtiug, das es dort mehr um den Compilerbau geht?


Ja, aber Compiler, zu deutsch Übersetzer, ist ein ziemlich allgemeines Konzept. Es ist im Grunde ein Programm, dass eine Eingabesprache einliest, in eine Zwischendarstellung überführt, analysiert, eventuell Transformationen durchführt und in eine Ausgabesprache wandelt. Es muss sich dabei nicht zwingend um Programmiersprachen handeln.

Als Beispiel im Buch sind unter anderem auch EQN und LaTeX genannt. Die grundlegenden Techniken zumindest für den Lexer und Parser sind die gleichen.

Ich meine... ich will Wiki-Syntax parsen :D


Welche, es gibt so viele davon. Wenn es eine existierende ist, dann würde ich aber auf jeden Fall versuchen auch einen schon existierenden Parser zu verwenden.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Beitragvon EnTeQuAk » Mittwoch 31. Januar 2007, 14:31

Joa es gibt viele ;) Das haben wir uns auch gedacht... waren mit keiner zu 100% zufrieden und bauen nach und nach mehr Funktionen und mehr Syntax-Objekte ein.

Immo siehts so aus: http://daucms.de/trac/wiki/MarkupImDetail
Das ist momentan alles, was implementiert ist und auch funktioniert... nur halt alles etwas.. einfach gemacht :D

Nichts gegen Tekisuto, was wir immo benutzen... aber ich bastel mir halt gerne meine eigenen Lösungen... egal, ob es schon welche gibt oder nicht. Ich lerne halt gerne und probiere gerne aus.



BlackJack: du sprachst von einer Deutschen Übersetzung? -- Ich finde irgentwie nichts darüber... hast du da einen Link?

MfG EnTeQuAk
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Re: Tokenizer

Beitragvon sape » Mittwoch 31. Januar 2007, 15:14

sunmountain hat geschrieben:
BlackJack hat geschrieben:Sunmountain geht schon etwas zu weit, was er beschreibt ist ein Parser und kein Lexer. Ein Lexer zerlegt die Eingabe erst einmal nur in einen Strom von Token oder Lexemen.

Das war für mich immer ein Tokenizer.
Ja und genau das ist ja ein Lexer. Tokenizer ist nur der "Moderner" Begriff.

http://de.wikipedia.org/w/index.php?tit ... edirect=no

Das was du beschrieben hast ist vielmehr ein parser mit vorgeschalteten Lexer. Der Lexer zerlegt dabei einen Strom nach einer definierten "Grammatik" ("Grammatik"=Besser gesagt, scannt er nach gültigen Tokens um die dann mit vorgeschalteten type zurückzugeben. Die eigentliche syntaktische Überprüfung übernimmt der Parser.) und gibt dann einen Ausgabestrom mit den Tokens zurück, die dabei einen vorgeschalteten Type habe, damit der Parser zuordnen kann.

Also so wie im Beispiel von BlackJack:
BlackJack hat geschrieben:[(INTEGER, 4), (PLUS, None), (INTEGER, 5)]


Diese Tokens dienen dem Parser als atomare Eingabezeichen. Der Parser kümmert sich um die syntaktische Überprüfung der übergebenen Tokens und überführt das ganze dann in einem AST oder meldet einen Fehler wenn es nicht einer der definierten grammatikalischen regeln zuzuordnen ist.

Ich hoffe ich habe das so richtig verstanden. Falls ich daneben liege bitte korrigieren.

lg
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Beitragvon EnTeQuAk » Mittwoch 31. Januar 2007, 15:40

Gut gesagt.

Denke, das erklärt es schon ganz gut... :D


Ich habe mir nun mal die ganzen Wikipedia Artikel durchgelesen (fast alle... muss ja noch nebenbei arbeiten ;) ) und muss sagen... großes Thema.


Ihr sprecht manchmal von einem Tree, einen Baum... einen AST :)

damit ist doch immer eine strukturierte, für den parser "besser lesbare" Form des ausgangstextes gemeint oder?

Also z.B.

aus folgendem Text:

Code: Alles auswählen

Ich bin ** dick geschrieben **
ich bin __ unterstrichen __

wird. (mal so ganz simple ausgedrückt)

Code: Alles auswählen

for item in tree:
 print item

----- # ausgabe:
txt :: 'Ich bin'
bold--start ::
txt :: 'dick geschrieben'
bold--ende ::
txt :: 'Ich bin'
underline--start
txt :: 'unterstrichen'
underline--ende


Das wäre ja eigentlich dann die Aufgabe eines Tokenizers, Lexers etc...

der parser würde das dann umwandeln in

Code: Alles auswählen

Ich bin
<b>
dick geschrieben
</b>
Ich bin
<u>
unterstrichen
</u>

(mal jetzt noch die richtige Einrückung etc. nicht beachtet)

Hmm... mal schaun, ob ich so etwas hinbekomme :)

Ich überlege gerade, wie so etwas zu machen ist.

Einfach nach und nach über den Text iterieren und dann 'match''en, ob der Start etc. vllt. enthalten ist ist doof...

ganz einfach wäre ein 'findall' und dann ein 'replace' -- aber das ist zu einfach und unflexibel :D


Und hier die Frage. Mann kan ja einen Text mit ' "text=dada".split('=') ' "zerteilen". Kann ich als Argument für das 'split' auch regular expressions nehmen? -- oder müsste ich da eventuell den txt eines 'match' Objektes übergeben?

MfG EnTeQuAk
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Beitragvon sape » Mittwoch 31. Januar 2007, 15:55

EnTeQuAk hat geschrieben:[...]
der parser würde das dann umwandeln in

Code: Alles auswählen

Ich bin
<b>
dick geschrieben
</b>
Ich bin
<u>
unterstrichen
</u>

Nein, nicht wenn es sich um einen AST handeln soll. Da würde der Parser definierte "Objekte" nehmen, die den Content beinhalten, als Repräsentation für die Einzelnen Elemente. Wobei so ein "Objekt" (=Node von Type X) wider darunterliegende Tokens Nodes haben kann. Das gute ist, das man dann dadurch einen Abstrakten Baum (AST) gewinnt der sich rekursive durchlaufen lässt.

Deine Überführung im Beispiel wäre dann der nächste schritt eines weiteren Parsers, der aus dem AST dann (X)HTML gültigen Code (Oder sonstigen Code) generiert.

Ich such mla material raus. Bis gleich.

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]