Wie erstellt man einen logischen booleschen Parser für die Texteingabe?

Question

Ich muss einen Parser erstellen, um in der Lage sein, logische Struktur aus einer Texteingabe zu extrahieren, um eine Abfrage für einige Web-Service zu erstellen.

Ich habe versucht, reguläre Ausdrücke zu verwenden, aber es wird sehr kompliziert, mit der Verschachtelungslogik umzugehen, also habe ich beschlossen, um Hilfe zu bitten, vielleicht mache ich es falsch.

ex:

((foo1 and bar) or (foo2 and bar2)) and ((foo3 and bar3) or foo4) and "this is quoted" 

das Ergebnis sollte wie folgt sein:

{ 
    { 
     foo1 
     AND 
     bar 
    } 
    OR 
    { 
     foo2 
     AND 
     bar2 
    } 
} 
AND 
{ 
    { 
     foo3 
     AND 
     bar3 
    } 
    OR 
    foo4 
} 
AND 
{ 
    "this is quoted" 
} 

Sprache verwendet wird, Actionscript 3, aber ich konnte Java-Version anzupassen.

Answer 1

gut, ist der Parser ganz einfach ...

zuerst müssen Sie eine ganze Menge Sachen (i Konstrukteurs auslassen werde, da ich glaube, dass Sie sie auf eigene Faust schreiben):

Ausdrücke (Ausgang):

class Expression {} 
class Operation extends Expression { 
    public var operand1:Expression; 
    public var operator:String; 
    public var operand2:Expression; 
} 
class Atom extends Expression { 
    public var ident:String; 
} 

Tokens (Zwischenformat):

class Token { 
    public var source:String; 
    public var pos:uint; 
} 
class Identiefier extends Token { 
    public var ident:String; 
} 
class OpenParenthesis extends Token {} 
class CloseParenthesis extends Token {} 
class Operator extends Token { 
    public var operator:String; 
} 
class Eof extends Token {} 

und a bis kenizer sollte, dass diese Schnittstelle

interface TokenStream { 
    function read():Token; 
} 

ich denke, implementieren Sie herausfinden, werden sich wie tokenize ...

so ist der Weg Quelle - (tokenizer) -> Token - (Parser) -> Ausdrücke ...

und hier die Analyseroutine, mit einem kleinen Helfer:

function parse(t:TokenStream):Expression { 
    var tk:Token = t.read(); 
    switch ((tk as Object).constructor) {//this is a really weird thing about AS3 ... need to cast to object, before you can access the constructor 
     case OpenParanthesis: 
      var e1:Expression = parse(t); 
      tk = t.read(); 
      switch ((tk as Object).constructor) { 
       case CloseParenthesis: 
        return e1; 
       case Operator: 
        var op:String = (tk as Operator).operator; 
        var e2:Expression = parse(t); 
        tk = t.read(); 
        if (tk is CloseParenthesis) 
         return new Operation(e1,op,e2); 
        else 
         unexpected(tk); 
      } 
      else 
       unexpected(tk); 
     break; 
     case Identifier: 
      return new Atom((tk as Identifier).ident); 
     default: 
      unexpected(tk); 
    } 
} 
function unexpected(tk:Token) { 
    throw "unexpected token "+tk.source+" at position "+tk.pos; 
} 

ist dies kein besonders guter Parser, aber es zeigt die nackten Grundlagen der Parsing-Routinen ... w Ich habe die Implementierung nicht überprüft, aber es sollte funktionieren ... es ist sehr primitiv und unnachgiebig ... Dinge wie Operatorenpräzedenz etc. fehlen komplett und so weiter ... aber wenn du das willst, versuchen Sie es ...

btw. Mit haXe mit Enums, würde der ganze Code viel kürzer und viel schöner aussehen ... Sie können es sich ansehen ...

viel Glück dann ...;)

greetz

back2dos

Answer 2

Sie benötigen einen Parser; Der einfachste Weg ist die Wiederverwendung eines bestehenden. Ich würde vorschlagen, dass Sie versuchen, JSON, da es beliebt und ganz in der Nähe, was Sie suchen.

Eine Abfrage wie (a AND (b oder c)) könnte so codiert werden:

 
{ "left": "a", 
    "op": "AND", 
    "right": 
    { 
    "left": "b", 
    "op": "OR", 
    "right": "c" 
    } 
} 

Nach Parsen Sie ein Objekt mit drei Feldern erhalten werden, genannt links, op und rechts. Sie sollten die Abfrage problemlos von dort aus erstellen können.

OK, dies funktioniert nur, wenn Sie das Format für Ihre Eingabe wählen können. Wenn das nicht möglich ist, müssen Sie möglicherweise selbst einen Parser schreiben. Sie können wahrscheinlich etwas wie rekursiven Descent verwenden, da die Syntax in Ihrem Beispiel einfach ist.