+ All Categories
Home > Technology > Tech Talk: Pyparsing

Tech Talk: Pyparsing

Date post: 03-Jul-2015
Category:
Upload: schlauch
View: 1,275 times
Download: 2 times
Share this document with a friend
22
Folie 1 Tech Talk: Pyparsing Tobias Schlauch, DLR Simulations- und Softwaretechnik 11. März 2008
Transcript
Page 1: Tech Talk: Pyparsing

Folie 1

Tech Talk: Pyparsing

Tobias Schlauch, DLR Simulations- und Softwaretechnik 11. März 2008

Page 2: Tech Talk: Pyparsing

Folie 2

Motivation

Problem

Vereinfachung des DataFinder-API zur Suche in Metadaten erforderlich

Anstatt Syntax mit Hilfe definierter Klassen abzubilden, soll einfache Verwendung von Zeichenketten ausreichen, wie z.B.

projectName = "X-38" and author = "Schütte"

Lösungvariante

Reguläre Ausdrücke

Schön… aber was macht das hier eigentlich???

"[-+]?(\d+(\.\d*)?|\.\d+)([eE][-+]?\d+)?"

Alternativen…?

Page 3: Tech Talk: Pyparsing

Folie 3

Pyparsing im Überblick

Was ist Pyparsing?

Klassenbibliothek zur Erstellung von Parsern (recursive descent)

Design auf einfache Erstellung und Aktualisierung ausgelegt

Parser für regulären Sprachen und Teilmenge kontextfreier Sprachen (vgl. Chomsky-Hierarchie)

Pure-Python, Python >= 2.3.2

MIT-Lizenz

Gute Dokumentation

Epydoc, Klassendiagramm, Beispiele, Wiki

Page 4: Tech Talk: Pyparsing

Folie 4

Was macht eigentlich ein Parser? (vereinfacht)

|H|e|l|l|o|,|Wo|r|l|d|!|

„Hello,World!“-Parser

Syntaktisch korrekt?

Zeichenstrom

|Hello|,|World|!|

Abgeleitete Token

Page 5: Tech Talk: Pyparsing

Folie 5

Grundlegende Vorgehensweise mit Pyparsing

• Definition der Grammatik (Token / Verknüpfungen)

• Hierarchische Definition

Optionale Definition von Ergebnisnamen und Parseraktionen

• Aufruf von parseString oder scanString

Standardmäßig werden Whitespaces ignoriert

Anwendung definierter Parseraktionen

• Verarbeitung des Ergebnisses als Liste oder unter Verwendung der definierter Namen

Page 6: Tech Talk: Pyparsing

Folie 6

Erstes BeispielHello World!

Definition der Token / Muster

greeting = oneOf("Hello Hi") + Literal(",") + Word(alphas) + Literal("!")

Aufruf von parseString()

print greeting.parseString("Hello, World!").asList()['Hello', ',', 'World', '!']

