Parser Combinators

Posted on June 26, 2018 by bierpilot

Eher durch Zufall bin ich letztens auf einen auch sehr interessanten Ansatz für einen Parsing Algorithmus gekommen, der mal so gar nichts mit dem was ich bisher so gemacht habe zu tun hat: Parser Combinators.

Die Idee dahinter: Man definiert Anstatt einer Grammatik mehrere, ineinander verschachtelte Mini-Parser, wobei ein Parser entweder ein Zeichen absorbiert (LIT, CCL) oder aber mehrere Parser entsprechend so Kombiniert, das man damit Alternativen (OR), Sequenzen (AND, SEQ) und semantische Operationen (JOIN) umsetzen kann. Der Aufruf der Funktionen definiert dann also die syntaktikalische Struktur, und es werden entsprechende Ergebnisse zurückgeliefert.

Sehr schön ist das ganze z.B. hier von Daniel Holden erklärt. Auf Basis dieses Blog-Eintrags habe ich mal einen Ansatz für eine Parser Combinator Library in Python in unter 100 Zeilen programmiert.

#-*- coding: utf-8 -*-
# Python Parser Combinators

def LIT(c):
	return lambda s: (c, s[len(c):]) if s.startswith(c) else None

def CCL(r):
	return lambda s: (s[0], s[1:]) if s[0] in r else None

def OR(a, b):
	return lambda s: a(s) or b(s) or None

def AND(a, b):
	def fn(a, b, s):
		res1 = a(s)
		if res1 is None:
			return None

		res2 = b(res1[1])
		if res2 is None:
			return None

		return [res1[0], res2[0]], res2[1]

	return lambda s: fn(a, b, s)

def SEQ(*args):
	assert len(args) > 0

	def fn(pl, s):
		ret = []
		for p in pl:
			res = p(s)
			if res is None:
				return None

			ret.append(res[0])
			s = res[1]

		return ret, s

	return lambda s: fn(args, s)

def POS(p):
	def fn(p, s):
		ret = []

		while s:
			res = p(s)
			if res is None:
				break

			ret.append(res[0])
			s = res[1]

		if not ret:
			return None

		return ret, s

	return lambda s: fn(p, s)

def JOIN(p):
	def fn(p, s):
		res = p(s)
		if res is None:
			return None

		return "".join(res[0]), res[1]

	return lambda s: fn(p, s)

par = {}

def CALL(n):
	global par
	return lambda s: par[n](s)

def SYM(n, p):
	global par
	par[n] = p
	return p

num = SYM("num", JOIN(POS(CCL("0123456789"))))
factor = SYM("factor", OR(num, SEQ(LIT("("), CALL("expr"), LIT(")"))))
term = SYM("term", OR(SEQ(factor, LIT("*"), CALL("term")), factor))
expr = SYM("expr", OR(SEQ(term, LIT("+"), CALL("expr")), term))

s = "1337+42*23+5"
print("> %s" % s)

while True:
	s = s or raw_input("> ")
	if not s:
		break

	r = expr(s)
	print("< %r" % r[0] if r else "(parse error)")
	s = None

#-*- coding: utf-8 -*-

# Python Parser Combinators

def LIT(c):

return lambda s: (c, s[len(c):]) if s.startswith(c) else None

def CCL(r):

return lambda s: (s[0], s[1:]) if s[0] in r else None

def OR(a, b):

return lambda s: a(s) or b(s) or None

def AND(a, b):

def fn(a, b, s):

res1 = a(s)

if res1 is None:

return None

res2 = b(res1[1])

if res2 is None:

return None

return [res1[0], res2[0]], res2[1]

return lambda s: fn(a, b, s)

def SEQ(*args):

assert len(args) > 0

def fn(pl, s):

ret = []

for p in pl:

res = p(s)

if res is None:

return None

ret.append(res[0])

s = res[1]

return ret, s

return lambda s: fn(args, s)

def POS(p):

def fn(p, s):

ret = []

while s:

res = p(s)

if res is None:

break

ret.append(res[0])

s = res[1]

if not ret:

return None

return ret, s

return lambda s: fn(p, s)

def JOIN(p):

def fn(p, s):

res = p(s)

if res is None:

return None

return "".join(res[0]), res[1]

return lambda s: fn(p, s)

par = {}

def CALL(n):

global par

return lambda s: par[n](s)

def SYM(n, p):

global par

par[n] = p

return p

num = SYM("num", JOIN(POS(CCL("0123456789"))))

factor = SYM("factor", OR(num, SEQ(LIT("("), CALL("expr"), LIT(")"))))

term = SYM("term", OR(SEQ(factor, LIT("*"), CALL("term")), factor))

expr = SYM("expr", OR(SEQ(term, LIT("+"), CALL("expr")), term))

s = "1337+42*23+5"

print("> %s" % s)

while True:

s = s or raw_input("> ")

if not s:

break

r = expr(s)

print("< %r" % r[0] if r else "(parse error)")

s = None

Es ist verblüffend: Man erhält bereits aus der Eingabe 1337+42*23+5 die Ausgabe
[‘1337’, ‘+’, [[’42’, ‘*’, ’23’], ‘+’, ‘5’]], was ja quasi schon einem Syntaxbaum entspricht.

