Auswahl Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
| Autor |
 Mathematische Terme als formale Sprache |
|
goeba
Senior 
Dabei seit: 24.03.2006
Mitteilungen: 1315
Aus: Göttingen
 |      Themenstart: 2010-04-04 12:47
|
Hallo,
kennt jemand eine Webseite, wo mathematische Terme als formale Sprache definiert sind?
Was ich meine, sind Ersetzungsregeln vom Typ
S -> S + S
S -> S * S
uswusf.
Ich würde das wohl auch selbst hinkriegen, aber ich würde mir die Arbeit gerne sparen.
LG
Andreas
|
 Profil
 www
 Quote
 Link |
Buri
Senior 
Dabei seit: 02.08.2003
Mitteilungen: 34707
Aus: Dresden
 | Beitrag No.1, eingetragen 2010-04-04 13:27
|
Hi Andreas,
bei älteren Programmiersprachen war es üblich, eine Syntaxbeschreibung in der sog. Backus-Naur-Form an das Programmierhandbuch anzuhängen, zuerst geschah dies im Jahre 1958 bei der Sprache, die später ALGOL 60 hieß, und die ich im Studium gelernt und angewendet habe.
Auch für die Datenbanksprache SQL (die es in unzähligen Versionen gibt, die sich keineswegs immer alle gut vertragen, wie es eigentlich mit der Schaffung von SQL gedacht war) gibt es solche Beschreibungen.
Heutzutage stehen in einem Programmierhandbuch ganz andere Dinge im Vordergrund, man programmiert eigentlich kaum noch, sondern klickt sich sein Projekt aus irgendwelchen Klassenbibliotheken zusammen, das Handbuch beschreibt ausführlich, welche Werkzeugleisten es gibt und was in den Menüs geschieht, und die eigentliche Beschreibung der Programmiersprache ist zwar irgendwo noch vorhanden, aber sehr in den Hintergrund getreten, und sie liegt meistens nicht in Backus-Naur-Form vor, sondern eher als eine Art Sammlung von Kochrezepten, die mit nützlichen Beispielen erläutert sind.
Also schau mal nach, ob du irgendwo Handbücher zu älteren Programmiersprachen findest, zum Beispiel könnte man das Buch von Niklaus Wirth nehmen, in dem er die Sprache PASCAL einführt, oder das Standardwerk von Kernighan / Ritchie über die Sprache C.
Über dieses Werk wurde hier im Forum geschrieben, daß es für Anfänger nicht geeignet ist, jedoch für den von dir gewünschten Zweck sollte es gut geeignet sein.
Gruß Buri
|
Profil
Quote
Link |
goeba
Senior
Dabei seit: 24.03.2006
Mitteilungen: 1315
Aus: Göttingen
| Beitrag No.2, vom Themenstarter, eingetragen 2010-04-04 14:46
|
Ich glaube, dann würde ich schon eher in ein Buch über theoretische Informatik schauen. Das wird ja heutzutage auch immer noch so gemacht, zumindest, wenn man Informatik richtig sutiert.
Ich kann ja mal anfangen. Als Startsymbol nehme ich T. Dann habe ich folgende Nichtterminale:
T: Startsymbol
S: Summe
D: Differenz
P: Produkt
Q: Quotienz
H: Potenz (H wie woch)
SR: Strichrechnung
PR: Punktrechnung
(V: Vorzeichenminusterm)
Das mit dem Vorzeichenminus lasse ich erst mal weg.
Terminale: +, -, *, /, (, ), Zahl
(das mit den Zahlen brauche ich nicht streng formal, weil ich später mit einem Computerprogramm zufällige Terme erzeugen will).
Jeder Term ist eine Summe, Differenz, Produkt, Quotient, Potenz
Also erst mal
T->SR
T->PR
T->H
SR->S
SR->D
PR->P
PR->Q
Dann habe ich
S->T+T (müsste so einfach sein, weil ich hier keine Klammern setzen muss)
D->T-(SR)
D->T-PR
D->T-H
P->(SR)*(SR)
P->PR*PR
(und Mischungen der beiden)
Hat bis hier jemand Anregungen, ob das evtl. auch einfacher geht? Ich denke, dass man, wenn man keine überflüssigen Klammern haben möchte, es so kompliziert machen muss.
[ Nachricht wurde editiert von goeba am 04.04.2010 15:02:18 ]
|
Profil
www
Quote
Link |
goeba
Senior 
Dabei seit: 24.03.2006
Mitteilungen: 1315
Aus: Göttingen
| Beitrag No.3, vom Themenstarter, eingetragen 2010-04-04 14:57
|
Ich glaube, es ist besser, noch zwei nichtterminale dazuzunehmen:
SR: Strichrechnung
PR: Punktrechnung
Ich ändere obigen Post diesbezüglich.
|
Profil
www
Quote
Link |
Rene_R
Senior 
Dabei seit: 18.02.2009
Mitteilungen: 253
Aus:
| Beitrag No.4, eingetragen 2010-04-04 15:10
|
Bisher hast du aber das Problem, dass du niemals mit deiner Erzeugung fertig wirst, weil du ständig neue Nichtterminale mit erzeugst. Ich würde das Ganze eher so angehen:
Nichtterminale: S (Startsymbol), Z (Zahl)
Terminale: +, -, *, /, (, ), 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
S -> S+S
S -> (S+S)
S -> S*S
S -> (S*S)
S -> S-S
S -> (S-S)
S -> S/S
S -> (S/S)
S -> Z
Jetzt müsstest du dir nurnoch Ableitungsregeln für Z definieren, was ein wenig komplizierter werden kann. Dabei kann es sinnvoll sein noch ein paar Nichtterminale zu definieren, damit du keine führenden Nullen oder mehrere Kommas hast. Das könnte dann etwa in folgender Art geschehen:
Z -> N
Z -> N,M
N -> 1M
N -> 2M
N -> 3M
N -> 4M
N -> 5M
N -> 6M
N -> 7M
N -> 8M
N -> 9M
M -> 0
M -> 0M
M -> 1
M -> 1M
M -> 2
M -> 2M
M -> 3
M -> 3M
M -> 4
M -> 4M
M -> 5
M -> 5M
M -> 6
M -> 6M
M -> 7
M -> 7M
M -> 8
M -> 8M
M -> 9
M -> 9M
Grüße
René
[ Nachricht wurde editiert von Rene_R am 04.04.2010 15:13:05 ]
|
Profil
Quote
Link |
Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 34707
Aus: Dresden
| Beitrag No.5, eingetragen 2010-04-04 15:37
|
2010-04-04 14:57 - goeba in Beitrag No. 3 schreibt:
Ich glaube, es ist besser, noch zwei nichtterminale dazuzunehmen: Hi goeba,
nein, ich glaube nicht, daß das gut ist.
Außerdem sollte es nur eine einzige Regel geben, in der Klammern vorkommen. Sie besagt im wesentlichen, daß das Einklammern absoluten Vorrang hat und ein eingeklammerter Term genau so zu behandeln ist wie ein Atom der Sprache (also wie eine Zahl oder eine Variable).
Die Vorrangregeln werden dadurch zur Wirkung gebracht, daß man die Produktionsregeln geeignet aufbaut.
Eigentlich ist es doch Standard und viele Tausend Mal gemacht worden, wie solche Regeln aussehen müssen. Unterschiede gibt es nur insofern, als man die Potenzierung mit dazunehmen kann oder auch nicht, und man kann auch logische Ausdrücke und Vergleiche mit dazunehmen (was natürlich in jeder vernünftigen Programmiersprache mit dazugehört).
Die Potenzierung wird von Compilerentwicklern leider recht stiefmütterlich behandelt, wie ich bereits anderswo im Forum erwähnt habe. Das einzig Vernünftige ist, diese Operation als rechts-assoziativ anzunehmen, wie es auch in der Mathematik üblich ist, sonst kann es zu sehr paradoxen Situationen kommen.
Meine Nichtterminalsymbole sind Ausdruck, Summand, Faktor, Atom.
Das Satzsymbol ist "Ausdruck", dieses Symbol bezeichnet sozusagen "alles, was es überhaupt gibt", und meine Regeln sind diese:
Ausdruck -> Summand
Ausdruck -> Ausdruck + Summand
Ausdruck -> Ausdruck - Summand
Ausdruck -> + Summand
Ausdruck -> - Summand
Summand -> Faktor
Summand -> Summand * Faktor
Summand -> Summand / Faktor
Faktor -> Atom
Faktor -> Atom ^ Faktor
Atom -> (Ausdruck)
Atom -> jedes beliebige Terminalsymbol.
Bei diesen Regeln werden die einstelligen Operatoren + und - mit gleichem Vorrang behandelt wie die zweistelligen, weil ich das für sinnvoll halte. Bei anderslautender Festlegung muß man die Regeln ein wenig umstellen, aber dazu habe ich keine Lust.
Die rot hervorgehobene Regel wird in den üblichen Sprachen andersherum genommen, also links-assoziativ, außer zum Beispiel in Mathematica und noch weiteren Sprachen.
Gruß Buri
[Die Antwort wurde nach Beitrag No.3 begonnen.]
|
Profil
Quote
Link |
goeba
Senior
Dabei seit: 24.03.2006
Mitteilungen: 1315
Aus: Göttingen
| Beitrag No.6, vom Themenstarter, eingetragen 2010-04-04 15:42
|
@Rene: Danke. Die Zahlen aber , wie gesagt, will ich nicht formal erzeugen.
@Buri: Ich fürchte, ich habe meine Aufgabenstellung nicht wirklich erläutert, weswegen wir jetzt unterschiedliche Sachen machen.
Ich will tatsächlich Terme mit meiner Grammatik erzeugen, und ich will dabei überflüssige Klammern vermeiden.
Wenn ich also ein Produkt habe, dann soll das z.B. P*P sein, wenn beide Faktoren ebenfalls Produkte sind, und P*(S), wenn z.B. der zweite eine Summe ist und ich die Klammern brauche.
Deine Grammatik erzeugt alle grammatikalisch korrenten Terme, löst aber, glaube ich, nicht meine Aufgabe.
Am Ende soll ein Programm herauskommen, das zufällig Rechenaufgaben von einstellbarer Komplexität erzeugt (wie komplex die Aufgabe ist, wird dadurch eingestellt, wie oft ich das Ersetzen von Nichtterminalen durch Nichtterminale zulasse).
LG
Andreas
|
Profil
www
Quote
Link |
Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 34707
Aus: Dresden
| Beitrag No.7, eingetragen 2010-04-04 16:22
|
2010-04-04 15:42 - goeba in Beitrag No. 6 schreibt:
1. Deine Grammatik erzeugt alle grammatikalisch korrenten Terme ...
2. löst aber, glaube ich, nicht meine Aufgabe. Hi goeba,
1. Ja, aber sie tut noch mehr. Sie legt auch fest, wie ein gegebener Ausdruck zu "parsen" ist.
2. Ich habe versucht, auf deine Frage zu antworten, aber es mag sein, daß ich dein Problem nicht richtig verstanden habe.
Ein Ausdruck der Form A * B + C gehört zur Sprache, aber das "Parsen" kann nur in der Form (A * B) + C geschehen, dafür sorgt die Art, wie die Regeln formuliert sind.
Dagegen kann man A * (B + C) nur so parsen, wie es mit Hilfe der Klammern angegeben ist.
Gruß Buri
|
Profil
Quote
Link |
TheBear
Senior
Dabei seit: 31.01.2006
Mitteilungen: 1223
Aus:
| Beitrag No.8, eingetragen 2010-04-04 17:32
|
Moin zusammen.
Mir scheint, dass ihr die Sache von der falschen Seite angeht, die bisher genannten Grammatiken sind eher geeignet, Ausdrücke zu parsen, nicht um sie zu generieren. Das liegt daran, dass ihr die konkrete Syntax der Ausdrücke zu beschreiben versucht, nicht die abstrakte Syntax. Nützlich wäre es eher, den Term als abstrakten Syntaxbaum (AST) zu generieren, und den Baum dann in einem inorder-Durchlauf auszugeben, wobei man die Klammern einfügt.
Als abstrakte Grammatik könnte man am z.B. folgendes nehmen:
Term -> Term Operator Term
Term -> Zahl | Variable
Operator -> '+' | '-' | '*' | '/' | '^'
Man beachte: In der Grammatik ist nirgends die Rede von Klammern, der Vorrang wird eindeutig dadurch geregelt, dass man einen Ausdruck als Baum speichert.
Beim Ausgeben schaut man, welche Präzedenz ein Kindknoten im Vergleich zur eigenen Präzedenz hat:
1. Hat er eine niedrigere Präzedenz, macht man beim Ausgeben Klammern drum.
2. Hat er die selbe Präzedenz und der aktuelle Operator ist nicht assoziativ (z.B. '-', '^' und '/'), macht man man ebenso Klammern drum.
3. Hat er eine höhere Präzedenz, gibt man ihn ohne Klammern aus.
Gruß TheBear
|
Profil
Quote
Link |
goeba
Senior
Dabei seit: 24.03.2006
Mitteilungen: 1315
Aus: Göttingen
| Beitrag No.9, vom Themenstarter, eingetragen 2010-04-04 18:20
|
@TheBear: Genau so werde ich es machen, das ist mir beim Spülen auch so gekommen.
@Buri: Aus Interesse: Sehe ich das richtig, dass Deine Grammatik auch Terme mit überflüssigen Klammern erzeugt, und würde meine Grammatik alle gültigen Terme ohne überflüssige Klammern erzeugen, wenn ich das so weiter durchziehen würde? Mir ist klar, dass Deine Grammatik für den üblichen Zweck, das Parsen, die sinnvollere ist.
LG
Andreas
|
Profil
www
Quote
Link |
Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 34707
Aus: Dresden
| Beitrag No.10, eingetragen 2010-04-04 18:35
|
2010-04-04 18:20 - goeba in Beitrag No. 9 schreibt:
@Buri: Aus Interesse: Sehe ich das richtig, dass Deine Grammatik auch Terme mit überflüssigen Klammern erzeugt ... Hi Andreas,
ja, natürlich. Es werden alle gültigen Ausdrücke erzeugt, auch solche mit überflüssigen Klammern. Im Thementitel ist das nicht erwähnt, die Frage kam später dazu.
Die Überlegungen von TheBear finde ich gut.
Ich möchte noch hinzufügen, daß man einen als Baum gespeicherten Ausdruck auch als vollständig geklammerten Ausdruck schreiben kann (aber dies ist schon kein beliebiger Ausdruck mehr, man darf das, was bereits geklammert ist, nicht noch einmal klammern), ferner kann man auch die umgekehrte polnische Notation verwenden, das ist alles äquivalent. Es handelt sich dann um die Aufgabe, in einem vollständig geklammerten Ausdruck die überflüssigen Klammern aufzuspüren, und TheBear hat angedeutet, wie man das tun kann, und dabei kann man die Einzelheiten noch genauer erklären, am besten an mehreren einfachen Beispielen.
Gruß Buri
|
Profil
Quote
Link |
goeba
Senior
Dabei seit: 24.03.2006
Mitteilungen: 1315
Aus: Göttingen
| Beitrag No.11, vom Themenstarter, eingetragen 2010-04-04 22:55
|
Ok,
ich habe das mal programmiert.
Hier eine Beispielausgabe, wobei einmal (oben) als Terminale Brüche zugelassen wurden, einmal (unten) nicht:
Ich habe, da man das ja möglichst im Kopf rechnen soll, als Exponenten generell nur natürliche Zahlen zugelassen, und habe auch den Zahlenbereich klein gewählt.
Trotzdem gibt es das ein oder andere Problem ;-)
Jedenfalls war es erst mal ein nettes Gedankenexperiment!
LG
Andreas
|
Profil
www
Quote
Link |
goeba
Senior
Dabei seit: 24.03.2006
Mitteilungen: 1315
Aus: Göttingen
| Beitrag No.12, vom Themenstarter, eingetragen 2010-04-04 23:05
|
Hier noch die Termklasse, die das erzeugt:
c++ //Definition der Klasse Term
//ZUm zufaelligen Erzeugen von Aufgaben
#ifndef TERM_H
#define TERM_H
#include <wx/string.h>
#include <vector>
#include "bruch.h"
#include <cmath>
#include <cstdlib>
class Term{
public:
Term();
wxString AusgabeLatex();
wxString Ausgabe();
static int Maxtiefe;
void ErzeugeZufaellig(int tiefe, bool Nurzahl = false);
enum{BRUCH, ZAHL, SUMME, PRODUKT, DIFFERENZ, QUOTIENT, POTENZ};
static int Zufall(int min, int max){return rand()%(max+1-min) + min ;}
int Termart;
private:
std::vector<Term*> Subterme;
int Zahlwert;
bruch Bruchwert;
};
#endif
|
c++ //Implementation der Klasse Term
#include "term.h"
int Term::Maxtiefe = 5;
Term::Term(){
Zahlwert = 0;
}
void Term::ErzeugeZufaellig(int tiefe, bool Nurzahl){
int Art=0;
if (tiefe == Maxtiefe)
Art = Zufall(ZAHL, ZAHL);
else
Art = Zufall(ZAHL, POTENZ);
if (Nurzahl)
Art = ZAHL;
Termart = Art; //Eigentlich bloed
switch (Art){
case ZAHL:
Zahlwert = Zufall(2,5);
break;
case BRUCH:
Bruchwert = bruch(1,5,2,5);
break;
default:
Subterme.push_back(new Term() );
Subterme.push_back(new Term() );
Subterme[0]->ErzeugeZufaellig(tiefe+1);
if (Art == POTENZ)
Subterme[1]->ErzeugeZufaellig(tiefe+1, true);
else
Subterme[1]->ErzeugeZufaellig(tiefe+1);
}
}
wxString Term::Ausgabe(){
wxString rueck;
bool muss = false;
switch(Termart){
case ZAHL:
rueck << Zahlwert;
break;
case BRUCH:
rueck << Bruchwert.Ausgabe();
break;
case SUMME:
rueck << Subterme[0]->Ausgabe() << "+" << Subterme[1]->Ausgabe();
break;
case DIFFERENZ:
rueck << Subterme[0]->Ausgabe() << "-";
//Wenn auf der rechten Seite Summe oder Differenz steht
//Muss eine Klammer drum:
muss = (Subterme[1]->Termart == SUMME) || (Subterme[1]->Termart == DIFFERENZ);
if (muss) rueck << "(";
rueck << Subterme[1]->Ausgabe();
if (muss) rueck << ")";
break;
case PRODUKT:
muss = (Subterme[0]->Termart == SUMME) || (Subterme[0]->Termart == DIFFERENZ);
if (muss) rueck << "(";
rueck << Subterme[0]->Ausgabe();
if (muss) rueck << ")";
rueck << "*";
muss = (Subterme[1]->Termart == SUMME) || (Subterme[1]->Termart == DIFFERENZ);
if (muss) rueck << "(";
rueck << Subterme[1]->Ausgabe();
if (muss) rueck << ")";
break;
case QUOTIENT:
muss = (Subterme[0]->Termart == SUMME) || (Subterme[0]->Termart == DIFFERENZ);
if (muss) rueck << "(";
rueck << Subterme[0]->Ausgabe();
if (muss) rueck << ")";
rueck << "/";
muss = (Subterme[1]->Termart == SUMME) ||
(Subterme[1]->Termart == DIFFERENZ) ||
(Subterme[1]->Termart == QUOTIENT) ||
(Subterme[1]->Termart == BRUCH);
if (muss) rueck << "(";
rueck << Subterme[1]->Ausgabe();
if (muss) rueck << ")";
break;
case POTENZ:
muss = !( (Subterme[0]->Termart == POTENZ) ||
(Subterme[0]->Termart == ZAHL) );
if (muss) rueck << "(";
rueck << Subterme[0]->Ausgabe();
if (muss) rueck << ")";
rueck << "^";
muss = !( (Subterme[1]->Termart == POTENZ) ||
(Subterme[1]->Termart == ZAHL) );
if (muss) rueck << "(";
rueck << Subterme[1]->Ausgabe();
if (muss) rueck << ")";
break;
}
return rueck;
}
wxString Term::AusgabeLatex(){
wxString rueck;
bool muss = false;
switch(Termart){
case ZAHL:
rueck << Zahlwert;
break;
case BRUCH:
rueck << Bruchwert.AusgabeLatex();
break;
case SUMME:
rueck << Subterme[0]->AusgabeLatex() << "+" << Subterme[1]->AusgabeLatex();
break;
case DIFFERENZ:
rueck << Subterme[0]->AusgabeLatex() << "-";
//Wenn auf der rechten Seite Summe oder Differenz steht
//Muss eine Klammer drum:
muss = (Subterme[1]->Termart == SUMME) ||
(Subterme[1]->Termart == DIFFERENZ);
if (muss) rueck << " \\left( ";
rueck << Subterme[1]->AusgabeLatex();
if (muss) rueck << " \\right) ";
break;
case PRODUKT:
muss = (Subterme[0]->Termart == SUMME) || (Subterme[0]->Termart == DIFFERENZ);
if (muss) rueck << " \\left( ";
rueck << Subterme[0]->AusgabeLatex();
if (muss) rueck << " \\right) ";
rueck << "\\cdot ";
muss = (Subterme[1]->Termart == SUMME) ||
(Subterme[1]->Termart == DIFFERENZ);
if (muss) rueck << " \\left( ";
rueck << Subterme[1]->AusgabeLatex();
if (muss) rueck << " \\right) ";
break;
case QUOTIENT:
//Quotienten in Latex als Brueche
rueck << " \\frac{ " << Subterme[0]->AusgabeLatex() <<
"}{" << Subterme[1]->AusgabeLatex() << "}";
break;
case POTENZ:
muss = !( (Subterme[0]->Termart == POTENZ) || (Subterme[0]->Termart == ZAHL) );
if (muss) rueck << " \\left( ";
rueck << "{" << Subterme[0]->AusgabeLatex() << "}";
if (muss) rueck << " \\right) ";
rueck << "^";
muss = !( (Subterme[1]->Termart == POTENZ) || (Subterme[1]->Termart == ZAHL) );
if (muss) rueck << " \\left( ";
rueck << Subterme[1]->AusgabeLatex();
if (muss) rueck << " \\right) ";
break;
}
return rueck;
}
|
[ Nachricht wurde editiert von goeba am 05.04.2010 09:42:08 ]
|
Profil
www
Quote
Link |
|
Wie unterstütze ich den Matheplaneten mit Geld?
[Neues Thema]