如何为文本输入制作逻辑布尔分析器？

Question

我需要使解析器能够从文本输入中提取逻辑结构，以构建一些Web服务的查询。

我试图使用正则表达式，但处理叠加逻辑变得非常复杂，所以我决定寻求帮助，也许我做的是错误的方式。

例如：

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

的结果应该是这样的：

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

使用的语言是ActionScript 3的，但我可以适应Java版本。

Answer 1

好，解析器是相当简单的...

首先，你需要相当多的东西（我会忽略构造函数，因为我想你可以写他们自己）：

表达式（输出）：

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; 
} 

令牌（中介格式）：

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 {} 

和至kenizer，应该实现此接口

interface TokenStream { 
    function read():Token; 
} 

我猜你会找出自己如何来标记......

这样的方式是源 - （标记生成器） - >标记 - （分析器） - >表情...

，这里的分析例程，用小帮手：

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; 
} 

这是不是一个特别好的解析器，但它表明分析例程的裸基本面... w ^实际上，我没有检查实现，但它应该工作......它是非常原始的和不被允许的......诸如运算符优先等的东西完全缺失，等等......但是如果你想要的话，有一个去...

btw。使用带枚举的haXe，整个代码看起来会更短，更漂亮......您可能需要查看它...

好运气，然后...;）

格尔茨

back2dos

Answer 2

你需要一个解析器;最简单的方法是重用一个现有的。我建议你尝试JSON，因为它很受欢迎，而且非常接近你要找的东西。

像查询（A和（B或C））可能会被编码的那样：

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

解析，你会得到一个对象有三个字段后，叫离开，运，右。您应该能够从那里轻松构建查询。

好吧，只有在您可以选择输入格式时才能使用。如果你不能，那么你可能必须自己写一个解析器。你可以使用类似递归下降的东西，因为你的例子中的语法很简单。