Daniel hat auch die C-Library mpc (Micro Parser Combinators) geschrieben, welche das ganze für C umsetzt. Und da wären wir schon wieder beim nächsten Problem: Die Sache ist eigentlich so elegant, das ich mir wieder die Frage stelle, ob die ganze Arbeit die ich bisher in die Phorward Library gesteckt habe es überhaupt noch Wert ist… oder ob man vielleicht sich einfach aus Spaß lieber damit beschäftigen sollte. Ernstaft nutzen würde es sowieso keiner, das musste ich ja schon inzwischen mehrfach schmerzlich feststellen. Aber naja, vielleicht muss man sich dabei einfach mal von dem Gedanken trennen, mit sowas erfolgreich zu sein… oder was heißt erfolgreich sein, es hat Spaß gemacht das zu programmieren, aber wenn es keiner nutzt und es eigentlich gar keinen Nutzen hat ausser das es einfach da ist und nicht genutzt wird, das ist irgendwie extrem demotivierend und ärgerlich.

Es gibt natürlich auch Paper dazu, wie man Parser Combinators sogar generalisiert hinbekommt. Also sozusagen das, was ich bereits mit GLR parsing mal im Ansatz versucht hatte zu verstehen (und kläglich gescheitert bin), nur eben genau anders herum (GLL).

Vielversprechende Papers dazu:

Denn wie auch Fefe in seinem Blog letztens schrieb, und was auch auf mich persönlich sehr stark zutrifft, und ich mit libphorward, UniCC, JS/CC, pynetree und min_lalr1 inzwischen eigentlich bis zur Gänze ausgereizt haben sollte:

Ich habe meine libc auch nicht geschrieben, damit ich eine libc habe (obwohl das ein schöner Seiteneffekt ist). Ich habe die geschrieben, damit ich das Problemumfeld verstanden habe. Und das habe ich jetzt. Genau so mit dem Webserver und dem LDAP-Server. Du merkst, ob du etwas verstanden hast, wenn du es jemand anderem erklären konntest. Und Programmieren ist ja am Ende wie jemand anderem was erklären, nur dass derjenige sehr maschinenlesbare Erklärungen braucht. 🙂

Ich treffe immer wieder Leute, die denken, man programmiert Open Source-Software, um Teil einer Community zu sein. Oder um am Ende die Software zu haben. Nein. Du programmierst, damit du am Ende das Problem verstanden hast.

Ich habe in meiner Karriere ein-zwei Mal Quellcode bei Plattenausfällen oder versehentlichem Löschen verloren. Das fühlt sich an wie eine Katastrophe, ist es aber nicht. Wenn du für die erste Version ein Jahr brauchtest, geht das nochmal hinschreiben in 1-2 Monaten. Denn diesmal hast du ja das Problemfeld verstanden. DAS ist die eigentliche Währung im Leben. Problemfelder verstanden haben.

Na denn… vielleicht auf zu neuen Ufern, und den Kram nun mal hinter sich lassen?

libphorward 0.22

Posted on April 5, 2018 by bierpilot

Langsam, aber stetig tut sich etwas bei meiner hobbymäßig weiterentwickelten C library libphorward, die auch als Phorward Toolkit, Phorward Foundation Libraries oder inzwischen auch einfach nur noch als The Phorward library bezeichnet wird.

Irgendwie scheine ich ein wenig mehr Disziplin dort hinein bekommen zu haben. Das liegt zum Teil daran, dass sich etwas bei UniCC getan hat, aber auch weil die Library inzwischen eine feste Basis hat, die nur noch geringfügig geändert und erweitert, aber nicht mehr komplett verworfen oder bereinigt wird. Leider ist immernoch nicht ganz genau klar, was der exakte Zweck der Library oder des Toolkits nun wirklich sein soll. In der Dokumentation dazu steht inzwischen folgender Abschnitt unter dem Titel “Intention behind this library”:

The cornerstone for this library was laid in 2006 during some experimenting with several algorithms and their implementation. It rapidly turned out to become a general purpose library serving as the base toolchain for several, mostly unfinished software projects which had their origin at J.M.K S.F. Software Technologies, which was later renamed to Phorward Software Technologies.

The library was then released to the public in 2011, together with the open source parser generator UniCC. Since then, it was gradually extended to newer and more enhanced features, mostly on tools relating to parser and compiler construction, but also features already known from other projects and remastered in a more generic and powerful way.

The final destination of the Phorward library is not entirely clear yet. For now, it mostly serves as a kind of playground for different projections, but it is also used by the UniCC parser generator and the meanwhile discontinued RapidBATCH scripting language as its foundation library.

Aber die Version 0.22 formiert sich langsam, und hat einige Neuerungen zu bieten, wie man dem Changelog detailliert entnehmen kann…

Phorward BNF

Das Endprodukt der zahlreichen Überarbeitungen in der Parsing Library, die bereits 2012 innerhalb der libphorward begonnen wurde, ist nun wieder ein neue Grammatik-Beschreibungssprache, die nun den offiziellen Namen PBNF trägt. Diese ähnelt der von pynetree und bis libphorward v0.21 verwendeten BNF-Sprache, hat aber eine deutlich vereinfachte Syntax, die auch UniCCv2 verwenden können soll.

