Università degli Studi di BolognaFacoltà di Ingegneria
Anno Accademico 2007/2008
Laurea Specialistica in Ingegneria Informatica
Linguaggi e Modelli Computazionali LS
Prof. Enrico Denti
Progetto di Matteo Iuliani
Un interprete per la notazione scacchistica Forsyth-Edwards
Analisi del problema
Una partita di scacchi, se non vengono fissati limiti di tempo, può durare ore o addirittura giorni
Si può pertanto presentare la necessità di dover interrompere una partita in corso di svolgimento
Esiste nel mondo degli scacchi una notazione standard (notazione Forsyth-Edwards) che permette di descrivere tutte le informazioni necessarie per poter proseguire la partita
Scopo del lavoro
Definire formalmente la grammatica che è alla base della notazione Forsyth-Edwards La notazione diviene quindi un vero e proprio
linguaggio
Realizzare un riconoscitore / interprete per tale linguaggio Verifica la correttezza sintattica e semantica di una
frase appartenente al linguaggio Se tutto è corretto, visualizza i pezzi sulla scacchiera
e tutte le altre informazioni contenute nella frase
Informazioni necessarie
Per descrivere una particolare posizione nel corso di una partita, servono 6 informazioni: Posizione dei pezzi
Giocatore che ha la mossa
Possibilità di arroccare
Casa in cui è possibile catturare en passant
Numero di semimosse dall'ultima spinta di pedone o dall'ultima cattura (usato per determinare se si può chiedere la patta per la regola delle cinquanta mosse)
Numero complessivo di mosse della partita
Grammatica EBNF
La notazione Forsyth-Edwards utilizza una stringa di 6 campi, a loro volta separati da uno spazio, per descrivere le 6 informazioni necessarie
Scopo ::= Stringa <EOF> Stringa ::= Posizione " " Muove " " Arrocco
" " Enpassant " " Semimosse " " Mosse
Grammatica EBNF
Viene descritta ogni singola riga della scacchiera, dalla 8 fino alla 1
Posizione ::= Riga "/" Riga "/" Riga "/" Riga "/" Riga "/" Riga "/" Riga "/" Riga
Entro ciascuna riga, è descritto il contenuto di ciascuna casa, a partire dalla colonna a della scacchiera fino alla colonna h Se in una riga sono presenti case vuote, una cifra
da 1 a 8 indica il numero di case vuote consecutive
Grammatica EBNF
Bisogna impedire che all'interno di una riga compaiano due cifre consecutive Ad esempio 23 indica che ci sono 2 case vuote
seguite da altre 3 case vuote Bisogna costringere l'utente a scrivere 5!!!
Riga ::= Pezzo RestoRiga | CaseVuote (RestoRigaStartPezzo)?
In questo modo, se c'è qualcosa dopo una cifra, deve essere per forza un pezzo
Grammatica EBNF
RestoRiga ::= Pezzo (RestoRiga)? | CaseVuote (RestoRigaStartPezzo)?
RestoRigaStartPezzo ::= Pezzo (RestoRiga)? Notiamo una ricorsione destra (in RestoRiga) e
un ciclo ricorsivo a destra Non costituiscono problemi per l'analisi LL
Controllo semantico: per ogni riga la somma tra il numero dei pezzi e il numero delle case vuote deve essere 8
Grammatica EBNF
I pezzi del Bianco sono indicati utilizzando le iniziali inglesi dei pezzi stessi in maiuscolo; quelli del Nero utilizzando le stesse lettere minuscole
Pezzo ::= "K" | "Q" | "R" | "B" | "N" | "P" | "k" | "q" | "r" | "b" | "n" | "p" |
CaseVuote ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8"
Grammatica EBNF
Muove ::= "w" | "b" Ha la mossa il Bianco ("w") o il Nero ("b")
Arrocco ::= "-" | (TipoArrocco)+ Il simbolo "-" indica che nessuno dei due
giocatori può arroccare; altrimenti vengono elencati i tipi di arrocco possibili (almeno uno)
Grammatica EBNF
TipoArrocco ::= "K" | "Q" | "k" | "q" Queste lettere hanno significati differenti
rispetto alle stesse lettere utilizzate nella descrizione dei pezzi:
"K": il Bianco può arroccare corto
"Q": il Bianco può arroccare lungo
"k": il Nero può arroccare corto
"q": il Nero può arroccare lungo
Controllo semantico: ogni lettera può comparire al massimo una volta in Arrocco
Grammatica EBNF
Enpassant ::= "-" | Casa Se è possibile catturare en passant (un pedone
ha appena effettuato la sua prima mossa di due case), si indica la casa "alle spalle" del pedone stesso
Casa ::= Colonna Traversa
Grammatica EBNF
Colonna ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" |
Traversa ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" |
CaseVuote e Traversa hanno la stessa parte destra; tuttavia ho preferito distinguerle Rappresentano due concetti differenti E hanno quindi una semantica differente
Grammatica EBNF
Semimosse ::= "0" | CifraNonNulla (Cifra)* Mosse ::= CifraNonNulla (Cifra)* Il numero di semimosse può essere nullo,
mentre il conteggio delle mosse parte da 1 (Mosse indica la prossima mossa della partita)
CifraNonNulla ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" |
Cifra ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Caratteristiche della grammatica
Secondo la classificazione di Chomsky, la grammatica è di tipo 2 in quanto le produzioni non sono regolari
Non è presente self-embedding, quindi il linguaggio generato dalla grammatica è di tipo 3 (regolare)
La grammatica è LL(1) Non sono presenti ε-rules nello scopo
Architettura
Packages: parser
classi relative alla gestione del parser classi generate in automatico da JavaCC
syntaxtree una classe per ogni metasimbolo della grammatica classi generate in automatico da JTB
Architettura
Packages: visitor
visitor di default generati in automatico da JTB ChessVisitor
raccoglie e struttura le informazioni relative a una partita di scacchi
offre metodi pubblici per poter accedere a tali informazioni
chess tutte le altre classi dell'applicazione
Package chess: classi
Pezzo - Casa modellano rispettivamente un pezzo e una casella della
scacchiera
Scacchiera modella la scacchiera prende da ChessVisitor le informazioni sulla posizione dei
pezzi offre metodi per vari controlli semantici:
numero dei pezzi posizione dei pezzi e coerenza con le possibilità di arroccare o catturare en passant se tocca muovere al bianco il re nero non può essere minacciato, e viceversa
Package chess: classi
Partita costruisce e valida un oggetto Scacchiera contiene le altre informazioni relative a una partita (raccolte
da ChessVisitor)
ChessException lanciata in caso di errore semantico
ChessFrame interfaccia grafica dell'applicazione visualizza le informazioni contenute in Partita
Main
Collaudo
Verifiche: corretto riconoscimento di errori sintattici e
semantici attraverso l'utilizzo di frasi errate corretto riconoscimento e interpretazione di frasi
sintatticamente e semanticamente corrette Le frasi sono state sia lette da file, sia inserite
manualmente Si è cercato di coprire le possibilità offerte
dalla grammatica
Limiti
Alcuni controlli semantici non sono stati implementati perché troppo complessi Ad esempio, non è possibile in generale affermare
se una determinata posizione dei pezzi sulla scacchiera sia compatibile con i numero di semimosse e/o mosse dichiarati
Questo perché il gioco degli scacchi è profondamente complesso
Il numero di posizioni legalmente ammesse è stimato essere fra 1043 e 1050
Possibili sviluppi futuri
Possibilità di proseguire la partita e quindi di poter salvare su file la stringa corrispondente alla nuova posizione definizione di una nuova grammatica
Miglioramento dell'interfaccia grafica Opzioni grafiche per l'utente
scelta dello stile della scacchiera scelta dello stile dei pezzi
Top Related