Progetto per gli esami di Ingegneria del Software e Intelligenza Artificiale



Scaricare 345.5 Kb.
Pagina4/7
23.05.2018
Dimensione del file345.5 Kb.
1   2   3   4   5   6   7

Riconoscimento del linguaggio

Stabilito il linguaggio, dobbiamo ora procedere a progettare un riconoscitore per tale linguaggio, che sarà parte integrante del sistema. Possiamo suddividere il riconoscimento in due distinte fasi, rispettivamente analisi lessicale ed analisi sintattica. L'analisi lessicale ha il compito di identificare all'interno del listato i diversi elementi lessicali come numeri, identificatori, operatori, ecc. Pertanto in uscita dall'analizzatore lessicale si avranno dei token diversi a seconda dell'elemento lessicale che è stato letto. L'analisi sintattica invece si occupa di ricevere i token in ingresso e di costruire le strutture dati opportune (variabili, domini, vincoli). Abbiamo dunque bisogno di due classi apposite che svolgono questi compiti, che sono Lexer (analizzatore lessicale) e Parser (analizzatore sintattico). Inoltre dobbiamo costruire una tassonomia per la rappresentazione dei token, per la quale ci sarà una classe base Token da cui deriveranno NumToken e IntToken (per i numeri), IdentToken (per identificare gli operatori), EOLToken (per il carattere di fine linea), EmptyToken (per il carattere di fine stringa), VariableToken (per gli identificatori delle variabili) e KeywordToken (per le parole chiave del linguaggio).

P
er i vincoli, la rappresentazione interna delle espressioni può essere fatta mediante un Abstract Parse Tree (APT), che verrà creato dal parser e che conterrà oggetti appartenenti alla tassonomia delle espressioni simboliche. La classe base di questa gerarchia è la classe Exp, dalla quale derivano OpExp (per le espressioni composte), AtomExp (per le espressioni atomiche), NumExp e IntExp (per i numeri), IdentExp (per le variabili), BoolExp (per le espressioni booleane).

P
er realizzare l'analisi sintattica si utilizzerà la tecnica dell'analisi ricorsiva discendente, che consiste nel mappare ogni elemento sintattico in una funzione (nel nostro caso un metodo della classe Parser) che si dovrà occupare di consumare i token che gli competono e di costruirne la corrispondente rappresentazione interna. Il Parser avrà quindi i metodi readProgram(), readVariable(), readDomain(), readConstraint(), readExp(), readTerm(), readFact() che espletano questa funzionalità.






Risoluzione

Una volta chiarita la struttura del sistema ed i modi con cui è possibile inizializzare i dati del problema, è ora giunto il momento di affrontare la parte più importante del progetto, ovvero la risoluzione del problema. Si sono previsti due tipi di risoluzione: lo standard backtracking e la propagazione. Avremo quindi due metodi differenti all'interno della classe CSProblem che permettono di avviare un tipo di risoluzione o l'altra. Si riportano gli algoritmi in linguaggio naturale:


Standard Backtracking (metodo solveSB())


  • Se ci sono vincoli violati o variabili con dominio vuoto riporta fallimento ed esegui backtracking

  • Se tutte le variabili sono istanziate (cioè è stata trovata una soluzione)

  • Aggiungi la soluzione corrente all'insieme delle soluzioni trovate

  • Se è stato raggiunto il numero di soluzioni richieste termina la risoluzione riportando successo

  • Altrimenti backtracking per ricercare le altre soluzioni

  • Altrimenti

  • Seleziona la variabile corrente usando l'euristica specificata

  • Seleziona il valore da assegnare alla variabile corrente secondo l'euristica specificata

  • Salva lo stato corrente delle variabili

  • Assegna il valore alla variabile corrente

  • Chiama ricorsivamente la risoluzione

  • In caso di successo termina la risoluzione con successo

  • Altrimenti

  • Ripristina lo stato precedente delle variabili

  • Rimuovi il valore appena considerato dal dominio della variabile corrente

  • Scegli il valore successivo e invoca ricorsivamente la risoluzione

Propagazione (metodo solve())




  • Se ci sono variabili con dominio vuoto riporta fallimento ed esegui backtracking

  • Se tutte le variabili sono istanziate (cioè è stata trovata una soluzione)

  • Aggiungi la soluzione corrente all'insieme delle soluzioni trovate

  • Se è stato raggiunto il numero di soluzioni richieste termina la risoluzione riportando successo

  • Altrimenti backtracking per ricercare le altre soluzioni

  • Altrimenti

  • Seleziona la variabile corrente usando l'euristica specificata

  • Seleziona il valore da assegnare alla variabile corrente secondo l'euristica specificata

  • Salva lo stato corrente delle variabili

  • Assegna il valore alla variabile corrente

  • Effettua la propagazione dei vincoli usando l'algoritmo specificato

  • Chiama ricorsivamente la risoluzione

  • In caso di successo termina con successo

  • Altrimenti

  • Ripristina lo stato precedente delle variabili

  • Rimuovi il valore appena considerato dal dominio della variabile corrente

  • Scegli il valore successivo e invoca ricorsivamente la risoluzione

Questi algoritmi mostrano la struttura ricorsiva che si è adottata per la risoluzione, in realtà per ognuno dei due tipi di risoluzione illustrati sono necessari due metodi che si invocano tra loro alternativamente: il primo si occupa di verificare se è stata trovata una soluzione e di operare la scelta della variabile da istanziare, il secondo invece si occupa di salvare lo stato delle variabili, di selezionare via via i valori da assegnare alla variabile corrente (e di propagare i vincoli nel secondo caso) ed eventualmente ripristinare lo stato precedente in caso di backtracking. Abbiamo messo in evidenza la necessità di dovere salvare (ad esempio in uno stack) lo stato delle variabili ad un certo punto della computazione, al fine di recuperarlo nel caso sia richiesto di fare un backtracking. Da notare che, nel secondo caso, è necessario salvare lo stato di tutte le variabili in quanto la propagazione potrebbe avere modificato il dominio di qualunque variabile e non solo di quella corrente.


Quando viene raggiunta una soluzione, essa dovrà essere memorizzata in una struttura dati apposita, perciò introduciamo una nuova classe Solution in grado di contenere i legami delle variabili ai valori che sono stati assegnati loro. Inoltre, visto che l'utente può richiedere anche più di una soluzione dobbiamo avere una classe in grado di contenere diversi oggetti di classe Solution, perciò aggiungiamo la classe SolutionVector.
Aggiungiamo poi metodi che saranno utili agli algoritmi di risoluzione, quali getConstraints() (che sovraccarica la getConstraints() già presentata) e che restituisce i vincoli in cui compaiono un insieme di variabili, getInvolvedVariables() che restituisce le variabili coinvolte in almeno uno dei vincoli specificati, getFutureVariables() che restituisce le variabili non istanziate, getInstantiatedVariables() che invece restituisce quelle istanziate e getCurrentVariable() che restituisce l’ultima variabile istanziata.
I
nfine, introduciamo il metodo applyArcConsistency() che restituisce un nuovo CSP ottenuto dal corrente applicando l’arc-consistenza.




Condividi con i tuoi amici:
1   2   3   4   5   6   7


©astratto.info 2019
invia messaggio

    Pagina principale