代码之家 › 专栏 › 技术社区 › a.s.t.r.o

如何为文本输入创建逻辑布尔解析器?

boolean actionscript parsing

a.s.t.r.o · 技术社区 · 16 年前

我需要使解析器能够从文本输入中提取逻辑结构,以便为某些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"
}

使用的语言是ActionScript3,但我可以修改Java版本。

2 回复 | 直到 11 年前

Gama11 zzapper 7 年前

嗯,解析器非常简单。。。

首先,您需要很多东西(我将省略构造函数,因为我想您可以自己编写它们):

表达式(输出):

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

和一个标记器,应该实现这个接口

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

这不是一个特别好的解析器,但它展示了解析例程的基本原理。。。嗯,实际上,我没有检查实现,但它应该可以工作。。。这是非常原始和不允许的。。。运算符优先级等内容完全丢失,等等。。。但是如果你想要的话,试试看。。。

Haxe 使用enum,整个代码看起来会更短、更漂亮。。。你可能想看看它。。。

redtuna 16 年前

JSON 因为它很受欢迎,而且非常接近你想要的。

像(A和(b或c))这样的查询可以这样编码:

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

解析之后,您将得到一个包含三个字段的对象,分别称为left、op和right。您应该能够从那里轻松地构建查询。

好的,这只有在您可以选择输入格式的情况下才能起作用。如果不能,那么您可能必须自己编写解析器。由于示例中的语法很简单,您可能可以使用类似递归下降的方法。