[PHP] come si fa un parser?! + problema matematico

[Fenomeno85]

Allora sto realizzando un progetto per i cavoli miei dove voglio tracciare una funzione matematica passata.

Adesso però escono alcuni problemi:
1) come realizzo un parser fatto come dio comanda?

attualmente ho spezzato la stringa passata mettendo ogni carattere in un array e poi controllo tutte le possibili combinazioni che posso avere. Ma questa soluzione mi fa cacare e son sicuro che non è da fare. (attualmente mi basterebbe anche disegnare una funzione che è solo somma o sottrazioni di monomi)

2) come scompongo un polinomio di grado n? Ruffini? ma se questo non funziona? perchè quando dovrò implementare le frazioni mi trovo un pò di problemi a capire dove la funzione non può essere assegnata.

~§~ Sempre E Solo Lei ~§~

[The3DProgrammer]

Allora sto realizzando un progetto per i cavoli miei dove voglio tracciare una funzione matematica passata.

Adesso però escono alcuni problemi:
1) come realizzo un parser fatto come dio comanda?

attualmente ho spezzato la stringa passata mettendo ogni carattere in un array e poi controllo tutte le possibili combinazioni che posso avere. Ma questa soluzione mi fa cacare e son sicuro che non è da fare. (attualmente mi basterebbe anche disegnare una funzione che è solo somma o sottrazioni di monomi)

2) come scompongo un polinomio di grado n? Ruffini? ma se questo non funziona? perchè quando dovrò implementare le frazioni mi trovo un pò di problemi a capire dove la funzione non può essere assegnata.

~§~ Sempre E Solo Lei ~§~


ciao.

Allora, se vuoi realizzare un parser come dio comanda devi definire una grammatica che descriva la sintassi delle tue funzioni. Tale grammatica dovrà poi essere analizzata per effettuare un riconoscimento dei simboli che guidino la procedura di parsing (analisi FIRST/FOLLOWS). Una volta fatto questo dovrai scrivere un parser ricorsivo, in grado di riconoscere sintatticamente le espressioni (ovviamente questo presuppone che dovrai realizzare un modulo di analisi semantica, in grado ad es di riconoscere espressioni in input del tipo f(x)/0). Tutto questo nn è tanto semplice cmq, e presuppone la conoscenza di alcune nozioni di teoria dei linguaggi (grammatiche, espressioni regolari, etc). Per il secondo problema nn puoi usare ruffini perkè presuppone che tu conosca almeno un valore per cui il polinomio si annulla, ma è proprio quello che stai cercando per sapere quali valori non appartengono al dominio (ovviamente potresti fare delle valutazioni di prova del polinomio per 1, 2 etc ma il problema rimane cmq)...fammici ragionare un po vediamo se riesco ad aiutarti ;)

[nightwolf]

Vedo che cominci bene l'estate :)

Per scomporre dovresti trovare le radici a1,a2...,an del polinomio in un certo intervallo controllando che la molteplicità di quelle rintracciabili nell'intervallo scelto coincida con il grado. Trovate tutte fai "coeff di grado massimo*(x-a1)*(x-a2)*..."

C'è il teorema di sturm che dovresti leggerti:

http://www.matematica.it/impedovo/articoli/L'algoritmo%20di%20Sturm.pdf

ciao ciao

[The3DProgrammer]

Vedo che cominci bene l'estate :)

Per scomporre dovresti trovare le radici a1,a2...,an del polinomio in un certo intervallo controllando che la molteplicità di quelle rintracciabili nell'intervallo scelto coincida con il grado. Trovate tutte fai "coeff di grado massimo*(x-a1)*(x-a2)*..."

C'è il teorema di sturm che dovresti leggerti:

http://www.matematica.it/impedovo/articoli/L'algoritmo%20di%20Sturm.pdf

ciao ciao

cakkio è vero :doh:

c'era quel metodo per il calcolo degli zeri che, applicando ruffini a cascata, consentiva di "setacciare" l'asse reale alla ricerca delle radici (ah, analisi 1....).

L'algoritmo di sturm è veramente molto interessante, nn lo conoscevo, grazie wolf ;)

[The3DProgrammer]