Hier das vielfach verwendete 4-function-calculator Beispiel:

%skip   /[\s]+/ ;
Int     := /[0-9]+/ ;

factor  : Int
        | '(' expr ')'
        ;

term    : term '*' factor = mul
        | term '/' factor = div
        | factor
        ;

expr$   : expr '+' term = add
        | expr '-' term = sub
        | term
        ;

%skip /[\s]+/ ;

Int := /[0-9]+/ ;

factor : Int

| '(' expr ')'

;

term : term '*' factor = mul

| term '/' factor = div

| factor

;

expr$ : expr '+' term = add

| expr '-' term = sub

| term

;

AST-Knoten werden jetzt mit dem = oder := Operatoren definiert.

Command-line tools

Die command-line tools pregex, plex und pparse sind jetzt einheitlich und flexibel nutzbar:

$ pregex -a find "\d+|[a-z]+" "123 abc456    78xy9"
123
abc
456
78
xy
9
$ plex -b ":" -e "\n" -i "123 abc456    78xy9" "\d+" "[a-z]+"
1:123
2:abc
1:456
1:78
2:xy
1:9
$ pparse "test := test \"Hallo\" | ;" "Hallo Hallo Hallo Hallo"
test
 test
  test
   test
    test
    Hallo (Hallo)
   Hallo (Hallo)
  Hallo (Hallo)
 Hallo (Hallo)
neo@falcon ~/Phorward/src/phorward $

$ pregex -a find "\d+|[a-z]+" "123 abc456 78xy9"

123

abc

456

$ plex -b ":" -e "\n" -i "123 abc456 78xy9" "\d+" "[a-z]+"

1:123

2:abc

1:456

1:78

2:xy

1:9

$ pparse "test := test \"Hallo\" | ;" "Hallo Hallo Hallo Hallo"

test

Hallo (Hallo)

neo@falcon ~/Phorward/src/phorward $

Und dann ist auch noch die Doku verbessert worden. Ich denke in Kürze ist es soweit, das v0.22 offiziell released wird, und es geht mit v0.23 weiter… bis hoffentlich bald, v1.0?

GLR parsing

Posted on February 21, 2018 by bierpilot

Update 24.02.2018: Das was ich hier vorher geschrieben hatte war totaler Murks. Jetzt wälze ich erstmal nochmal die Paper dazu und dann sollte ich das nochmal ganz neu aufrollen…

So mal wieder nach längerer Zeit ein neues Posting hier. Muss mal wieder ein paar Gedanken sammeln. Beschäftige mich seit ca. zwei Wochen nun endlich mal mit GLR Parsern, obwohl ich in dem Buch Parsing Techniques von Grune und Jacobs, welches ich schon seit einiger Zeit sporadisch wälze, noch gar nicht in dem Kapitel angekommen bin (zzt. Kapitel 7.2 auf Seite 210, von ca. 640 Seiten). Aber das Parse-Verfahren habe ich mir schon mehrfach angeschaut, es aber nie wirklich umgesetzt.

Aber für die Umsetzung erstmal ein wenig Forschung betrieben…

…und einen (eigenen!) Algorithmus aufgebaut…

-- Grammar --

seq : seq Ident | Ident
def : Ident ':' seq
defs : defs def | def
bingo$: defs

-- State 0 --
Kernel (1):
        bingo : . defs
Epsilon (0):
        (empty)

 -> Shift on 'Ident', goto state 3
 -> Goto state 1 on 'defs'
 -> Goto state 2 on 'def'

-- State 1 --
Kernel (2):
        bingo : defs .   { >&eof< }
        defs : defs . def
Epsilon (0):
        (empty)

 -> Shift on 'Ident', goto state 3
 <- Reduce on '&eof' by production 'bingo : defs'
 -> Goto state 4 on 'def'

-- State 2 --
Kernel (1):
        defs : def .   { >&eof< >Ident< }
Epsilon (0):
        (empty)

 <- Reduce on '&eof' by production 'defs : def'
 <- Reduce on 'Ident' by production 'defs : def'

-- State 3 --
Kernel (1):
        def : Ident . : seq
Epsilon (0):
        (empty)

 -> Shift on ':', goto state 5

-- State 4 --
Kernel (1):
        defs : defs def .   { >&eof< >Ident< }
Epsilon (0):
        (empty)

 <- Reduce on '&eof' by production 'defs : defs def'
 <- Reduce on 'Ident' by production 'defs : defs def'

-- State 5 --
Kernel (1):
        def : Ident : . seq
Epsilon (0):
        (empty)

 -> Shift on 'Ident', goto state 7
 -> Goto state 6 on 'seq'

-- State 6 --
Kernel (2):
        def : Ident : seq .   { >&eof< >Ident< }
        seq : seq . Ident
Epsilon (0):
        (empty)

 -> Shift on 'Ident', goto state 8
 <- Reduce on '&eof' by production 'def : Ident : seq'
 <- Reduce on 'Ident' by production 'def : Ident : seq'

-- State 7 --
Kernel (1):
        seq : Ident .   { >&eof< >Ident< }
Epsilon (0):
        (empty)

 <- Reduce on '&eof' by production 'seq : Ident'
 <- Reduce on 'Ident' by production 'seq : Ident'

-- State 8 --
Kernel (1):
        seq : seq Ident .   { >&eof< >Ident< }
Epsilon (0):
        (empty)

 <- Reduce on '&eof' by production 'seq : seq Ident'
 <- Reduce on 'Ident' by production 'seq : seq Ident'

-- Grammar --

seq : seq Ident | Ident

def : Ident ':' seq

defs : defs def | def

bingo$: defs

-- State 0 --

Kernel (1):

bingo : . defs

Epsilon (0):

(empty)

-> Shift on 'Ident', goto state 3

-> Goto state 1 on 'defs'

-> Goto state 2 on 'def'

-- State 1 --

Kernel (2):

bingo : defs . { >&eof< }

defs : defs . def

Epsilon (0):

(empty)

-> Shift on 'Ident', goto state 3

<- Reduce on '&eof' by production 'bingo : defs'

-> Goto state 4 on 'def'

-- State 2 --

Kernel (1):

defs : def . { >&eof< >Ident< }

Epsilon (0):

(empty)

<- Reduce on '&eof' by production 'defs : def'

<- Reduce on 'Ident' by production 'defs : def'

-- State 3 --

Kernel (1):

def : Ident . : seq

Epsilon (0):

(empty)

-> Shift on ':', goto state 5

-- State 4 --

Kernel (1):

defs : defs def . { >&eof< >Ident< }

Epsilon (0):

(empty)

<- Reduce on '&eof' by production 'defs : defs def'

<- Reduce on 'Ident' by production 'defs : defs def'

-- State 5 --

Kernel (1):

def : Ident : . seq

Epsilon (0):

(empty)

-> Shift on 'Ident', goto state 7

-> Goto state 6 on 'seq'

-- State 6 --

Kernel (2):

def : Ident : seq . { >&eof< >Ident< }

seq : seq . Ident

Epsilon (0):

(empty)

-> Shift on 'Ident', goto state 8

<- Reduce on '&eof' by production 'def : Ident : seq'

<- Reduce on 'Ident' by production 'def : Ident : seq'

-- State 7 --

Kernel (1):

seq : Ident . { >&eof< >Ident< }

Epsilon (0):

(empty)

<- Reduce on '&eof' by production 'seq : Ident'

<- Reduce on 'Ident' by production 'seq : Ident'

-- State 8 --

Kernel (1):

seq : seq Ident . { >&eof< >Ident< }

Epsilon (0):

(empty)

<- Reduce on '&eof' by production 'seq : seq Ident'

<- Reduce on 'Ident' by production 'seq : seq Ident'

…der auch direkt unter Verwendung eines Graph-structured Stack arbeitet. Ich finde bei diesen Informatikbüchern ja immer interessant, dass manche Sache sehr theoretisch behandelt werden. Da wird dann einfach mal der komplette Parse-Stack kopiert und nach einem missglückten Shift dann komplett verworfen. Naja, wenn man das ganze implementieren will, noch dazu in einer Programmiersprache ohne Garbage Collection, dann kopiert man sicherlich nicht erstmal alle Element eines dynamisch allokierten Stacks und deren dynamsiche Stack-Elemente, um diese dann einen Shift später wieder frei zu geben. Mega-Ineffizient.

Naja, und nachdem ich zuerst dachte, es könnte auch klappen, wenn man den Lookahead global hält, wurde ich eines besseren belehrt, denn das geht (rein logisch gesehen) nicht. Es scheint aber so ungefähr zu funktionieren, wie hier, nur das da momentan noch das Stack merging fehlt (zusammenführen mehrerer Stack-Stränge bei einem gemeinsamen Shift). Dazu muss ich aber erstmal noch ein bisschen forschen und testen.

Was es jetzt noch zu lösen gilt (und wo warscheinlich die meiste arbeit drin steckt):

Einen eindeutigen (den besten?) Syntaxbaum aus den (bei ambigen Grammatiken dann mehrpfadigen) Parse-Graphen erzeugen
Effiziente Garbage Collection
Lookahead-Caching bzw. geht das nicht doch mit einem Lookahead?

Bin mal gespannt…

Parsergeneratoren – Dilemma?

Posted on December 1, 2017 by bierpilot

Ja…wohin nun?

Da haben wir den Salat! Einmal den UniCC gepuschelt, schon fragt man sich, warum man den ganzen aufwand der letzten Jahre getrieben hat, einen Parser Generator (und zwar exakt denselben Algorithmus) in die libphorward einzubauen.

Und dann stellt man auch wieder fest, das gewisse Java-Werkzeuge aus dem Bereich (okay, in dem Fall ALL(*)) noch besser sind… ach kein Plan.

RapidBATCH 6

Posted on October 8, 2017 by bierpilot

Wenn man nach diesem Posting aus 2014 geht wäre es viel lieber schon viel früher so gekommen. Wie dem auch sei: RapidBATCH ist jetzt frei!

Ich habe aus einem altem Backup und mit den aktuellen Tools, der libphorward und UniCC, die unfertigen Sourcen von RapidBATCH 6 portiert und halbwegs zum laufen bekommen.

Hier das offiziellen RapidBATCH open source project: https://github.com/phorward/rapidbatch

