¿Cuál es el algoritmo para analizar expresiones en notación infija?

Question

Me gustaría analizar expresiones booleanas en PHP. Como en:

A and B or C and (D or F or not G) 

Los términos se pueden considerar identificadores simples. Tendrán una pequeña estructura, pero el analizador no necesita preocuparse por eso. Solo debe reconocer las palabras clave and or not (). Todo lo demás es un término.

Recuerdo que escribimos simples evaluadores de expresiones aritméticas en la escuela, pero no recuerdo cómo se hizo. Tampoco sé qué palabras clave buscar en Google/SO.

Una biblioteca preparada sería agradable, pero como recuerdo, el algoritmo era bastante simple, por lo que podría ser divertido y educativo volver a implementarlo yo mismo.

Answer 1

Iría con el analizador Pratt. Es casi como un descenso recursivo pero más inteligente :) Una explicación decente de Douglas Crockford (de la fama de JSLint) here.

Answer 2

¿Por qué no jsut usa el analizador de PHP?

$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); 

En realidad, esa segunda expresión regular está mal (y sólo se requiere si es necesario para evitar cualquier inyección de código) -, pero se entiende la idea.

C.

Answer 3

Se podría utilizar un analizador sintáctico LR para construir un árbol de análisis y luego evaluar el árbol para obtener el resultado. Una descripción detallada que incluye ejemplos se puede encontrar en Wikipedia. Si no lo has codificado tú mismo, escribiré un pequeño ejemplo esta noche.

Answer 4

Dijkstra's shunting yard algorithm es el tradicional para pasar de infijo a postfix/gráfico.

Answer 5

La manera más simple es usar expresiones regulares que convierte su expresión en una expresión en sintaxis php y luego usar eval, como lo sugiere symcbean. Pero no estoy seguro de si desea usarlo en el código de producción.

La otra forma es codificar su propio recursive descent parser simple. No es tan difícil como podría sonar. Para una gramática simple como la suya (expresiones booleanas), puede codificar fácilmente una desde cero. También puede usar un generador de analizadores similar a ANTLR para php, probablemente la búsqueda de un generador de analizadores php arroje algo.

Answer 6

Implementé el algoritmo del patio de maniobras según lo sugerido por el zócalo. Sin embargo, este algoritmo simplemente le da la notación de postfijo, también conocida como notación polaca inversa (RNP). Aún tiene que evaluarlo, pero eso es bastante fácil una vez que tiene la expresión en RNP (descrita por ejemplo here).

El código siguiente podría no ser bueno, mi conocimiento de PHP es algo limitado. Sin embargo, debería ser suficiente para obtener la idea.

$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"; 

Answer 7

analizadores descendente recursivo son divertido de escribir yfácil de leer. El primer paso es escribir tu gramática.

Quizás esta es la gramática que desea.

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

Convertir esto en un analizador de descenso recursivo es muy fácil. Simplemente escriba una función por no terminal.

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 (") 

Esto no se ha completado. Usted tiene que proporcionar un poco más de código:

• Funciones de entrada.consume, peek y is_term son funciones que usted proporciona. Serán fáciles de implementar usando expresiones regulares. consume(s) lee el siguiente token de entrada y arroja un error si no coincide con s. peek() simplemente devuelve un vistazo al siguiente token sin consumirlo. is_term(s) devuelve true si s es un término.

• Funciones de salida.OR, AND, NOT y TERM se invocan cada vez que se analiza con éxito una parte de la expresión. Ellos pueden hacer lo que quieras.

• Función de contenedor. En lugar de simplemente llamar al expr directamente, querrá escribir una pequeña función de envoltura que inicialice las variables utilizadas por consume y peek, luego llame al expr, y finalmente compruebe que no haya entradas sobrantes que no se hayan consumido.

Incluso con todo esto, todavía hay una pequeña cantidad de código. In Python, the complete program is 84 lines, y eso incluye algunas pruebas.