Как сделать логический логический парсер для ввода текста? - PullRequest
Новая
       17

Как сделать логический логический парсер для ввода текста?

1 голос
/ 21 августа 2009

Мне нужно сделать синтаксический анализатор, чтобы иметь возможность извлекать логическую структуру из текстового ввода для построения запроса для некоторого веб-сервиса.

Я пытался использовать регулярные выражения, но становится действительно сложно обрабатывать логику имберикации, поэтому я решил обратиться за помощью, может быть, я делаю это неправильно.

например: 

( (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.

Ответы [ 2 ]

5 голосов
/ 21 августа 2009

ну, парсер довольно простой ...

сначала вам понадобится довольно много вещей (я опущу конструкторы, так как, думаю, вы можете написать их самостоятельно):

выражения (вывод): 

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 с перечислениями, весь код выглядел бы намного короче и намного красивее ... вы можете взглянуть на него ...

0 голосов
/ 21 августа 2009

Вам нужен парсер; Самый простой способ - это повторно использовать существующий. Я бы посоветовал вам попробовать JSON , поскольку он популярен и довольно близок к тому, что вы ищете.

Запрос типа (a AND (b OR c)) может быть закодирован так: 

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

После синтаксического анализа вы получите объект с тремя полями, которые называются left, op и right. Вы сможете легко построить запрос оттуда.

ОК, это может работать, только если вы можете выбрать формат для ввода. Если вы не можете, то вам, возможно, придется написать парсер самостоятельно. Возможно, вы можете использовать что-то вроде рекурсивного спуска, поскольку синтаксис в вашем примере прост.

...