Zumindest funktioniert ein Großteil der damaligen Testfiles. Mir ist dabei aufgefallen, dass ich damals die drei Module von RapidBATCH, also Compiler, Virtual Machine und den eigentlichen Funktionsumfang, so dermaßen auseindergerupft hatte, weil ich dachte “je modularer desto besser” und auch weil es mal Pläne gab, RapidBATCH als Domain-specific Language zu vermarkten ohne die Sourcen freizugeben 😀 naja fail, leider alles verbockte Scheiße.

Egal, irgendwie muss es ja weitergehen, vielleicht nun auch so.

Ach ja ich bin jetzt Open Source mäßig bei GitHub, wohne mit meiner Freundin zusammen und bin umgezogen. Jo. Das wars auch schon…

Softwaremuseum

Posted on October 12, 2016 by bierpilot

Neben der aktuellen Software auch allerhand lustige Projekte aus den guten alten Zeiten von 2000 bis etwa 2006 findet man jetzt im “Museum” von Phorward Software:

http://phorward-software.com/download/

A step Phorward.

Posted on September 6, 2016 by bierpilot

Manchmal ist es so, dass man Dinge mal einige Zeit zur Seite legt, bevor man damit wieder weitermacht. Letzte Woche war es bei mir wieder mal soweit, die etwas angestaubten Spielsachen der alten Zeit wieder rauszukramen… meine private Software ;). Da ist ja wirklich viel passiert die letzten, ja man kann sagen 10 Jahre, und dennoch gab es nicht wirklich was neues.

Und doch, es macht mir immernoch Spaß. Zumindest es in einer gewissen Weise auch zu einem Ende zu bringen oder sich vielleicht auch von manchen Dingen zu trennen, an denen man sehr lange festgehalten hat, wo man aber letztendlich keine weitere Zeit mehr reinstecken möchte oder auch sollte.

Jedenfalls hat meine Website phorward-software.com ein Update erfahren… es gibt jetzt dort einen aktualisierten Projekte-Bereich für die Projekte phorward, pynetree, JS/CC und UniCC.

Vor allem an phorward (libphorward, bzw. das Phorward Toolkit) habe ich immernoch Bock weiterzumachen, da es für mich die einzige Möglichkeit ist, weiterhin was in C zu coden und diese Library wirklich alle Themen abdeckt, die ich persönlich super interessant finde. Die libphorward ist ja quasi mein eigenes Steckenpferd einer libmega (Insider wissen, was gemeint ist!) die richtig geile C-Funktionen bereithält (plist, pstack, pstr), und noch dazu add-ons für reguläre Ausdrücke (pregex), Lexing (plex), Parsing (pparse) und sogar virtuelle Maschinen (pvm) bereitstellt. Ursprünglicher Zweck dahinter war es immernoch, einmal ein RapidBATCH damit neu zu entwickeln. Das steht aber weiterhin noch in den Sternen.
pynetree ist ja das im letzten Jahr gestartete Projekt einer Python-Parser-Bibliothek mit linksrekursiven Grammatiken, die durch einen Top-Down-Packrat-Parser geparst werden, und sich gemeinsam mit phorward eine eigene TBNF-Sprache teilt. Hier wird auf jeden Fall noch weitergemacht!
JS/CC, der JavaScript-Compiler-Compiler, den ich bereits 2007 veröffentlich habe, hat neue Freunde gefunden. Er wird von mir nicht mehr weiterentwickelt oder verfolgt, scheint aber durch die Programmierer Andrew Brobston und Sergiy Shatunov eine gelungende Anbindung an Node.JS gefunden zu haben und wird in einem ganz anderen Rahmen als ursprünglich gedacht weiterentwickelt. Finde ich aber gut, immerhin ein Open Source Projekt welches von Menschen gebraucht, genutzt und sogar Weiterentwickelt wird. JS/CC wird jetzt unter jscc.brobston.com, respektive bei GitHub unter https://github.com/abrobston/jscc weiterentwickelt.
UniCC, das eigentlich als “universeller Parser Generator” gedachte Vorzeigeprojekt von mir vor inzwischen auch schon wieder 4 Jahren wird jetzt mehr oder minder eingestampft. Es erfolgt jetzt noch einmal ein Update des Benutzerhandbuchs sowie eine komplette Neu-Lizenzierung der Software unter der BSD-Lizenz, dann wird sie freigelassen. Immerhin: Der UniCC compiliert nach wie vor mit der aktuellsten libphorward, die als Unterbau fungiert. Einziger mir bekannter Einsatz dieses Tools ist das Projekt impact bei MEGA, dessen gesamte Formelsprache in UniCC entwickelt worden ist, und immerhin sogar auf 8 verschiedenen Architekturen läuft.

Alles in allem Plane ich auch, die Webseite unter phorward.info nochmal neu aufzusetzen, warscheinlich als ViUR Projekt und auch mehr mit dem Open Source Hintergedanken. Sozusagen als “mein Software Blog”, ohne es weiterhin auf dieser kommerziellen Schiene, auf der Phorward Software ja ursprünglich aufbaute, zu fahren. Da ist nämlich nichts mehr.

pynetree

Aside

