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

algorithm expression-trees language-agnostic parsing php

Pregunta

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 pueden considerarse identificadores simples. Tendrán una pequeña estructura, pero el analizador no necesita preocuparse por eso. Sólo debe reconocer las palabras clave and or not ( ) . Todo lo demás es un término.

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

Una biblioteca ya hecha estaría bien, pero según recuerdo, el algoritmo era bastante simple, por lo que podría ser divertido y educativo reimplementarlo.

Respuesta popular

Los analizadores de descenso recursivo son divertidos de escribir y fáciles de leer . El primer paso es escribir tu gramática.

Tal vez esta es la gramática que quieres.

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 súper fácil. Solo escribe 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 está completo. Tienes que proporcionar un poco más de código:

  • Funciones de entrada. consume , peek , y is_term son funciones que ofrece. Serán fáciles de implementar utilizando expresiones regulares. consume(s) lee el siguiente token de entrada y emite 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 llaman cada vez que una parte de la expresión se analiza con éxito. Ellos pueden hacer lo que tu quieras.

  • Función de envoltura. En lugar de solo llamar directamente a expr , querrá escribir una pequeña función de envoltorio que inicialice las variables utilizadas por consume y peek , luego llamar a expr , y finalmente verifica para asegurarse de que no haya entradas sobrantes que no hayan sido consumidas.

Incluso con todo esto, sigue siendo una pequeña cantidad de código. En Python, el programa completo es de 84 líneas , y eso incluye algunas pruebas.



Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow