Design- Frage: Excel Umrechnung 'F1:H2' --> (5,7,2,1)

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.
Benutzeravatar
pillmuncher
User
Beiträge: 1118
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Sonntag 25. Oktober 2015, 11:56

Hab es gerichtet & vereinfacht:

Code: Alles auswählen

import re


def compose(f, g):
    def composed(x):
        return f(g(x))
    return composed


class ParsingError(Exception):
    pass


class Parser:

    def _parse(self, result, text):
        raise NotImplementedError

    def parse(self, text):
        result, rest = self._parse([], text)
        if rest:
            raise ValueError('Found trailing string: {}'.format(rest))
        else:
            return result

    def __add__(self, parser):
        return Then(self, parser)

    def __or__(self, parser):
        return Either(self, parser)


class Bind(Parser):

    def __init__(self, parser, function):
        self.parser = parser
        self.function = function

    def _parse(self, result, text):
        r, t = self.parser._parse([], text)
        return self.function(r)._parse(result + r, t)


def bind_compose(f, g):
    def bind_composed(parser):
        return Bind(Bind(parser, g), f)
    return bind_composed


class Return(Parser):

    def __init__(self, value):
        self.value = value

    def _parse(self, result, text):
        if self.value is not None:
            return result + [self.value], text
        else:
            return result, text


class Then(Parser):

    def __init__(self, first, second):
        self.first = first
        self.second = second

    def _parse(self, result, text):
        return self.second._parse(*self.first._parse(result, text))


class Either(Parser):

    def __init__(self, first, second):
        self.first = first
        self.second = second

    def _parse(self, result, text):
        try:
            return self.first._parse(result, text)
        except ValueError:
            return self.second._parse(result, text)


class Optional(Parser):

    def __init__(self, parser):
        self.parser = parser

    def _parse(self, result, text):
        try:
            return self.parser._parse(result, text)
        except ValueError:
            return result, text


class RegexParser(Parser):

    def __init__(self, pattern, name):
        self.pattern = pattern
        self.name = name
        self.match = re.compile(pattern=pattern).match

    def _parse(self, result, text):
        match = self.match(text)
        if match:
            return (
                result + [{self.name: match.group()}],
                text[match.end():],
            )
        else:
            raise ValueError('could not parse pattern "{}": {}'
                             .format(self.pattern, text))


##############################################################################


column = RegexParser(pattern='[A-Z]+', name='Column')
row = RegexParser(pattern='\d+', name='Row')
colon = RegexParser(pattern=':', name='Colon')
dollar = RegexParser(pattern='\$', name='Dollar')


def check_columns_are_monotonic(result):
    result = iter(result)
    for token in result:
        if 'Column' in token:
            start_column = token['Column']
            break
    for token in result:
        if 'Column' in token:
            end_column = token['Column']
            break
    else:
        return Return(None)
    if start_column > end_column:
        raise ParsingError('Wrong order of column indices!')
    else:
        return Return(None)


def check_rows_are_monotonic(result):
    result = iter(result)
    for token in result:
        if 'Row' in token:
            start_row = int(token['Row'])
            break
    for token in result:
        if 'Row' in token:
            end_row = int(token['Row'])
            break
    else:
        return Return(None)
    if start_row > end_row:
        raise ParsingError('Wrong order of row indices!')
    else:
        return Return(None)


EXCEL_ADDRESS = (
    bind_compose(check_columns_are_monotonic, check_rows_are_monotonic)(
        Optional(dollar)
        + column
        + Optional(dollar)
        + row
        + Optional(
            colon
            + Optional(dollar)
            + column
            + Optional(dollar)
            + row))
    |
    Bind(
        Optional(dollar)
        + column
        + colon
        + Optional(dollar)
        + column, check_columns_are_monotonic)
    |
    Bind(
        Optional(dollar)
        + row
        + colon
        + Optional(dollar)
        + row, check_rows_are_monotonic)
)


def parse(addr):
    return EXCEL_ADDRESS.parse(addr)


def show(addr):
    import pprint
    print(addr)
    pprint.pprint(parse(addr))
    print()


