Taschenrechner (oder: wie schreibe ich einen parser?)

[for_maniac]

Hi@all

ich möchte Python lernen, das will ich mit einen Projekt und zwar einen Taschenrechner machen.
Einen Taschenrechner hab ich zuvor schon in C geschrieben diese kann aber nur Eingaben im Format Zahlen Operator Zahlen ausführen.

Diesen Tr möchte ich in Python dahingehend weiterentwickeln das der Ausdruck länger werden kann und mit klammern also, zahl op zahl op...

Bisher hab ich schon rausgefunden das ich dazu einen Parser brauche, ich hab aber keine Ahnung wie so etwas aussieht.
Es wäre toll wenn ihr mir ein paar websites zu dem Thema nennen könntet oder auch ein paar Codebeispiele, die gut erklärt sind.

Der Angehängte Code spiegelt in etwa auch mein Prog. kenntnisse wieder, ich hab also noch nicht alzuviel ahnung.

Hier der TR den ich in C geschrieben habe:

Code: Alles auswählen

#include <stdio.h>
#include <math.h>
#include <string.h>
int main(){

while(1){

char eingabe[20];
char z1[20], z2[20];
int i=0,op,a=0;
float zahl1=0,zahl2=0, erg=0;

printf("Geben sie die Rechnug ein: ");
scanf("%s",&eingabe);

for(i=0,a=0;eingabe[i]>= 0x30 && eingabe[i]<=
0x39;i++,a++){z1[a]=eingabe[i];}
z1[a]=0x0;

op=eingabe[i];

for(i++,a=0;eingabe[i]>= 0x30 && eingabe[i]<=
0x39;i++,a++){z2[a]=eingabe[i];}
z2[a]=0x0;

for(i=strlen(z1)-1,a=0; i>=0;i--,a++){zahl1=zahl1+(z1[i]-
0x30)*pow(10,a);}

for(i=strlen(z2)-1,a=0; i>=0;i--,a++){zahl2=zahl2+(z2[i]-
0x30)*pow(10,a);}

if(op==0x2B){erg= zahl1 +zahl2;}
if(op==0x2D){erg= zahl1 -zahl2;}
if(op==0x2A){erg= zahl1 *zahl2;}
if(op==0x2F){erg= zahl1 /zahl2;}

printf("%.2f %c %.2f = %.2f\n\n",zahl1,op,zahl2,erg);
}
return 0;
}

MFG for_maniac[/list]

[modelnine]

Kleiner "recursive descent"-Parser für das ganze (mit lookahead 1, also LALR(1)):

Code: Alles auswählen

# -*- coding: iso-8859-15 -*-
# Grammar specification is at start of function. Non-Terminals are lower-case,
# Terminals are uppercase or symbols.

import math
import operator

functions = {"log":math.log,
             "exp":math.exp} # Some example functions,
                             # all taking only one parameter.
variables = {"pi":math.pi,
             "e":math.exp(1)} # Some example constants.

# Little debugging function which outputs the token we are at.
def print_pos(name,expr,i):
    print name, expr
    print " "*(len(name)+i), "^"

# addexpr -> mulexpr [+|- mulexpr]*
def parse_addexpr(expr,i):
    print_pos("parse_addexpr",expr,i)

    # Initial addexpr -> mulexpr.
    val, i = parse_mulexpr(expr,i)

    # Check for possible operator [+|-]
    while i < len(expr):
        if expr[i] == "+":
            op = operator.add
        elif expr[i] == "-":
            op = operator.sub
        else:
            # Unknown operator, this might be a closing bracket.
            # Cannot raise an invalid input exception here as we are
            # called recursively. Just return to calling production.
            break
        i += 1

        # Parse following addexpr.
        newval, i = parse_mulexpr(expr,i)

        # Do operation on val and newval.
        val = op(val,newval)

    return val, i

# mulexpr -> powexpr [*|/ powexpr]*
def parse_mulexpr(expr,i):
    print_pos("parse_mulexpr",expr,i)

    # Initial mulexpr -> bracketexpr.
    val, i = parse_powexpr(expr,i)

    # Check for possible operator [*|/]
    while i < len(expr):
        if expr[i] == "*":
            op = operator.mul
        elif expr[i] == "/":
            op = operator.div
        else:
            # Some unknown operator. Cannot raise input exception here as
            # this might actually be a +|-.
            break
        i += 1

        # Parse the following mulexpr.
        newval, i = parse_powexpr(expr,i)

        # Combine values.
        val = op(val,newval)

    return val, i

