Parserbau

L

leon_20v

Aktives Mitglied
Hallo Leute,

ich brauch bitte hilfe beim Parserbau.

Mein Parser soll folgendes können:
Ich gebe eine String an z.B. s1 > 10 && s2 ==1.

Ich muss dann die Variable die in s1 steht mit 10 vergleichen und die in s2 mit 1. Wen beide Aussagen wahr sind, soll etwas passieren.

Irgendwie hab ich keine Ahnung wie ich das Problem anfassen soll? Statt dem und könnte ja auch ein oder sein. es könnte nicht nur s1 heißen sondern s10 und ein < könnte auch == oder ein != sein.

Wie geht man denn sowas an?


Vielen Dank
 
dzim

dzim

Top Contributor
Ich denke mal Divide and Conquer ist die Methode, oder?
Teile das Problem erst einmal auf, erkenne das "&&" und zu erhälst zwei Blöcke. "s1 > 10" und "s2 == 1", diese musst du dann weiter evaluieren.

Wie würde man das aufbauen? Am Besten in einem Baum, den du dann später einfacher evaluieren kannst:
Also irgendwie so
Code: 
Root {

 operator = AND

 left = {
   operator = GREATER
   left = s1
   right = 10
 }

 right = {
   operator = EQUAL
   left = s2
   right = 1
 }
}

Das Evaluieren muss dann irgendwie rekursiv abgearbeitet werden. Also beim Blatt anfangen anfangen und dann nach vorne arbeiten.
So irgendwie würde ich es wohl machen.
 
Zuletzt bearbeitet:
L

leon_20v

Aktives Mitglied
Vielen Dank für die schnelle Antwort.


Wenn es dann noch sowas gibt, hört der Spass aber dann auf

s1 > 10 && s2 == 1 || s3 != 2


Durch deine "" sehe ich gerade, wäre es einfach man das so angeben würde.
 
kaoZ

kaoZ

Top Contributor
naja du hast ja Trennzeichen, entweder && oder || sprich die Logischen Operatoren, diese kannst du zum einen zum aufsplitten nehmen und zum anderen gleich in eine Listen mit Operatoren schreiben lassen , später setzt du dann einfach alles wieder so wie du es brauchst über den Index zusammen ;)

Du musst dir halt vorher gedanken darüber machen wo und mit welchen Zeichen du trennen willst.
 
Zuletzt bearbeitet:
ARadauer

ARadauer

Top Contributor
javascript...

Java: 
    public static void main(String[] args) throws ScriptException {
        //
                
        ScriptEngineManager manager = new ScriptEngineManager();
        ScriptEngine engine = manager.getEngineByName("js");
         
        engine.put("s1", 12);
        engine.put("s2", 1);
        engine.put("s3", 3);
        engine.eval("result = s1 > 10 && s2 == 1 || s3 != 2");
        
        System.out.println(engine.get("result"));
    }
ausser du willst dir das selber bauen, aber dann würde ich mir ein entsprechendes buch besorgen...
 
L

leon_20v

Aktives Mitglied
ARadauer hat gesagt.:
javascript...

Java: 
    public static void main(String[] args) throws ScriptException {
        //
                
        ScriptEngineManager manager = new ScriptEngineManager();
        ScriptEngine engine = manager.getEngineByName("js");
         
        engine.put("s1", 12);
        engine.put("s2", 1);
        engine.put("s3", 3);
        engine.eval("result = s1 > 10 && s2 == 1 || s3 != 2");
        
        System.out.println(engine.get("result"));
    }
ausser du willst dir das selber bauen, aber dann würde ich mir ein entsprechendes buch besorgen...
Zum Vergrößern anklicken....


Vielen Dank,

Ich frage mich gerade nur wie das mit der Performance ist? Wenn ich ganz viele Vergleiche durchführe und nur die Variablen setze? Wenn der jedesmal parst ist es glaub zu langsam, Weil ich es über 1000 mal pro sekunde durchführe mit jeweils geänderten variablen (also in s steht immer was anderes drinn)

Welches Buch würdest du mir da empfehlen?
 
Zuletzt bearbeitet:
Thallius

Thallius

Top Contributor
Was soll denn bitte das Endergebnis deiner Bemühungen sein?

Ich glaube fast Du bist hier irgendwie auf einem vollkommenen Holzweg und versuchst etwas das eigentlich per programmcode abgebildet werden sollte als Formel in einem String abzubilden.

Ander wüßte ich keinen Anwendungsfall wo man über 1000x pro Sekunde eine Formel parsen muss.

Gruß

Claus
 
windl

windl

Bekanntes Mitglied
Hallo,

ich habe vor einiger Zeit einmal einen Parser geschrieben der nur die Grundfunktionen bei Mathe abdeckt. Trotzdem kann er als Anhaltspunkt für Dich dienen.
Vielleicht hilft er Dir - würde mich freuen.

Gruß
Uwe
 

Anhänge

  • mathParser.zip
    22,2 KB · Aufrufe: 8
Tobse

Tobse

