hack3r (Normal User)
Rookie
Messaggi: 38
Iscritto: 14/06/2009
|
eco che salto fuori con questa domanda, mi chiedo effettivamente a cosa serve studiare i metodi per la conversione di automi es :
da automa finito non deterministico ad automa finito deterministico, (con la costruzione dei sottoinsiemi)
oppure da espressione regolare ad automa finito
grazie in anticipo
|
|
TheKaneB (Member)
Guru^2
Messaggi: 1792
Iscritto: 26/06/2009
|
Serve per scrivere dei parser, i quali a loro volta servono per creare compilatori ed interpreti.
Un parser deve riconoscere un testo scritto in un certo linguaggio e crearne l'albero sintattico. Se il linguaggio da riconoscere è espresso per mezzo di una grammatica CF, allora le produzioni di quella grammatica saranno a loro volta dei linguaggi CF o regolari e qui entrano in gioco gli algoritmi per trasformare un'espressione regolare in automa a stati finiti.
L'automa a stati finiti che viene generato sarà quello che effettivamente svolgerà il lavoro di riconoscimento di quella espressione regolare, che unito a tutti gli altri automi, uno per ogni produzione della grammatica, comporrà i vari pezzi del parser.
Una volta ottenuto un parser poi lo si può associare ad una virtual machine (ad esempio come motore di scripting di un videogioco), un code generator (come ad esempio un interprete con Jit Compilation, o un classico compilatore), un motore di rendering (ad esempio un parser per l'HTML può essere associato ad un sistema di rendering grafico per produre pagine web, come WebKit, Gecko e Trident per capirci) e tante altre cose...
Spero di aver soddisfatto la tua curiosità e allo stesso tempo di averti dato spunto per approfondire la questione!
|
|
hack3r (Normal User)
Rookie
Messaggi: 38
Iscritto: 14/06/2009
|
grazie mille
ho trovato un ottimo libro : automi linguaggi e calcolabilità, non vedo l'ora di divorarmelo
ps. però generalmente un programmatore/ingegnere del software non deve prendersi carta e penna e trasformare le sue grammatiche in DFA da implementare, giusto !? A quelli ci pensano i generatori di parser e/o di lexer come bison o flex !
|
|
hack3r (Normal User)
Rookie
Messaggi: 38
Iscritto: 14/06/2009
|
scusate ancora ma secondo voi per esempio è meglio implementarsi da 0 il proprio parser o usare un generatore
|
|
TheKaneB (Member)
Guru^2
Messaggi: 1792
Iscritto: 26/06/2009
|
Postato originariamente da hack3r:
scusate ancora ma secondo voi per esempio è meglio implementarsi da 0 il proprio parser o usare un generatore |
A scopo didattico è meglio crearselo da zero, così impari meglio tutti i dettagli. Poi, se ti serve per cose professionali, userai bison e flex, ovviamente, in modo da concentrarti sugli aspetti meno noiosi del programma |
|
hack3r (Normal User)
Rookie
Messaggi: 38
Iscritto: 14/06/2009
|
grazie
|
|