pyParse musste ich nochmal kurzerhand umbenennen, weil es ein Projekt Namens pyParse schon gibt… ist mir nicht aufgefallen, weil SCHEISS GOOGLE einem ja immer verbessern muss, und deshalb andere Begriffe gefunden hat.

Der neue Name des Projektes lautet jetzt pynetree. Zum einen weil Pinien sehr schöne Bäume sind und einen tollen AST abgeben, zum anderen der Pythonbezug – Passt!

https://bitbucket.org/codepilot/pynetree/overview

pyParse (bzw. jetzt pynetree)

Posted on November 15, 2015 by bierpilot

Es gibt wieder was neues aus der Welt des Compilerbaus von mir:

Nachdem ich mir mal letzte Woche das Paper Packrat Parsers Can Support Left Recursion [Warth, Douglass, Millstein] durchgelesen hatte und den dort gezeigten Algorithmus implementierte, fiel der Groschen: Linksrekursive Grammatiken lassen sich nun DOCH mit einem Nicht-LR-Parser parsen! Also das, wonach ich die ganze Zeit gesucht hatte… oft war ich nah dran, aber es hat dann doch nicht gereicht oder anderweitige Probleme aufgezeigt, die das “proof of concept” nicht werden lassen wollten. Die Lösung ist nun ein modifizierter Packrat-Parser! So ungefährt muss es auch mein lieber Martin Stoilov mit seinem rpatk gelöst haben.

Da ich mir erst nicht so ganz sicher war, ob mein Ansatz jetzt wirklich funktioniert, musste ich zuerst noch ein paar Tests durchführen bzw. es etwas voranbringen… die waren aber diesmal wirklich erfolgreich! Man kann damit arbeiten wie mit einer Grammatik für einen LR-Parser. Einzig und allein die Reihenfolge der Produktionen ist hier zu beachten, was bei einem LR-Parser (wie z.B. libphorward) nicht der Fall ist.

Habe das ganze mal in Python ausprogrammiert und inzwischen schon zu einem kleinen Open Source Projekt gemacht, welches auf den Namen ~~pyParse~~ pynetree hört, und unter der MIT-Lizenz steht.

https://bitbucket.org/codepilot/pynetree/src

#-*- coding: utf-8 -*-
from pyparse import Parser

g = {
	"factor": ["INT", "( expr )"],
	"mul": "term * factor",
	"div": "term / factor",
	"term": ["mul", "div", "factor"],
	"add": "expr + term",
	"sub": "expr - term",
	"expr": ["add", "sub", "term"],
	"calc": "expr"
}

p = Parser(g, "calc")
p.addToken("INT", r"\d+")

p.addAction("INT")
p.addAction("mul")
p.addAction("div")
p.addAction("add")
p.addAction("sub")
p.addAction("calc")

p.dump(p.parse("1 + 2 * ( 3 + 4 ) * 5 - 6 / 7"))

#-*- coding: utf-8 -*-

from pyparse import Parser

g = {

"factor": ["INT", "( expr )"],

"mul": "term * factor",

"div": "term / factor",

"term": ["mul", "div", "factor"],

"add": "expr + term",

"sub": "expr - term",

"expr": ["add", "sub", "term"],

"calc": "expr"

}

p = Parser(g, "calc")

p.addToken("INT", r"\d+")

p.addAction("INT")

p.addAction("mul")

p.addAction("div")

p.addAction("add")

p.addAction("sub")

p.addAction("calc")

p.dump(p.parse("1 + 2 * ( 3 + 4 ) * 5 - 6 / 7"))

und gibt

calc
  sub
    add
      INT (1)
      mul
        mul
          INT (2)
          add
            INT (3)
            INT (4)
        INT (5)
    div
      INT (6)
      INT (7)

calc

sub

add

INT (1)

mul

INT (2)

add

INT (3)

INT (4)

INT (5)

div

INT (6)

INT (7)

aus.

pyparse kann inzwischen sogar eine BNF-Grammatik ähnlich der libphorward interpretieren (selbstverständlich ist der Parser dafür in pyParse entwickelt!)

#-*- coding: utf-8 -*-
from pyparse import Parser

p = Parser("$INT /\\d+/ %emit;"
		   "f: INT | '(' e ')';"
		   "mul %emit: t '*' f;"
		   "div %emit: t '/' f;"
		   "t: mul | div | f;"
		   "add %emit: e '+' t;"
		   "sub %emit: e '-' t;"
		   "e %goal: add | sub | t;")

p.dump(p.parse("123+456*789"))

#-*- coding: utf-8 -*-

from pyparse import Parser

p = Parser("$INT /\\d+/ %emit;"

"f: INT | '(' e ')';"

"mul %emit: t '*' f;"

"div %emit: t '/' f;"

"t: mul | div | f;"

"add %emit: e '+' t;"

"sub %emit: e '-' t;"

"e %goal: add | sub | t;")

p.dump(p.parse("123+456*789"))

pyParse wird wohl dann als erstes mal in ViUR eingebaut… GEIL! 😀

Schadenfroyde

Posted on September 1, 2015 by bierpilot

Ihr werdet fallen… genau so tief und bodenlos, wie euer Niveau und eure Frechheit.

