Qual è l'algoritmo per l'analisi delle espressioni nella notazione infisso?

algorithm expression-trees language-agnostic parsing php

Domanda

Vorrei analizzare le espressioni booleane in PHP. Come in:

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

I termini possono essere considerati identificatori semplici. Avranno una piccola struttura, ma il parser non deve preoccuparsi di questo. Dovrebbe solo riconoscere le parole chiave and or not ( ) . Tutto il resto è un termine.

Ricordo che abbiamo scritto semplici valutatori di espressioni aritmetiche a scuola, ma non ricordo più come è stato fatto. Né so quali parole chiave cercare in Google / SO.

Una libreria già pronta sarebbe carina, ma poiché ricordo che l'algoritmo era piuttosto semplice, sarebbe divertente ed istruttivo ri-implementarlo da solo.

Risposta popolare

I parser di discendenza ricorsivi sono divertenti da scrivere e facili da leggere . Il primo passo è scrivere la tua grammatica.

Forse questa è la grammatica che desideri.

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

Trasformare questo in un parser di discesa ricorsivo è semplicissimo. Basta scrivere una funzione per non terminale.

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

Questo non è completo. Devi fornire un po 'più di codice:

  • Funzioni di input. consume , dare peek e is_term sono le funzioni che fornisci. Saranno facili da implementare usando le espressioni regolari. consume(s) legge il prossimo token di input e genera un errore se non corrisponde a s . peek() restituisce semplicemente una sbirciata al prossimo token senza consumarlo. is_term(s) restituisce true se s è un termine.

  • Funzioni di uscita. OR , AND , NOT e TERM vengono chiamati ogni volta che una parte dell'espressione viene analizzata correttamente. Possono fare tutto ciò che vuoi.

  • Funzione wrapper. Invece di chiamare direttamente expr , ti consigliamo di scrivere una piccola funzione wrapper che inizializza le variabili utilizzate da consume e peek , quindi chiama expr e infine controlla che non ci siano input rimanenti che non vengono consumati.

Anche con tutto questo, è ancora una piccola quantità di codice. In Python, il programma completo è di 84 righe e include alcuni test.



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché