Progetto per lesame di Linguaggi e Modelli Computazionali LS Chiara Chiara Gualtieri.

ITINERARI SM

TOOL PER ITINERARI TURISTICI NELLA

REPUBBLICA DI SAN MARINO

Progetto per l’esame di “Linguaggi e Modelli Computazionali LS”

Chiara Gualtieri

Sviluppo di un semplice linguaggio perla descrizione di un itinerario turistico nel centro storico di RSM il quale prevede le seguenti attività: Visita di un museo Visita di una chiesa Visita a un monumento Visita di un punto panoramico Visita libera per negozi Pranzo presso un ristorante

OBIETTIVO

WORKFLOW

Definizione di un linguaggio in grado di descrivere le attività previste per creare un itinerario.

Realizzare un’interprete per tale linguaggio che: accetti in ingresso una stringa di caratteri esegua un’analisi sintattica al fine di riconoscere se la

stringa è una frase lecita del linguaggio esegua le azioni corrispondenti alla semantica della frase

immessa Realizzazione di una rappresentazione sotto forma di

albero Realizzare uno strumento grafico che visualizzi le attività

previste nell’itinerario e le informazioni relative ad esse

GRAMMATICA (1/5)

<S> ::= inizio <Visita> fine

<Visita> ::= Partenza prevista in: <Nome> <Coordinate> alle <Ora> del giorno <Data > <Tipo>

<Nome> ::= ( <PAROLA> )+

<Descrizione> ::= ( <PAROLA> )+

<Data> ::= <NUMERO> /<NUMERO> / <NUMERO>

<Ora> ::= ore <NUMERO> : <NUMERO>

<Tipo> ::= <Turistico> | <Culturale> | <Misto>

<Culturale> ::= Itinerario Culturale: ( <TappaCul> )+

<Turistico> ::= Itinerario Turistico: ( <TappaTur >| <VisitaNegozi >)+

<Misto> ::= Itinerario Misto: ( <Tappa> | <VisitaNegozi> )+

<TappaTur> ::= ( <TAPPATUR> | Ristorante: ) <InfoTappa>

<TappaCul >::= ( <TAPPACUL> | Ristorante: ) <InfoTappa>

<Tappa> ::= ( <TAPPACUL> | <TAPPATUR> | Ristorante: ) <InfoTappa>

<InfoTappa> ::= <Nome > <Coordinate> dalle <Ora> alle <Ora> ( <Prezzo >)* ( <Descrizione >)*

<VisitaNegozi> ::= Visita negozi dalle <Ora> alle <Ora>

<Prezzo >::= <NUMERO> . <NUMERO> euro

<Coordinate> ::= <NUMERO> - <NUMERO>

Elenco TOKEN

