FunktionsParser schreiben

[das-mo]

Hi,
Ich programmiere mit einem Freund in der Schule zusammen einen Funktionsplotter und mein Ziel ist es dabei auch gleich einen schönen Parser mit einzubauen. Ich habe mich schon ein bisschen durchs WWW gelesen und hab auch bisschen Lektüre (Compiler-Bau Teil1,2). Ich habe nur ein kleines Problem.
Ich weiß einfach nicht wie und wo ich anfangen soll. Ja also ich habe die Funktion an sich, bzw. das anch dem f(x)= und das muss ich aufsplitten. Ich denke auch das es sinnvoll ist die einzelnen Ausdrücke mit dem jeweiligen Vorzeichen einzeln zu "speichern" und dann aufzulösen, da ich evtl. noch die Ableitung berechnen möchte und das geht mit Kntoten ja schlecht (?oder?). So ich denke dieses erste Aufsplitten ist mit einer Schleife und 2-3 abfragen schnell geschrieben. Nur wie mache ich dann am besten weiter. "Speicher" ich die Ausdrücke jeweils in einzelnen Obejkten einer eigenen Klasse? Und wie gehe ich am besten mit potenzen und sin,cos,sprt .... um ?

Gruß das-mo

 

[kirax]

Es macht auf jeden Fall Sinn, die Ausdrücke zu trennen und getrennt zu speichern.
Spontan würde mir eine Baumstruktur in den Sinn kommen, damit kannst du gleich die Hierarchie bei den Rechenregeln abbilden. Z.B.

(5+4)*3^2

wird ca. zu

[*]------+
 |       |
[^]-+  [( )]
 |  |    |
 3  2   [+]--+
         |   |
         5   4

Und das kannst du dann von (links) unten nach oben durcharbeiten.

 

[das-mo]

Ok Danke.
So in etwa mit einer Baumstruktur hab ich mir das auch gedacht nur da hab ich jetzt ne Frage.
Setz ich vor dem Parsen einen Wert für x ein oder lös ich die funktion erst auf und setze dann ein?

 

[Cola_Colin]

Erst in die Baumstruktur zerlegen und diese dann mit dem Wert versorgen, würde ich spontan sagen.

 

[das-mo]

Aber wie speicher ich denn jede einzelne zahl und jeden operator etc. ab, sodass ich das am ende noch ausrechnen und evtl ableiten kann?

 

[Antoras]

Schau dir mal die beiden Tutorials hier an: Interpreterbau - Ein Anfang und Compilerbau
Beide beschreiben den Aufbau eines Recursive Descent Parsers (RDP) und geben einen kleinen Einblick in die Materie. Der Code ist zwar in C++ verfasst aber gut mit Text erklärt - es sollte also kein Problem sein zu verstehen wie vorgegangen wird, auch wenn du kein C++ kannst.

Ich hab in Java auch mal eine Implementierung eines kleinen Matheparsers geschrieben, der Funktionen und Konstanten erkennen kann (ebenfalls auf Basis eines RDP). Wenn du willst kann ich den Code posten.

 

[das-mo]

Das mit dem Code wäre nett, weil mein größtes Problem liegt, wen ich mal so weiter drüber nachdenke, wie ich denn letztendlich die einzelnen erkannten Teile(Ausdrücke, operatoren, Potenzen,...) abspeicher und nacher zusammenfüge. Aber Danke auch für die links, werd mich da mal bisschen umgucken.

 

[Antoras]

weil mein größtes Problem liegt, wen ich mal so weiter drüber nachdenke, wie ich denn letztendlich die einzelnen erkannten Teile(Ausdrücke, operatoren, Potenzen,...) abspeicher und nacher zusammenfüge

In einem Parsebaum. Aber das Prinzip ist in den Tutorials beschrieben.

Der Java-Code ist nicht dokumentiert, funktioniert aber auch nach dem RDP-Prinzip. Mehr dazu erklärt dir Wikipedia oder die Tutorials. Testen kannst du den Code z.B. damit:

import de.interpreter.ScriptEngine;

public class InterpreterTest {