def main():
    show('A1')
    show('$A1')
    show('A$1')
    show('$A$1')
    show('A1:G7')
    show('$A$1:$G$7')
    show('$A:$G')
    show('1:1')
    # show('2:1')
    # show('$G1:$A1')


if __name__ == '__main__':
    main()
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
pillmuncher
User
Beiträge: 1118
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Montag 26. Oktober 2015, 14:27

Oder so:

Code: Alles auswählen

import copy
import re


class ParsingError(Exception):
    pass


class Parser:

    def join(self, result):
        return result

    def parse(self, t0):
        result, rest = self(t0)
        if rest:
            raise ValueError('Found trailing string: {}'.format(rest))
        else:
            return result

    def __call__(self, t0):
        raise NotImplementedError

    def __add__(self, parser):
        return Then(self, parser)

    def __or__(self, parser):
        return Either(self, parser)

    def __getitem__(self, join):
        new = copy.copy(self)
        new.join = join
        return new


class Bind(Parser):

    def __init__(self, parser, function):
        self.parser = parser
        self.function = function

    def __call__(self, t0):
        r1, t1 = self.parser(t0)
        r2, t2 = self.function(r1)(t1)
        return self.join(r1, r2), t2

    def join(self, r1, r2):
        return [r1, r2]


def bind_compose(f, g):
    def bind_composed(parser):
        return Bind(Bind(parser, g), f)
    return bind_composed


class Return(Parser):

    def __init__(self, result):
        self.result = result

    def __call__(self, t0):
        if self.result is None:
            return [], t0
        else:
            return self.join(self.result), t0

    def __str__(self):
        return 'Return({})'.format(self.result)

    __repr__ = __str__


class Then(Parser):

    def __init__(self, first, second):
        self.first = first
        self.second = second

    def __call__(self, t0):
        r1, t1 = self.first(t0)
        r2, t2 = self.second(t1)
        return self.join(r1, r2), t2

    def join(self, r1, r2):
        return [r1, r2]


class Either(Parser):

    def __init__(self, first, second):
        self.first = first
        self.second = second

    def __call__(self, t0):
        try:
            r, t = self.first(t0)
        except ParsingError:
            r, t = self.second(t0)
        return self.join(r), t


class Optional(Parser):

    def __init__(self, parser):
        self.parser = parser

    def __call__(self, t0):
        try:
            r, t = self.parser(t0)
        except ParsingError:
            return [], t0
        return self.join(r), t


class PrefixOperator(Parser):

    def __init__(self, operator, operand):
        self.operator = operator
        self.operand = operand

    def __call__(self, t0):
        r1, t1 = self.operator(t0)
        r2, t2 = self.operand(t1)
        return self.join(r1, r2), t2

    def join(self, r1, r2):
        return [r1, r2]


class InfixOperator(Parser):

    def __init__(self, left, operator, right):
        self.left = left
        self.operator = operator
        self.right = right

    def __call__(self, t0):
        r1, t1 = self.left(t0)
        r2, t2 = self.operator(t1)
        r3, t3 = self.right(t2)
        return self.join(r1, r2, r3), t3

    def join(self, r1, r2, r3):
        return [r1, r2, r3]


class RegexParser(Parser):

    def __init__(self, pattern):
        self.pattern = pattern
        self.match = re.compile(pattern=pattern).match

    def __call__(self, t0):
        match = self.match(t0)
        if match:
            return self.join(match.group()), t0[match.end():]
        else:
            raise ParsingError(
                'could not parse pattern "{}": {}' .format(self.pattern, t0)
            )


##############################################################################


from collections import namedtuple
from string import ascii_uppercase


ALPHA_VALUES = {k: v for v, k in enumerate(ascii_uppercase, start=1)}


def column2int(column):
    return sum(
        ALPHA_VALUES[c] * len(ALPHA_VALUES) ** i
        for i, c in enumerate(reversed(column))
    )


Column = namedtuple('Column', 'index absolute')
Row = namedtuple('Row', 'index absolute')
Cell = namedtuple('Cell', 'column row')
CellRange = namedtuple('CellRange', 'first last')
ColumnRange = namedtuple('ColumnRange', 'first last')
RowRange = namedtuple('RowRange', 'first last')