ora che ci penso xò potresti avere anche dei problemi di rappresentazione delle radici reali.... :eek:

[Fenomeno85]

Vedo che cominci bene l'estate :)

Per scomporre dovresti trovare le radici a1,a2...,an del polinomio in un certo intervallo controllando che la molteplicità di quelle rintracciabili nell'intervallo scelto coincida con il grado. Trovate tutte fai "coeff di grado massimo*(x-a1)*(x-a2)*..."

C'è il teorema di sturm che dovresti leggerti:

http://www.matematica.it/impedovo/articoli/L'algoritmo%20di%20Sturm.pdf

ciao ciao

si tranquilla la inizio :D ... alla fine nel tempo che ho libero se non esco con gli amici o leggo i vari libri di patricia cornwell o mi metto a programmare un pò :D

intanto leggo questo teorema :D grazie

ps: ma economia te sai dove la butta fuori che non la trovo?

~§~ Sempre E Solo Lei ~§~

[Fenomeno85]

un up per come si fa un parser :D

intanto sto studiando come buttare il teorema di sturn ma da quanto sto anche vedendo mi da una poca precisione ... e per esempio scartare un intervallo di 1 mi sembra troppo.

~§~ Sempre E Solo Lei ~§~

[sottovento]

un up per come si fa un parser :D

intanto sto studiando come buttare il teorema di sturn ma da quanto sto anche vedendo mi da una poca precisione ... e per esempio scartare un intervallo di 1 mi sembra troppo.

~§~ Sempre E Solo Lei ~§~
Ciao
a proposito del parser: non si tratta di un programma difficile (a breve, spero, postero' un parser piuttosto "particolare"), c'e' tanta teoria e puoi trovare la cose gia' fatte in Internet.
Mi chiedevo solo una cosa: ti serve veramente? Magari ti serve per esercizio, ma... non sono esperto di php, ma so che e' interpretato, per cui potresti mettere la funzione che ti serve in un file e poi eseguirla.
Perdonami se magari ho detto una castroneria, ma il vantaggio dei linguaggi interpretati e' appunto la possibilita' di fare certi giochetti....
Nel caso invece voglia implementare un parser da te... beh, ricorda che la grammatica e' gia' ben definita, non ti serve fare questo passaggio.
Ci sono almeno due tecniche piuttosto "pratiche" per passare poi dalla teoria all'implementazione: ti consiglio la discesa ricorsiva.

Per quanto riguarda la scelta degli intervalli, ... non e' un reato chiedere all'utente. Casomai cerca di trappare i suoi errori

High Flying
Sottovento

[Fenomeno85]

no il problema è che io ho x^2 + 23*x^4 per esempio e devo controllare che quella sia corretta :)

praticamente io devo avere solo K1*x^n1 + k2*x^n2 + ... + Kn

dove nx>=0 mentre Kx per ogni R.


la scelta degli intervalli la lascio all'utente ... dato che non è un programma e io alla fine butto fuori una immagine png non posso dire sali allarga o altro :D

comunque sui dati del range ho già fatto tutti i vari controlli ;)

Il problema è che vorrei avere anche divisioni di polinomi e questo è un grosso problema, dato che io devo sapere dove non andare.

~§~ Sempre E Solo Lei ~§~

[Fenomeno85]

ma dove sbaglio

[code]
<?php

$string = "+23*x^5";

if (ereg("(\+\d+\*x\^\d+)",$string,$regs)) echo "ok";
else echo "no";


?>
[\code]

accidenti eppure mi sembra giusta :muro: non so quante miliardi di prove che ho fatto :muro:

~§~ Sempre E Solo Lei ~§~

[Fenomeno85]

gente ce l'ho fatta ma ho lasciato stare le espressioni regolari almeno so dove ci sono i problemi e segnalo all'utente l'errore.

http://fenomeno85.altervista.org/hannibal/prova.php

che ve ne pare?

~§~ Sempre E Solo Lei ~§~

[shinya]

Copio e incollo l'esempio che metti sotto "Esempi di funzioni accettate" e mi dice Formula sbagliata: flag^2+3

[Fenomeno85]

grazie mille, sistemato il bug :mano:

~§~ Sempre E Solo Lei ~§~