Corso di Laurea Specialistica in Ingegneria Informatica Itinerari aerei Progetto per lesame di...

Corso di Laurea Specialistica in Ingegneria Informatica

Itinerari aerei

Progetto per l’esame di Linguaggi e Modelli Computazionali LS realizzato da Stefano Landi

Prof. Enrico Denti

Anno Accademico 2006-2007

Scopo del progetto

• Definire un linguaggio che possa essere di aiuto nella descrizione e nella valutazione di itinerari aerei

• Aiutare l’utente: tramite opportuni controlli, a specificare correttamente e

logicamente tutti i dati a scegliere quindi il volo migliore per le sue esigenze

Il problema

• Vi sono oggigiorno compagnie che si definiscono point-to-point, ovvero che non permettono di pianificare voli con scalo, ma forniscono solo il supporto per l’acquisto di biglietti per voli singoli

• Il proliferare delle compagnie low cost ha fatto sì che l’utente possa voler pianificare un itinerario con voli di diverse compagnie (e i siti delle compagnie non permettono gli “incroci” tra di loro!)

Il problema• Volando in aereo ci si trova ad avere a che fare con:

fusi orari diversivalute diverse (dipendenti dallo stato)possibilità di scali in città diverse (quello che interessa

generalmente all’utente è da dove si parte e dove si arriva, non le “fermate intermedie”!)

possibilità di voli diretti o con uno o più scaliprezzi molto diversi a seconda del giorno, della compagnia… costi tipicamente distinti per prezzo base e tasse tempi di percorrenza totali molto diversi dipendenti da

numero di scali, tragitti, tempi intermedi di attesa in aeroporto…

Grammatica

• Utilizzo la notazione dello strumento jjdoc• G = <VT, VN, P, S>• P è l’insieme di tutte le produzioni della

grammatica

• Il mio fine è descrivere e valutare un viaggio aereo, e di conseguenza la grammatica ha come scopo proprio:Scopo::= “Viaggio:“ Viaggio <EOF>

Grammatica• Viaggio::= ( “Possibilita:” Possibilita )*

• Da notare la presenza dell’ ‘*’ => del fatto che ci possano essere 0…N possibilità di viaggio => che non ce ne siano affatto! La grammatica accetta senza problemi la frase “Viaggio:”.

• Questo non genera incoerenza: tutto avviene correttamente, semplicemente le soluzioni valutate saranno zero.

• … d’altra parte un programma scritto in C o in Java con un Main vuoto cosa fa? … nulla, ma “funziona” benissimo! Allo stesso modo il mio valutatore, se non vengono fornite possibilità da valutare, non dà nessun errore ma logicamente non fa nulla e non fornisce alcun risultato!

• D’altra parte ci potremmo immaginare uno strumento automatico di generazioni di frasi, da poi valutare, per esempio a partire da un db: se non vi fossero possibilità nel db corrispondenti alle scelte dell’utente (in input per esempio da interfaccia grafica), verrebbe generata solo la frase “Viaggio:”.

Grammatica

• Possibilita::= “{“ ( “Volo:” Volo )+ “}”

• Notare il ‘+’ : una possibilità di itinerario produce 1…N voli: non ha infatti senso in questo caso prevedere una possibilità senza voli. Se esiste una possibilità, ci deve essere almeno un volo.

• Niente self embedding: una e una sola parentesi graffa prima, una e una sola dopo: nessun livello di nesting di cui tenere conto.

Grammatica

• Volo::= “[“ “Codice:” <STRINGAALFANUMERICA> “Partenza:” Partenza “Arrivo:” Arrivo “Costo:” Costo “]”

• Partenza::= “(“ “Data:” <DATA> “Ora:” <ORA> “Fuso:” <FUSO> “Luogo:” <STRINGAALFANUMERICA> “)”

• L’espansione del VN Arrivo è analoga a quella della Partenza : le ho lasciate differenziate per questione di ordine e di leggibilità

• Ammetto anche numeri nel luogo: considero valida anche luoghi come “città1” (utilizzabili per prove o debug)

Grammatica

• Costo::= “(“ “Prezzo:” <NUMEROCONDUEDECIMALI> “Tasse:” <NUMEROCONDUEDECIMALI> “Valuta:” <VALUTA> “)”

• Grammatica rigida: i numeri vanno espressi forzatamente con due decimali. D’altra parte questa è l’usanza tipica di molte valute. Infatti siamo abituati ai centesimi per gli Euro, per la sterlina, per i Dollari…

• Ipotizzo (ragionevolmente) che il prezzo e le tasse di un volo siano espresse nella stessa valuta

Grammatica – Token

• <#NUMERO>::= ["0"-"9"]

