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.
cracki
User
Beiträge: 72
Registriert: Montag 25. Dezember 2006, 05:01

implementier nen richtigen parser, samt statemachine und allem
...meh...
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Aber dieser muss die Syntax ja auch irgentwie treffen können oder? :D

Möchte ich übrigens auch...

oder ich warte erstma auf 'sape''s Lösung... mal schaun, wie seins ausschaut

MfG EnTeQuAk
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

BlackJack hat geschrieben: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.
XML ja, BBCode nein. Für BBCode parsen habe ich für pocoo doch einen relativ komplexen Lexer/Parser Verschnitt schreiben müssen. Probleme sind verschachtelte Quote/Code Blöcke, da geht mit Regex nichts mehr und code/list blöcke ansich, die kein BBCode in sich erlauben etc.

Wer sowas sucht: http://trac.pocoo.org/browser/pocoo/tru ... /bbcode.py
TUFKAB – the user formerly known as blackbird
cracki
User
Beiträge: 72
Registriert: Montag 25. Dezember 2006, 05:01

kann so schwer ja nicht sein. tokenisieren, parsen, ausgeben...

hab schon mal nen PEG parser geschrieben. einziges problem ist wie ich aus dem baum dann was gescheites mache. das wuerde ich am liebsten ins grammar einarbeiten... da fehlt mir noch die breitsicht was da ne uebliche art ist das zu machen.

aber bbcode ist doch keine huerde, oder?
...meh...
BlackJack

blackbird hat geschrieben:
BlackJack hat geschrieben: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.
XML ja, BBCode nein. Für BBCode parsen habe ich für pocoo doch einen relativ komplexen Lexer/Parser Verschnitt schreiben müssen. Probleme sind verschachtelte Quote/Code Blöcke, da geht mit Regex nichts mehr und code/list blöcke ansich, die kein BBCode in sich erlauben etc.
Das "Nein" verstehe ich jetzt nicht? Wo widersprichst Du mir denn? Oder wo gibt's Probleme mit einem rekursiv absteigenden Parser?
Benutzeravatar
jens
Python-Forum Veteran
Beiträge: 8502
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Ich stecke zwar da nicht so tief in der Materie, aber mal eine generelle Frage...
cracki hat geschrieben:tokenisieren, parsen, ausgeben...
Dieser Aufbau wird doch immer wieder gemacht. Könnte man nicht eine Variante bauen, die allgemein Gültig ist?

Ich meine, das man nicht direkt die Regeln "wenn input = xy dann output =xy" festlegt, sondern das nochmals in einer weiteren Ebene.

Also das man einen Parser hat, bei den man die Syntax quasi per config definiert. So könnte man den Parser für verschiedene Markups gleichzeitig nutzten.

Im Grunde so wie pygments mit seinen verschiedenen Lexer.

GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

jens hat geschrieben:
cracki hat geschrieben:tokenisieren, parsen, ausgeben...
Dieser Aufbau wird doch immer wieder gemacht. Könnte man nicht eine Variante bauen, die allgemein Gültig ist?
Klar, PyParsing und ZestyParser lassen grüßen.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

jens hat geschrieben: Also das man einen Parser hat, bei den man die Syntax quasi per config definiert. So könnte man den Parser für verschiedene Markups gleichzeitig nutzten.
Ja kann man. Daran versuche ich mich ja gerade.

Ansonsten, wer es richtig allgemein haben will kann ich nur PyParsing empfehlen. Damit habe ich mich einige Zeit beschäftigt und finde es Ziemlich Klasse gemacht.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

jens hat geschrieben:Also das man einen Parser hat, bei den man die Syntax quasi per config definiert.
Es gibt ja auch welche die EBNF als Config akzeptieren. Sieh dir mal als Beispiel dan guten alten yacc an, der versteht BNF.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

EnTeQuAk hat geschrieben: So... so soll das aber nicht erkannt werden... *grml* -- wie kann ich da besser vorgehen -- wie müsste ich über den Text iterieren, um Tokens anzufertigen, um solche Sachen auch "zuferlässig" zu treffen?
Einfach im Lexer den Text spliten:

Code: Alles auswählen

src = """{{{LITERAL_ALL_CHARS
}}}
**//test//**
"""    
regexp = re.compile(r'({{{|}}}|\*\*|//|__|)')
output = [x for x in regexp.split(src) if x != '']
print output

Code: Alles auswählen

['{{{', 'LITERAL_ALL_CHARS\n', '}}}', '\n', '**', '//', 'test', '//', '**', '\n']
Die einzelnen Tokens muss dann der Lexer mit den richtigen Typ versehen.

BTW: Wichtig ist das der ausdruck im re-teil in runden klammern eingeschlossen ist!!

r'({{{|}}}|\*\*|//|__|)' = OK
r'{{{|}}}|\*\*|//|__|' = Nicht OK weil dann sowas bei rauskommt:

Code: Alles auswählen

['LITERAL_ALL_CHARS\n', '\n', 'test', '\n']
lg
cracki
User
Beiträge: 72
Registriert: Montag 25. Dezember 2006, 05:01

jens hat geschrieben:Könnte man nicht eine Variante bauen, die allgemein Gültig ist?

Ich meine, das man nicht direkt die Regeln "wenn input = xy dann output =xy" festlegt, sondern das nochmals in einer weiteren Ebene.

Also das man einen Parser hat, bei den man die Syntax quasi per config definiert. So könnte man den Parser für verschiedene Markups gleichzeitig nutzten.
genau sowas habe ich ja auch gemacht. der parser ist ein modul mit funktionen und klassen. das grammar ist ein grosses dict mit nonterminal -> grammar zuordnungen und alles ist mit funktionen modelliert. man muss das grammar selbst also nicht nochmal parsen, weils schon code ist.

alles was man dann noch macht, ist: "parse(input, grammar)" und raus kommt ein baum.

ich weiss, PEGs sind relativ starr und scheinbar auch nicht sehr fehlertolerant was den input angeht. und wie man den baum gescheit weiterverarbeitet (oder beim parsen gleich verarbeitet), das wissen fehlt mir noch.
...meh...
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

cracki hat geschrieben:und wie man den baum gescheit weiterverarbeitet (oder beim parsen gleich verarbeitet), das wissen fehlt mir noch.
Wie man generell einen AST verarbeitet oder modellieren sollte um leichten Zugriff zu haben oder speziell von dem PEG?
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

sape hat geschrieben:
EnTeQuAk hat geschrieben: So... so soll das aber nicht erkannt werden... *grml* -- wie kann ich da besser vorgehen -- wie müsste ich über den Text iterieren, um Tokens anzufertigen, um solche Sachen auch "zuferlässig" zu treffen?
Einfach im Lexer den Text spliten:

Code: Alles auswählen

src = """{{{LITERAL_ALL_CHARS
}}}
**//test//**
"""    
regexp = re.compile(r'({{{|}}}|\*\*|//|__|)')
output = [x for x in regexp.split(src) if x != '']
print output

Code: Alles auswählen

['{{{', 'LITERAL_ALL_CHARS\n', '}}}', '\n', '**', '//', 'test', '//', '**', '\n']
Die einzelnen Tokens muss dann der Lexer mit den richtigen Typ versehen.

BTW: Wichtig ist das der ausdruck im re-teil in runden klammern eingeschlossen ist!!

r'({{{|}}}|\*\*|//|__|)' = OK
r'{{{|}}}|\*\*|//|__|' = Nicht OK weil dann sowas bei rauskommt:

Code: Alles auswählen

['LITERAL_ALL_CHARS\n', '\n', 'test', '\n']
lg
Hey... das mit der Klammer wars :D Das werde ich gleich mal ausprobieren.

Herzlichen Dank! :)

MfG EnTeQuAk
cracki
User
Beiträge: 72
Registriert: Montag 25. Dezember 2006, 05:01

sape hat geschrieben:Wie man generell einen AST verarbeitet oder modellieren sollte um leichten Zugriff zu haben oder speziell von dem PEG?
wie ich einen AST so bequem wie moeglich weiterverarbeite. dazu zaehlt z.b. baum stutzen, transformationen, solche geschichten. braucht dich aber nicht kuemmern, weil es geht ja, nur ists mir zu umstaendlich. hab auch das drachenbuch noch nicht gelesen, also...
...meh...
BlackJack

Hier noch ein Versuch einen Parser für die dauCMS Syntax zu schreiben:

http://www.ubuntuusers.de/paste/7241/

Eigentlich habe ich den Parser weggelassen. Es gibt einen `Lexer` und einen `DirectXHTMLWriter` der den Tokenstrom direkt und inkrementell in ein HTML-Dokument überführt. Es gibt also keinen AST, sondern immer nur soviel Informationen im Speicher, wie für die Zerlegung einer einzelnen Eingabezeile und den Stack für offene XML-Tags benötigt wird.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

EDIT:

Jack, wie gewohnt saubere Qualität!! :) -- *thumbs-upp*

Ich werde an meiner Version *trotzdem* weiter basteln :D

@EnTe: Ich würde BlackJacks Variante nehmen für euer vorhaben. Sieht sehr preformant und speicher schonend aus :) Meine wird wohl ein wenig Overkill, da ich gleich einen allgemeinen Markup=>AST=>X-Beliebiges Format-Generator schrieben werde (Bin schon ziemlich weit.), der auch BBC, reStr, etc in ein AST überführen kann. -- Also für euer vorhaben wird es wider zu groß denke ich.

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

Hmm, irgendwie verstehe ich nicht so ganz wie dein Lexer den Beginn- und End-Tag von Markups mit gleichen Token unterscheiden kann :? Bei mir musste ich dafür ein par Zeilen schreiben.

EDIT: Ups, hab ein Denkfehler gehabt. Ist für Markups ja garnicht notwendig. Wenn z.B. ein ohne endtag gefunden wurde, wird es ehe als plaintext interpretiert.
BlackJack

sape hat geschrieben:Hmm, irgendwie verstehe ich nicht so ganz wie dein Lexer den Beginn- und End-Tag von Markups mit gleichen Token unterscheiden kann :? Bei mir musste ich dafür ein par Zeilen schreiben.
Das kann mein Lexer auch nicht, das wird im HTML-Writer mit dem Stack gemacht.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Nun hab ichs verstanden, nach dem ich die Scource ein wenig länger durchgelesen habe. (Einige Sachen waren für mich nicht so offensichtlich.)

BTW: Die regexp von dir verstehe ich noch nicht. Müssen die so Kompliziert sein?

Ich hab das so gelöst mit de regexp (Kleiner Ausschnitt):

Code: Alles auswählen

[...]
from ast.ast import MarkupClassNames as MCN

_NAME_OF_THIS_MODULE = os.path.basename(__file__).split('.')[0]


class BasisLexer(object):[...]
    def __init__(self, source):
        self.markup_identifier = (
            # Markups die den gleichen Bezeichner für Begin und Ende verwenden.
            {MCN.MARKUP_BOLD:      (r'\*\*', None)}, # <- **
            {MCN.MARKUP_ITALIC:    (r'//', None)},
            {MCN.MARKUP_UNDERLINE: (r'__', None)},
            # Markups die unterschiedliche Bezeichner für Begin und Ende verwenden.
            {MCN.MARKUP_CODE:      (r'{{{', r'}}}')}
        )
        self.init(source)
        
    def init(self, source):
        mre = re.compile(self._merge_markups_to_restr())
        self.source = [x for x in mre.split(source) if x != '']
        self._lexer_stream = None
        [...]
        
    def _merge_markups_to_restr(self):
        li = list()
        for elem in self.markup_identifier:
            identifier = elem.values()[0]
            if identifier[1] is not None:
                li.append("%s|%s|" % (identifier[0], identifier[1]))
            else:
                li.append("%s|" % identifier[0])
        
        return r"(%s)" % "".join(li)[0:-1]

[...]
Das ergibt (\*\*|//|__|{{{|}}}). Damit splite ich den text. Ist das eventuell nicht ok? Welchen vorteil habe ich mit deinen regexp code? -- Bisher habe ich damit alles richtig gesplitet gekriegt ohne Fehler.

BTW: Falls gleich die fragen kommen wegen `` def init(self, source):``
Ganz Simpel: Jeder Lexer erbt nachher von ``BasisLexer`` und muss
``self.markup_identifier `` in ``__init__`` implementieren und darf nicht ``BasisLexer.__init__(...)`` aufrufen, sondern muss ``self.init(...)`` aufrufen. Den Rest erledigt die Klasse. Eventuell noch ein par Anpassungen (Falls der Lexer nicht genug kann)...
BlackJack

sape hat geschrieben:BTW: Die regexp von dir verstehe ich noch nicht. Müssen die so Kompliziert sein?

Ich hab das so gelöst mit de regexp (Kleiner Ausschnitt):

[…]

Das ergibt (\*\*|//|__|{{{|}}}). Damit splite ich den text. Ist das eventuell nicht ok? Welchen vorteil habe ich mit deinen regexp code? -- Bisher habe ich damit alles richtig gesplitet gekriegt ohne Fehler.
Das ist schon okay, erkennt aber weder Überschriften noch "Befehle mit Argumenten" wie ``#image[spam/eggs.png]``. Den ersten Teil habe ich genauso wie Du.
Antworten