BEGIN	{
			pilots["feifffe"] = 118
			pilots["feiffe"] = 118
			pilots["lessenk"] = 57
			pilots["rünen"] = 533
			pilots["hlenbrock"] = 553
			pilots["ubry"] = 399
			pilots["ilhard"] = 486
			pilots["reudenr"] = 489
			pilots["eisterj"] = 549
			pilots["eyer"] = 28
			pilots["ierig"] = 529
			pilots["rbecke"] = 410
			pilots["ies"] = 268
			pilots["einert"] = 365
			pilots["elmer"] = 522
			pilots["ampus"] = 65

			aircraft["D-7393"] = 21
			aircraft["D-8984"] = 5
			aircraft["D-6235"] = 19
			aircraft["D-8883"] = 95
			aircraft["D-0962"] = 100

			utypes["N"] = 1
			utypes["S"] = 2

			sequipment["W"] = 104
			sequipment["F"] = 105
			have_start = 0
		}

END		{
			generate()

			#for( i in times )
			#	print i " " counts[i] " " mintohhmm(times[i])

		}


/[0-9]+\.[0-9]+\.[0-9]+/	{
						if( $0 ~ /Im Zeitraum/ )
							next

						datum = trim($0)
					}

/[0-9]+:[0-9]+-[0-9]+:[0-9]+/ {
						generate()

						line = trim($0)
						if( line ~ /^[0-9]+:[0-9]+-[0-9]+:[0-9]+/ )
						{
							split(line, vonbis, /-| |\t/)
							von = vonbis[1]
							bis = vonbis[2]
						}

						if( $4 == "W" )
							startart = "W"
						else if( $4 == "F" )
							startart = "F"
						
						if( $5 == "S" )
							flugart = "S"
						else if( $5 == "N" )
							flugart = "N"

						for( i in aircraft )
						{
							if( $0 ~ i )
							{
								flugzeug = aircraft[i]
								kennz = i
								break
							}
						}

						if( flugzeug )
							have_start = 1
					}

/SRÜ/				{
						if( !bem )
							bem = "Seilrissübung"
					}

/SR/				{
						if( !bem )
							bem = "Seilriss"
					}

					{
						if( !have_start )
							next

						for( i in pilots )
						{
							if( $0 ~ i )
							{
								if( pilot )
								{
									if( pilot != pilots[i] )
									{
										passenger = pilots[i]
										passename = i
									}
								}
								else
								{
									pilot = pilots[i]
									pillename = i
								}
							}
						}
					}

function generate()
{
	if( datum && flugzeug )
	{
		if( !( kennz == "D-6235" || kennz == "D-8984" ) )
		{
			passenger = ""
			passename = ""
		}
		else if( passenger && ( pilot == 268 || pilot == 486 || pilot == 118) )
		{
			a = passenger
			aa = passename

			passenger = pilot
			passename = pillename

			pilot = a
			pillename = aa
		}

		if( pilot )
		{
			if( !startart )
				startart = "W"
			if( !flugart )
				flugart = "S"

			print "# " flugzeug " " kennz " " von " " bis " " \
					mintohhmm(mindiff(von,bis)) " " startart " " flugart " " \
						pilot " " passenger

			sql = "insert into usages ( takeoff_time, touchdown_time, " \
					"pilot_id, primary_equipment_id, passenger_id, payment_id,"\
					"takeoff_location_id, touchdown_location_id,"\
					"type_id, description, secondary_equipment_id ) values"

			sql = sql sprintf( \
					"('%s', '%s', %s, %s, %s, 1, 95, 95, %s, '%s', %s);", \
						sqltime(datum, von), sqltime(datum, bis), \
							pilot, flugzeug, passenger ? passenger : "NULL", \
								utypes[flugart], bem, sequipment[startart] )

			print sql

			#print "---"
			#print flugzeug  " " kennz
			#print von
			#print bis
			#print startart 
			#print flugart 
			#print pilot " " pillename
			#print passenger " " passename
			#print bem

			times[kennz] = times[kennz] + mindiff( von, bis )
			counts[kennz] = counts[kennz] + 1
		}
		else
			print "FICKEN!"
	}

	flugzeug = ""
	kennz = ""
	von = ""
	bis = ""
	startart = ""
	flugart = ""
	pilot = ""
	pillename = ""
	passenger = ""
	passename = ""
	bem = ""
	
	have_start = 0
}

function mindiff( von, bis )
{
	split(von, x, ":")
	h = x[1]
	m = x[2]

	split(bis, x, ":")
	hh = x[1]
	mm = x[2]

	diff = (hh * 60) - (h * 60) + (mm - m)
	return diff
}

function mintohhmm( min )
{
	h = int(min / 60)
	m = min % 60
	return sprintf( "%02d:%02d", h, m )
}

function sqltime( datum, zeit )
{
	split(zeit, x, ":")
	h = x[1]
	m = x[2]

	split(datum, x, ".")
	D = x[1]
	M = x[2]
	Y = x[3]

	return Y "-" M "-" D " " h ":" m ":00"
}

function ltrim( s )
{
    sub( /^[ \t\n]+/, "", s )
    return s
}

function rtrim( s )
{
    sub( /[ \t\n]+$/, "", s )
    return s
}