def make_relative_column(index):
    return Column(column2int(index), False)


def make_absolute_column(_, index):
    return Column(column2int(index), True)


def make_relative_row(index):
    return Row(int(index), False)


def make_absolute_row(_, index):
    return Row(int(index), True)


def make_cell(column, row):
    return Cell(column, row)


def make_cell_range(left, _, right):
    if left.column.index > right.column.index:
        raise ValueError('wrong column values!')
    if left.row.index > right.row.index:
        raise ValueError('wrong row values!')
    return CellRange(left, right)


def make_column_range(left, _, right):
    if left.index > right.index:
        raise ValueError('wrong column values!')
    return ColumnRange(left, right)


def make_row_range(left, _, right):
    if left.index > right.index:
        raise ValueError('wrong row values!')
    return RowRange(left, right)


COLUMN = RegexParser('[A-Z]+')
ROW = RegexParser('\d+')
COLON = RegexParser(':')
DOLLAR = RegexParser('\$')
COLUMN_ADDRESS = (
    PrefixOperator(DOLLAR, COLUMN)[make_absolute_column]
    | COLUMN[make_relative_column]
)
ROW_ADDRESS = (
    PrefixOperator(DOLLAR, ROW)[make_absolute_row]
    | ROW[make_relative_row]
)
CELL_ADDRESS = (COLUMN_ADDRESS + ROW_ADDRESS)[make_cell]
EXCEL_ADDRESS = (
    InfixOperator(COLUMN_ADDRESS, COLON, COLUMN_ADDRESS)[make_column_range]
    | InfixOperator(ROW_ADDRESS, COLON, ROW_ADDRESS)[make_row_range]
    | InfixOperator(CELL_ADDRESS, COLON, CELL_ADDRESS)[make_cell_range]
    | CELL_ADDRESS
)


def parse(addr):
    return EXCEL_ADDRESS.parse(addr)


def show(addr):
    import pprint
    print(addr)
    pprint.pprint(parse(addr))
    print()


def main():
    show('A1')
    show('$A1')
    show('A$1')
    show('$A$1')
    show('A1:B2')
    show('$A$1:$G$7')
    show('$A:$G')
    show('AA:AG')
    show('$1:$1')
    # show('2:1')
    # show('$G1:$A1')
    assert parse('$A$1:$G$7').last.column.absolute


if __name__ == '__main__':
    main()
Ergebnis:

Code: Alles auswählen

A1
Cell(column=Column(index=1, absolute=False), row=Row(index=1, absolute=False))

$A1
Cell(column=Column(index=1, absolute=True), row=Row(index=1, absolute=False))

A$1
Cell(column=Column(index=1, absolute=False), row=Row(index=1, absolute=True))

$A$1
Cell(column=Column(index=1, absolute=True), row=Row(index=1, absolute=True))

A1:B2
CellRange(first=Cell(column=Column(index=1, absolute=False), row=Row(index=1, absolute=False)), last=Cell(column=Column(index=2, absolute=False), row=Row(index=2, absolute=False)))

$A$1:$G$7
CellRange(first=Cell(column=Column(index=1, absolute=True), row=Row(index=1, absolute=True)), last=Cell(column=Column(index=7, absolute=True), row=Row(index=7, absolute=True)))

$A:$G
ColumnRange(first=Column(index=1, absolute=True), last=Column(index=7, absolute=True))

AA:AG
ColumnRange(first=Column(index=27, absolute=False), last=Column(index=33, absolute=False))

$1:$1
RowRange(first=Row(index=1, absolute=True), last=Row(index=1, absolute=True))
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
NoPy
User
Beiträge: 123
Registriert: Samstag 28. Dezember 2013, 12:39

Donnerstag 29. Oktober 2015, 20:22

Du liest mich Schweigen vor Ehrfurcht ;)