	public static void main(final String... args) throws IOException {
		final String s1 = "(10+5)-3*(2-(10/5)*+2)-100-((((-100)+1)+1)+1)*(40-2)+((((-100)+1)+1)+1)-(10+5)-3*(2-(10/5)*2)-100-((((-100)+1)+1)+1)*(40-2)+((((-100)+1)+1)+1)";
		final String s2 = "11+max(5,6)+min(2,max(4,11))*2";
		final String s3 = "def hello() { 50 + 3 }";
		final String s4 = "min(4,9,13,1,84)";
		final String s5 = "2*3)";
		final String s6 = "uga()";
		
		final ScriptEngine se = new ScriptEngine();
		System.out.println(se.parse(s1).eval()); // 6990
		System.out.println(se.parse(s2).eval()); // 21
		System.out.println(se.parse(s3).eval()); // 53
		System.out.println(se.parse(s4).eval()); // 1
		try {System.out.println(se.parse(s5).eval()); } catch (final Exception e) { e.printStackTrace(); }
		try {System.out.println(se.parse(s6).eval()); } catch (final Exception e) { e.printStackTrace(); }
	}
}

Wichtig sind eigentlich bloß die parse- und eval-Methoden. Eine EBNF nach der der Code vorgeht liegt bei.

 

[das-mo]

Womit hast du das geschrieben, ich find mich in dem Ordner nicht zurecht.^^

 

[Antoras]

> Womit hast du das geschrieben
Mit meiner IDE?
> ich find mich in dem Ordner nicht zurecht
Alles unterhalb von src sind die Sourcen, dann gibt es noch die EBNF und sonst ist da nichts. Wie du die Sourcen ausführst musst du schon selbst wissen. Am einfachsten ist es wohl die von deiner IDE zu importieren und dann mit dem Testcode, den ich oben gepostet habe, auszuführen.

 

[das-mo]

Bisschen rumgespielt und habs dann irgndwann reinbekommen.

Ich habe eine kleine Frage nebenbei:
Wie erstelle ich eine generische Arraylist? Ich habe die Klasse Token und möchte dort immer die gescannten Token vermerken. Ich krieg nur immer eine Fehlermeldung bei der Erstellung der Arraylist zurück:

  ArrayList<Token> obj_token = new ArrayList<Token>();

ERR: <bezeichner> erwartet

 

[Antoras]

Dies Syntax ist korrekt, das hört sich so an wie wenn der Typ 'Token' nicht gefunden wurde. Hast du ihn importiert?

 

[das-mo]

Das ist eine Klasse im selben Package, die muss ich doch garnicht importieren!?

EDIT: Hab es trotzdem mal importiert, hat sich aber nichts geändert.

 

[Antoras]

Dann zeig mal mehr Code. In der geposteten Zeile kann ich keinen Fehler erkennen.

 

[das-mo]

Klasse Token:

package Parser;

public class Token
{
  private int int_start;
  private int int_end;

  private int int_type;
  /*
   0 = Zahl
   1 = +, 2 = -, 3 = *, 4 = /
   5 = Bereich von Klammer umschlossen; auch potenzen, sin, sqrt, ...
   */

  private int int_spc;
  /*
    0 = normale Klammer
    1 = sqrt
    2 = sin, 3 = cos, 4 = tan, 5 =cot
   */


  //Konstruktoren
  public Token () {}

  public Token (int type, int pos)
  {
    int_type = type;
    int_start = pos;
  }

  public Token (int type, int pos1, int pos2)
  {
    int_type = type;
    int_start = pos1;
    int_end = pos2;

    if (type == 5)
    {
      int_spc = 0;
    }
  }

  public Token (int type, int spc, int pos1, int pos2)
  {
    int_type = type;
    int_spc = spc;
    int_start = pos1;
    int_end = pos2;
  }

  //Methoden zum Setzen/Erhalten von Eigenschaften/Variablen
  public void setStart (int pos)
  {
    int_start = pos;
  }

  public void setEnd (int pos)
  {
    int_end = pos;
  }

  public void setType (int type)
  {
    int_type = type;
  }

  public void setSpc (int spc)
  {
    int_spc = spc;
  }

  public int getStart ()
  {
    return int_start;
  }

  public int getEnd ()
  {
    return int_end;
  }

  public int getType ()
  {
    return int_type;
  }

  public int getSpc ()
  {
    return int_spc;
  }
}

Klasse vom Scanner:

package Parser;
import java.util.*;

public class Scanner
{
  private String String_fkt;
  private int int_pos;
  private boolean error;
  ArrayList<Token> obj_token = new ArrayList<Token>();

  //Konstruktoren
  public Scanner () {}
  public Scanner (String fkt)
  {
    String_fkt = fkt;
  }