function trim( s )
{
    return rtrim(ltrim(s))
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

BEGIN {

pilots["feifffe"] = 118

pilots["feiffe"] = 118

pilots["lessenk"] = 57

pilots["rünen"] = 533

pilots["hlenbrock"] = 553

pilots["ubry"] = 399

pilots["ilhard"] = 486

pilots["reudenr"] = 489

pilots["eisterj"] = 549

pilots["eyer"] = 28

pilots["ierig"] = 529

pilots["rbecke"] = 410

pilots["ies"] = 268

pilots["einert"] = 365

pilots["elmer"] = 522

pilots["ampus"] = 65

aircraft["D-7393"] = 21

aircraft["D-8984"] = 5

aircraft["D-6235"] = 19

aircraft["D-8883"] = 95

aircraft["D-0962"] = 100

utypes["N"] = 1

utypes["S"] = 2

sequipment["W"] = 104

sequipment["F"] = 105

have_start = 0

}

END {

generate()

#for( i in times )

# print i " " counts[i] " " mintohhmm(times[i])

}

/[0-9]+\.[0-9]+\.[0-9]+/ {

if( $0 ~ /Im Zeitraum/ )

datum = trim($0)

}

/[0-9]+:[0-9]+-[0-9]+:[0-9]+/ {

generate()

line = trim($0)

if( line ~ /^[0-9]+:[0-9]+-[0-9]+:[0-9]+/ )

{

split(line, vonbis, /-| |\t/)

von = vonbis[1]

bis = vonbis[2]

}

if( $4 == "W" )

startart = "W"

else if( $4 == "F" )

startart = "F"

if( $5 == "S" )

flugart = "S"

else if( $5 == "N" )

flugart = "N"

for( i in aircraft )

{

if( $0 ~ i )

{

flugzeug = aircraft[i]

kennz = i

break

}

if( flugzeug )

have_start = 1

}

/SRÜ/ {

if( !bem )

bem = "Seilrissübung"

}

/SR/ {

if( !bem )

bem = "Seilriss"

}

{

if( !have_start )

for( i in pilots )

{

if( $0 ~ i )

{

if( pilot )

{

if( pilot != pilots[i] )

{

passenger = pilots[i]

passename = i

}

else

{

pilot = pilots[i]

pillename = i

}

function generate()

{

if( datum && flugzeug )

{

if( !( kennz == "D-6235" || kennz == "D-8984" ) )

{

passenger = ""

passename = ""

}

else if( passenger && ( pilot == 268 || pilot == 486 || pilot == 118) )

{

a = passenger

aa = passename

passenger = pilot

passename = pillename

pilot = a

pillename = aa

}

if( pilot )

{

if( !startart )

startart = "W"

if( !flugart )

flugart = "S"

print "# " flugzeug " " kennz " " von " " bis " " \

mintohhmm(mindiff(von,bis)) " " startart " " flugart " " \

pilot " " passenger

sql = "insert into usages ( takeoff_time, touchdown_time, " \

"pilot_id, primary_equipment_id, passenger_id, payment_id,"\

"takeoff_location_id, touchdown_location_id,"\

"type_id, description, secondary_equipment_id ) values"

sql = sql sprintf( \

"('%s', '%s', %s, %s, %s, 1, 95, 95, %s, '%s', %s);", \

sqltime(datum, von), sqltime(datum, bis), \

pilot, flugzeug, passenger ? passenger : "NULL", \

utypes[flugart], bem, sequipment[startart] )

print sql

#print "---"

#print flugzeug " " kennz

#print von

#print bis

#print startart

#print flugart

#print pilot " " pillename

#print passenger " " passename

#print bem

times[kennz] = times[kennz] + mindiff( von, bis )

counts[kennz] = counts[kennz] + 1

}

else

print "FICKEN!"

}

flugzeug = ""

kennz = ""

von = ""

bis = ""

startart = ""

flugart = ""

pilot = ""

pillename = ""

passenger = ""

passename = ""

bem = ""

have_start = 0

}

function mindiff( von, bis )

{

split(von, x, ":")

h = x[1]

m = x[2]

split(bis, x, ":")

hh = x[1]

mm = x[2]

diff = (hh * 60) - (h * 60) + (mm - m)

return diff

}

function mintohhmm( min )

{

h = int(min / 60)

m = min % 60

return sprintf( "%02d:%02d", h, m )

}

function sqltime( datum, zeit )

{

split(zeit, x, ":")

h = x[1]

m = x[2]

split(datum, x, ".")

D = x[1]

M = x[2]

Y = x[3]

return Y "-" M "-" D " " h ":" m ":00"

}

function ltrim( s )

{

sub( /^[ \t\n]+/, "", s )

return s

}

function rtrim( s )

{

sub( /[ \t\n]+$/, "", s )

return s

}

function trim( s )

{

return rtrim(ltrim(s))

}

Bierpiloten-Blog

Vom Fliegen, Coden und sonstigem Kram…

Category Archives: Coding / Programmieren

Parser Combinators

libphorward 0.22

Phorward BNF

Command-line tools

GLR parsing

Parsergeneratoren – Dilemma?

RapidBATCH 6

Softwaremuseum

A step Phorward.

pynetree

Aside

pyParse (bzw. jetzt pynetree)

Schadenfroyde