Analizzatori Sintattici con Cup
Giuseppe Morelli
Introduzione
• Cup (Constructor of Useful Parsers) è un
sistema per la generazione di parser LALR a
partire da semplici file di specifica.
• È scritto in Java
• Il file di specifica include codice java
• Il parser prodotto è codice java
• Cup richiede un file di specifica, basato sulla
grammatica per la quale si intende realizzare il
parser, ed uno scanner in grado di riconoscere e
“spezzare” l’input in TOKEN
Sintassi del file di specifica
• Un file di specifica contiene diverse sezioni
come di seguito riportate:
1. Dichiarazioni preliminari (specifiche per
package ed import, codice utente etc..)
2. Lista di simboli terminali e non terminali
3. Precedenza ed associatività dei terminali
4. La grammatica vera e propria
Package ed Import Specification
• Il significato e la sintassi delle istruzioni
riportate in tale sezione è la stessa di un
qualsiasi e “normale” programma Java.
• La dichiarazione di package sarà pertanto:
– package name;
• L’import di librerie di classi potrà avvenire
attraverso:
– import package_name.class_name;
• Oppure
– import package_name.*;
User code Components
• E’ possibile aggiungere codice utente al parser
generato da Cup..
• Le dichiarazioni possibili sono molteplici:
– action code {:….:}: contiene il codice normalmente
usato all’interno della grammatica (es. gestione della
tabella dei simboli). Tale codice verrà inserito in una
classe non public separata dalla classe principale del
parser.
– parser code {:….:}: permette di inserire metodi e
dichiarazioni direttamente nella classe parser (es.
includere metodi per lo scanning direttamente nel
parser, oppure riscrivere metodi per la gestione degli
errori)
– init with {:….:}: permette di specificare del codice
che il parser deve invocare prima della richiesta del
primo token(inizializzazione dello scanner, tabelle e
strutture dati). Il codice di tale dichiarazione è inserito
in un metodo void della classe parser.
– scan with {:….:}: permette di specificare come il
parser può richiedere i token allo scanner. Il codice
viene inserito in un metodo del parser che deve
restitutire un Symbol
Lista di Simboli
• In questa sezione vengono specificati i nomi e
forniti i tipi di tutti i simboli terminali e non
terminali della grammatica.
• Sintassi
• classname rappresenta il tipo del valore
associato al simbolo.
• In mancanza del tipo si assume che il simbolo
non mantiene valore
Precedenza ed associatività
• In tale sezione devono essere specificate le
precedenze ed le regole di associatività dei
terminali; esistono tre tipi di dichiarazioni
• La precedenza è determinata dall’ordine di
scrittura dalla più bassa alla più alta (altobasso)
• Ai simboli per i quali non è specificata una
precedenza è associata precedenza minima
• Cup assegna una precedenza anche alle
produzioni della grammatica: tale precedenza
coincide con la precedenza dell’ultimo simbolo
terminale che appare nel corpo della produzione
• Alle Produzioni senza precedenza è assegnata
una precedenza minima.
La Grammatica
• In tale sezione vengono descritte le produzioni
della grammatica.
• Il simbolo iniziale della stessa è specificato
attraverso l’istruzione start with non-terminal; o
in assenza viene considerato il primo simbolo
della prima produzione.
• Ogni produzione nella grammatica ha la forma:
– NONTERMINALE ::= {{azioni}* {NONTERMINALI}*
{TERMINALI}*}*;
– Ogni simbolo a destra può essere etichettato
utilizzando il simbolo “:” seguito dall’etichetta
• Le produzioni di un non terminale devono
essere dichiarate assieme utilizzando il simbolo
“|”