Come analizzare questo tipo di espressioni?

Question

Non ho uno sfondo di compilatori quindi non sono sicuro se questa è una cosa comune in quell'area. Esistono tecniche standard per analizzare espressioni come questa? (Say, scheda indica la profondità)

And 
    A + B = 1 
    C + D = 1 
    Or 
     P + Q = 1 
     K = 1 
    And 
     Q = 1 
     R = 2 

Dovrebbe essere analizzato come:

((A+B=1) AND (C+D=1) AND ((P+Q=1) OR (K=1)) AND ((Q=1) AND (R=2))) 

Non sono sicuro se devo ricorrere ad una valutazione basata pila? Attualmente sto provando uno e posterò un codice funzionante se riesco a farlo funzionare.

Qualche suggerimento su un modo semplice per raggiungere questo obiettivo?

Answer 1

si Supponendo che chiedono su come analizzare le espressioni costruite di operatori con diversi precedenze e associativities - assolutamente.

Un approccio efficace è chiamato "top-down precedenza degli operatori", e forse anche "precedenza degli operatori", e l'analisi "precedenza arrampicata". Qui ci sono alcune fonti belle che spiegano l'approccio in dettaglio:

• Pratt parsing (anche la original paper) del take su di esso

• Douglas Crockford

• di take su di esso un Pythonist

• un Java version

La cosa veramente interessante è il modo in po 'di codice in realtà prende.

I concetti chiave sono:

• prefisso vs infisso vs mixfix

• precedenza: è 3 + 4 * 5 analizzato come (3 + 4) * 5 o 3 + (4 * 5)?

• associatività: è x - y - z analizzato come x - (y - z) o (x - y) - z?

Casualmente, ho appena imparato questa roba da poco e finito per scrivere un un articolo sul mio blog su un approccio simile per operatore analisi, che potete trovare here. Nel mio approccio, mi occupo di operatori infissi, prefissi, postfix e mixfix (ad esempio ? :); le precedenze e le associatività sono tutte specificate nelle tabelle; Io uso uno stack per tenere traccia degli operatori i cui operandi non sono ancora stati trovati. Il parser quindi crea un albero di analisi, in cui ogni nodo è una sottoespressione.