print greeting.parseString(„Hi, SISTEC")pyparsing.ParseException: Expected "!" (at char 13), (line:1, col:14)

Ups „!“ vergessen

Page 7: Tech Talk: Pyparsing

Folie 7

Pyparsing GrundlagenDefinition fester Token

Literal / CaselessLiteral

ifToken = Literal("if")

Findet das Token in if(x=1) und in ifAndOnlyYouAndMe

Keyword / CaselessKeyword

ifToken = Keyword("if")

Findet das Token in if(x=1), aber nicht in ifAndOnlyYouAndMe

Caseless-Varianten geben als Ergebnis immer die definierte Variante zurück, also hier if

Page 8: Tech Talk: Pyparsing

Folie 8

Pyparsing GrundlagenDefinition variabler Token

Word – Definition durch erlaubte Zeichen

name = Word("Tabios")

name = Word("T", "abios")

CharsNotIn – Definition durch nicht erlaubter Zeichen

name = CharsNotIn(",;:-!")

Zusätzlich Spezifikation der Länge möglich (min, max, exakt)

Regex

Erwartet als Parameter einen regulären Ausdruck, wie für das Standardmodul re

Vorher nach Pyparsing-Lösung suchen!!!

Page 9: Tech Talk: Pyparsing

Folie 9

Pyparsing GrundlagenVerknüpfungen

And (+) – Definition erforderlicher Ausdrücke in fester Reihenfolgesentence = And([subject, verb, object])sentence = subject + verb + object

Each (&) – Definition erforderlicher Ausdrücke in beliebiger Reihenfolgeidentity = persNumber & name

Or (^) – Definition optionaler Ausdrücke (Priorität: Zeichenkettenlänge) operator = Literal("<") ^ Literal("<=")

MatchFirst (|) – Definition optionaler Ausdrücke (Priorität: Definitions-reihenfolge)

operator = Literal("<=") | Literal("<")

Page 10: Tech Talk: Pyparsing

Folie 10

Pyparsing GrundlagenOptionale Ausdrücke, Wiederholungen

Optional

Definition optionaler Ausdrücke

dateTime = day + "." + month + "." + year + Optional(time)

ZeroOrMore

Ähnlich zu Optional, aber erlaubt Wiederholungen

logMsg = dateTime + ZeroOrMore(Word(alphas))

OneOrMore

Ähnlich zu ZeroOrMore, aber erfordert mindestens einen Treffer

logMsg = dateTime + OneOrMore(Word(alphas))

Page 11: Tech Talk: Pyparsing

Folie 11

Pyparsing Grundlagen Konvertierungen

Upcase - Konvertierung in Großbuchstaben

Suppress - Unterdrückung von Tokendate = day + Suppress(".") + month + Suppress(".") + yearprint date.parseString("11.03.2008").asList()["11", "03", "2008"]

Combine – Verbindet einzelne Token zu einer Zeichenkettedate = Combine(day + "." + month + "." + year)print date.parseString("11.03.2008").asList()["11.03.2008"] anstatt ["11", ".", "03", ".", "2008"] (ohne Combine)

Page 12: Tech Talk: Pyparsing

Folie 12

Pyparsing GrundlagenRekursive Grammatiken

Forward – Platzhalter zur Definition rekursiver Grammatiken

Beispiel Parsen einer Liste

list = Forward()

listItem = Word(alphas)

list << (listItem + Suppress(Literal(",")) + list | listItem)

print list.parseString("Wert , Name, test").asList()

["Wert", "Name", "test"]

Klammerung beachten! (Operator | bindet stärker als <<)

Überprüfung auf Endlosrekursion durch Aufruf von validate()

Page 13: Tech Talk: Pyparsing

Folie 13

Pyparsing GrundlagenParseraktionen

Erlaubt Änderung der erkannten Token während des Parsevorgangs

Hinzufügen / Entfernen von Informationen

Konvertierungen

3 Schnittstellen

f(t); t – Liste erkannter Token

f(l, t); l – Position im zu parsenden String

f(s, l, t); s – Zu parsender String

Hilfsfunktionen

replaceWith(replaceString)

removeQuotes()

Page 14: Tech Talk: Pyparsing

Folie 14

Pyparsing GrundlagenParseraktionen - Beispiel

Definition einer Aktion zur Konvertierungdef convertNumValue(t):

numValue = t.asList()[0] try:

return int(numValue) except ValueError:

return float(numValue)Anhängen der AktionnumValue.setParseAction(convertNumValue) odernumValue.addParseAction(convertNumValue)

Ergebnisprint numValue.parseString("12340").asList()[12340] anstatt ["12340"]

Page 15: Tech Talk: Pyparsing

Folie 15

Pyparsing GrundlagenHilfsfunktionen (kleine Auswahl)

oneOf – Vereinfachte Definition von Alternativen

options = oneOf("< > <= = >=")

delimitedList – Parsen von Listen

list = delimitedList(Word(alphas), ",")

nestedExpr – Parsen von verschalteten Ausdrücken

nested = nestedExpr("(", ")", Word(alphas))

print nested.parseString("(abc(def(gh)))").asList()

[["abc", ["def", ["gh"]]]]

operatorPrecedence – Parsen von Operatorrangfolgen (später mehr)

Page 16: Tech Talk: Pyparsing

Folie 16

Pyparsing GrundlagenVerarbeitung von Ergebnissen

Geparste Token werden in einer hierarchischen Struktur zurückgegeben (ParsingResults)

Verarbeitung der Token als Listen, XML, Dictionary oder über die Objekteigenschaften möglich

Verarbeitung als Dictionary oder über Objekteigenschaften setzt Benennung der Ergebnisse bei der Definition voraus

Überschaubarer Grammatiken -> Benennung nicht unbedingt erforderlich

Komplexer Grammatiken -> Benennung empfohlen

Page 17: Tech Talk: Pyparsing

Folie 17

Pyparsing GrundlagenVerarbeitung von Ergebnissen - Beispiel

Definition der Token / Muster date = day.setResultsName("day") + "." +

month.setResultsName("month") + "." + year.setResultsName("year")token = date.parseString("11.03.2008")Ausgabenprint token.asList()["11", ".", "03", ".", "2008"]print token.asXML()"<ITEM><day>11</day><ITEM>"."</ITEM><month…"print token.asDict(){"day": "11", "month": "03", "year": "2008"}print token.day"11"

Page 18: Tech Talk: Pyparsing

Folie 18

Pyparsing Grundlagen…

Pyparsing enthält noch etliche Details, die aber den Rahmen dieses Vortrags sprengen, z.B.:

Ergebnisgruppierungen Group, Dict

Weitere Hilfsfunktionen

Verarbeitung XML, HTML

Positionsabhängige Hilfsfunktionen

Tokenkonstanten (z.B. für Kommentare)

Page 19: Tech Talk: Pyparsing

Folie 19

Performance-Tuning

Aktivierung von Packrat-Parsing (enablePackrat)

Verwendung von Psyco (http://psyco.sourceforge.net/)

- n/a -614.4packrat + psyco

- n/a -365.7psyco

395.8428.7packrat

146.5160.6base

Python V2.5

(lines parsed /second)

Python V2.4.1

(lines parsed /second)

Verliog-Parser

Quelle: http://pyparsing.wikispaces.com/News

Page 20: Tech Talk: Pyparsing

Folie 20

Suchrestriktionen im DataFinderDefinition der Grammatik (stark vereinfacht)

literal = QuotedString("'")propertyName = Word(alphas)comparisionTerm = propertyName + oneOf("< > <= => =") +

literal

searchRestriction = operatorPrecedence(comparisionTerm, [("not", 1, opAssoc.RIGHT),

("and", 2, opAssoc.LEFT), ("or", 2, opAssoc.LEFT)])

BeispielmyRestr = "a > 'test' and not(b < '3')"print searchRestriction.parseString(myRestr).asList()[["a", " >", "test", "and", ["not", "b", "<", "3"]]]

Page 21: Tech Talk: Pyparsing

Folie 21

Suchrestriktionen im DataFinderAnwendung

Zentrale Grammatikdefinition wird genutzt für

Transformation der geparsten Token auf Syntax der Bibliothek, welche intern zur Suchabfrage genutzt wird

Syntax-Highlighting

Page 22: Tech Talk: Pyparsing

Folie 22

Vielen Dank! Fragen??

Pyparsing Links

News: http://pyparsing.wikispaces.com/News

Beispiele: http://pyparsing.wikispaces.com/Examples

Download: http://sourceforge.net/project/showfiles.php?group_id=97203

Weiterführendes zum Thema:

Compilerbau: http://de.wikipedia.org/wiki/Compilerbau

Aho, Sethi, Ullman: Compilerbau, Tl. 1. Oldenbourg, 1999

Recursive Descent Parser: http://en.wikipedia.org/wiki/Recursive_descent_parser

Packrat-Parsing: http://pdos.csail.mit.edu/~baford/packrat/

Alternative Python-Parsersysteme: http://pythonsource.com/open-source/parser-generators


Recommended