S-Expressions parsen

[BastiL]

Hallo,

ich muss eine Datei mit s-Expressions parsen. Als Basis habe ich die folgende Library gefunden:

http://www.unixuser.org/~euske/python/sexpr.py

Ich lese die Datei in einen String und bekomme die Segmente in einer Liste zurück - eigentlich super.
Bei mir gibt es jetzt ein Problem: Die Datei enthält Binärdaten und darf daher nicht auf einmal geparst werden. Ich muss vielmehr immer nur einzelne Segmente einlesen und analysieren - dann weiss ich wie das folgende Segment eizulesen ist.
Ich bekomme es irgendwie nicht hin den Parser so zu modifizieren, dass er nur das nächste Segment (bis alle Klammern wieder geschlossen sind) liest und zurückgibt. Irgendwie muss da doch die feed-Methode angepasst werden? Wer kann mir da einen Tipp geben?

Danke.

[tordmor]

Zeilen 121-123

Code: Alles auswählen

            if len(self.build_stack) == 1:
              # current working list is the last one in the stack.
              self.feed_next(self.build)

Hier wird ein abgeschlossenes Ergebnis in die Ergebnisliste aufgenommen. Wenn Du hier die for-schleife verlässt sollte er nur das erste Ergebnis liefern.

[BastiL]

Zeilen 121-123

Code: Alles auswählen

            if len(self.build_stack) == 1:
              # current working list is the last one in the stack.
              self.feed_next(self.build)

Hier wird ein abgeschlossenes Ergebnis in die Ergebnisliste aufgenommen. Wenn Du hier die for-schleife verlässt sollte er nur das erste Ergebnis liefern.

Danke. Das hatte ich schon versucht, indem ich ein "return" eingebaut habe. Dann bekomme ich beim Aufruf der Funktion einen Backtrace, weil "feed" dann noch einmal mit einem leeren String aufgerufen wird. Dieser Aufruf kommt offenbar von "terminate" her.

[sma]

Der erwähnte Parser ist IMHO viel zu kompliziert. Einfache SEXPR kann ich 15 Zeilen einlesen. Als Scanner nehme ich einen regulären Ausdruck. Wenn man aus einer Datei lesen will, muss die next()-Funktion geändert werden. Das sollte aber auch in ~10 Zeilen zu machen sein. Ja, ich weiß, dass ich " und \ noch nachbehandeln müsste. Das sei dem Leser überlassen.

Code: Alles auswählen

import re

class Cons:
    def __init__(self, car, cdr):
        self.car, self.cdr = car, cdr
    def __str__(self):
        return "(%s %s)" % (self.car, self.cdr)

def read(s):
    i = re.finditer(r'([()]|(?:\\.|[^\s();"])+|"(?:\\.|[^"])+")|;.*?\n|\s+', s)
    def next():
        while True:
            t = i.__next__().group(1)
            if t: return t
    def readlist():
        t = next()
        if t == ')': return None
        return Cons(read(t), readlist())
    def read(t):
        if t == '(': return readlist()
        if t == ')': raise SyntaxError
        return t
    return read(next())

print(read("(this ;comment\n is (a test (sentences) (des()) (yo)))"))

Stefan

[snafu]

Der erwähnte Parser ist IMHO viel zu kompliziert. Einfache SEXPR kann ich 15 Zeilen einlesen.

Du bist ja auch Regex-sma. ;P

[BastiL]

Der erwähnte Parser ist IMHO viel zu kompliziert. Einfache SEXPR kann ich 15 Zeilen einlesen. Als Scanner nehme ich einen regulären Ausdruck. Wenn man aus einer Datei lesen will, muss die next()-Funktion geändert werden. Das sollte aber auch in ~10 Zeilen zu machen sein. Ja, ich weiß, dass ich " und \ noch nachbehandeln müsste. Das sei dem Leser überlassen.

Danke, Stefan das funktioniert gut habe ich gerade getestet. Dateien einlesen klappt gut. Und wirklich viel simpler. Was muss ich noch tun, um " und \ zu behandeln?
Ich bekomme am Ende eines Tokens immer noch ein "None", woher kommt das?

Danke.

Grüße Bastian

Edit: Teils selbst gelöst und gelöscht.

[BastiL]

So ich habe mal etwas rumgespielt und auf der Basis von Stefans Vorschlag das folgende gebaut (ich weiss, da ist eine Endlos-Schleife drin)

Code: Alles auswählen

#! /usr/bin/python

import re, sys, mmap, os

def readascii(s):
    i = re.finditer(r'([()]|(?:\\.|[^\s();"])+|"(?:\\.|[^"])+")|;.*?\n|\s+', s)
    def next():
        while True:
            t = i.next().group(1)
	    if t: return t
    def readlist():
        global position
	t = next()
        if t == ')':
	    position = i.next().end()
	    return None
	return [read(t), readlist()]
    def read(t):
        if t == '(': return readlist()
        if t == ')': raise SyntaxError        
	return t
    return read(next())

# print(read("(this ;comment\n is) (1 (a test (sentences) (des()) (yo)))"))

# main

position=0
absolutposition=0
tmplist=[]

if __name__ == "__main__": 
 
    with open(sys.argv[1], "r+") as f:
        map = mmap.mmap(f.fileno(), 0)

    while True:
        
	print map.tell()
	i=map.read(10).split(' ',1)[0].split('(',1)[1]
	print 'Prefix:', i

        if i[0]=='0':
           tmplist = readascii(map[absolutposition:])
	   print 'Kommentar', tmplist
        else:
            try:
                int(i[0])
                print 'unbekannter Prefix: ',i
		readascii(map[absolutposition:])
		# print tmplist
            except ValueError:
	        pass

# mmap-Objekt weitergehen
        absolutposition = absolutposition + position
	print 'Verschiebe um', position, 'auf Pos:', absolutposition
	map.seek(absolutposition,0)

Und folgende Testdatei:

Code: Alles auswählen

(0 "Ein Kommentar")

(0 "noch einer")
(4 (60 0 0 1 2 4 4 4 8 4 4))

(0 "aha:")
(2 3)

(0 "obwohl")

Das Ganze erkennt die doppelte schließende Klammer am Ende von Zeile 4 nicht und ich weiss nicht wieso. Wenn man zwischen den beiden Klammern ein Leerzeichen einbaut, dann läuft es...
Außerdem gefällt mir meine bisherige Lösung zum Zählen der Position und dem Verschieben des Zeigers nicht so richtig, v.a. das "global" ist natürlich unschön.

Grüße Bastian

[sma]

Cons-Zellen sind seit 50 Jahren der traditionelle Weg, S-Expressions zu repräsentieren. Da kenne ich einfach den Algorithmus auswendig. Mit Listen geht es natürlich auch. Ich habe außerdem eingebaut, dass " entfernt und \ ersetzt wird:

Code: Alles auswählen

import re

def read(s): 
    i = re.finditer(r'([()]|(?:\\.|[^\s();"])+|"(?:\\.|[^"])+")|;.*?\n|\s+', s) 
    def next(): 
        while True: 
            t = i.__next__().group(1)
            if t: 
                if t[0] == '"': t = t[1:-1]
                return re.sub(r'\\(.)', '\\1', t)
    def readlist(l): 
        t = next() 
        if t == ')': return l
        l.append(read(t))
        return readlist(l)
    def read(t): 
        if t == '(': return readlist([]) 
        if t == ')': raise SyntaxError 
        return t 
    return read(next()) 

print(read('(this ;comment\n is ("a test" (sentences) (des\\(\\)) (yo)))'))

Stefan

[BastiL]

Cons-Zellen sind seit 50 Jahren der traditionelle Weg, S-Expressions zu repräsentieren. Da kenne ich einfach den Algorithmus auswendig. Mit Listen geht es natürlich auch. Ich habe außerdem eingebaut, dass " entfernt und \ ersetzt wird:

Danke. Das lässt sich wirklich gut an mit deinem Vorschlag. Ich werde die Änderungen aktualisieren.
Hast Du eine Idee, wieso in meinem ersten Konzept (s.o.) am Ende von Zeile vier die doppelte schließende Klammer nicht erkannt wird? Danke.

Grüße Bastian

[BastiL]

Danke Stefan,

ich habe das eingebaut. Mein Programm sieht jetzt so aus:

Code: Alles auswählen

#! /opt/bin/python

import re, sys, mmap, os 

def readascii(s):
    i = re.finditer(r'([()]|(?:\\.|[^\s();"])+|"(?:\\.|[^"])+")|;.*?\n|\s+', s)
    def next():
        while True:
            t = i.next().group(1)
	    print t
            if t:
                if t[0] == '"': t = t[1:-1]
                return re.sub(r'\\(.)', '\\1', t)
    def readlist(l):
        global position
        t = next()
        if t == ')':
	    position = i.next().end() 
	    return l
        l.append(read(t))
        return readlist(l)
    def read(t):
        if t == '(': return readlist([])
        if t == ')': raise SyntaxError
        return t
    return read(next())

# main

position=0
absolutposition=0
tmplist=[]
comments=[]

if __name__ == "__main__":
 
    f = open(sys.argv[1], "r+")
#    with open(sys.argv[1], "r+") as f:
    map = mmap.mmap(f.fileno(), 0)

    while True:
       
#        print map.tell()
	i=map.read(10).split(' ',1)[0].split('(',1)[1]
        print 'Prefix:', i

        if i[0]=='0':
            tmplist = readascii(map[absolutposition:])
	    comments.append(tmplist[1])
	    print comments
        else:
            try:
                int(i[0])
                print 'unbekannter Prefix: ',i
                tmp = readascii(map[absolutposition:])
		print tmp
        # print tmplist
            except ValueError:
                pass

        # auf dem mmap-Objekt weitergehen
        absolutposition = absolutposition + position
        print 'Verschiebe um', position, 'auf Pos:', absolutposition
        map.seek(absolutposition,0)

Wenn ich die Testdatei von oben verwende, dann läuft es immer noch nicht über Zeile vier hinaus, weil die doppelte schließende Klammer dort nicht erkannt wird (ist an der debugging-Ausgabe zu sehen). Wenn ich ein Leerzeichen zwischen die beiden schließenden Klammern baue, dann läuft es. Warum?
Änderung gegenüber deinem Vorschlag: Zusätzlicher Zeichenzähler. Ich weiss um die Endlosschleife.

Danke und Gruß

Bastian

[sma]

Ich würde sagen, dass `position = i.next().end()` (Zeile 18) ist falsch, denn das verschluckt das nächste Zeichen. Warum `end`? Wäre nicht `start` besser?

Stefan

[BastiL]

Ich würde sagen, dass `position = i.next().end()` (Zeile 18) ist falsch, denn das verschluckt das nächste Zeichen. Warum `end`? Wäre nicht `start` besser?

Danke Stefan. Dein Einwand macht Sinn. Allerdings bleibt das Problem bestehen, nachdem ich es geändert habe.
Deine Basis-Variante funktioniert. Sobald ich die Zeichenzählung einbringe. wird die doppelte schließende Klamme rnicht mehr erkannt...Könnte ich die Zeichen irgendwie anders zählen?