Top Contributor
Die Eine Möglichkeit ist - wie meine Vorredner sagten - Divide and Conquer. Ich möchte aber ein paar sachen über Parser generell loswerden:
Normalerweise benutzt man einen sogenannten Tokenizer. Dieser Tokenizer ist dazu in der Lage, zu "raten", was eine Variable ist und was eine Zahl, einen String zu erkennen u.s.w, sodass bei folgendem Input
Java: 
s1 < 10 && s2 > 10 || s3 > 50
Folgende Sequenz an Token dabei herauskommt:
Code: 
Identifier: s1 (Identifier weil s1 ja auch der Name einer Methode, Klasse oder sonst was sein könnte)
Operator: Less-Than
Integer: 10
Operator: Logical-And
Identifier: s2
Operator: Greater-Than
Integer: 10
Operator: Locial-Or
Identifier: s3
Operator: Greater-Than
Integer 50
In Perl, Python oder PHP z.B. werden Variablen durch ein $ gekennzeichnet. Damit kann der Tokenizer bereits erkennen, dass es sich um eine Variable handelt. Zweites Beispiel in PHP:
PHP: 
$s1 < 10 || $s2 == "Hello World!"
Code: 
Variable: s1
Operator: Less-Than
Integer: 10
Operator: Logical-Or
Variable: s2
Operator: Equals
String: Hello World!

Bei XML kann der Parser damit schon wunderbar arbeiten.
Bei Programmcode kann der Parser nur Herr über sehr komplexe ausdrücke werden, wenn er die Tokens aus dem Tokenizer in sogenannte Expressions aufteilt (Klassen-Definitionen oder import-statements sind ja dann leicht zu parsen, da braucht es nicht viel mehr).
Eine Expression kann ausgeführt werden und liefert dann einen Wert zurück. Nochmal das Beispiel von oben etwas variiert:
PHP: 
$s1 + $s3 < 10 + $s2

Der Parser sieht: Variable s1. Jetzt muss zunächst mal überprüft werden, ob es die gibt oder nicht. Falls ja resultiert folgende Expression: [c]VariableExpression: Return-Type <Typ von $s1>, Variable-Name: s1[/c].
Jetzt sieht der parser ein +. Ergo, letzte expression plus die nächste.
Code: 
AdditionExpression: Return-Type int {
    Operand1: VariableExpression: Return-Type <Typ von $s1>, Variable-Name: s1
    Operand2: VariableExpression: Return-Type <Typ von $s2>, Variable-Name: s2
}
Jetzt sieht er ein Less-Than. Also die Letzte Expression mit der nächsten Vergleichen. Die Nächste Expresion wird geparsed (Rekursion!) und es resultiert:
Code: 
AdditionExpression: Return-Type int {
    Operand1: ValueExpression: Return-Type int, Value: 10
    Operand2: VariableExpression: Return-Type <Typ von $s3>, Variable-Name: s3
}
Jetzt hat der Parser die Zwei Expressions die er less-than vergleichen soll. Es folgt also
Code: 
LessThanExpression: Return-Type boolean {
    LeftOperand: AdditionExpression: Return-Type int {
        Operand1: VariableExpression: Return-Type <Typ von $s1>, Variable-Name: s1
        Operand2: VariableExpression: Return-Type <Typ von $s2>, Variable-Name: s2
    }
    RightOperand: AdditionExpression: Return-Type int {
        Operand1: ValueExpression: Return-Type int, Value: 10
        Operand2: VariableExpression: Return-Type <Typ von $s3>, Variable-Name: s3
    }
}

Auf diese Weise wirst du Herr über komplexe Vergleiche / boolsche bedingungen, verkettete Methodenaufrufe, String-Zusammenknüpfungen u.s.w u.s.w.. Aber soetwas selbst zu schreiben braucht wirklich viel Kompetenz (Design-Fehler rächen sich später seeeeeeeehr böse!) und Zeit. Wenn du vor hast, einen Parser für eine Programmiersprache zu schreiben (ob ne eigene oder z.B. JavaScript ist da total egal), besorg dir ein Buch dafür.
Und bedenke: Wenn der Input geparsed ist, ist er noch lange nicht überprüft. Was wenn s1 kein int sondern ein String ist? Und zum Ausführen des Codes musst du die Methode zum Ausführen aller Expressions implementieren. An eine Geschwindigkeit wie sie die jetzigen Interpreter haben wirst du nicht rankommen. Einen Compiler und eine VM zu schreiben (womit du an die Geschwindigkeiten der aktuellen Interpreter schon rankommen könntest) ist für einen alleine mehr als too much.
 
Zuletzt bearbeitet:
L

leon_20v

Aktives Mitglied
Thallius hat gesagt.:
Was soll denn bitte das Endergebnis deiner Bemühungen sein?

Ich glaube fast Du bist hier irgendwie auf einem vollkommenen Holzweg und versuchst etwas das eigentlich per programmcode abgebildet werden sollte als Formel in einem String abzubilden.

Ander wüßte ich keinen Anwendungsfall wo man über 1000x pro Sekunde eine Formel parsen muss.

Gruß

Claus
Zum Vergrößern anklicken....


Es kommt ein String an, in diesem steht diese Gramatik. S1, S2- SUnendlich stehen werte drinn (Es gibt im normalfall bis zu 20 S-Variablen).

Diese S-Variablen ändern ihren Wert, teilw. alle 20ms. Dann muss nach der Grammatik geprüft werden und anschließend entsprechend gehandelt.

Die Grammatik kann zur Laufzeit vom Benutzer angegeben werden. Es ist also eine Art Trigger.
 

Aktuelle Jobs

Neue Themen


Oben