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

[EnTeQuAk]

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

[sunmountain]

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]

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]

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]

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.

[Leonidas]

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.

[EnTeQuAk]

Sehr interessante Links Leonidas -- Danke!

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


MfG EnTeQuAk

[BlackJack]

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]

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

[sunmountain]

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]

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

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]

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

[sape]

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:

[(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]

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:

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


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]

[...]
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.

[sape]

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

[sape]

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

[Leonidas]

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?

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.

[sape]

[...]
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?
[...]

Halte es für übertrieben oder unperformant; Aber ich (Und das sage ich als ein Nichtinformatiker), würde gleich eine saubere Lösung anstreben.

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)]

Dieser Strom wird dann an einen Gramma übergeben der überprüft ob es einer der grammatikalischen Regeln folgt, die du definiert hast. Z.B. muss nach einem ** ein Literal folgen (Alle möglichen Zeichen erlaubt bis auf "Keywords" (Z.B. **, __, etc) und MUSS mit ** enden.

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.

[EnTeQuAk]

Das nenne ich flexibel

Hört sich sehr schön an

Ich werde mich dann mal für ne Weile verabschieden.

denn...

Aber ich (Und das sage ich als ein Nichtinformatiker), würde gleich eine saubere Lösung anstreben.

Ich auch

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