Parser di equazione (espressione) con precedenza?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho sviluppato un parser di equazioni utilizzando un semplice algoritmo di stack che gestirà operatori binari (+, -, |, &, *, /, ecc.), operatori unari (!) e parentesi.
Utilizzando questo metodo, tuttavia, tutto ha la stessa precedenza: viene valutato da sinistra a destra indipendentemente dall'operatore, sebbene la precedenza possa essere applicata utilizzando le parentesi.
Quindi in questo momento "1+11*5" restituisce 60, non 56 come ci si potrebbe aspettare.
Anche se questo è adatto per il progetto attuale, voglio avere una routine generica da poter utilizzare per progetti successivi.
Modificato per chiarezza:
Qual è un buon algoritmo per analizzare le equazioni con precedenza?
Sono interessato a qualcosa di semplice da implementare e capire che posso codificarmi da solo per evitare problemi di licenza con il codice disponibile.
Grammatica:
Non capisco la domanda di grammatica: l'ho scritta a mano.È abbastanza semplice da non vedere la necessità di YACC o Bison.Ho semplicemente bisogno di calcolare stringhe con equazioni come "2+3 * (42/13)".
Lingua:
Lo sto facendo in C, ma sono interessato a un algoritmo, non a una soluzione specifica per il linguaggio.Il C è di livello sufficientemente basso da poter essere facilmente convertito in un'altra lingua in caso di necessità.
Esempio di codice
Ho pubblicato il codice di test per il parser di espressioni semplici Di cui parlavo sopra.I requisiti del progetto sono cambiati e quindi non ho mai avuto bisogno di ottimizzare il codice in termini di prestazioni o spazio poiché non era incorporato nel progetto.È nella forma dettagliata originale e dovrebbe essere facilmente comprensibile.Se faccio qualcosa in più in termini di precedenza degli operatori, probabilmente sceglierò il trucco macro perché corrisponde al resto del programma in semplicità.Se mai lo utilizzerò in un progetto reale, però, sceglierò un parser più compatto/veloce.
Domanda correlata
-Adamo
Soluzione
Nel modo più duro
Vuoi un parser di discesa ricorsivo.
Per ottenere la precedenza devi pensare in modo ricorsivo, ad esempio, utilizzando la stringa di esempio,
1+11*5
per farlo manualmente, dovresti leggere il file 1, quindi vedere il vantaggio e avviare una "sessione" di analisi ricorsiva completamente nuova a partire da 11...e assicurati di analizzare il file 11 * 5 nel proprio fattore, producendo un albero di analisi con 1 + (11 * 5).
Tutto questo sembra così doloroso anche solo tentare di spiegarlo, soprattutto con l'ulteriore impotenza di C.Vedi, dopo aver analizzato l'11, se invece * fosse effettivamente un +, dovresti abbandonare il tentativo di creare un termine e analizzare invece il 11 stesso come fattore.La mia testa sta già esplodendo.È possibile con la strategia decente ricorsiva, ma esiste un modo migliore...
Il modo più semplice (giusto).
Se usi uno strumento GPL come Bison, probabilmente non dovrai preoccuparti dei problemi di licenza dato che il codice C generato da bison nonècoperto dalla GPL (IANAL ma sono abbastanza sicuro che gli strumenti GPL non forzano la GPL codice/binari generati;per esempio Apple compila codice come, ad esempio, Aperture con GCC e lo vende senza dover GPL detto codice).
Scarica Bisonte (o qualcosa di equivalente, ANTLR, ecc.).
Di solito c'è del codice di esempio su cui puoi semplicemente eseguire bison e ottenere il codice C desiderato che dimostra questo calcolatore a quattro funzioni:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Guarda il codice generato e vedi che non è così facile come sembra.Inoltre, i vantaggi dell'utilizzo di uno strumento come Bison sono 1) impari qualcosa (soprattutto se leggi il libro Dragon e impari le grammatiche), 2) eviti NIH cercando di reinventare la ruota.Con un vero strumento generatore di parser, hai effettivamente la speranza di espanderlo in seguito, mostrando ad altre persone che conosci che i parser sono il dominio degli strumenti di analisi.
Aggiornamento:
Le persone qui hanno offerto molti buoni consigli.Il mio unico avvertimento contro il salto degli strumenti di analisi o il semplice utilizzo dell'algoritmo Shunting Yard o un parser ricorsivo decente fatto a mano è che i piccoli linguaggi giocattolo1 un giorno potrebbero trasformarsi in grandi linguaggi reali con funzioni (sin, cos, log) e variabili, condizioni e cicli for.
Flex/Bison potrebbe essere eccessivo per un interprete piccolo e semplice, ma un parser+valutatore una tantum può causare problemi in futuro quando è necessario apportare modifiche o aggiungere funzionalità.La tua situazione varierà e dovrai usare il tuo giudizio;semplicemente non farlo punire altre persone per i tuoi peccati [2] e costruire uno strumento meno che adeguato.
Il mio strumento preferito per l'analisi
Il miglior strumento al mondo per il lavoro è il Parsec libreria (per parser ricorsivi decenti) fornita con il linguaggio di programmazione Haskell.Assomiglia molto BNF, o come uno strumento specializzato o un linguaggio specifico del dominio per l'analisi (codice di esempio [3]), ma in realtà è solo una normale libreria in Haskell, il che significa che viene compilata nella stessa fase di creazione del resto del codice Haskell e puoi scrivere codice Haskell arbitrario e chiamarlo all'interno del tuo parser, e puoi mescolare e abbinare altre librerie tutto nello stesso codice.(A proposito, incorporare un linguaggio di analisi come questo in un linguaggio diverso da Haskell comporta un sacco di confusione sintattica.L'ho fatto in C# e funziona abbastanza bene ma non è così carino e conciso.)
Appunti:
1 Richard Stallman dice, in Perché non dovresti usare Tcl
La lezione principale di EMACS è che una lingua per le estensioni non dovrebbe essere un semplice "linguaggio di estensione".Dovrebbe essere un vero linguaggio di programmazione, progettato per scrivere e mantenere programmi sostanziali.Perché le persone vorranno farlo!
[2] Sì, sarò per sempre segnato dall'uso di quel "linguaggio".
Tieni inoltre presente che quando ho inviato questa voce, l'anteprima era corretta, ma Il parser meno che adeguato di SO ha mangiato il mio tag di ancoraggio vicino al primo paragrafo, dimostrando che i parser non sono qualcosa con cui scherzare perché se usi espressioni regolari e hack una tantum probabilmente otterrai qualcosa di sottile e piccolo sbagliato.
[3] Frammento di un parser Haskell che utilizza Parsec:una calcolatrice a quattro funzioni estesa con esponenti, parentesi, spazi bianchi per la moltiplicazione e costanti (come pi ed e).
aexpr = expr `chainl1` toOp
expr = optChainl1 term addop (toScalar 0)
term = factor `chainl1` mulop
factor = sexpr `chainr1` powop
sexpr = parens aexpr
<|> scalar
<|> ident
powop = sym "^" >>= return . (B Pow)
<|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))
toOp = sym "->" >>= return . (B To)
mulop = sym "*" >>= return . (B Mul)
<|> sym "/" >>= return . (B Div)
<|> sym "%" >>= return . (B Mod)
<|> return . (B Mul)
addop = sym "+" >>= return . (B Add)
<|> sym "-" >>= return . (B Sub)
scalar = number >>= return . toScalar
ident = literal >>= return . Lit
parens p = do
lparen
result <- p
rparen
return result
Altri suggerimenti
IL Algoritmo di manovra è lo strumento giusto per questo.Wikipedia è davvero confusa a riguardo, ma sostanzialmente l'algoritmo funziona in questo modo:
Supponiamo che tu voglia valutare 1 + 2 * 3 + 4.Intuitivamente, "sai" che devi prima fare il 2 * 3, ma come ottieni questo risultato?La chiave è rendersi conto che quando si esegue la scansione della stringa da sinistra a destra, si valuterà un operatore quando l'operatore quello segue ha una precedenza inferiore (o uguale a).Nel contesto dell'esempio, ecco cosa vuoi fare:
- Guarda a:1 + 2, non fare nulla.
- Ora guarda 1 + 2 * 3, continua a non fare nulla.
- Ora guarda 1 + 2 * 3 + 4, ora sai che 2 * 3 deve essere valutato perché l'operatore successivo ha la precedenza inferiore.
Come lo implementi?
Vuoi avere due stack, uno per i numeri e un altro per gli operatori.Metti continuamente i numeri in pila.Confronti ogni nuovo operatore con quello in cima allo stack, se quello in cima allo stack ha una priorità più alta, lo estrai dallo stack degli operatori, estrai gli operandi dallo stack dei numeri, applica l'operatore e inserisci il risultato sulla pila dei numeri.Ora ripeti il confronto con l'operatore top of stack.
Tornando all'esempio, funziona così:
N = [] ops = [
- Leggi 1.N = [1], Op = [ ]
- Leggi +.N = [1], Operazioni = [+]
- Leggi 2.N = [1 2], Op = [+]
- Leggere
*.N = [1 2], Op = [+ *] - Leggi 3.N = [1 2 3], Op = [+ *]
- Leggi +.N = [1 2 3], Op = [+ *]
- Pop 3, 2 ed esegui 2
*3 e spingere il risultato su N.N = [1 6], Op = [+] +è associativo a sinistra, quindi vuoi estrarre anche 1, 6 ed eseguire +.N = [7], Op = [].- Infine spingi il [+] sullo stack dell'operatore.N = [7], Op = [+].
- Pop 3, 2 ed esegui 2
- Leggi 4.N = [7 4].Operazioni = [+].
- Hai esaurito gli input, quindi vuoi svuotare gli stack adesso.Al termine del quale otterrai il risultato 11.
Ecco, non è così difficile, vero?E non invoca alcuna grammatica o generatore di parser.
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Ottima spiegazione dei diversi approcci:
- Riconoscimento ricorsivo-discendente
- L'algoritmo delle manovre
- La soluzione classica
- Arrampicata con precedenza
Scritto in linguaggio semplice e pseudo-codice.
Mi piace quello "arrampicata con precedenza".
C'è un bell'articolo Qui sulla combinazione di un semplice parser a discesa ricorsiva con l'analisi a precedenza degli operatori.Se di recente hai scritto parser, dovrebbe essere molto interessante e istruttivo da leggere.
Molto tempo fa, ho creato il mio algoritmo di analisi, che non sono riuscito a trovare in nessun libro sull'analisi (come il Dragon Book).Osservando i puntatori all'algoritmo Shunting Yard, vedo la somiglianza.
Circa 2 anni fa, ho scritto un post a riguardo, completo di codice sorgente Perl, su http://www.perlmonks.org/?node_id=554516.È facile effettuare il porting in altre lingue:la prima implementazione che ho fatto è stata nell'assemblatore Z80.
È ideale per il calcolo diretto con i numeri, ma puoi usarlo per produrre un albero di analisi, se necessario.
Aggiornamento Poiché più persone possono leggere (o eseguire) Javascript, ho reimplementato il mio parser in Javascript, dopo che il codice è stato riorganizzato.L'intero parser contiene meno di 5k di codice Javascript (circa 100 righe per il parser, 15 righe per una funzione wrapper) inclusa la segnalazione degli errori e i commenti.
Puoi trovare una demo dal vivo su http://users.telenet.be/bartl/expressionParser/expressionParser.html.
// operator table
var ops = {
'+' : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
'-' : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
'*' : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
'/' : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
'**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};
// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };
// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
var startOffset = r.offset;
var value;
var m;
// floating point number
// example of parsing ("lexing") without aid of regular expressions
value = 0;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
if(r.string.substr(r.offset, 1) == ".") {
r.offset++;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
}
if(r.offset > startOffset) { // did that work?
// OK, so I'm lazy...
return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
} else if(r.string.substr(r.offset, 1) == "+") { // unary plus
r.offset++;
return parseVal(r);
} else if(r.string.substr(r.offset, 1) == "-") { // unary minus
r.offset++;
return negate(parseVal(r));
} else if(r.string.substr(r.offset, 1) == "(") { // expression in parens
r.offset++; // eat "("
value = parseExpr(r);
if(r.string.substr(r.offset, 1) == ")") {
r.offset++;
return value;
}
r.error = "Parsing error: ')' expected";
throw 'parseError';
} else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) { // variable/constant name
// sorry for the regular expression, but I'm too lazy to manually build a varname lexer
var name = m[0]; // matched string
r.offset += name.length;
if(name in vars) return vars[name]; // I know that thing!
r.error = "Semantic error: unknown variable '" + name + "'";
throw 'unknownVar';
} else {
if(r.string.length == r.offset) {
r.error = 'Parsing error at end of string: value expected';
throw 'valueMissing';
} else {
r.error = "Parsing error: unrecognized value";
throw 'valueNotParsed';
}
}
}
function negate (value) {
return -value;
}
function parseOp(r) {
if(r.string.substr(r.offset,2) == '**') {
r.offset += 2;
return ops['**'];
}
if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
return ops[r.string.substr(r.offset++, 1)];
return null;
}
function parseExpr(r) {
var stack = [{precedence: 0, assoc: 'L'}];
var op;
var value = parseVal(r); // first value on the left
for(;;){
op = parseOp(r) || {precedence: 0, assoc: 'L'};
while(op.precedence < stack[stack.length-1].precedence ||
(op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {
// precedence op is too low, calculate with what we've got on the left, first
var tos = stack.pop();
if(!tos.exec) return value; // end reached
// do the calculation ("reduce"), producing a new value
value = tos.exec(tos.value, value);
}
// store on stack and continue parsing ("shift")
stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
value = parseVal(r); // value on the right
}
}
function parse (string) { // wrapper
var r = {string: string, offset: 0};
try {
var value = parseExpr(r);
if(r.offset < r.string.length){
r.error = 'Syntax error: junk found at offset ' + r.offset;
throw 'trailingJunk';
}
return value;
} catch(e) {
alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
return;
}
}
Sarebbe utile se potessi descrivere la grammatica che stai attualmente utilizzando per analizzare.Sembra che il problema potrebbe essere lì!
Modificare:
Il fatto che tu non capisca la domanda di grammatica e che "l'hai scritta a mano" molto probabilmente spiega perché hai problemi con le espressioni della forma "1+11*5" (cioè con la precedenza degli operatori) .Cercare su Google la "grammatica delle espressioni aritmetiche", ad esempio, dovrebbe fornire alcuni buoni suggerimenti.Tale grammatica non deve essere complicata:
<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>
<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>
<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>
andrebbe bene, ad esempio, e può essere banalmente ampliato per gestire alcune espressioni più complicate (incluse funzioni, ad esempio, o poteri,...).
Ti suggerisco di dare un'occhiata Questo filo, per esempio.
Quasi tutte le introduzioni alle grammatiche/analisi trattano le espressioni aritmetiche come esempio.
Si noti che l'utilizzo di una grammatica non implica affatto l'utilizzo di uno strumento specifico (alla Yacc, Bisonte,...).In effetti, sicuramente stai già utilizzando la seguente grammatica:
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
(o qualcosa del genere) senza saperlo!
Hai pensato di utilizzare Potenzia lo Spirito?Ti permette di scrivere grammatiche simili a EBNF in C++ in questo modo:
group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));
Quando poni la tua domanda non è necessaria alcuna ricorsione.La risposta è tre cose:Notazione suffissa più algoritmo Shunting Yard più valutazione dell'espressione suffissa:
1).Notazione suffissa = inventata per eliminare la necessità di specificare esplicitamente la precedenza.Leggi di più in rete, ma ecco il succo:espressione infissa ( 1 + 2 ) * 3 sebbene facile da leggere ed elaborare per gli esseri umani, non molto efficiente per l'elaborazione tramite macchina.Cosa è?Regola semplice che dice "riscrivi l'espressione memorizzandola nella cache in precedenza, quindi elaborala sempre da sinistra a destra".Quindi l'infisso ( 1 + 2 ) * 3 diventa un suffisso 12+3*.POST perché l'operatore viene posizionato sempre DOPO gli operandi.
2).Valutazione dell'espressione suffissa.Facile.Leggere i numeri dalla stringa suffisso.Spingerli in pila finché non viene visualizzato un operatore.Controlla il tipo di operatore: unario?binario?terziario?Estrai dallo stack tutti gli operandi necessari per valutare questo operatore.Valutare.Rimetti il risultato in pila!E hai quasi finito.Continua a farlo finché lo stack non avrà una sola voce = valore che stai cercando.
Facciamo ( 1 + 2 ) * 3 che in postfisso è "12+3*".Leggi il primo numero = 1.Mettilo in pila.Leggi dopo.Numero = 2.Mettilo in pila.Leggi dopo.Operatore.Quale?+.Che tipo?Binario = necessita di due operandi.Apri lo stack due volte = argright è 2 e argleft è 1.1 + 2 fa 3.Rimettine 3 in pila.Leggi successivo dalla stringa suffisso.È un numero.3.Premere.Leggi dopo.Operatore.Quale?*.Che tipo?Binario = necessita di due numeri -> pop stack due volte.Prima entra in argright, la seconda volta in argleft.Valuta l'operazione: 3 per 3 fa 9. Inserisci 9 nello stack.Leggi il carattere suffisso successivo.È nullo.Fine dell'input.Pop stack onec = questa è la tua risposta.
3).Shunting Yard viene utilizzato per trasformare l'espressione infissa (facilmente) leggibile dall'uomo in un'espressione suffissa (anche facilmente leggibile dall'uomo dopo un po' di pratica).Facile da codificare manualmente.Vedi i commenti sopra e in rete.
Dipende da quanto vuoi che sia "generale".
Se vuoi che sia davvero molto generale, ad esempio essere in grado di analizzare funzioni matematiche come sin(4+5)*cos(7^3) probabilmente avrai bisogno di un analizzare l'albero.
In cui, non penso che sia opportuno incollare qui un'implementazione completa.Ti suggerirei di dare un'occhiata a uno dei famigerati "Libro del drago".
Ma se vuoi solo il supporto per la precedenza, allora potresti farlo convertendo prima l'espressione in una forma suffissa in cui dovrebbe essere disponibile un algoritmo che puoi copiare e incollare Google oppure penso che tu possa codificarlo tu stesso con un albero binario.
Quando lo hai in forma suffissa, da quel momento in poi è un gioco da ragazzi poiché capisci già come lo stack aiuta.
Suggerirei di imbrogliare e utilizzare il file Algoritmo di manovra.È un mezzo semplice per scrivere un semplice parser di tipo calcolatrice e tiene conto della precedenza.
Se vuoi tokenizzare correttamente le cose e avere variabili, ecc.coinvolto, andrei avanti e scriverei un parser di discesa ricorsivo come suggerito da altri qui, tuttavia se hai semplicemente bisogno di un parser in stile calcolatrice, questo algoritmo dovrebbe essere sufficiente :-)
Ho trovato questo su PIClist riguardo a Algoritmo dello scalo di manovra:
Harold scrive:
Ricordo di aver letto, molto tempo fa, di un algoritmo che ha convertito espressioni algebriche in RPN per una facile valutazione.Ogni valore di infix o operatore o parentesi era rappresentato da un auto ferroviario su una pista.Un tipo di auto si è diviso su un'altra pista e l'altro è continuato dritto davanti.Non ricordo i dettagli (ovviamente!), Ma ho sempre pensato che sarebbe stato interessante codificare.Questo è quando stavo scrivendo 6800 (non 68000) codice di montaggio.
Questo è "Algorythm del cantiere di shunting" ed è ciò che la maggior parte dei parser di macchina usa.Vedi l'articolo sull'analisi di Wikipedia.Un modo semplice per codificare l'algoratura del cantiere di shunting è usare due stack.Uno è lo stack "Push" e l'altro lo stack "Riduci" o "risultato".Esempio:
pstack = () // vuoto rStack = () Input:1+2*3 Precedente = 10 // Riduci più bassa = 0 // Non ridurre
inizio:gettone '1':isnumber, messo in pstack (push) token '+':ISOPERATOR set Precedence = 2 If Precedence <precedente_operator_precedence quindi riduci () // vedi sotto put '+' in Pstack (push) token '2':isnumber, messo in pstack (push) token '*':Isoperatore, set precedenza = 1, messo in pstack (push) // Controlla la precedenza come // sopra token '3':ISNUMBER, messo in pstack (push) estremità dell'input, è necessario ridurre (l'obiettivo è vuoto pstack) ridotto () // fatto
Per ridurre, gli elementi pop dallo stack push e metterli nello stack dei risultati, scambiare sempre i primi 2 elementi su Pstack se sono del modulo "Numero": Numero ":
pstack:'1' '+' '2' '' '3' stack:() ...pstack:() stack:'3' '2' '' '1' '+'
se l'espressione fosse stata:
1*2+3
Quindi il grilletto di riduzione sarebbe stata la lettura del token "+" che ha una precendeca inferiore a quella già spinta, quindi avrebbe fatto:
pstack:'1' '' '2' stack:()...pstack:() stack:'1' '2' ''
e poi spinto "+" e poi "3" e infine ridotto:
pstack:'+' '3' rstack:'1' '2' ''...pstack:() stack:'1' '2' '' '3' '+'
Quindi la versione breve è:spingere i numeri, quando si spingono gli operatori controlla la precedenza del precedente operatore.Se era più alto di quello dell'operatore che deve essere spinto ora, prima riduci, quindi spingi l'attuale operatore.Per gestire i parenti, salvare semplicemente la precedenza del "precedente operatore" e mettere un segno sullo pstack che indica all'algorythm di riduzione di smettere di ridurre quando si risolve l'interno di una coppia di Paren.Il parente di chiusura innesca una riduzione così come la fine dell'input e rimuove anche il marchio di parente aperto dallo pstack e ripristina la precedenza della "precedente operazione" in modo che l'analisi possa continuare dopo il parente vicino da cui si era interrotto.Questo può essere fatto con ricorsione o senza (suggerimento:Usa uno stack per archiviare la precedente precedente quando si incontrano un '(' ...).La versione generalizzata di questo consiste nell'utilizzare un generatore di parser implementato Shunting Yard Algorythm, F.Ex.Usando YACC o Bison o Tacche (analogo TCL di YACC).
Peter
-Adamo
Ho pubblicato la fonte per un ultra compatto (1 classe, <10 KiB) Valutatore matematico Java sul mio sito web.Questo è un parser di discesa ricorsivo del tipo che ha causato l'esplosione cranica per il poster della risposta accettata.
Supporta la precedenza completa, le parentesi, le variabili denominate e le funzioni ad argomento singolo.
ho rilasciato un parser di espressioni basato su Il piazzale di smistamento di Dijkstra algoritmo, secondo i termini del Licenza Apache 2.0:
Un'altra risorsa per l'analisi della precedenza è il file Parser di precedenza degli operatori voce su Wikipedia.Copre l'algoritmo di smistamento di Dijkstra e un algoritmo alternativo ad albero, ma più in particolare copre un algoritmo di sostituzione macro davvero semplice che può essere banalmente implementato di fronte a qualsiasi parser ignorante di precedenza:
#include <stdio.h>
int main(int argc, char *argv[]){
printf("((((");
for(int i=1;i!=argc;i++){
if(argv[i] && !argv[i][1]){
switch(argv[i]){
case '^': printf(")^("); continue;
case '*': printf("))*(("); continue;
case '/': printf("))/(("); continue;
case '+': printf(")))+((("); continue;
case '-': printf(")))-((("); continue;
}
}
printf("%s", argv[i]);
}
printf("))))\n");
return 0;
}
Invocarlo come:
$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))
Il che è fantastico nella sua semplicità e molto comprensibile.
Ho implementato a parser di discesa ricorsivo a Giava nel Parser MathEclipse progetto.Potrebbe anche essere usato come a Kit di strumenti web di Google modulo
Attualmente sto lavorando a una serie di articoli per creare un parser di espressioni regolari come strumento di apprendimento per modelli di progettazione e programmazione leggibile.Puoi dare un'occhiata codice leggibile.L'articolo presenta un chiaro utilizzo dell'algoritmo dei cantieri di manovra.
Ho scritto un parser di espressioni in F# e ne ho parlato nel blog qui.Utilizza l'algoritmo del cantiere di manovra, ma invece di convertire da infisso a RPN, ho aggiunto un secondo stack per accumulare i risultati dei calcoli.Gestisce correttamente la precedenza degli operatori, ma non supporta gli operatori unari.L'ho scritto per imparare il Fa#, non per imparare l'analisi delle espressioni, però.
È possibile trovare una soluzione Python che utilizza pyparsing Qui.L'analisi della notazione infissa con vari operatori con precedenza è abbastanza comune, quindi pyparsing include anche il file infixNotation (precedentemente operatorPrecedence) generatore di espressioni.Con esso puoi facilmente definire espressioni booleane usando, ad esempio, "AND", "OR", "NOT".Oppure puoi espandere la tua aritmetica a quattro funzioni per utilizzare altri operatori, come !per fattoriale, o '%' per modulo, oppure aggiungi operatori P e C per calcolare permutazioni e combinazioni.Potresti scrivere un parser infisso per la notazione matriciale, che includa la gestione degli operatori '-1' o 'T' (per inversione e trasposizione).L'esempio operatorPrecedence di un parser a 4 funzioni (con '!' inserito per divertimento) è Qui e lo è un parser e un valutatore più completo Qui.
So che questa è una risposta tardiva, ma ho appena scritto un piccolo parser che consente a tutti gli operatori (prefisso, postfisso e infisso sinistro, infisso destro e non associativo) di avere precedenza arbitraria.
Ho intenzione di espanderlo per un linguaggio con supporto DSL arbitrario, ma volevo solo sottolineare che non sono necessari parser personalizzati per la precedenza degli operatori, è possibile utilizzare un parser generalizzato che non necessita affatto di tabelle e cerca semplicemente la precedenza di ciascun operatore così come appare.Le persone hanno menzionato parser Pratt personalizzati o parser di smistamento che possono accettare input illegali: questo non ha bisogno di essere personalizzato e (a meno che non ci sia un bug) non accetterà input errati.In un certo senso non è completo, è stato scritto per testare l'algoritmo e il suo input è in una forma che richiederà una certa preelaborazione, ma ci sono commenti che lo rendono chiaro.
Si noti che mancano alcuni tipi comuni di operatori, ad esempio il tipo di operatore utilizzato per l'indicizzazione, ad esempio table[index] o per chiamare una funzione function(parameter-expression, ...) Li aggiungerò, ma pensa a entrambi come operatori suffissi in cui ciò che si trova tra i demetri '[' e ']' o '(' e ')' viene analizzato con un'istanza diversa del parser di espressioni.Mi spiace di averlo tralasciato, ma è presente la parte suffissa: aggiungere il resto probabilmente raddoppierà quasi la dimensione del codice.
Dato che il parser è composto da solo 100 righe di codice racchetta, forse dovrei semplicemente incollarlo qui, spero che non sia più lungo di quanto consentito da StackOverflow.
Alcuni dettagli sulle decisioni arbitrarie:
Se un operatore suffisso a bassa precedenza compete per gli stessi blocchi infissi di un operatore con prefisso a bassa precedenza, l'operatore prefisso vince.Questo non appare nella maggior parte delle lingue poiché la maggior parte non ha operatori suffissi con bassa precedenza.- ad esempio:((dati a) (sinistra 1 +) (pre 2 non)(dati b)(post 3 !) (sinistra 1 +) (dati c)) è a+non b!+c dove not è un operatore di prefisso e !è l'operatore suffisso ed entrambi hanno un valore inferiore precedenza di + quindi vogliono raggruppare in modi incompatibili come (a+non b!) +c o come A+(non B!+C) In questi casi l'operatore prefisso vince sempre, quindi il secondo è il modo in cui analizza
Gli operatori infissi non associativi sono davvero lì in modo che tu non debba fingere che gli operatori che restituiscono tipi diversi da quelli che hanno senso insieme, ma senza avere tipi di espressione diversi per ciascuno è un kludge.Pertanto, in questo algoritmo, gli operatori non associativi rifiutano di associarsi non solo con se stessi ma con qualsiasi operatore con la stessa precedenza.Questo è un caso comune poiché < <= == >= etc non si associano tra loro nella maggior parte delle lingue.
La questione di come diversi tipi di operatori (sinistra, prefisso, ecc.) interrompono i legami di precedenza è una questione che non dovrebbe sorgere, perché non ha davvero senso dare a operatori di tipi diversi la stessa precedenza.Questo algoritmo fa qualcosa in questi casi, ma non mi prendo nemmeno la briga di capire esattamente cosa perché una grammatica del genere è in primo luogo una cattiva idea.
#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4))
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))
(struct prec-parse ([data-stack #:mutable #:auto]
[op-stack #:mutable #:auto])
#:auto-value '())
(define (pop-data stacks)
(let [(data (car (prec-parse-data-stack stacks)))]
(set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
data))
(define (pop-op stacks)
(let [(op (car (prec-parse-op-stack stacks)))]
(set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
op))
(define (push-data! stacks data)
(set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))
(define (push-op! stacks op)
(set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))
(define (process-prec min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((>= (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-prec min-prec stacks))))))))
(define (process-nonassoc min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((> (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-nonassoc min-prec stacks))
((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
))))))
(define (apply-op op stacks)
(let [(op-type (car op))]
(cond ((eq? op-type 'post)
(push-data! stacks `(,op ,(pop-data stacks) )))
(else ;assume infix
(let [(tos (pop-data stacks))]
(push-data! stacks `(,op ,(pop-data stacks) ,tos)))))))
(define (finish input min-prec stacks)
(process-prec min-prec stacks)
input
)
(define (post input min-prec stacks)
(if (null? input) (finish input min-prec stacks)
(let* [(cur (car input))
(input-type (car cur))]
(cond ((eq? input-type 'post)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(process-prec (cadr cur)stacks)
(push-data! stacks (cons cur (list (pop-data stacks))))
(post (cdr input) min-prec stacks))))
(else (let [(handle-infix (lambda (proc-fn inc)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(proc-fn (+ inc (cadr cur)) stacks)
(push-op! stacks cur)
(start (cdr input) min-prec stacks)))))]
(cond ((eq? input-type 'left) (handle-infix process-prec 0))
((eq? input-type 'right) (handle-infix process-prec 1))
((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))
(else error "post op, infix op or end of expression expected here"))))))))
;alters the stacks and returns the input
(define (start input min-prec stacks)
(if (null? input) (error "expression expected")
(let* [(cur (car input))
(input-type (car cur))]
(set! input (cdr input))
;pre could clearly work with new stacks, but could it reuse the current one?
(cond ((eq? input-type 'pre)
(let [(new-stack (prec-parse))]
(set! input (start input (cadr cur) new-stack))
(push-data! stacks
(cons cur (list (pop-data new-stack))))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks)))
((eq? input-type 'data)
(push-data! stacks cur)
(post input min-prec stacks))
((eq? input-type 'grouped)
(let [(new-stack (prec-parse))]
(start (cdr cur) MIN-PREC new-stack)
(push-data! stacks (pop-data new-stack)))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks))
(else (error "bad input"))))))
(define (op-parse input)
(let [(stacks (prec-parse))]
(start input MIN-PREC stacks)
(pop-data stacks)))
(define (main)
(op-parse (read)))
(main)
Ecco una semplice soluzione ricorsiva scritta in Java.Nota che non gestisce i numeri negativi ma puoi aggiungerli se vuoi:
public class ExpressionParser {
public double eval(String exp){
int bracketCounter = 0;
int operatorIndex = -1;
for(int i=0; i<exp.length(); i++){
char c = exp.charAt(i);
if(c == '(') bracketCounter++;
else if(c == ')') bracketCounter--;
else if((c == '+' || c == '-') && bracketCounter == 0){
operatorIndex = i;
break;
}
else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
operatorIndex = i;
}
}
if(operatorIndex < 0){
exp = exp.trim();
if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
return eval(exp.substring(1, exp.length()-1));
else
return Double.parseDouble(exp);
}
else{
switch(exp.charAt(operatorIndex)){
case '+':
return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
case '-':
return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
case '*':
return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
case '/':
return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
}
}
return 0;
}
}
L'algoritmo potrebbe essere facilmente codificato in C come parser di discesa ricorsiva.
#include <stdio.h>
#include <ctype.h>
/*
* expression -> sum
* sum -> product | product "+" sum
* product -> term | term "*" product
* term -> number | expression
* number -> [0..9]+
*/
typedef struct {
int value;
const char* context;
} expression_t;
expression_t expression(int value, const char* context) {
return (expression_t) { value, context };
}
/* begin: parsers */
expression_t eval_expression(const char* symbols);
expression_t eval_number(const char* symbols) {
// number -> [0..9]+
double number = 0;
while (isdigit(*symbols)) {
number = 10 * number + (*symbols - '0');
symbols++;
}
return expression(number, symbols);
}
expression_t eval_term(const char* symbols) {
// term -> number | expression
expression_t number = eval_number(symbols);
return number.context != symbols ? number : eval_expression(symbols);
}
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
expression_t eval_sum(const char* symbols) {
// sum -> product | product "+" sum
expression_t product = eval_product(symbols);
if (*product.context != '+')
return product;
expression_t sum = eval_sum(product.context + 1);
return expression(product.value + sum.value, sum.context);
}
expression_t eval_expression(const char* symbols) {
// expression -> sum
return eval_sum(symbols);
}
/* end: parsers */
int main() {
const char* expression = "1+11*5";
printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);
return 0;
}
le prossime librerie potrebbero essere utili: yupana - operazioni strettamente aritmetiche; tinyexpr - operazioni aritmetiche + funzioni matematiche C + una fornita dall'utente; MPC - combinatori di parser
Spiegazione
Catturiamo una sequenza di simboli che rappresentano l'espressione algebrica.Il primo è un numero, cioè una cifra decimale ripetuta una o più volte.Faremo riferimento a tale notazione come regola di produzione.
number -> [0..9]+
L'operatore di addizione con i suoi operandi è un'altra regola.Lo è o number o qualsiasi simbolo che rappresenta sum "*" sum sequenza.
sum -> number | sum "+" sum
Prova il sostituto number in sum "+" sum quello sarà number "+" number in cui a sua volta potrebbe essere ampliato [0..9]+ "+" [0..9]+ che finalmente potrebbe essere ridotto a 1+8 che è l'espressione corretta dell'addizione.
Anche altre sostituzioni produrranno un'espressione corretta: sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
A poco a poco potremmo assomigliare a un insieme di regole di produzione ovvero grammatica che esprimono tutte le possibili espressioni algebriche.
expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+
Per controllare la precedenza dell'operatore altera la posizione della sua regola di produzione rispetto agli altri.Guarda la grammatica sopra e nota la regola di produzione per * è posto sotto + questo forzerà product valutare prima sum.L’implementazione combina semplicemente il riconoscimento dei modelli con la valutazione e quindi rispecchia da vicino le regole di produzione.
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
Qui valutiamo term prima e restituiscilo se non c'è * carattere dopo di esso questa è una scelta lasciata nella nostra regola di produzione altrimenti - valuta i simboli dopo e ritorna term.value * product.value questa è la scelta giusta nella nostra regola di produzione, ad es. term "*" product