# powexpr -> bracketexpr [^ bracketexpr]*
def parse_powexpr(expr,i):
    print_pos("parse_powexpr",expr,i)

    # Parse initial bracketexpr.
    val, i = parse_bracketexpr(expr,i)

    # Check for a possible continuation.
    while i < len(expr):
        # Check for pow signal.
        if expr[i] <> "^":
            break
        i += 1

        # Parse new value.
        newval, i = parse_bracketexpr(expr,i)

        # Do powering.
        val = val**newval

    return val, i

# bracketexpr -> number | ( addexpr ) | name [ ( addexpr [, addexpr]* ) ] |
#                - bracketexpr
def parse_bracketexpr(expr,i):
    print_pos("parse_bracketexpr",expr,i)

    # Check for actual data content.
    if i == len(expr):
        # Can raise an exception here, an empty bracketexpr is always bad.
        raise ValueError("No token in bracketexpr")

    # Check for possible brackets.
    if expr[i] == "(":
        # Parse bracketexpr -> ( addexpr )
        i += 1
        val, i = parse_addexpr(expr,i)

        if i == len(expr) or expr[i] <> ")":
            # An opening bracket must always be followed by a closing
            # bracket after the term. In case the closing bracket is not
            # found, the term is surely invalid.
            raise ValueError("Opening bracket not closed in bracketexpr")
        i += 1
    elif expr[i].isdigit() or expr[i] == ".":
        # Parse bracketexpr -> number
        val, i = parse_number(expr,i)
    elif expr[i].isalpha() or expr[i] in "_":
        # Parse bracketexpr -> funcname ( addexpr [, addexpr]* )
        name, i = parse_name(expr,i)

        # Handle brackets.
        if i == len(expr) or expr[i] <> "(":
            if name not in variables:
                raise ValueError("Invalid variable name in bracketexpr")
            val = variables[name]
        else:
            i += 1

            args = []
            while True:
                # Handle addexpr.
                newval, i = parse_addexpr(expr,i)
                args.append(newval)

                # Check for function end.
                if i == len(expr):
                    raise ValueError("No closing bracket after func "
                                     "in bracketexpr")
                elif expr[i] == ",":
                    # Another argument is coming.
                    i += 1
                elif expr[i] == ")":
                    # Closing bracket, end of function call.
                    i += 1
                    break
            if name not in functions:
                raise ValueError("Invalid function name in bracketexpr")
            try:
                val = functions[name](*args)
            except:
                raise ValueError("Function call invalid in bracketexpr")
    elif expr[i] == "-":
        # Unary minus.
        i += 1
        val, i = parse_bracketexpr(expr,i)

        # Invert value.
        val *= -1
    else:
        # We found something else, this is always an error.
        raise ValueError("Unknown token in bracketexpr")

    return val, i

# number = DIGITS+ [ . DIGITS* ] | . DIGITS+
# DIGITS = 0 .. 9
def parse_number(expr,i):
    print_pos("parse_number",expr,i)

    data = []
    if expr[i] == ".":
        # Second production.
        data.append(expr[i])
        i += 1

        # Consume decimal part.
        while i < len(expr) and expr[i].isdigit():
            data.append(expr[i])
            i += 1

        # Check whether any decimal part was actually there.
        if len(data) == 1:
            raise ValueError("Lone dot as number in number.")
    else:
        data.append(expr[i])
        i += 1

        # Consume integer part.
        while i < len(expr) and expr[i].isdigit():
            data.append(expr[i])
            i += 1

        # Consume possible decimal part.
        if i < len(expr) and expr[i] == ".":
            data.append(expr[i])
            i += 1
            while i < len(expr) and expr[i].isdigit():
                data.append(expr[i])
                i += 1

    val = float("".join(data))
    return val, i

# name -> ALPHA ALNUM*
# ALPHA -> A..Z | a..z | _
# ALNUM -> ALPHA | 0..9
def parse_name(expr,i):
    print_pos("parse_name",expr,i)

    # Get initial name part.
    name = [expr[i]]
    i += 1

    # Loop until no more name characters are found.
    while i < len(expr) and ( expr[i].isalnum() or expr[i] in "_" ):
        name.append(expr[i])
        i += 1

    val = "".join(name)
    return val, i

def evaluate(expr):
    # Start with starting non-terminal.
    val, i = parse_addexpr(expr,0)

    # Did it consume everything? If not, the input is bogus.
    if i < len(expr):
        raise ValueError("Not all input consumed by addexpr, invalid token?")

    # Return evaluated value.
    return val

print evaluate("10+10^2*3+log(5)-3/4*5+-5")

Der basiert auf folgender Grammatik:

Code: Alles auswählen

start -> addexpr
addexpr -> mulexpr [ +|- mulexpr ]*
mulexpr -> powexpr [ *|/ powexpr ]*
powexpr -> bracketexpr [ ^ bracketexpr ]*
bracketexpr -> number | ( addexpr ) | name [ ( addexpr [ , addexpr ]* ) ] | - bracketexpr
number -> DIGITS+ [ . DIGITS* ] | . DIGITS+
name -> ALPHA ALNUM*

Ich hab ihn eben beim schreiben leider auf Englisch dokumentiert, aber vielleicht hilfts trotzdem; wenn Du Probleme damit hast meld Dich dann übersetz ich auch gerne Teile davon.

Wenn Du ein gutes Buch über Parser u.Ä. lesen willst kann ich nur die "Drachenbücher" von Aho und Ullmann empfehlen, eine Suche auf Amazon zeigt Dir welche ich meine. Die sind natürlich etwas fortgeschrittener, aber eine "einfache" Einführung in Parser gibts eigentlich nicht soweit ich weiß, da das Thema an sich schon reichlich komplex ist und sehr viel mit Berechenbarkeit und Maschinen-Modellen zu tun hat.

Nur als Nebennote: der obige Parser kommt ohne einen Tokenizer aus. Wenn man einen Tokenizer davorschalten würde wäre er etwas übersichtlicher (gerade was das ignorieren von Whitespace angeht, was dieser Parser überhaupt nicht kann), aber ich denke man erkennt auch so was er macht. Die Grammatik ist ganz davon abgesehen auch in einer bestimmten Form, deswegen ist sie fast direkt in einen LALR(1)-Parser zu übersetzen (man sieht dass es eine Funktion pro Nicht-Terminal gibt, und dass diese Funktionen immer ein Zeichen Lookahead machen um zu gucken ob etwas oder welches Nicht-Terminal als nächstes kommt).

PS: Die Grammatik hat in dieser Form ein kleines "Gotcha," denn -2^0.5 wird nicht so ausgewertet wie man denkt (also -(2^0.5)), sondern als (-2)^0.5. Das müßte man durch eine Veränderung in powexpr und bracketexpr beheben, aber dazu hab ich jetzt keine Lust mehr. Was es allerdings richtig auswertet: 2^-0.5 -> (2)^(-0.5).

--- Heiko.

[for_maniac]

Ich glaub ich versteh da nur Bahnhof, mal schauen wie weit ich komm.
Aber ich hab jetzt schon selbst eine Idee.
Und zwar :

-Klammern: die Eingabe durchgehen wenn er auf eine öffnende Klammer stößt die Position in eine Variable schreiben, wenn die nächste Klammer wieder eine öffnende dann die variable überschreiben, falls schließende kommt position in zweite variable schreiben

damit hab ich schon mal den innersten klammer ausdruck diesen werte ich aus und ersetze ihn durch das ergebnis und lasss es wieder durchlaufen bis keine klammern mehr da sind

-um punkt vor strich zu beachten schau ich welcher operator auf eine Zahl folgt ist es ein * oder / wert lasse ich beide Berechnen und Ersetze den Ausdruck durch das Ergebniss

das wiederhole ich solange bis nur noch + und - vorhanden ist dann muss ich den ausdruck nur noch von links nach rechts durchgehen und habe das ergebniss.

Was haltet ihr von der Idee und was würdet ihr noch verbessern?

[mr.hide]

Am einfachsten wird es sein du entwirfst dir erst einmal einen Moore Automat und implementierst diesen dann.

So dürfte es relativ einfach sein.

Bei Fragen zu Moore Automaten sind Wikipedia und Google deine Freunde

[modelnine]

Ein Moore-Automat hilft herzlich wenig beim Parsen eines Ausdrucks. Er ist geeignet um den Ausdruck in Einzelteile zu zerlegen (als sogenannter Tokenizer), aber mehr auch nicht, denn er ist im Endeffekt nur ein DEA mit Nebeneffekten.

Um eine solche Sprache zu parsen (man bemerke dass es Klammerungen gibt) braucht man einen Kellerautomaten (was schon daran deutlich wird dass der Parser den ich geschrieben habe rekursiv ist; das ist nichts anderes als die Simulation eines DKA).

Um den Ausdruck auszuwerten (und dabei die Rechenregeln zu befolgen) hilft nur ein DKA, den ich oben in Form eines LALR(1) Parsers implementiert habe, und eben eine Grammatik die die Ausdrucksauswertung beschreibt, wie ich sie in BNF-Form angegeben habe.

--- Heiko.

[modelnine]

Du machst nichts anderes als einen DKA zu schreiben mit dem was Du beschreibst, nur so nebenbei.

Du tust Dir auf jeden Fall keinen Gefallen wenn Du probierst das ganze selbst zu schreiben, guck doch erst mal ob Du den Parser irgendwie verstehen kannst... Wenn Du die ganzen Leerzeilen und Kommentare rauslöscht wirds wahrscheinlich auch übersichtlicher, ich wage auf jeden Fall zu behaupten dass alles selbstgeschriebene auf keinen Fall besser als das was ich geschrieben habe funktioniert, sondern eher schlechter, weil Du Dich um Operator-Präzedenz, Klammerungen, etc. selbst kümmern mußt. Bei der Grammatik die ich benutzt habe gibts das frei Haus mit.

--- Heiko.

[mr.hide]

Jo, da hast du Recht
Wobei Sich jeder Kellerautomat auch als "normalen" Automat darstellen läßt


Aber dennoch sollte er so etwas selber entwerfen, sonst wird er den Quellcode nie verstehen ...

EDIT: Die Frage ist nur bei was man mehr lernt.
Etwas fertiges findet man natürlich immer.

[modelnine]

Wobei Sich jeder Kellerautomat auch als "normalen" Automat darstellen läßt

Was für ein Quark. Mehr sag ich dazu nicht. Schließlich gibts nicht umsonst die Unterscheidung zwischen rekursiven und nicht rekursiven Sprachen.

Ganz davon abgesehen: Ja, Du hast recht, es ist sicherlich toller so was alleine hinzukriegen. Nur wenn er noch absolut keine Ahnung von Grammatiken, Parsern, u.Ä. hat ist es relativ schwierig sowas auf die Beine zu stellen. Deswegen mein Vorschlag: erst mal verstehen was jemand anderes macht, dann selbst schreiben...

--- Heiko.

[for_maniac]

@modeline

wenn ich deinen code richtig verstanden habe macht er genau das was auf dieser Seite: http://www.willemer.de/informatik/compiler/bspcalc.htm
beschrieben ist. Seh ich das Soweit richtig?

Das entspricht dann glaub ich auch weitest gehend meiner idee nur das ich es nicht so elegant programmiert hätte mit rekursion etc.

[modelnine]

Jein. Er ist ähnlich wie der da präsentierte Parser, nur ist meine Grammatik ein Stückchen komplexer, da sie auch Variablen-Namen, Funktionsaufrufe und Exponierung kennt, und vor allen Dingen ist die Grammatik die dort gezeigt wird links-rekursiv, was sich eigentlich überhaupt nicht dafür eignet in einen "recursive descent"-Parser umzusetzen, während ich die Grammatik genau aus diesem Hinblick rechts-rekursiv gemacht habe. Sonst: es ist mehr oder weniger das selbe, ja.

Elegant programmieren mit Rekursion mußt Du nicht; der Parser kann auch einen externen Stack benutzen, das sieht nur nicht mehr so schön aus. Im Endeffekt ist wie ich bereits sagte die Rekursion nur _eine_ Möglichkeit um einen Kellerautomaten zu emulieren, es geht auch immer der direkte Stack. Wenn ich heute abend noch Zeit habe schreib ich mal ein Programm was einen expliziten Stack benutzt und keine Rekursion.

--- Heiko.

[BlackJack]

Ich hab mich auch mal drangesetzt.

