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