Recursive asıllı ayrıştırıcılar fun to write ve easy to read vardır. İlk adım dilbilgisi yazmak için.

Belki bu istediğiniz dilbilgisi.

expr        = and_expr ('or' and_expr)*
and_expr    = not_expr ('and' not_expr)*
not_expr    = simple_expr | 'not' not_expr
simple_expr = term | '(' expr ')'

Bir özyinelemeli iniş çözümleyici bu dönüm süper kolaydır. Sadece nonterminal başına bir fonksiyon yazmak.

def expr():
    x = and_expr()
    while peek() == 'or':
        consume('or')
        y = and_expr()
        x = OR(x, y)
    return x

def and_expr():
    x = not_expr()
    while peek() == 'and':
        consume('and')
        y = not_expr()
        x = AND(x, y)
    return x

def not_expr():
    if peek() == 'not':
        consume('not')
        x = not_expr()
        return NOT(x)
    else:
        return simple_expr()

def simple_expr():
    t = peek()
    if t == '(':
        consume('(')
        result = expr()
        consume(')')
        return result
    elif is_term(t):
        consume(t)
        return TERM(t)
    else:
        raise SyntaxError("expected term or (")

Bu tam değildir. Eğer biraz daha fazla kod sağlamak zorunda:

• Input functions. consume, peek ve is_term Eğer sağlayan fonksiyonları vardır. Onlar düzenli ifadeleri kullanarak uygulamak kolay olacak. consume(s) girişinin sonraki belirteci okur ve maç değilse bir hata atar s. peek() sadece onu tüketmeden sonraki belirteç bir göz verir. s bir terimdir ise is_term(s) true döndürür.

• Output functions. OR, AND, NOT ve TERM ifadenin bir parça başarılı bir şekilde her zaman denir çözümlü. Onlar ne istersen yapabilirsin.

• Wrapper function. Bunun yerine sadece expr, doğrudan, sen consume ve {tarafından kullanılan değişkenlere başlangıç ​​biraz sarıcı fonksiyon yazmak isteyeceksiniz çağıran [(3)] }, sonra [(1)]} {çağırır ve son olarak tüketilen alamadım kalan hiçbir girişi olmadığından emin olmak için denetler.

Hatta tüm bu ile, yine kod küçük bir miktar. In Python, the complete program is 84 lines, ve birkaç testleri içerir.

Neden jsut PHP ayrıştırıcı kullanmak değil mi?

 $terms=array('and','or','not','A','B','C','D'...);
 $values=array('*','+','!',1,1,0,0,1....);

 $expression="A and B or C and (D or F or not G)";
 $expression=preg_replace($terms, $values,$expression);
 $expression=preg_replace('^(+|-|!|1|0)','',$expression);
 $result=eval($expression);

Aslında bu 2 regex yanlış (ve herhangi bir kod enjeksiyonu önlemek için gerekirse sadece gerekli) - ama fikir olsun.

C.

Ben Pratt çözümleyici ile gitmek istiyorum. Neredeyse recursive asıllı ama akıllı :) (JSLint şöhret) Douglas Crockford A terbiyeli bir açıklama gibi here.

Dijkstra's shunting yard algorithm postfix / grafiğine infix gidiş için geleneksel biridir.

Sen sonuç elde etmek için bir ayrıştırma ağacı oluşturmak için bir LR ayrıştırıcı kullanmak ve daha sonra ağaç değerlendirmek olabilir. Örnekler de dahil olmak üzere ayrıntılı bir tarifi bulunabilir Wikipedia. Zaten kendiniz kodlanmış yoksa ben küçük bir örnek bu gece yazacağım.

Basit yolu symcbean tarafından önerildiği gibi, php sözdizimi bir ifadenin içine ifadeyi dönüştürür Regexes kullanın ve sonra eval kullanmaktır. Ama üretim kodunda kullanmak isterim eğer emin değilim.

Diğer yol, kendi basit kod için recursive descent parser. Bu kadar zor gelebilir gibi değildir. Basit bir dilbilgisi gibi sizinki (boolean ifadeler) için, kolayca sıfırdan bir kod olabilir. Ayrıca bir şey açacak muhtemelen php ayrıştırıcı jeneratör ararken, php için Antlr benzer bir ayrıştırıcı jeneratör kullanabilirsiniz.

Baza önerdiği gibi manevra bahçesinde algoritması uyguladık. Ancak bu algoritma sadece aka Polonyalı notasyonu (RNP) ters, size postfix gösterimde verir. Hala değerlendirmek zorunda, ama sen RNP'nin ifadeyi aldıktan sonra oldukça kolay (örneğin tarif here).

Aşağıdaki kod iyi bir PHP tarzı olmayabilir, benim PHP bilgi biraz sınırlıdır. Bu olsa fikir edinmek için yeterli olmalıdır.

$operators = array("and", "or", "not");
$num_operands = array("and" => 2, "or" => 2, "not" => 1);
$parenthesis  = array("(", ")");

function is_operator($token) {
    global $operators;
    return in_array($token, $operators);
}

function is_right_parenthesis($token) {
    global $parenthesis;
    return $token == $parenthesis[1];
}

function is_left_parenthesis($token) {
    global $parenthesis;
    return $token == $parenthesis[0];
}

function is_parenthesis($token) {
    return is_right_parenthesis($token) || is_left_parenthesis($token);
}

// check whether the precedence if $a is less than or equal to that of $b
function is_precedence_less_or_equal($a, $b) {
    // "not" always comes first
    if ($b == "not")
        return true;

    if ($a == "not")
        return false;

    if ($a == "or" and $b == "and")
        return true;

    if ($a == "and" and $b == "or")
        return false;

    // otherwise they're equal
    return true;
}


function shunting_yard($input_tokens) {
    $stack = array();
    $output_queue = array();

    foreach ($input_tokens as $token) {
        if (is_operator($token)) {
            while (is_operator($stack[count($stack)-1]) && is_precedence_less_or_equal($token, $stack[count($stack)-1])) {
                    $o2 = array_pop($stack);
                    array_push($output_queue, $o2);
            }
            array_push($stack, $token);

        } else if (is_parenthesis($token)) {
            if (is_left_parenthesis($token)) {
                array_push($stack, $token);
            } else {
                while (!is_left_parenthesis($stack[count($stack)-1]) && count($stack) > 0) {
                    array_push($output_queue, array_pop($stack));
                }
                if (count($stack) == 0) {
                    echo ("parse error");
                    die();
                }
                $lp = array_pop($stack);
            }
        } else {
            array_push($output_queue, $token);  
        }
    }

    while (count($stack) > 0) {
        $op = array_pop($stack);
        if (is_parenthesis($op))
            die("mismatched parenthesis");
        array_push($output_queue, $op);
    }

    return $output_queue;
}

function str2bool($s) {
    if ($s == "true")
        return true;
    if ($s == "false")
        return false;
    die('$s doesn\'t contain valid boolean string: '.$s.'\n');
}

function apply_operator($operator, $a, $b) {
    if (is_string($a))
        $a = str2bool($a);
    if (!is_null($b) and is_string($b))
        $b = str2bool($b);

    if ($operator == "and")
        return $a and $b;
    else if ($operator == "or")
        return $a or $b;
    else if ($operator == "not")
        return ! $a;
    else die("unknown operator `$function'");
}

function get_num_operands($operator) {
    global $num_operands;
    return $num_operands[$operator];
}

function is_unary($operator) {
    return get_num_operands($operator) == 1;
}

function is_binary($operator) {
    return get_num_operands($operator) == 2;
}

function eval_rpn($tokens) {
    $stack = array();
    foreach ($tokens as $t) {
        if (is_operator($t)) {
            if (is_unary($t)) {
                $o1 = array_pop($stack);
                $r = apply_operator($t, $o1, null);
                array_push($stack, $r);
            } else { // binary
                $o1 = array_pop($stack);
                $o2 = array_pop($stack);
                $r = apply_operator($t, $o1, $o2);
                array_push($stack, $r);
            }
        } else { // operand
            array_push($stack, $t);
        }
    }

    if (count($stack) != 1)
        die("invalid token array");

    return $stack[0];
}

// $input = array("A", "and", "B", "or", "C", "and", "(", "D", "or", "F", "or", "not", "G", ")");
$input = array("false", "and", "true", "or", "true", "and", "(", "false", "or", "false", "or", "not", "true", ")");
$tokens = shunting_yard($input);
$result = eval_rpn($tokens);
foreach($input as $t)
    echo $t." ";
echo "==> ".($result ? "true" : "false")."\n";