  //Methoden zum Setzen von Eigenschaften/Variablen
  public void setFunction (String fkt)
  {
    String_fkt = fkt;
  }

 

[Antoras]

Der Code ist korrekt, entweder ist dein Compiler kaputt oder du hast sonst noch irgendwo einen Fehler. Ist das der komplette Code? Wie sieht die genaue Fehlermeldung aus?

Im übrigen schreibt man Variablennamen in Java in "lowerCamelCase" und trennt sie nicht mit Unterstrichen. Und packages sind nur "lowercase".

 

[das-mo]

ja ok package war nen versehen, aber was ist ist denn bitte lowercamelcase^^

EDIT: oben steht die vollständige Fehlermeldung: <bezeichner> erwartet in Zeile 9

 

[Antoras]

CamelCase: String_fkt => stringFkt

Mit was für einem Tool übersetzt du den Code? Mit javac? Wenn ja mit bestimmten Parametern?

 

[das-mo]

Ähhh ich benutze den JBuilder 9 ^^

EDIT: Hat das vlt. damit was zu tun, dass der JBuilder die JDK 1.4.1 am laufen hat?
EDIT: Hab jetzt die JDK 1.6 drauf und immernoch der selbe Fehler

 

[Antoras]

Ja, Generics werden glaube ich erst ab 1.5 unterstützt. Versuche mal mit einer neueren Version zu kompilieren.

 

[das-mo]

Guckst du oben. Hab ich aktualisiert.

 

[Antoras]

Hast du beim JBuilder auch eingestellt, dass mit dem neuesten JDK kompiliert werden soll? Wie das geht weiß ich nicht, das kannst du in den Optionen der IDE aber bestimmt einstellen.

 

[das-mo]

Hab ich

 

[das-mo]

Gibt es eine Alternative zur Arraylist? Vector funktioniert auch nicht...

 

[Gast2]

Du kannst die ArrayList ohne Generics verwenden, evtl. schluckter das dann.
Ich würde allerdings mal Java und die IDE neu aufsetzen bei dir.

 

[das-mo]

JBuilder kann ich leider nicht neu aufsetzen, ist ne schullizenz und ich hab die aktivierungsdatei nicht mehr^^, aber ich installier mir gerade netbeans

EDIT: Tadaaaa Netbeans nimmt es an

 

[das-mo]

Ich hätte da nochmal ne kleine Frage:
Kommen sich Switch und Schleifen eig in die Quere wenn ich break anwende?

switch (blabla)
{
case 1:
   while(blabla)
   {
     if(blabla)
        {
          break;
        }
   }
}

Stoppt das break; jetzt die Schleife oder das switch?

 

[eRaaaa]

Wie wäre es denn wenn du es einfach ausprobierst?

	public static void main(String[] args) throws Exception {
		int i = 1;
		switch (i) {
		case 1:
			while (true) {
				if (true) {
					break;
				}
			}
			//break;   //<----------------
		case 2:
			System.out.println("Durchfall?");
		}
	}

 

[das-mo]

Wie eig erwartet bricht das break; die Schleife und nicht die Klammer ab.....

 

[das-mo]

So ich bin nochmal da

Wie kann ich machen, das alle Klassen mit ein und dem selben Objekt arbeiten?
z.B. ich hab die ArrayList<Token> und würd gerne, dass mehrere Klassen, ohne dass das Objekt immer wieder neu übergeben werden muss, damit arbeiten können.

Gruß das-mo

 

[eRaaaa]

Was gefällt dir denn am Übergeben nicht? Wenns dir zu umständlich wird nimm ein Dependency-Injection Framework zur Hand Das ist aber eig. die gängige Art...
ansonsten wäre eine alternative Antwort auf deine Frage: statte das Feld mit dem entsprechenden Zugriffsmodifier aus und statisch

 

[das-mo]

wenn ich denn möchte, dass man nur innerhalb dieses packages drauf zugreifen kann muss ich dann schreiben:
protected static ArrayList<Token> ??
Und wenn es static ist kann ichh es dann noch großartig ändern?

 

[eRaaaa]

wenn ich denn möchte, dass man nur innerhalb dieses packages drauf zugreifen kann muss ich dann schreiben:
protected static ArrayList<Token> ??

Äh nein nicht ganz, nur package = kein Modifier --> http://www.java-forum.org/blogs/eraaaa/98-java-modifier.html
protected ist noch ein Stück offener

Und wenn es static ist kann ichh es dann noch großartig ändern?

?! --> http://www.java-forum.org/stichwort-static/1353-bedeutet-static.html