Erstmal ein paar Tips zum C Programm. Die lassen sich teilweise auch auf Python übertragen. So einer ist zum Beispiel: Wo immer es möglich ist Bibliotheksfunktionen benutzen, anstatt etwas selbst zu schreiben. Das setzt natürlich voraus, dass man die entsprechenden Funktionen kennt. Sowohl Python als auch C kommen mit einer recht umfangreichen Bibliothek daher, wobei Python ziemlich viele "High-Level" Module mitbringt, weil man sich um den Kleinkram nicht so sehr wie in C kümmern muss.

Es gibt in C beispielsweise eine Funktion `isdigit()`, die testet ob ein Zeichen eine Ziffer ist. Das ist kürzer und lesbarer als selbst auf Unter- und Obergrenze des entsprechenden Zeichenkodebereichs zu testen.

Das kann man sich in Deinem Taschenrechner aber auch komplett sparen, weil es eine Funktion gibt, die eine Zeichenkette mit Ziffern in ein `double` umwandelt.

Aber fangen wir mal bei der Eingabe an. Das `scanf()` ist gefährlich, weil man mehr als 20 Zeichen eingeben kann und damit einfach Daten über `eingabe` hinaus in den Speicher geschrieben werden. `fgets()` ist immer sicherer, da man dort eine maximale Anzahl von Zeichen angeben kann.

Für das Umwandeln von Zeichenkette mit Ziffern nach `double` gibt's wie gesagt eine Funktion (`atof()`) und man kann mit `strpbrk()` eines aus einer Menge von Zeichen in einer Zeichenkette suchen lassen. Mit diesen beiden Funktionen lässt sich im Grunde in nur drei Zeilen die `eingabe` in zwei Zahlen und einen Operator zerlegen.

Dann kommt die Rechnung. In C bietet sich für die vier ``if``-Abfragen eine ``switch``/``case`` Konstruktion an, und anstelle der Hexadezimalnotation wären einzelne literale Zeichen für die Operatoren lesbarer. Also statt ``0x2b`` ein ``'+'``.

Code: Alles auswählen

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INPUT_SIZE 20

/* Erlaubte Operatoren. */
static const char *OPERATORS = "+-*/";

int main(void)
{
    char eingabe[INPUT_SIZE + 1];
    char *operator;
    double zahl1, zahl2, ergebnis;

    while (1) {
        printf("Geben sie die Rechnung ein (zahl op zahl): ");
        fgets(eingabe, INPUT_SIZE, stdin);
        
        zahl1 = atof(eingabe);
        operator = strpbrk(eingabe, OPERATORS);
        if (operator == NULL) {
            printf("Keine Operation (%s) angegeben.\n", OPERATORS);
            continue;
        }
        zahl2 = atof(operator + 1);
        
        switch (*operator) {
            case '+': ergebnis = zahl1 + zahl2; break;
            case '-': ergebnis = zahl1 - zahl2; break;
            case '*': ergebnis = zahl1 * zahl2; break;
            case '/': ergebnis = zahl1 / zahl2; break;
            default:
                /* Sollte nie ausgeführt werden, solange für jedes Zeichen
                   in `OPERATORS` ein Fall existiert. */
                printf("PANIK! (%s:%d:'%c')", __FILE__, __LINE__, *operator);
                return EXIT_FAILURE;
        }
        
        printf("%.2f %c %.2f = %.2f\n\n", zahl1, *operator, zahl2, ergebnis);
    }
}

Ist etwas kürzer und ohne die ganzen Schleifen und Details übersichtlicher. Kleiner Testlauf:

Code: Alles auswählen

bj@s8n:~> ./a.out
Geben sie die Rechnung ein (zahl op zahl): 42 + 23
42.00 + 23.00 = 65.00

Geben sie die Rechnung ein (zahl op zahl): 1 / 2
1.00 / 2.00 = 0.50

Geben sie die Rechnung ein (zahl op zahl):
Keine Operation (+-*/) angegeben.
Geben sie die Rechnung ein (zahl op zahl): hallo * welt
0.00 * 0.00 = 0.00

Geben sie die Rechnung ein (zahl op zahl): test*
0.00 * 0.00 = 0.00

Geben sie die Rechnung ein (zahl op zahl): -
0.00 - 0.00 = 0.00
Geben sie die Rechnung ein (zahl op zahl): 0x20 + 8
32.00 + 8.00 = 40.00

Hier sieht man einen interessanten Aspekt von `atof()`: Führende Leerzeichen werden ignoriert und bei dem ersten Auftauchen eines Zeichens, das nicht zu einer Fliesskommazahl gehören kann, wird die Konvertierung abgebrochen. Was im Extremfall, also keine gültigen Ziffern, zu einer Null führt. Wenn man etwas mehr Kontrolle über solche Einfabefehler haben möchte, dann kann man `strtod()` zum Umwandeln benutzen, muss aber natürlich noch extra Quelltext zum Erkennen eines Fehlers und entsprechender Reaktion darauf schreiben.

Neben Fliesskommazahlen kann man übrigens auch Hexadezimalzahlen bzw. alle Zahl-Literale eingeben, die man auch in C-Quelltext angeben könnte. Problematisch ist allerdings die Angabe von ``+`` oder ``-`` innerhalb einer Zahl, da das erste Auftreten von so einem Zeichen vom Programm als Operator erkannt wird. Die Zahl ``1e-2`` macht also Probleme, obwohl es sich um eine gültige Fliesskommazahl handelt.

Das C Programm nach Python portiert kann so aussehen:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import division
import operator

operations = { '+': operator.add,
               '-': operator.sub,
               '*': operator.mul,
               '/': operator.truediv }

def main():
    while True:
        line = raw_input('Geben sie die Rechnung ein (Zahl op Zahl): ')
        try:
            components = line.split()
            zahl1 = float(components[0])
            operation = components[1]
            zahl2 = float(components[2])
        except ValueError, error:
            print 'Fehler in einer Zahl:', error
            continue
        except IndexError:
            print ('Zu wenige Angaben. '
                   'Bitte zwei Zahlen und eine Operation angeben.')
            continue
        
        try:
            ergebnis = operations[operation](zahl1, zahl2)
            print '%s %s %s = %s' % (zahl1, operation, zahl2, ergebnis)
        except KeyError:
            print 'Unbekannte Operation %r' % operation


if __name__ == '__main__':
    main()

Ich habe `str.split()` verwendet um die Eingabe zu zerlegen, was natürlich den Anwender im Gegensatz zum C-Programm zwingt, Leerzeichen zwischen die Zahlen und den Operator zu schreiben.

Man sieht zwei wichtige Unterschiede zwischen den Programmen. In Python muss man sich um die Fehler kümmern, da im Python-Zen unter anderem der Satz Errors should never pass silently. steht. Fehler sollten also nie einfach ignoriert oder durch einen vorgegebenen Wert ersetzt werden.

Und es gibt in Python kein ``switch``/``case`` Gegenstück in der Syntax. Das wird oft durch ein Dictionary mit den Fällen als Schlüssel und den dazugehörigen Funktionen als Wert umgesetzt.

Testlauf:

Code: Alles auswählen

Geben sie die Rechnung ein (Zahl op Zahl): 42 + 23
42.0 + 23.0 = 65.0
Geben sie die Rechnung ein (Zahl op Zahl): 1 / 2
1.0 / 2.0 = 0.5
Geben sie die Rechnung ein (Zahl op Zahl): 5 # 5
Unbekannte Operation '#'
Geben sie die Rechnung ein (Zahl op Zahl):
Zu wenige Angaben. Bitte zwei Zahlen und eine Operation angeben.
Geben sie die Rechnung ein (Zahl op Zahl): 7 -
Zu wenige Angaben. Bitte zwei Zahlen und eine Operation angeben.
Geben sie die Rechnung ein (Zahl op Zahl): 0x20 + 8
32.0 + 8.0 = 40.0
Geben sie die Rechnung ein (Zahl op Zahl): abc * def
Fehler in einer Zahl: invalid literal for float(): abc

Für kompliziertere Ausdrücke kann man sich natürlich einen Parser komplett selbst schreiben, aber das sollte man höchstens zu Lernzwecken machen. Für den "echten" Einsatz sind Parsergeneratoren vorzuziehen, denen man eine Grammatik vorgibt und die dann den Quelltext für einen Parser generieren. Für C ist das traditionell ``lex``/``yacc`` bzw. ``bison``. Für Python finde ich pyparsing sehr interessant. Dort setzt man eine Grammatik zur Laufzeit aus Objekten zusammen. Die Schreibweise erinnert an EBNF-Notation.