<NUMERO: ([0-9])+> <PAROLA: ([A-Z,a-z,0-9,_,\'])+> <TAPPACUL: Museo: | Chiesa: > <TAPPATUR: Monumento: | Punto

Panoramico: >


<Visita> ::= Partenza prevista in: <Nome> <Coordinate> alle <Ora> del giorno <Data >

<Tipo>



<Turistico> ::= Itinerario Turistico: ( <TappaTur>| <VisitaNegozi>)+






<InfoTappa> ::= <Nome > <Coordinate> dalle <Ora> alle <Ora> ( <Prezzo >) *

(<Descrizione>)*

GRAMMATICA (2/5)

SCOPO


Ogni <Visita> prevede: <Nome> , <Coordinate>, <Ora> e <Data> che rappresentano la

partenza <Tipo> è il tipo di itinerario

Esempio:

“ Partenza prevista in: Porta del Paese 280- 210 alle ore 12:12 del giorno 1/9/2009 Itinerario Misto: ”

GRAMMATICA (3/5)

In questo caso le coordinate sono espresse in pixel,

relativamente ad una cartina da me scelta

<Visita> ::= Partenza prevista in: <Nome> <Coordinate> alle <Ora> del giorno

<Data> < Tipo>

GRAMMATICA (4/5)


<Visita> ::=Partenza prevista in: <Nome> <Coordinate> alle <Ora> del giorno <Data>

<Tipo>









<InfoTappa>::=<Nome > <Coordinate> dalle <Ora> alle <Ora> (<Prezzo >)*

( <Descrizione >)*

Sono previste 3 tipologie di itinerario: Culturale:

Prevede una o più tappe culturali Turistico:

Prevede una o più tappe turistiche oppure una o più visite libere per negozi Misto:

Prevede qualsiasi tipo di tappa, unendo le possibilità offerte dagli altri due tipi di itinerario

GRAMMATICA (4/5)



<Tipo>






<Visita> ::= Partenza prevista in: <Nome> <Coordinate> alle <Ora> del giorno <Data >

<Tipo>



<Turistico> ::= Itinerario Turistico: ( <TappaTur>| <VisitaNegozi>)+


<InfoTappa> ::= <Nome > <Coordinate> dalle <Ora> alle <Ora> ( <Prezzo >) *

(<Descrizione>)*

GRAMMATICA (4/5)





GRAMMATICA (4/5)





Questa parte di grammatica esprime le attività che compongono un itinerario:

La parte lessicale prevede tra l’elenco di Token:<TAPPACUL: Museo: | Chiesa:> <TAPPATUR: Monumento: | Punto Panoramico:>

Quindi: Visita di un museo <TAPPACUL> <InfoTappa> TAPPACUL= Museo: Visita di una chiesa <TAPPACUL> <InfoTappa> TAPPACUL= Chiesa: Visita a monumento <TAPPATUR> <InfoTappa> TAPPATUR= Monumento: Visita pto panoramico <TAPPATUR> <InfoTappa> TAPPATUR =Punto Visita libera per negozi Visita negozi dalle <Ora> alle <Ora> Pranzo presso un ristorante Ristorante: <InfoTappa>

Panoramico:


La generica tappa <Tappa> non contiene la

visita ai negozi perché era stata inserita qui

GRAMMATICA (5/6)



<Tipo>










( <Descrizione >)*


( <Descrizione >)* Nome ::= ( <PAROLA> )+ Descrizione ::= ( <PAROLA> )+ Data ::= <NUMERO>/<NUMERO>/<NUMERO> Ora ::= ore <NUMERO>:<NUMERO>Prezzo ::= <NUMERO>.<NUMERO> euroCoordinate ::= <NUMERO> "-" <NUMERO>

Esempi di parti frasi lecite:Chiesa: Chiesa dei Cappuccini 400-220 dalle ore 12:12 alle ore 12:12

Ristorante: Ristorante Il Loco 250-200 dalle ore 12:00 alle ore 14:00 19.90 euro menu fisso

Museo: Museo delle armi 100-100 dalle ore 12:00 alle ore 13:00 7.90 euro

Punto Panoramico: Stazione funivia 35-85 dalle ore 15:00 alle ore 15:15

Visita negozi dalle 12:12 alle 14:00

GRAMMATICA (6/6)

Nome Coordinate dalle Ora alle OraNomeCoordinate dalle Ora alle Ora PrezzoDescrizione

Elenco TOKEN

<NUMERO: ([0-9])+> <PAROLA: ([A-Z,a-z,0-9,_,\'])+> <TAPPACUL: Museo: | Chiesa: > <TAPPATUR: Monumento: | Punto

Panoramico: >

inizio

Partenza prevista in: Porta del Paese 280- 210 alle ore 11:00 del giorno 1/9/2009

Itinerario Misto:

Chiesa: Chiesa dei Cappuccini 400-220 dalle ore 11:30 alle ore 12:30


Museo: Museo delle armi 100-100 dalle ore 14:45 alle ore 15:30 7.90 euro

Punto Panoramico: Stazione funivia 35-85 dalle ore 15:30 alle ore 16:00

Chiesa: Chiesa San Francesco 300-180 dalle ore 16:15 alle ore 17:00

Visita negozi dalle ore 17:00 alle ore 18:00

fine

ESEMPIO

PROPRIETÀ DELLA GRAMMATICA

La grammatica è di Tipo 2 (context-free) secondo la classificazione di Chomsky, in quanto tutte le produzioni risultano essere nella forma:

Il linguaggio generato risulta essere di tipo Tipo 3 (regolare) poiché la grammatica non contiene self-embedding.

A αcon α (VT VN)*, A VN

RICONOSCITORE

La grammatica è LL(1) Utilizza al più 1 simbolo per riconoscere con certezza

la produzione da scegliere starter symbols disgiunti (non è necessario ricorrere

ai director symbols poiché nessun metasimbolo genera la stringa vuota).

Quindi: Le frasi vengono analizzate Left-to-Right applicando

la left most derivation l’analisi top-down è deterministica il riconoscitore sarà deterministico

ARCHITETTURA DEL SISTEMA

Testo

Il testo è acquisito tramite interfaccia grafica: Digitando il testo Caricando un file di testo


Testo

Lexer

Analisi Lessicale:vengono individuate le singole parole (Token) di una fraseSequenza di

caratteri

Sequenza di TOKEN


Testo

Lexer

Parser

Analisi Sintattica:si verifica che una frase sia costruita secondo le regole grammaticali che descrivono il linguaggio

Rappresentazione interna della frase

AST

Sequenza di caratteri

Sequenza di TOKEN

VISITOR

La classe DepthFirstVisitor (generata da JTB) è stata estesa da due sottoclassi:

TreeVisitorvisita l’APT e ne fornisce una rappresentazione grafica sotto forma di albero (la quale verrà passata all’interfaccia grafica).

LuoghiVisitorvisita l’APT e fornisce un elenco di tutte le tappe che costituiscono l’itinerario tranne le visite ai negozi (servirà per realizzare la visualizzazione dell’itinerario).

NegoziVisitorvisita l’APT e fornisce un elenco delle eventuali visite ai negozi (servirà per realizzare la visualizzazione dell’itinerario).

Ciascun visitor realizza una visita di tipo depth first avvalendosi del meccanismo del double dispatch

VISITOR

TreeVisitor

LuoghiVisitor

NegoziVisitor

SEMANTICA (1/3)

Parte del controllo semantico è effettuato direttamente dal Parser, i controlli più complicati sono invece eseguiti dagli oggetti ControlloOrari e ControlloMappa

I controlli effettuati direttamente dal Parser sono: Controllo della data

Data ::= <NUMERO> "/" <NUMERO> "/" <NUMERO> Controllo dell’ora

Ora ::= "ore" <NUMERO> ":" <NUMERO>

Considerando che il Token numero è:<NUMERO: (["0"-"9"])+>

SEMANTICA (2/3)

I controlli effettuati dall’oggetto ControlloOrari (package Semantica) sono: Orario di inizio visita di una Tappa minore o uguale

a quello della fine ( tiVisitan ≤ tfVisitan ) Orario di fine visita della Tappa precedente minore

o uguale all’orario di inizio visita della Tappa successiva (tfVisitan ≤ tiVisitan+1)

Esempio:

Chiesa: Chiesa dei Cappuccini 400-220 dalle ore 11:30 alle ore 12:30


11:30<12:30 corretto!!

12:30<13:00 corretto!!

SEMANTICA (3/3)

ControlloMappa (package Semantica)Problema:Dato un <Nome> di una tappa, <Coordinate> deve indicare il giusto punto sulla cartina (consistenza). <InfoTappa>::=<Nome > <Coordinate> dalle <Ora> alle <Ora> (<Prezzo >)*

(<Descrizione >)*

Soluzione:Prevedere una tabella che abbia come elementi (Nome,

Coordinate) ed effettuare controllo: inutile inserire <Coordinate> in input, difficoltà se si vuole cambiare la cartina, in caso il luogo non si trovi in tabella si ha errore semantico anche se il luogo esiste

Lasciare il controllo semantico all’operatore che immette l’input: possibilità di inserire qualsiasi tappa, modalità della visualizzazione è provvisoria (sviluppi futuri: tecnologie di localizzazione google maps, GPS)

SEMANTICA (3/3)

ControlloMappa: Problema:Dato un <Nome> di una tappa, <Coordinate> deve indicare il giusto punto sulla cartina (consistenza).

Scelta: Soluzione intermedia:ControlloMappa dispone di una HashMap<luogo,coordinate> contenente le indicazioni <luogo, coordinate> di gran parte delle tappe da poter visitare. Per ogni luogo:

Se <luogo,coordinate> è presente nell’elenco: vengono segnalati errori in caso di coordinate non corrette

Se <luogo,coordinate> non è presente nell’elenco: il controllo semantico è lasciato all’operatore

STRUMENTI UTILIZZATI

Linguaggio: Java (jdk1.6.0_10) :

Ambiente di sviluppo: NetBeans IDE 6.5

Generazione automatica parser: JavaCC 4.2 Strumento per la generazione automatica delle

classi necessarie a creare l’albero sintattico (AST) e per l’implementazione di Visitor che operano depth-first: Java Tree Builder 1.3.2

Generazione della documentazione: JJDoc

CLASSI GENERATE DA JAVACCImplementa il Lexer:

contiene il metodo getNextToken() il quale implementa l’ASF

deterministico che riconosce i token descritti dalleespressioni regolari

Implementa il Parser:chiama il Lexer ogni volta che necessita del prossimo token.Contiene un metodo per ogni

simbolo non terminale presentenella specifica della grammatica

Ogni chiamata al metodo getNextToken() restituisce un oggetto di

questa classe

PACKAGE

ViewContiene le interfacce grafiche ed il manager dell’applicazione

SemanticaContiene le classi usate nel controllo semantico

parserItinerarioContiene le classi per lo scanning, il parsing e la costruzione dell’AST

syntaxTreeContiene le classi necessarie per la costruzione dell’AST

visitorContiene i Visitor creati da JTB in automatico, TreeVisitor, LuoghiVisitor e NegoziVisitor

INTERFACCIA GRAFICA

INTERFACCIA GRAFICA

Cartina che mostra le Tappe

dell’itinerario

Informazioni relative alle Tappe

dell’itinerario

COLLAUDO

Per il collaudo del sistema sono stati scritti alcuni significativi file di codice che verificassero:

Creazione corretta dell’albero utilizzando le 3 tipologie di itinerario: turistico, culturale e misto

Segnalazione di errori sintattici Segnalazione di errori semantici da parte del

parser (Ora, Data) Segnalazione di errori semantici da parte delle

classi nel package Semantica (orarioPrecedente<OrarioSuccessivo; <luogo,coordinate>)

Corretta visualizzazione dell’itinerario

SVILUPPI FUTURI

Rendere il riconoscitore capace di identificare un maggior numero di attività che compongono un itinerario

Prevedere un miglior sistema di localizzazione delle tappe

Automatizzare l’inserimento di una tappa dell’itinerario

DEMO

DEMO

Progetto per lesame di Linguaggi e Modelli Computazionali LS Chiara Chiara Gualtieri.

Documents

Transcript of Progetto per lesame di Linguaggi e Modelli Computazionali LS Chiara Chiara Gualtieri.