Ich werde es gewiss nicht so machen, weil ich es nicht verstehe und nicht einfach mit copy/paste irgend etwas zusammenschubsen will.
Aber ich werde es mir nach und nach anschauen. Das sieht sehr spannend aus. Es wird wohl immer mal wieder eine Frage dazu geben.

Vielen Dank, Du erweiterst gerade meinen Horizont!

Also ich habe grob verstanden, worauf Du hinauswillst, glaube ich. So eine Art "Teile und Herrsche".

Meine ersten Fragen (ich fange mal hinten an):

Code: Alles auswählen

def parse(addr):
    return EXCEL_ADDRESS.parse(addr)
Was genau passiert hier? EXCEL_ADDRESS sorgt für das Erzeugen eines Objektes der Klasse InfixOperator, die von Parser erbt und als Parameter für den Konstruktor eine Oder- Verknüfung aller möglichen Beschreibungen für gültige Excel- Bereiche (wobei - soweit ich das überblickt habe - die Überprüfung, ob die von- Spalte/Zeile kleiner ist, als die bis- Spalte/Zeile noch nicht integriert ist, oder? Also C10:A3 wäre gültig, oder?)

Wie ist die Konstruktion EXCEL_ADDRESS = (Funktionsaufruf()) zu verstehen? Was wird damit definiert?

Code: Alles auswählen

    def parse(self, t0):
        result, rest = self(t0)
        if rest:
            raise ValueError('Found trailing string: {}'.format(rest))
        else:
            return result
was passiert bei self(t0)?
Benutzeravatar
pillmuncher
User
Beiträge: 1118
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Donnerstag 29. Oktober 2015, 21:43

NoPy hat geschrieben:Ich werde es gewiss nicht so machen, weil ich es nicht verstehe und nicht einfach mit copy/paste irgend etwas zusammenschubsen will.
Statt selber Parserkombinatoren zu bauen, kannst du eine entsprechende Bibliothek verwenden. Ich mag Parcon. Dazu unten mehr.
NoPy hat geschrieben:Also ich habe grob verstanden, worauf Du hinauswillst, glaube ich. So eine Art "Teile und Herrsche".
Wie immer beim Programmieren. ;)
NoPy hat geschrieben:Meine ersten Fragen (ich fange mal hinten an):

Code: Alles auswählen

def parse(addr):
    return EXCEL_ADDRESS.parse(addr)
Was genau passiert hier? EXCEL_ADDRESS sorgt für das Erzeugen eines Objektes der Klasse InfixOperator, die von Parser erbt und als Parameter für den Konstruktor eine Oder- Verknüfung aller möglichen Beschreibungen für gültige Excel- Bereiche (wobei - soweit ich das überblickt habe - die Überprüfung, ob die von- Spalte/Zeile kleiner ist, als die bis- Spalte/Zeile noch nicht integriert ist, oder? Also C10:A3 wäre gültig, oder?)

Wie ist die Konstruktion EXCEL_ADDRESS = (Funktionsaufruf()) zu verstehen? Was wird damit definiert?
Man muss das alles aus ein paar Meter Entfernung betrachten, um die Grobstruktur erkennen zu können. Die übergreifende Idee ist, kleine Parser für Teilaufgaben zu verwenden und diese "zusammenzustecken", wodurch man wieder Parser erhält. Der Then-Parser beispielsweise bekommt bei der Initialisierung zwei Parser als Argumente. Er parst, indem er erst den ersten Parser aufruft, und erhält von diesem dessen Parsingergebnis und den restlichen, noch nicht geparsten Text. Mit diesem Text ruft Then dann den zweiten Parser auf, erhält von diesem dessen Parsingergebnis und den nicht geparsten restlichen Text. Die beiden Ergebnisse werden zu einer Liste zusammengefügt und diese Liste - durch self.join() transformiert - und der restliche Text werden als Returnwert zurückgegeben. Ein Parser ist also - mathematisch betrachtet - eine Funktion vom Typ Text --> (ParsingResult, Text). Damit Parser Objekte dieses Interface zur Verfügung stellen, müssen sie aufrufbar sein und in Python macht man das, indem man die __call__()-Methode implementiert. Ein Objekt x mit dieser Methode kann ich mittels x(...) aufrufen. Dadurch, dass ich lediglich die Aufrufbarkeit verlange, erreiche ich, dass man auch einfache Parser-Funktionen statt Klassen schreiben kann.

Zur Vereinfachung der Parser-Kombination habe ich zwei Operatoren implementiert. p1 + p2 bedeutet damit dasselbe wie Then(p1, p2). p1 | p2 bedeutet dasselbe wie Either(p1, p2), und Either versucht erst mit p1 zu parsen und dann und nur dann mit p2, wenn p1 scheitert.

Dass man mit + aus zwei Parsern einen neuen machen kann ist im Prinzip dasselbe, wie wenn man mit + aus zwei Zahlen eine neue macht.

Die Prüfung darauf, dass der zweite Zeilen-/Spaltenwert nie kleiner ist als der vorhergehende, passiert in den make_*_range() Funktionen. In den make_*() Funktionen werden die Datenstrukturen aus der Listenform in eine aussagekräftigere Datenstruktur übersetzt, zusammen mit den genannten Prüfungen. Diese Funktionen werden den Parsern mithilfe des Subskriptionsoperators mitgegeben, eine Idee, die ich von Parcon geklaut habe. Meine Implementierung ist nicht ganz korrekt, hier & hier habe ich es besser gemacht.

Die Idee ist also, sowohl die Parser zu neuen Parsern kombinieren zu können, als auch die Ergebnisse so zu transformieren, wie man es haben möchte, ohne dazu in den Parserklassen herumfummeln zu müssen.
NoPy hat geschrieben:

Code: Alles auswählen

    def parse(self, t0):
        result, rest = self(t0)
        if rest:
            raise ValueError('Found trailing string: {}'.format(rest))
        else:
            return result
was passiert bei self(t0)?
Wie oben schon beschrieben, ist auf Parsern die __call__()-Methode definiert, deswegen sind Parser aufrufbar. Und self ist ja ein Parser.

Hier noch eine Implementierung mit Parcon für Python 2.7: http://www.python-forum.de/pastebin.php?mode=view&s=467

Der Grund, warum es monadische Bind und Return Parser gibt, ist übrigens, damit man kontextsensitive Grammatiken parsen kann. Angenommen Strings der Form <Länge n in Dezimalschreibweise>:<n Buchstaben>, dann kann man das mit Parcon ganz einfach so machen:

Code: Alles auswählen

from parcon import OneOrMore, Chars, digit, concat, Bind, End
LEN = OneOrMore(digit)[concat][int]
STR = Bind(LEN + ':', Chars) + End()
print(STR.parse_string('5:hallo'))
Ergebnis:

Code: Alles auswählen

hallo
Wenn ich dagegen das hier versuche:

Code: Alles auswählen

print(STR.parse_string('5:halloabc'))
ist das Ergebnis:

Code: Alles auswählen

Traceback (most recent call last):
  File "parc.py", line 158, in <module>
    main1()
  File "parc.py", line 154, in main1
    print(STR.parse_string('5:halloabc'))
  File "/home/mick/.virtualenvs/parcon/local/lib/python2.7/site-packages/parcon/__init__.py", line 619, in parse_string
    raise ParseException("Parse failure: " + format_failure(result.expected))
parcon.ParseException: Parse failure: At position 7: expected one of EOF
Mit yacc, bison oder - Gott bewahre! - Regulären Ausdrücken kann man sowas nur schwer bis gar nicht parsen.
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
pillmuncher
User
Beiträge: 1118
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Freitag 30. Oktober 2015, 18:24

NoPy hat geschrieben:Wie ist die Konstruktion EXCEL_ADDRESS = (Funktionsaufruf()) zu verstehen?
Die Klammern dienen nur dazu, dass ich dazwischen mehrzeilig schreiben kann. Genau wie hier:

Code: Alles auswählen

In [1]: x = (
   ...:     1
   ...:     +
   ...:     2
   ...: )

In [2]: x
Out[2]: 3
In specifications, Murphy's Law supersedes Ohm's.
Antworten