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
Suche Informationen über -- Text - lexer - parser --
- sunmountain
- User
- Beiträge: 89
- Registriert: Montag 13. März 2006, 17:18
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.
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.
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.
[(INTEGER, 4), (PLUS, None), (INTEGER, 5)]
Wie ein Token aussieht, beschreibt man meistens als regulären Ausdruck.
Mein Lieblings-Parsergenerator in Python ist PyParsing.
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. --- mit einfachen Regular Expressions wird das schwierig... da muss ein einhaltlicher Lexer her, der das Suchen anhand der Regex übernimmt.
MfG EnTeQuAk
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]
MfG EnTeQuAk
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.
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.
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
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.
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 (former) Modvoice
Sehr interessante Links Leonidas -- Danke!
Das Buch ist wirklich genial Das werde ich mir mal ausdrucken (sind ja net sooo viele Seiten )
MfG EnTeQuAk
Das Buch ist wirklich genial Das werde ich mir mal ausdrucken (sind ja net sooo viele Seiten )
MfG EnTeQuAk
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.
-- hi hi nee ich hab nur die Wikipediaseite gesehen sorry
Sehe ich das richtiug, das es dort mehr um den Compilerbau geht?
Ich meine... ich will Wiki-Syntax parsen
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
Sehe ich das richtiug, das es dort mehr um den Compilerbau geht?
Ich meine... ich will Wiki-Syntax parsen
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
- sunmountain
- User
- Beiträge: 89
- Registriert: Montag 13. März 2006, 17:18
Das war für mich immer ein Tokenizer.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.
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.EnTeQuAk hat geschrieben:Sehe ich das richtiug, das es dort mehr um den Compilerbau geht?
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.
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.Ich meine... ich will Wiki-Syntax parsen
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
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
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
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
Ja und genau das ist ja ein Lexer. Tokenizer ist nur der "Moderner" Begriff.sunmountain hat geschrieben:Das war für mich immer ein Tokenizer.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.
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:
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.BlackJack hat geschrieben:[(INTEGER, 4), (PLUS, None), (INTEGER, 5)]
Ich hoffe ich habe das so richtig verstanden. Falls ich daneben liege bitte korrigieren.
lg
Gut gesagt.
Denke, das erklärt es schon ganz gut...
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:
wird. (mal so ganz simple ausgedrückt)
Das wäre ja eigentlich dann die Aufgabe eines Tokenizers, Lexers etc...
der parser würde das dann umwandeln in
(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
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
Denke, das erklärt es schon ganz gut...
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 __
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
der parser würde das dann umwandeln in
Code: Alles auswählen
Ich bin
<b>
dick geschrieben
</b>
Ich bin
<u>
unterstrichen
</u>
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
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
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.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>
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.
Erstmal zu den Node-Typen vom AST, aus dem der AST eine Python-Code besteht:
http://docs.python.org/lib/module-compiler.ast.html
http://epydoc.sourceforge.net/stdlib/co ... odule.html
Jederer dieser Nodes hat Content. Z.B.: Hat die Node Add zwei Summanden und weitere Nodes. Man kann dann z.B. von dem Punkt rekursive zum nächsten oder davorliegenden Node gehen. -- Es spielt keine Rolle bei welcher Node man sich befindet, man kann immer vor oder Zurück gehen (Falls davor oder dahinter weitere Nodes existieren.).
Naja, die ganze Verkettung aus den Nodes (die Man an hand ihres Types identifizieren kann) Bildet dann den sogenannten AST der, wenn richtig implementiert, sehr mächtig ist.
Wenn deine API steht kannst du dann sehr simpel (Siehe z.B: ElementTree für XML ) auf die einzelenen Nodes vom AST zurückgreifen.
Der nächste schritt wäre dann einen Parser zu schreiben, der den AST in eine andere darstellbare Form überführt -> Z.B: XHTML, XML, etc.
lg
http://docs.python.org/lib/module-compiler.ast.html
http://epydoc.sourceforge.net/stdlib/co ... odule.html
Jederer dieser Nodes hat Content. Z.B.: Hat die Node Add zwei Summanden und weitere Nodes. Man kann dann z.B. von dem Punkt rekursive zum nächsten oder davorliegenden Node gehen. -- Es spielt keine Rolle bei welcher Node man sich befindet, man kann immer vor oder Zurück gehen (Falls davor oder dahinter weitere Nodes existieren.).
Naja, die ganze Verkettung aus den Nodes (die Man an hand ihres Types identifizieren kann) Bildet dann den sogenannten AST der, wenn richtig implementiert, sehr mächtig ist.
Wenn deine API steht kannst du dann sehr simpel (Siehe z.B: ElementTree für XML ) auf die einzelenen Nodes vom AST zurückgreifen.
Der nächste schritt wäre dann einen Parser zu schreiben, der den AST in eine andere darstellbare Form überführt -> Z.B: XHTML, XML, etc.
lg
Leis dir mal folgendes durch: http://www.rg16.asn-wien.ac.at/~python/ ... /kap20.htm
Ist zwar ein "simples" Beispiel, erklärt aber die Funktionsweise gut.
lg
Ist zwar ein "simples" Beispiel, erklärt aber die Funktionsweise gut.
lg
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Im Zweifelsfall einfach ausprobieren - es stellt sich heraus, dass das nicht geht. Aber es gibt ja auch noch re.split(), welches auch mit regulären Ausdrücken arbeitet.EnTeQuAk hat geschrieben: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?
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Halte es für übertrieben oder unperformant; Aber ich (Und das sage ich als ein Nichtinformatiker), würde gleich eine saubere Lösung anstreben.EnTeQuAk hat geschrieben:[...]
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?
[...]
Das sieht für mich so aus, das ich einen Lexer aka Tokenizer habe, der mir atomare Eingabezeichen liefert mit vorangeschalteten Typ. In deinem Fall würde es so aussehen das er den kram wie ``Ich bin ** dick geschrieben ** `` z.B. so zerlegt:
Code: Alles auswählen
[(LITERAL, 'Ich bin'), (MARKUP_BOLD, None), (LITERAL, ' dick geschrieben ', (MARKUP_BOLD, None)]
Wenn der Gramma das für OK befindet, reicht er den Strom unverändert an den AST-Generator weiter, der das in ein AST erzeugt/hinzufügt. Das ganze geht da so lange bis die Datei bis zum ende durchgearbeitet wurde. -- Das Ganze nenne ich dann einfach mal Parser + Generator
Der vorteil ist, das du dann einen AST (Nach deiner eigenen Kreation) hast der eine abstrakte Repräsentation für deine Wiki-Code-Syntax darstellt, mit dem du dann fasst alles machen kannst -- Z.B. ist es jetzt ein einfaches einen neuen Parser zu schreiben, der aus dem AST z.B. XML-Code generiert oder (X)HTML, oder, oder.
Das nenne ich flexibel
lg
EDIT: Fehler ausgebessert.
Hört sich sehr schön anDas nenne ich flexibel
Ich werde mich dann mal für ne Weile verabschieden.
denn...
Ich auchAber ich (Und das sage ich als ein Nichtinformatiker), würde gleich eine saubere Lösung anstreben.
Nun ja -- ich werde dann ab und zu mal wieder mit ein paar Fragen ankommen
Danke nochmal an alle Linkposter, Tipp&Trickposter etc... ihr habt mir wiedermal geholfen, meinen Horizont erweitert!
MfG EnTeQuAk