EBNF-Notation ist eine gängige Möglichkeit eine Grammatik zu beschreiben. Für die vier Grundrechenarten mit Klammerung für ganze Zahlen könnte eine EBNF-Grammatik so aussehen:

Code: Alles auswählen

<add_op>     ::= '+' | '-'
<mult_op>    ::= '*' | '/'
<number>     ::= <digit> | <digit> <digits>
<digit>      ::= '0' | '1' | '2' | ... | '9'
<atom>       ::= <number> | '(' <expression> ')'
<term>       ::= <atom> | <atom> <mult_op> <term>
<expression> ::= <term> | <term> <add_op> <expression>

Das man nicht einfach ``<expression> <op> <expression>`` schreiben kann, liegt daran, dass man "Punkt-vor-Strichrechnung" und Klammerung damit nicht gewährleistet. Durch das Einfügen von ``<term>`` und die Aufteilung der "Punkt"- und "Strich"rechenzeichen ist der übliche Operatorvorrang sichergestellt.

Der Syntaxbaum für den Ausdruck ``1+2*3`` sieht dann so aus (Übergang von Ziffern zu ``<atom>`` ist verkürzt dargestellt):

Code: Alles auswählen

        <expression>
             |
    +--------+-----------------+
    |        |                 |
    |        |            <expression>
    |        |                 |
    |        |              <term>
    |        |                 |
    |        |        +--------+---------+
    |        |        |        |         |
 <term>      |        |        |      <term>
    |        |        |        |         |
 <atom>  <add_op>  <atom>  <mult_op>  <atom>
    |        |        |        |         |
   '1'      '+'      '2'      '*'       '3'

Das die Klammerung funktioniert kann man am Syntaxbaum für den Ausdruck ``2*(3+4)`` sehen:

Code: Alles auswählen

        <expression>
             |
          <term>
             |
    +--------+--------------------+
    |        |                    |
    |        |                 <term>
    |        |                    |
    |        |                 <atom>
    |        |                    |
    |        |     +--------------+----------------+
    |        |     |              |                |
    |        |     |         <expression>          |
    |        |     |              |                |
    |        |     |     +--------+--------+       |
    |        |     |     |        |        |       |
    |        |     |     |        |   <expression> |
    |        |     |     |        |        |       |
    |        |     |  <term>      |     <term>     |
    |        |     |     |        |        |       |
 <atom>  <mult_op> |  <atom>  <add_op>  <atom>     |
    |        |     |     |        |        |       |
   '2'      '*'   '('   '3'      '+'      '4'     ')'

Die Grammatik mit `pyparsing` ausgedrückt, sieht so aus:

Code: Alles auswählen

from pyparsing import Word, Forward, ZeroOrMore, Suppress, Group, oneOf, nums

def grammar():
    add_op = oneOf('+ -')
    mult_op = oneOf('* /')
    number = Word(nums)
    expression = Forward()
    atom = number | Suppress('(') + expression + Suppress(')')
    term = Forward()
    term << Group(atom + ZeroOrMore(mult_op + term))
    expression << term + ZeroOrMore(add_op + expression)
    return expression

def test():
    parser = grammar()
    for test in ('1 + 2 * 3',
                 '2 * (3 + 4)',
                 '1 + 2 - 3',
                 '2 * 3 / 4'):
        result = parser.parseString(test).asList()
        print '%15s => %s = %f' % (test, result, evaluate(result))

Das Ergebnis der Testfunktion:

Code: Alles auswählen

      1 + 2 * 3 => [['1'], '+', ['2', '*', ['3']]]
    2 * (3 + 4) => [['2', '*', [['3'], '+', ['4']]]]
      1 + 2 - 3 => [['1'], '+', ['2'], '-', ['3']]
      2 * 3 / 4 => [['2', '*', ['3', '/', ['4']]]]
 

Man bekommt also verschachtelte Listen, bei denen an den geraden Indizes die Zahlen oder Unterlisten und an den ungeraden Indizes die Operationen stehen. Das lässt sich mit einer rekursiven Funktion leicht auswerten.

Code: Alles auswählen