• <#NUMEROSENZAZERO>::= ["1"-"9"]

• <#LETTERA>::= ["a"-"z", "A"-"Z", "_"]

• Le espansioni che iniziano con ‘#’ sono interne al mondo dei token e non interessano le produzioni, che non le vedono non le possono utilizzare.

Grammatica - osservazioni

• La grammatica è volutamente abbastanza rigida (richiede di scrivere ogni volta Codice:, Partenza:, Ora:, Luogo:, …): questo perché intendevo dare una struttura che facilitasse non solo la lettura automatica ma anche “umana” di una frase del linguaggio

• Per quello che riguarda i token ho voluto intenzionalmente essere restrittivo nel modo di specificare date e orari: questo impone una attenzione maggiore da parte dell’utente nello scrivere le frasi, ma aiuta l’individuazione di errore da parte del programma


• La grammatica comprende la stringa vuota nella seconda produzione (quella che contiene in EBNF il simbolo ’*’: un viaggio può produrre da 0 a N possibilità), ma questa può essere eliminata con una semplice manipolazione algebrica

• Scopo::= “Viaggio:“ Viaggio <EOF>• Viaggio::= ( “Possibilita:” Possibilita )*


• Infatti possiamo facilmente vedere come:

Scopo::= “Viaggio:“ Viaggio <EOF>

Viaggio::= ( “Possibilita:” Possibilita )*

equivale a

Scopo::= “Viaggio:“ (Viaggio)? <EOF>

Viaggio::= ( “Possibilita:” Possibilita )+


• Utilizzando la BNF non Extended possiamo vedere come la -rule possa essere eliminata

Scopo::= “Viaggio:“ Viaggio <EOF>

Viaggio::= “Possibilita:” Possibilita Viaggio |

che equivale a

Scopo::= “Viaggio:“ Viaggio | “Viaggio:“ <EOF>

Viaggio::= “Possibilita:” Possibilita Viaggio | “Possibilita:” Possibilita


• Il linguaggio è di tipo 3 ma, secondo la classificazione di Chomsky, la grammatica è di tipo 2 in quanto le produzioni non sono regolarigrammatica di tipo 2 + assenza di self-embedding => il

linguaggio è regolare la grammatica non è stata riscritta per leggibilità

• la grammatica è LL(1)

Strumenti utilizzati

• Java 1.6

• JavaCC 4.0

• Java Tree Builder 1.3.2

• NetBeans 5.5

Architettura

• packages creati e “imposti” dagli strumenti automatici utilizzati

• packages creati seguendo il modello architetturale dato dagli strumenti automatici

Architettura

• syntaxtree contiene quanto necessario all’albero sintattico una serie di classi relative ai nodi una classe per ogni metasimbolo della grammatica

• parser contiene quanto serve per la gestione del parser classi per il parser e per i token per la gestione delle eccezioni e degli errori lessicali

• visitor contiene vari visitor di default generati dallo strumento automatico (presenti ma non

sfruttati durante l’esecuzione) il visitor ItinerarioVisitor che si occupa della valutazione dell’albero:

controlla la coerenza dei dati e fornisce l’output

Architettura

• main contiene solo il (brevissimo) file di lancio dell’applicazione

• grafica contiene quando relativo all’interfaccia grafica e alla gestione degli eventi e di quanto compete l’interfaccia

• utility contiene alcune classi atte a semplificare la gestione dei dati inseriti nell’albero sintattico e metodi sfruttati nella valutazione da parte del visitor e nella successiva visualizzazione in output

esplicitati solo i metodi principali!

eseguono i controlli della coerenza dei dati inseriti (orari compatibili, città degli scali corrette…)

L’interfaccia grafica

Limiti dell’applicazione e sviluppi futuri

• L’applicazione non esegue alcun controllo tra le città e i fusi orari inseriti in input: per fare ciò sarebbe infatti necessario avere una enorme tabella con tutte le corrispondenze

• Le valute possibili utilizzabili sono poche, date solo a titolo di esempio: per una funzionalità completa ne andrebbero inserite molte altre

• I possibili sviluppi futuri potrebbero andare in varie direzioni: pianificazione di itinerari con andata e ritorno ordine dei voli in output fornito sulla base di più parametri o con parametri

secondari (es: visualizzazione per numero di scali e, in caso parità, anche di costo) si potrebbe consentire il confronto anche tra voli con città di partenza e/o di arrivo

diverse, purché nel raggio di un certo numero di Km ulteriori opzioni di visualizzazione o di controllo

Corso di Laurea Specialistica in Ingegneria Informatica Itinerari aerei Progetto per lesame di...

Documents

Transcript of Corso di Laurea Specialistica in Ingegneria Informatica Itinerari aerei Progetto per lesame di...