def evaluate(ast):
    numbers = list()
    for element in ast[::2]:
        if isinstance(element, list):
            numbers.append(evaluate(element))
        else:
            numbers.append(int(element))
    result = numbers[0]
    for operation, number in zip(ast[1::2], numbers[1:]):
        result = operations[operation](result, number)
    return result

Im Archiv von `pyparsing` befinden sich zwei etwas umfangreichere Beispiele für das Auswerten von Ausdrücken bzw. ein kompletter Taschenrechner mit Funktionen und Variablenzuweisungen.

Die einfachste Art (ausser ``eval``) einen Taschenrechner zu programmieren, dürfte die umgekehrte Polnische Notation sein (Reverse Polish Notation, kurz RPN), welche eindeutige Auswertung von Ausdrücken ohne Klammerung erlaubt. Dabei werden erst die Operanden und dann die Operationen angegeben. Die Operanden (Zahlen) landen auf einem Stapel und die Operationen holen sich von dort ihre Argumente und legen das Ergebnis wieder auf dem Stapel ab.

Man kann ganz einfach Operationen definieren, die mehr oder weniger als zwei Operanden erwarten. Sogar solche, die keinen Operanden erwarten, also Konstanten.

Code: Alles auswählen

import math
import operator

def create_rpnfunc(func, arg_count):
    if arg_count > 0:
        def rpn_func(stack):
            args = stack[-arg_count:]
            stack[-arg_count:] = []
            stack.append(func(*args))
    else:
        rpn_func = lambda stack: stack.append(func())
    return rpn_func

def create_rpnfuncs():
    operations = (# Operations with 0 operands.
                  (('PI', lambda: math.pi),
                   ('E', lambda: math.e)),
                  # Operations with 1 operand.
                  (('negate', operator.neg),
                   ('abs', operator.abs),
                   ('invert', operator.invert),
                   ('sin', math.sin),
                   ('cos', math.cos),
                   ('radians', math.radians),
                   ('degrees', math.degrees)),
                  # Operations with 2 operands.
                  (('+', operator.add),
                   ('-', operator.sub),
                   ('*', operator.mul),
                   ('/', operator.truediv),
                   ('^', operator.pow),
                   ('modulo', operator.mod)))
    
    result = dict()
    for arg_count, ops in enumerate(operations):
        for name, func in ops:
            result[name] = create_rpnfunc(func, arg_count)
    return result

rpn_operations = create_rpnfuncs()

def rpn_evaluate(expression):
    stack = list()
    for element in expression.split():
        try:
            stack.append(float(element))
        except ValueError:
            try:
                rpn_operations[element](stack)
            except KeyError:
                raise Exception('Unknown operation %r' % element)
    return stack

def rpn_test():
    for test in ('1 2 3 * +',
                 '2 3 4 + *',
                 '1 2 3 - +',
                 '2 3 4 / *',
                 '2 PI * degrees sin'):
        print test, '=', rpn_evaluate(test)

[for_maniac]

Estmal Danke an alle für die Umfangreiche hilfe, mit den ganzen sachen bin ich erstmal eine weile beschäftigt.
Könnt ihr mir auch irgendwelche Bücher oder Websites zu diesen Thema (Grammatik, Automaten, Bäume etc.) empfehlen, damit ich eine Beschäftigung in den Semesterferien habe, nur E-Technik wird auch langweilig ?

MFG for_maniac

[mr.hide]

"Grundlagen der Informatik" Da ist auch ein Programm zum simulieren von Automaten dabei, das ist recht gut.

Werd wohl mein Wissen über Automaten auch noch mal auffrischen

[helmut]

Hallo Matthias,

welches Buch meinst Du. Bei amazon werden 4 unterschiedliche Bücher mit dem Titel "Grundlagen der Informatik" aufgeführt.

- VMI Buch AG - Aho, Jeffrey, Ullman
- Oldenbourg - Pepper
- Hanser Fachbuchverlag - Walter
- Vieweg - Schaback

Gruss, Helmut

[modelnine]

Auch hier kann ich nur "Aho und Ullmann" empfehlen.

--- Heiko.

[mr.hide]

Die ISBN ist:
3446229876

Ich fand es eigentlich recht gut.

Gut finde ich die Beispiele mit dem beiliegenden Programm "Machines"
Aber ich glaub das ist Freeware und dürfte auch so aufzutreiben sein.