Manualetto

JAVACC

Nicola Fanizzi

Dipartimento di InformaticaUniversità di Bari “Aldo Moro”

[2013/05/17-20:39:44]

[ 2 ]

Questo manuale è basato sulla documentazione ufficiale di JavaCC.

• Sito ufficiale: http://javacc.java.net//• JavaCC FAQ: http://www.engr.mun.ca/~theo/JavaCC-FAQ• Usenet group: comp.compilers.tools.javaccJava, JavaCC e JJTree sono marchi registrati.

INDICE

1 Introduzione 5

1.1 JavaCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Linea di Comando . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 File Prodotti da JavaCC . . . . . . . . . . . . . . . . . . . . 9

1.4 Struttura di una Specifica JavaCC . . . . . . . . . . . . . . . 10

1.4.1 Opzioni . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4.2 Produzioni . . . . . . . . . . . . . . . . . . . . . . . 15

2 Analisi Lessicale 17

2.1 L’Analizzatore Lessicale . . . . . . . . . . . . . . . . . . . . 17

2.2 Funzionamento del Token Manager . . . . . . . . . . . . . 18

2.3 Dichiarazioni per il Token Manager . . . . . . . . . . . . . 19

2.4 Token: Regole per Espressioni Regolari . . . . . . . . . . . . 19

2.4.1 Lista di Stati Lessicali . . . . . . . . . . . . . . . . . . 20

2.4.2 Tipi di Espressioni Regolari . . . . . . . . . . . . . . 20

2.4.3 Specifica di Espressioni Regolari . . . . . . . . . . . . 21

2.5 Prefissi Comuni . . . . . . . . . . . . . . . . . . . . . . . . 24

2.6 La Classe dei Token . . . . . . . . . . . . . . . . . . . . . . 25

2.7 Azioni Lessicali . . . . . . . . . . . . . . . . . . . . . . . . 26

2.7.1 Variabili . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.7.2 Esempi . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.7.3 Token Speciali e Parser . . . . . . . . . . . . . . . . . 29

2.8 Analisi Lessicale Efficiente . . . . . . . . . . . . . . . . . . 30

3 Analisi Sintattica 33

3.1 Produzioni BNF . . . . . . . . . . . . . . . . . . . . . . . . 33

3.1.1 Espansioni BNF . . . . . . . . . . . . . . . . . . . . . 34

3.1.2 Lookahead Locale . . . . . . . . . . . . . . . . . . . 35

3.2 Produzioni Javacode . . . . . . . . . . . . . . . . . . . . . . 37

[ 3 ]

[ 4 ]

4 Lookahead 39

4.1 Lookahead: Cos’è, a che Serve . . . . . . . . . . . . . . . . . 39

4.2 Punti di Scelta nelle Specifiche . . . . . . . . . . . . . . . . 42

4.3 Determinare la Scelta Giusta . . . . . . . . . . . . . . . . . 42

4.3.1 Specifiche Multiple di Lookahead per Token . . . . . 44

4.3.2 Lookahead Globale . . . . . . . . . . . . . . . . . . . 46

4.3.3 Lookahead Locale . . . . . . . . . . . . . . . . . . . 46

4.4 Lookahead Sintattico . . . . . . . . . . . . . . . . . . . . . 48

4.5 Lookahead Semantico . . . . . . . . . . . . . . . . . . . . . 51

4.6 Struttura Generale della Direttiva . . . . . . . . . . . . . . . 52

5 Gestione degli Errori 53

5.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.2 Messaggistica d’Errore . . . . . . . . . . . . . . . . . . . . . 54

5.3 Recupero degli Errori . . . . . . . . . . . . . . . . . . . . . 54

5.3.1 Recupero Superficiale . . . . . . . . . . . . . . . . . 55

5.3.2 Recupero in Profondità . . . . . . . . . . . . . . . . 56

6 Esempi 59

6.1 Filtro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.2 Convertitore CSV2HTML . . . . . . . . . . . . . . . . . . . . 62

6.3 Calcolatrice . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6.4 Mini Linguaggio Ita . . . . . . . . . . . . . . . . . . . . . . 66

7 Costruzione di alberi sintattici 69

7.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . 69

7.2 Ambito dei Nodi ed Azioni Utente . . . . . . . . . . . . . . . 71

7.3 Gestione Eccezioni . . . . . . . . . . . . . . . . . . . . . . . 72

7.4 Metodi di Servizio per lo Scope dei Nodi . . . . . . . . . . . 72

7.5 Tener Traccia dei Token . . . . . . . . . . . . . . . . . . . . 73

7.6 Ciclo di Vita di un Nodo . . . . . . . . . . . . . . . . . . . . 73

7.7 Supporto alla Visita . . . . . . . . . . . . . . . . . . . . . . 74

7.8 Opzioni per JJTree . . . . . . . . . . . . . . . . . . . . . . . 74

7.9 Stati di JJTree . . . . . . . . . . . . . . . . . . . . . . . . . . 76

7.10 Nodi come Oggetti . . . . . . . . . . . . . . . . . . . . . . . 77

7.11 Altri Esempi . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Indice Analitico 80

CAPITOLO

1

INTRODUZIONE

Un meta-compilatore o generatore di parser è un sistema che, a partire

dalla specifica di un linguaggio, costruisce un programma (analizzato-

re) capace di riconoscere sequenze (frasi) del linguaggio. In generale la

specifica comprende sia l’aspetto lessicale sia quello sintattico, cosa che

permette la costruzione automatica del parser, mentre l’aspetto seman-

tico viene lasciato al lavoro (aggiuntivo) del progettista, anche se sono

previsti costrutti che permettono di arricchire il parser con azioni lega-

te alla semantica e scritte nello stesso linguaggio di programmazione del

programma generato.

1.1 JAVACCQuesto manuale si propone di illustrare l’utilizzo di JavaCC (“Java Compi-

ler Compiler”), uno strumento open-source per la costruzione automaticadi analizzatori lessicali e sintattici in Java. A partire da una specifica for-

male della grammatica del linguaggio, esso produce classi in puro codice

Java atte a leggere ed analizzare frasi in tale linguaggio.

JavaCC risulta particolarmente utile allorché i linguaggi da analizzare

presentino strutture tanto complesse da sconsigliare un approccio non

automatizzato. Questa tecnologia è nata per rendere più semplice l’im-

plementazione dei linguaggi di programmazione – da cui il termine “com-

pilatore di compilatori” –ma trova applicazione anche per linguaggi più

semplici e di tipo diverso (scripting, markup, ecc.). JavaCC non automa-tizza anche la costruzione esplicita degli alberi sintattici, ma esistono (al-

meno) due altri strumenti a corredo che possono essere utilizzati a ta-

le scopo: JJTree e JTB. Risulta facile, inoltre, estendere le specifiche per

automatizzare la costruzione delle tabelle dei simboli.[ 5 ]

[ 6 ] 1. INTRODUZIONESia JavaCC sia i parser generati con questo strumento girano su nu-

merose piattaforme. Molti linguaggi hanno già una specifica per JavaCC

come quella dello stesso Java, JavaScript, RTF, Visual Basic, PHP, Python,

C, C++, ma anche XML, HTML, SQL, e molti altri ancora.

Le caratteristiche principali di JavaCC sono le seguenti:

• ANALISI TOP-DOWN: JavaCC genera parser ricorsivi discendenti

(differenti dai parser ascendenti generati, ad esempio, da strumen-

ti come YACC e Bison, si veda [1, 4]). Ciò consente di trattare un

gran numero di grammatiche libere di forma diversa (sebbene la ri-

corsione sinistra sia vietata). Inoltre i parser discendenti sono più

semplici per quel che riguarda il loro debugging e si prestano al-

l’utilizzo a partire da qualunque non-terminale, consentendo anche

il passaggio di valori (attributi) su e giù per l’albero di derivazione

durante il processo d’analisi.

• AMPIA COMUNITÀ DI UTENTI: JavaCC è di gran lunga il generatore

automatico di parser più usato in congiunzione con applicazioni Ja-

va, con centinaia di migliaia di download ed una platea stimata di

circa qualche decina di migliaia di utenti professionali, come testi-

moniato anche dal numero dei partecipanti alle varie mailing-list e

newsgroup.

• SPECIFICA LESSICALE E SINTATTICA IN UNO STESSO FILE: Le speci-

fiche lessicali in forma di espressioni regolari, stringhe, ecc. e quelle

sintattiche (in EBNF) sono scritte insieme in uno stesso file. Ciò ren-

de la grammatica di agevole lettura (si possono usare espressioni

regolari – inline – nella specifica della grammatica) ed anche di piùfacile manutenzione.

• PREPROCESSORE PER LA COSTRUZIONE DEGLI ALBERI SINTATTI-

CI: JavaCC contiene JJTree, un preprocessore molto potente per la

costruzione di alberi.

• CUSTOMIZZAZIONE: JavaCC offre tante opzioni per adattare il suo

comportamento e quello dei parser generati, come ad es. i tipi di ca-

ratteri Unicode per il flusso di caratteri in input, il numero di tokenper il controllo di ambiguità, ecc.

• PURO JAVA AL 100%: JavaCC gira su tutte le piattaforme Java-compliant. Viene utilizzato su tanti tipi di macchine con nessu-no sforzo relativo al porting – aderendo pienamente alla filosofia

“Write Once, Run Everywhere” di Java.• GENERAZIONE DI DOCUMENTAZIONE: JavaCC include lo strumen-

to JJDoc che converte file-grammatica in file di documentazione

(anche in HTML).

• NUMEROSI ESEMPI: La release di JavaCC contiene molti esempi

di specifiche di grammatiche. Gli esempi, assieme alla loro docu-

mentazione, costituiscono un valido ausilio all’apprendimento di

JavaCC.

1.1. JAVACC [ 7 ]

• INTERNAZIONALIZZAZIONE: Uno scanner generato da JavaCC può

manipolare input Unicode e le sue specifiche lessicali possono inclu-dere qualunque carattere Unicode. Ciò facilita la descrizione deglielementi in un linguaggio, come Java, che ammette caratteriUnicode(in numero maggiore rispetto a quelli ASCII).

• SPECIFICHE DI LOOKAHEAD SINTATTICHE E SEMANTICHE: Per de-

fault, JavaCC genera un parser LL(1). Tuttavia, ci potrebbero esse-

re molte parti non LL(1) nella grammatica. JavaCC offre le capa-

cità di lookahead sintattico e semantico per risolvere casi di non-

determinismo shift-shift1 in modo locale nei punti esatti, ad esem-pio quando il parser è LL(k) solo in certi punti ed LL(1) altrove.

I casi di ambiguità shift-reduce2 e reduce-reduce3, tipici dei parserascendenti, non costituiscono un problema per parser top-down.

• SPECIFICHE IN BNF ESTESA: JavaCC consente di scrivere specifiche

in EBNF – come (A)*, (A)+, ecc. – nelle regole lessicali e sintattiche.L’uso dell’EBNF solleva, in parte, dalla necessità di usare la ricorsio-

ne sinistra. Di fatto, risulta più leggibile rappresentare una regola

come A ::= y(x)* piuttosto che con A ::= Ax | y.• STATI ED AZIONI LESSICALI: JavaCC offre la possibilità di usare stati

ed azioni lessicali come in Lex/Flex [1]. Aspetti specifici di JavaCC

che lo rendono superiore ad altri strumenti sono lo status speciale

attribuito a costrutti come TOKEN, MORE, SKIP, cambiamenti di stato,ecc. Questo favorisce specifiche più pulite e messaggi d’errore e di

avvertimento più precisi con JavaCC.

• ANALISI LESSICALE CASE-INSENSITIVE: Le specifiche lessicali

possono definire i token senza tener conto della distinzione

minuscole/maiuscole a livello globale o anche locale.

• TOKEN SPECIALI: I token definiti come speciali nella specifica les-

sicale sono ignorati in fase di analisi sintattica, ma possono es-

sere elaborati da altri strumenti. Un’applicazione utile potrebbe

essere quella relativa all’elaborazione dei commenti ai fini della

documentazione.

• DEBUGGING AVANZATO: Attraverso opzioni qualiDEBUG_TOKEN_MANAGER, DEBUG_PARSER e DEBUG_LOOKAHEAD, si puòottenere una analisi dettagliata del processo di analisi lessicale,

sintattica e lookahead.

• GESTIONE OTTIMALE ERRORI: La gestione degli errori con JavaCC

è tra le migliori tra i vari generatori automatici di parser. Ja-

vaCC genera parser capaci di indicare il punto di errore e fornire

informazioni diagnostiche complete.

1Parola (token) ambivalente dal punto di vista lessicale.2L’algoritmo di parsing, potrebbe sia spostarsi (shift) sul prossimo token sia ridurre

(reduce) una sequenza di simboli in cima allo stack.3Accade quando si può ridurre più di una sequenza di simboli in cima allo stack.

[ 8 ] 1. INTRODUZIONE1.2 LINEA DI COMANDODigitando semplicemente il comando javacc su una console si può otte-nere facilmente un aiuto sulla sintassi corretta per la sua invocazione. Il

risultato è il seguente:

% javaccJava Compiler Compiler Version 5.0 (Parser Generator)Usage:javacc option-settings inputfile"option-settings" is a sequence of settings separated by spaces.Each option setting must be of one of the following forms:

-optionname=value (e.g., -STATIC=false)-optionname:value (e.g., -STATIC:false)-optionname (equivalent to -optionname=true. e.g., -STATIC)-NOoptionname (equivalent to -optionname=false. e.g., -NOSTATIC)Option settings are not case-sensitive, so one can say "-nOsTaTiC" insteadof "-NOSTATIC". Option values must be appropriate for the correspondingoption, and must be either an integer, a boolean, or a string value.The integer valued options are:

LOOKAHEAD (default 1)CHOICE_AMBIGUITY_CHECK (default 2)OTHER_AMBIGUITY_CHECK (default 1)The boolean valued options are:

STATIC (default true)SUPPORT_CLASS_VISIBILITY_PUBLIC (default true)DEBUG_PARSER (default false)DEBUG_LOOKAHEAD (default false)DEBUG_TOKEN_MANAGER (default false)ERROR_REPORTING (default true)JAVA_UNICODE_ESCAPE (default false)UNICODE_INPUT (default false)IGNORE_CASE (default false)COMMON_TOKEN_ACTION (default false)USER_TOKEN_MANAGER (default false)USER_CHAR_STREAM (default false)BUILD_PARSER (default true)BUILD_TOKEN_MANAGER (default true)TOKEN_MANAGER_USES_PARSER (default false)SANITY_CHECK (default true)FORCE_LA_CHECK (default false)CACHE_TOKENS (default false)KEEP_LINE_COLUMN (default true)The string valued options are:

OUTPUT_DIRECTORY (default Current Directory)TOKEN_EXTENDS (default java.lang.Object)TOKEN_FACTORY (default none)JDK_VERSION (default 1.5)GRAMMAR_ENCODING (defaults to platform file encoding)EXAMPLE:javacc -STATIC=false -LOOKAHEAD:2 -debug_parser mygrammar.jj%Ogni opzione può essere impostata sulla linea di comando comemostrato

in questo messaggio oppure nel file di specifica della grammatica (come

si vedrà in seguito).

Se la stessa opzione viene impostata sia su linea di comando sia nella

specifica della grammatica, impostazione della linea di comando ha la

1.3. FILE PRODOTTI DA JAVACC [ 9 ]

precedenza.

1.3 FILE PRODOTTI DA JAVACCJavaCC legge una specifica generalmente contenuta in un file di estensio-

ne .jj e, se questa risulta corretto, produce un insieme di file Java. Se le

opzioni sono lasciate ai valori di default, vengono generati i file seguenti:

• file di base (boiler-plate):– SimpleCharStream.java tipo di stream collegato flusso di

caratteri in ingresso;

– Token.java rappresenta i token in input;– TokenMgrError.java errore che può essere lanciato dall’analiz-zatore lessicale (token manager);

– ParseException.java eccezione che evidenzia un input nonconforme alla grammatica del parser;

• file customizzati (nel seguito il prefisso NN indica un genericoprefisso scelto dall’utente):

– NN.java classe del parser;– NNTokenManager.java classe del token manager;– NNConstants.java interfaccia che associa le classi di token anomi simbolici.

Altri file possono essere prodotti a seconda delle opzioni contenute

nel file di specifica. Ad es., se si usa l’opzione JAVA_UNICODE_ESCAPE allo-ra invece di SimpleCharStream.java sarà prodotto JavaCharStream.java. Se si usa l’opzione USER_CHAR_STREAM, allora si produce l’interfacciaCharStream.java invece della classe SimpleCharStream.java.Analogamente, l’opzione USER_TOKEN_MANAGER causa la generazione di

un’interfaccia TokenManager.java, invece di una vera e propria classe peril token manager.

I file di base (boiler-plate) vengono prodotti solo se non esistono già.Ciò ha due importanti conseguenze: essi vanno cancellati prima di ri-

chiamare JavaCC, se si sono fatti cambiamenti che possono richiedere

modifiche in tali file. Inoltre, all’occorrenza, si potrebbe aver bisogno di

modificare manualmente tali file per implementare soluzioni ad hoc; da-to che JavaCC non li sovrascrive4, si può star sicuri che i file non saranno

modificati tacitamente.

4Se si usano plugin JavaCC per le IDE, questi potrebbero sovrascrivere ogni volta i file

esistenti.

[ 10 ] 1. INTRODUZIONE1.4 STRUTTURA DI UNA SPECIFICA JAVACCPreliminarmente, i file di specifica seguono le regole standard dei file

Java, anche a livello di spaziatura e di sequenze di escape Unicode (ad es.,le occorrenze di stringhe della forma \uxxxx - dove xxxx sia un valoreesadecimale - vengono convertite nel corrispondente carattere Unicodeprima dell’elaborazione del file).

A questa disciplina fanno eccezione gli operatori Java che contengo-

no5 i caratteri < e > che non sono token validi per JavaCC, in modo daconsentire un uso appropriato di specifiche di token annidate.

Infine, JavaCC considera riservate le seguenti parole:

EOF IGNORE_CASE JAVACODE LOOKAHEADMORE PARSER_BEGIN PARSER_END SKIPSPECIAL_TOKEN TOKEN TOKEN_MGR_DECLSI file di specifica per JavaCC hanno generalmente l’estensione .jj. Vo-

lendo rappresentare formalmente la struttura di un file di specifica nello

stesso linguaggio utilizzato da JavaCC, si può scrivere:

spec i f ica : : = opzioni"PARSER_BEGIN" "(" <ID> ")"unita_di_compilazione_java"PARSER_END" "(" <ID> ")"( produzione ) *

<EOF>

Il file di specifica inizia con una lista di opzioni (facoltativa) che è seguita

da una unità di compilazione Java (codice) racchiusa tra PARSER_BEGIN(<ID>) e PARSER_END(<ID>), dove il <ID> è un identificatore valido. Ti-picamente essa ospita la classe del parser da produrre. Segue una lista

di produzioni della grammatica che si chiude con un token speciale diend-of-file.Il nome usato nelle direttive PARSER_BEGIN e PARSER_END deve essere

identico: esso corrisponderà al nome dato al parser generato (ovvero alla

sua classe). Ad esempio, se si usa Prova come nome, allora i file generatisaranno:

• Prova.java: la classe del parser generato;• ProvaTokenManager.java: Il token manager generato;• ProvaConstants.java: contiene costanti d’utilità.

Un generico file Prova.jj ha il seguente formato:1 options{2 /* codice per settare i vari flag delle opzioni */3 /* (questa sezione e’ opzionale) */4 }5

6 PARSER_BEGIN(Prova)7

5Ossia, per la precisione: <<, >>, >>>, <<=, >>=, e >>>=.

1.4. STRUTTURA DI UNA SPECIFICA JAVACC [ 11 ]

8 public class Prova {9 /* Qui definizione metodi aggiuntivi per il parser */10 /* Puo’ anche essere lasciato vuoto */11 /* Puo’ essere inserito qui il metodo main() */12 }13

14 PARSER_END(Prova)15

16 TOKEN_MGR_DECLS :17 {18 /* Dichiarazioni ad uso dello scanner */19 /* (opzionale, serve per usi speciali) */20 }21

22 /* Sezione per le regole dei token23 del parser24 ed azioni */

Tra i costrutti PARSER_BEGIN e PARSER_END si può inserire un’unità dicompilazione Java (ossia l’intero contenuto di un file Java). Essa dovreb-

be contenere la dichiarazione di una classe con lo stesso nome utilizzato

nelle direttive (Prova nell’esempio precedente).1 PARSER_BEGIN(NOME)2 ...3 class NOME {4 ...5 }6 ...7 PARSER_END(NOME)

JavaCC non compie controlli particolari su tale unità, per cui è possi-

bile che un file di specifica venga elaborato da JavaCC senza problemi e,

tuttavia, vengano riconosciuti errori in fase di compilazione dei file Java

generati.

Se tale unità contiene dichiarazioni di package, queste vengono inclu-se in tutti i file generati. Se, invece, comprende dichiarazioni import,queste sono incluse nei file generati per il parser ed il token manager.

Il file generato per il parser contiene tutto quello che è nell’unità di

compilazione e, in aggiunta, il codice per il parser incluso alla fine della

classe relativa.

La classe del parser generato contiene la dichiarazione di un metodo

pubblico per ogni non-terminale indicato nel file di specifica. L’analisi

di un dato non-terminale si ottiene chiamando il metodo corrispondente.

Diversamente da Yacc, in JavaCC non c’è un unico simbolo iniziale possi-

bile – si può cominciare l’analisi con un qualunque non-terminale della

grammatica.

Il token manager generato fornisce invece un solo metodo pubblico:

• Token getNextToken() throws ParseError;Maggiori dettagli sono forniti nel seguito. Inoltre si può far

riferimento alla documentazione ufficiale delle API di JavaCC.

[ 12 ] 1. INTRODUZIONE1.4.1 OPZIONISe presente, la sezione delle opzioni comincia con la parola riservata di

JavaCC options, seguita da una lista di una o più impostazioni (option-binding) racchiusa tra parentesi graffe. la meta-regola è:opzioni : : = [ "options" "{" ( impostazione ) * "}" ]

Ogni impostazione specifica il settaggio di una opzione. Una stessa opzione

non può essere impostata più volte. Come detto in precedenza, le opzioni

possono anche essere settate sulla riga di comando (queste ultime ven-

gono considerate come impostazioni a maggiore precedenza sulle altre

modalità).

Le impostazioni si scrivono secondo la meta-regola:

impostazione : : = nomeOpzione "=" costante_java ";"dove le possibili opzioni sono:

• LOOKAHEAD: Numero di token da considerare in anticipo per prende-re una in un punto di scelta durante il parsing. Il valore di default

è 1. Più basso il numero più risulterà veloce il parser. Come si ve-drà, questo numero può essere sovrascritto per specifiche regole di

produzione all’interno della grammatica.

• CHOICE_AMBIGUITY_CHECK: Questa opzione a valori interi (default 2)rappresenta il numero di token da considerare per controllare l’am-

biguità di scelte del tipo A | B |... . Ad esempio, se esistesse unprefisso comune di due token (assumendo l’opzione impostata a 3)JavaCC saprebbe dire se usare un lookahead pari a 3 per la disam-

biguazione. Inoltre se A e B hanno un prefisso comune di tre tokenallora JavaCC saprà dire solo se c’è bisogno di un lookahead di 3 o

maggiore. Incrementando il valore si hanno maggiori informazioni

sull’ambiguità al costo di una minore efficienza. Per grandi gram-

matiche (es. quella di un linguaggio completo) valori alti portano i

controlli a richiedere troppo tempo.

• OTHER_AMBIGUITY_CHECK: Tale opzione a valori interi (default 1) rap-presenta il numero di token considerati nel controllo di ambiguità

di altri tipi di scelte (ad es., della forma (A)*, (A)+ e (A)?). Ciò ri-chiede più tempo del controllo della scelta pertanto il default viene

impostato a 1 piuttosto che a 2.• STATIC: Opzione booleana (default true). Se posta a true, tutti imetodi e le variabili delle classi parser e token manager sono indi-

cate come static nel codice generato. ciò consente di avere un solooggetto parser ma questo risulterà più efficiente. Per avere la pos-

sibilità di analisi sintattiche diverse tramite lo stesso programma

si dovrà chiamare il metodo ReInit() per ri-inizializzare il parserquando questo è statico. Se è parser non è statico, si possono creare

multiple istanze usabili simultaneamente attraverso thread diversi.

• DEBUG_PARSER: Opzione booleana (default false) che serve ad otte-nere informazioni di debug dal parser generato. Posta a true fa

1.4. STRUTTURA DI UNA SPECIFICA JAVACC [ 13 ]

sì che il parser generi un trace delle proprie azioni. La tracciatu-

ra può essere disabilitata attraverso il metodo disable_tracing()della classe del parser generato. La si può riprendere in seguito

chiamando enable_tracing().• DEBUG_LOOKAHEAD: Opzione booleana (default false) che posta a truefa sì che il parser generi tutte le informazioni di tracing fornite a

causa dell’opzione DEBUG_PARSER ed in più anche il tracciamentodelle azioni eseguite nelle operazioni di lookahead.

• DEBUG_TOKEN_MANAGER: Opzione booleana (default false) usata perottenere informazione sul debugging dal token manager generato.

Settata a true induce il tokenmanager a generare un trace delle pro-prie azioni. Tale trace è abbastanza dettagliato per cui si dovrebbe

usare solo in caso di estrema difficoltà nella ricerca di errori legati

al lessico. Tipicamente, in tale situazione, si può trovare il problema

considerando le ultime linee del trace.

• ERROR_REPORTING: Opzione booleana (default true) che messa a fal-se fa sì che gli errori di tipo sintattico vengano riportati in mi-

nor dettaglio. L’unica ragione per metterla a false è l’aumento diefficienza.

• JAVA_UNICODE_ESCAPE: Opzione booleana (default false). Quando èsettata a true, il parser usa un oggetto Inputstream che elabora se-quenze di escape di Java Unicode (\u...) prima di mandare i carat-teri al token manager. Per default, le sequenze di escape non ven-

gono elaborate. L’opzione viene ignorata se è posta a true l’opzioneUSER_TOKEN_MANAGER, oppure USER_CHAR_STREAM.• UNICODE_INPUT: Opzione booleana (default false). Quando è settataa true, il parser usa un oggetto InputStream che legge file Unicode.Per default, si assume di avere in input file ASCII. L’opzione vie-

ne ignorata se è posta a true l’opzione USER_TOKEN_MANAGER, oppureUSER_CHAR_STREAM.• IGNORE_CASE: Opzione booleana (default false) che posta a vero in-duce il token manager ad ignorare la differenza tra maiuscole e mi-

nuscole nella specifica dei token e dei file in input. Ciò è utile nel-

la scrittura di grammatiche per linguaggi come PASCAL e HTML.

È anche possibile localizzare l’effetto di IGNORE_CASE tramite unmeccanismo spiegato nel seguito.

• USER_TOKEN_MANAGER: Opzione booleana (default false) che indu-ce il token manager a lavorare con i token specificati. Se messa atrue, il parser accetterà token da qualsiasi token manager di tipoTokenManager – un’interfaccia generata nella directory del parser.

• SUPPORT_CLASS_VISIBILITY_PUBLIC: Opzione booleana (defaulttrue). Fa generare le classi di supporto (Token, ParseException, ecc.)con visibilità public. Semessa a false, esse saranno private a livellodi package.

[ 14 ] 1. INTRODUZIONE• USER_CHAR_STREAM: Opzione booleana (default false). l’azione di de-fault è di generare un lettore del flusso di caratteri come specificato

dalle opzioni JAVA_UNICODE_ESCAPE e UNICODE_INPUT. Il token ma-nager riceve caratteri da tale stream reader. Se viene messa a true,il token manager leggerà i caratteri da qualunque flusso di caratte-

ri del tipo CharStream. Tale file viene generato nella directory delparser. L’opzione viene ignorata se USER_TOKEN_MANAGER è posta atrue.

• BUILD_PARSER: Opzione booleana (default true) che induce a gene-rare il file del parser. Se messa a false, il file del parser non vie-ne generato. Questo serve quando si vuole generare solo il token

manager da usarsi senza parser associato.

• BUILD_TOKEN_MANAGER: Opzione booleana (default true) che serve afar generare il file per il token manager. Se messa a false, il file deltoken manager non viene generato. Può servire solo a risparmiare

tempo nella generazione del parser (in fase di debugging) in modo

da lasciare le specifiche lessicali intatte.

• TOKEN_MANAGER_USES_PARSER: Opzione booleana (default false) chemessa a true, fa includere nel token manager un campo parser chesi riferisce all’istanza del parser corrispondente. Lo scopo di un par-

ser in un token manager sta nell’uso di parte della sua logica nelle

azioni lessicali. Quest’opzione non ha effetto se STATIC è posta atrue.• TOKEN_EXTENDS: Opzione che richiede una stringa (default “). Laclasse Token normalmente estende java.lang.Object. Tale opzione

può essere settata al nome di una diversa classe da usare come base

per la classe Token.

• TOKEN_FACTORY: Opzione che richiede una stringa (default ""). Essaindica che i token andranno creati chiamando Token.newToken().Va settata per indicare una classe Token-factory che contiene unme-

todo public static Token newToken(int ofKind, String image)• SANITY_CHECK: Opzione booleana (default true). JavaCC effettuamolti controlli sintattici e semantici sul file di specifica durante la

generazione del parser. Alcuni rilevamenti, come quello della ricor-

sione sinistra, dell’ambiguità e del cattivo uso delle lambda-regole

può essere soppresso per una generazione più veloce settando tale

opzione a false. La presenza di tali errori (pur non rilevati per via

dell’opzione posta a false) può causare un comportamento inattesoda parte del parser.

• FORCE_LA_CHECK: Opzione booleana che controlla il rilevamentodell’ambiguità tramite lookahead effettuato da JavaCC. Per default

(false), il rilevamento viene effettuato per tutti i punti di scelta do-ve il lookahead di default è pari a 1, mentre non viene effettuato

nei punti dove c’è un’esplicita specifica di lookahead oppure se l’op-

zione LOOKAHEAD sia settata ad un valore diverso da 1. Mettendo

1.4. STRUTTURA DI UNA SPECIFICA JAVACC [ 15 ]

l’opzione a true si effettuano i controlli in ogni punto a prescinderedalle specifiche di lookahead nel file.

• COMMON_TOKEN_ACTION: Opzione booleana (default false). Quan-do viene settata a true, ogni chiamata al metodo getNextToken() causa una chiamata ad un metodo CommonTokenAction() de-finito dall’utente, dopo che il token sia stato accettato dal to-

ken manager. L’utente deve definire questo metodo nella se-

zione TOKEN_MGR_DECLS. La firma del metodo è la seguente:void CommonTokenAction(Token t)• CACHE_TOKENS: Opzione booleana (default false). Quando viene set-tata a true, il parser effettua il lookahead di token supplementari inanticipo. Questo apporta miglioramenti delle prestazioni. Tuttavia,

in tale caso, potrebbero non funzionare le applicazioni interattive

dato che il parser ha bisogno di lavorare in maniera sincrona con

la disponibilità di token dal flusso di input. In tali casi, è meglio

lasciare l’opzione al suo valore di default.

• OUTPUT_DIRECTORY: Opzione a valori stringa che ha come defaultla directory corrente. Serve a cambiare la directory ove andranno

posti i file generati.

In maniera forse controintuitiva, i nomi delle opzioni non sono case-

sensitive.

1.4.2 PRODUZIONILe produzioni del file di specifica sono di quattro tipi, come evidenziato

dalla meta- regola:

produzione : : = dic_token_manager

| regola_ER

| prod_bnf

| prod_javacode

Le dichiarazioni per il token manager (dic_token_manager) vengo-

no usate per introdurre dichiarazioni (in Java) da inserire nel token

manager da generare (cfr. §2.3).

Le regole lessicali (regola_ER) vengono usate per indicare i token della

grammatica per i quali si genera il token manager (cfr. §2.4), includendo

anche le specifiche di token (anonimi) inserite direttamente (inline) nelleregole grammaticali per il parser.

Infine, le produzioni BNF (prod_bnf, cfr. §3.1) e le produzioni Javaco-

de (prod_javacode, cfr. §3.2) sono usate per definire la grammatica dalla

quale si genera il parser.

[ 16 ] 1. INTRODUZIONE

CAPITOLO

2

ANALISI LESSICALE

2.1 L’ANALIZZATORE LESSICALEIn un compilatore convenzionale l’analisi lessicale viene svolta da unmo-

dulo detto scanner o lexer. JavaCC usa il termine token manager (gestoredei token). Il token manager analizza il flusso di caratteri in input sepa-

rando spezzoni detti token e assegnando ad ogni token un suo tipo. Ad

esempio, consideriamo il seguente frammento di codice:

1 int main() {2 /* programmino */3 return 0; }Il token manager potrebbe suddividere la stringa come segue: "int", "", "main", "(", ")", " ", "{", "\n", "\t", "/* programmino */", "\n", "return", " ", "0", ";", " ", "}" e l’end-of-file.La spaziatura ed i commenti sono in genere scartati subito, quindi i

token veri e propri saranno: "int", "main", "(", ")", "{", "return", "0", ";", "}" e EOF. Ad ognuni stringa viene attribuito un tipo di token (di seguitodenotati con maiuscole, dato che i loro codici saranno rappresentati da

costanti Java). Ad es.: PCINT, ID, PARS, PARD, GRAFS, PCRETURN, COSTINT, PEV, GRAFD. Ogni token estratto viene rappresentato da un oggetto di classeToken che, tra gli altri, presenta i seguenti attributi:• .kind: il tipo di token codificato come intero;• .image: la stringa estratta dall’input.La sequenza di oggetti Token viene prodotta in base alle espressioni

regolari descritte nella sezione dedicata nella specifica. Tale sequenza

[ 17 ]

[ 18 ] 2. ANALISI LESSICALEviene quindi inviata tipicamente ad un oggetto di tipo Parser per ulteriorielaborazioni.

2.2 FUNZIONAMENTO DEL TOKEN MANAGERLa specifica lessicale di JavaCC è organizzata in un insieme di stati les-sicali. Ogni stato lessicale è denominato con un identificatore. C’è unostato standard detto DEFAULT. Il token manager è in ogni istante in unodi questi stati. Quando il token manager viene inizializzato, si parte con

lo stato DEFAULT. Lo stato iniziale può essere modificato attraverso unparametro nella costruzione di un oggetto token manager.

Ogni stato lessicale contiene una lista ordinata di espressioni regola-

ri; l’ordine è quello in cui esse compaiono nella specifica. Ci sono quat-

tro tipi di espressioni regolari: SKIP, MORE, TOKEN e SPECIAL_TOKEN. Tuttele espressioni regolari che dovessero occorrere nelle regole della sintas-

si (cfr. §3.1.1) sono considerate appartenere allo stato DEFAULT ed il loroordine di occorrenza dipende dalla loro posizione nel file di specifica.

La corrispondenza (match) tra i pattern dei token ed il flusso dicaratteri in input viene disciplinata come segue:

• tutte le espressioni regolari appartenenti allo stato lessicale

corrente sono considerate come candidate potenziali;

• il tokenmanager consuma il massimo numero di caratteri del flusso

di input che corrispondano a quelli previsti dall’espressione;

– il token manager preferisce la corrispondenza più lungapossibile;

• se ci sono diverse corrispondenze di pari lunghezza, si sceglie

l’espressione regolare che compare per prima nel file di specifica.

Come detto, il token manager è da considerarsi in un unico stato lessi-

cale (corrente). In ogni dato momento, il token manager considera esclu-

sivamente le espressioni regolari relative allo stato corrente. Dopo aver

trovato una corrispondenza, si può specificare un’azione lessicale da ese-guire (cfr.§2.7) ed (opzionalmente) anche un nuovo stato in cui transita-

re. Se non viene specificato un nuovo stato lessicale, il token manager

resta nello stato corrente.

Il tipo d’espressione regolare specifica cosa fare quando la corrispon-

denza con l’espressione viene trovata:

• SKIP semplicemente scarta la stringa trovata (dopo aver eseguitol’eventuale azione lessicale).

• MORE continua portandosi dietro la stringa trovata (eventualmen-te cambiando stato). La stringa costituirà un prefisso della nuova

stringa da trovare.

• TOKEN Crea un token usando la stringa trovata da mandare al parser(o comunque dal chiamante).

2.3. DICHIARAZIONI PER IL TOKEN MANAGER [ 19 ]

• SPECIAL_TOKEN Crea un token speciale che non partecipa al parsing(vedi più avanti).

Quando si giunge a fine-file, questo evento causa la creazione del token

speciale <EOF> (a prescindere dallo stato corrente dell’analizzatore lessi-cale). Se <EOF> occorre mentre si completava la corrispondenza con un’e-spressione regolare, o subito dopo il match con un’espressione regolareMORE, viene riportato un errore.Dopo che è stata trovata la corrispondenza con un’espressione rego-

lare, l’eventuale azione lessicale viene eseguita. Tutte le variabili e i me-

todi dichiarati nella sezione TOKEN_MGR_DECLS (cfr. §2.7) sono disponibiliper l’uso: le variabili e i metodi elencati possono essere utilizzati. Subi-

to dopo, il token manager cambia lo stato se ne è specificato uno nuovo.

Quindi si intraprende un’azione finale che dipende dal tipo di espressio-

ne regolare (tra quelli su elencati): se il tipo è TOKEN, il token trovato vie-ne restituito; se è SPECIAL_TOKEN, il token trovato viene salvato per essererestituito assieme al prossimo token trovato.

2.3 DICHIARAZIONI PER IL TOKEN MANAGERRiprendendo il discorso fatto per le produzioni (cfr. §1.4.2), la meta-

regola per descrivere le dichiarazioni per il token manager risulta la

seguente:

dic_token_manager : : = "TOKEN_MGR_DECLS" ":" bloccoLa sezione delle dichiarazioni del token manager inizia con la parola ri-

servata TOKEN_MGR_DECLS seguita da : e da un blocco di codice Java (blocco) con dichiarazioni e istruzioni per il token manager. Tale codice verrà

trascritto nel tokenmanager così che le dichiarazioni e le istruzioni siano

accessibili alle azioni lessicali (descritte in §2.7 seguito).

Si noti che in ogni file di specifica ci può essere una sola sezione delledichiarazioni.

2.4 TOKEN: REGOLE PER ESPRESSIONI REGOLARIUna regola per espressioni regolari serve a definire entità lessicali che

vengono elaborate dal token manager generato. La meta-regola che la

descrive è la seguente:

regola_ER : : = [ l i s t a _ s t a t i _ l e s s i c a l i ]

tipo_ER [ "[" "IGNORE_CASE" "]" ] ":""{" specifica_ER ( "|" specifica_ER ) * "}"Una regola per espressioni regolari inizia con la specifica (opzionale) di

una lista di stati lessicali ai quali si applica. Lo stato lessicale standard èdenominato DEFAULT. Qualora non esistano altri stati s’intende che talestato sia implicitamente lo stato corrente.

Segue una descrizione del tipo delle espressoni regolari contenute nel-

le graffe. Può essere presente anche l’indicazione opzionale IGNORE_CASE

[ 20 ] 2. ANALISI LESSICALEad indicare che non si farà differenza tra minuscole e maiuscole nel rico-

noscimento dell’espressione regolare – si ha lo stesso effetto dell’opzioneIGNORE_CASE, tranne che nella regola questo è locale anziché globale (pertutte le espressioni regolari).

Segue, infine, una lista di specifiche di espressioni regolari che

descrivono in maggior dettaglio le entità lessicali di questa regola.

2.4.1 LISTA DI STATI LESSICALILa lista degli stati lessicali descrive l’insieme di stati ai quali si applicano

le successive regole di espressioni regolari.

Gli stati lessicali vengono elencati seguendo la meta-regola:

l i s t a _ s t a t i _ l e s s i c a l i : : = "<" "*" ">" | "<" id ( "," id ) * ">"Usando la forma <*>, la regola si applica a tutti gli stati. Altrimenti si ap-plica a tutti gli stati indicati nella lista di identificatori, separati da virgole,

posta tra parentesi angolari.

2.4.2 TIPI DI ESPRESSIONI REGOLARIPer specificare la tipologia delle regole per espressioni regolari, questi si

possono indicare in quattro modi

tipo_ER : : = "TOKEN" | "SPECIAL_TOKEN" | "SKIP" | "MORE"che possono essere così spiegati:

• TOKEN: l’espressione regolare della regola descrive un token del lin-guaggio. Per ogni corrispondenza trovata con tale espressione, il

token manager crea un oggetto Token da restituire al parser;• SPECIAL_TOKEN: l’espressione regolare descrive token speciali chesono simili ai token tranne che per il fatto di non avere significato

ai fini del parsing: le produzioni BNF li ignorano. I token speciali so-

no comunque passati al parser in modo che questo possa utilizzarli.

Precisamente vengono passati in congiunzione con i token normali

nelle vicinanze attraverso il campo specialToken della classe Token. I token speciali sono utili all’elaborazione di lessemi come i com-

menti che non hanno significato per il parsing ma servono al file in

input;

• SKIP: le corrispondenti espressioni regolari della semplicementesaltate (ignorate) dal token manager;

• MORE: A volte è utile costruire gradualmente un token da passareal parser. Le corrispondenze con questo tipo di espressioni regolari

viene salvata in un buffer fino alla corrispondenza con lessemi di ti-

po TOKEN o SPECIAL_TOKEN. Quindi tutte le corrispondenze nel buffere i TOKEN/SPECIAL_TOKEN finali vengono concatenate per formare ununico TOKEN/SPECIAL_TOKEN che viene passato al parser. Se invecesi incontra una corrispondenza con una regola di SKIP il contenutodel buffer viene eliminato.

2.4. TOKEN: REGOLE PER ESPRESSIONI REGOLARI [ 21 ]

2.4.3 SPECIFICA DI ESPRESSIONI REGOLARILa specifica delle espressioni regolari inaugura la sezione dedicata alle

entità che fanno parte del lessico. Ogni regola per espressioni regolari

può contenere un numero variabile di specifiche di espressioni regolari

(separate da |, cfr. 2.4).Le specifiche seguono la meta-regola:

specifica_ER : : = ER [ blocco ] [ ":" id ]

Ogni specifica contiene un’espressione regolare (ER), eventualmente se-

guita da un blocco di istruzioni Java (azione lessicale). Si può infine

indicare anche uno stato lessicale d’arrivo (preceduto da :).Ogni volta che si trovi la corrispondenza dell’input con l’espressione

regolare si esegue l’eventuale azione lessicale seguita dalle azioni comuni

a tutti i token. Quindi si intraprende l’azione che può dipendere dal tipo

di token. Infine, se è stato specificato anche uno stato lessicale, il token

manager transita in quello stato per continuare la sua elaborazione (lo

stato di partenza è sempre DEFAULT).La meta regola per le espressioni regolari (dotate di nome) è la

seguente:

ER : : = stringa_java

| "<" [ [ "#" ] id ":" ] scelte_ER_complesse ">"| "<" id ">"| "<" "EOF" ">"

Le espressioni regolari possono essere inserite in due zone del file

della grammatica:

• in una specifica di espressione regolare come parte di una regola di

produzione relativa;

• in un’unità d’espansione (d’una regola grammaticale, si veda 3.1.1).

In questo caso è come se l’espressione regolare fosse definita nella

posizione data come segue:

1 <DEFAULT>2 TOKEN:3 {4 ER5 }6

e quindi si può poi farvi riferimento nell’espansione attraverso la

sua etichetta.

Seguendo la meta-regola:

1. Un tipo di espressione regolare è quello del letterale-stringa (vali-do in Java). Il flusso di caratteri in input trova corrispondenza con

questo tipo di espressione regolare se il token manager è in uno

stato lessicale per il quale è prevista tale espressione e la prossima

stringa di caratteri in input è uguale alla stringa data (a volte senza

riferimento alla differenza maiuscole/minuscole).

[ 22 ] 2. ANALISI LESSICALE2. Un altro tipo è quello delle espressioni complesse. Queste espressio-ni vengono inserite tra parentesi angolari <...> e possono essereetichettate con un identificatore. Questa etichetta potrà poi essere

impiegata per riferirsi all’espressione regolare dall’interno di unità

d’espansione o da altre espressioni regolari. Se l’etichetta è prece-

duta da una #, si tratta di una espressione regolare privata, e si potràusare l’etichetta solo da parte di altre espressioni e non di espan-

sioni. Le etichette sono separate dalle scelte di espressioni regolari

seguenti usando il simbolo :.3. Un’espressione regolare può fare da riferimento ad altre espressionietichettate nel qual caso viene scritta come etichetta racchiusa tra

parentesi angolari <...>.4. Infine, si può fare riferimento all’espressione regolare predefinita<EOF> che corrisponde alla condizione di fine-file.

Le espressioni regolari private non sono trattate come token da resti-tuire da parte del token manager. Il loro scopo è esclusivamente la

facilitazione della definizione di altre espressioni più complesse.

Esempio 2.1 (costanti in virgola mobile): Si consideri la seguente defi-

nizione dei letterali floating-point in Java:

1 TOKEN :2 {3 < LETTERALE_FLOATING_POINT:4 (["0"-"9"])+ "." (["0"-"9"])* (<ESP>)? (["f","F","d","D"])?5 | "." (["0"-"9"])+ (<ESP>)? (["f","F","d","D"])?6 | (["0"-"9"])+ <ESP> (["f","F","d","D"])?7 | (["0"-"9"])+ (<ESP>)? ["f","F","d","D"]8 >9 | < #ESP: ["e","E"] (["+","-"])? (["0"-"9"])+ >10 }Il token LETTERALE_FLOATING_POINT è definito usando la definizio-ne di un altro token, ESP. Il carattere # che precede l’etichet-ta ESP indica che questa esiste solo allo scopo di definire altri

token (LETTERALE_FLOATING_POINT in tal caso). La definizione diLETTERALE_FLOATING_POINT non è influenzata dalla presenza o assenzadi #. Tuttavia, ciò ha conseguenze per il comportamento del token mana-ger. Se si omette #, il token manager riconoscerà erroneamente stringhecome "E123" come token di tipo ESP (anziché come identificatori Java).Le scelte per le espressioni regolari complesse sono fatte da una lista di

una o più espressioni complesse separate da |:scelte_ER_complesse : : = ER_complessa ( "|" ER_complessa ) *Per la corrispondenza basta il match con una delle espressioni regolari

costituenti:

Un’espressione regolare complessa è una sequenza di

unita_ER_complessa.

2.4. TOKEN: REGOLE PER ESPRESSIONI REGOLARI [ 23 ]

ER_complessa : : = ( unita_ER_complesse ) *

Per il match bisogna trovare la corrispondenza multipla di più unità

complesse concatenate.

Queste unità sono descritte dalla meta-regola:

unita_ER_complessa : : = stringa_java

| "<" id ">"| l i s t a _ ca ra t t e r i

| "(" scelte_ER_complesse ")"[ "+" | "*" | "?" ]

Una unità di espressione regolare complessa:

1. può essere un letterale stringa, nel qual caso il token manager devetrovare la corrispondenza esatta con la stringa.

2. può essere un riferimento ad un’altra espressione regolare che saràstata etichettata per cui possiamo farvi riferimento. I riferimentinon devono creare cicli nei mutui rapporti di dipendenza tra i token.

3. può essere costituita da una lista di caratteri (da intendersi comeinsieme). La corrispondenza che deve essere trovata è con uno dei

caratteri consentiti dalla lista.

4. può essere data da un insieme di scelte di espressioni complesseracchiuse tra parentesi tonde (...) e separate da |. In tal caso, lacorrispondenza da trovare è con una delle espressioni alternative.

Le scelte tra parentesi possono avere uno dei tre suffissi (opzionali):

• +: indica che la corrispondenza con una o più ripetizioni delleespressioni tra parentesi;

• *: indica la corrispondenza con zero o più ripetizioni delleespressioni tra parentesi;

• ?: indica la corrispondenza con la stringa vuota o con una delleespressioni tra parentesi.

Si noti che, diversamente dalle espansioni BNF illustrate nel seguito, l’e-

spressione regolare [...] non equivale a (...)?. Ciò perché si usa ilcostrutto [...] per descrivere liste di caratteri nelle espressioni regolari.Una lista di caratteri descrive un set di caratteri, ed è definita

attraverso la seguente meta-regola:

l i s t a _ ca ra t t e r i : : = [ "~" ] "[" [ descr_caratteri

( "," descr_caratteri ) * ] "]"Essa consiste in una lista di descrittori di caratteri separati da virgole ed

inclusa tra quadre [ ]. Ogni descrittore descrive un singolo carattere oun intervallo. Se viene anteposto il prefisso ~, l’insieme è da intendersicomplementato (rispetto all’insieme dei caratteri Unicode).Formalmente il descrittore segue la meta-regola:

[ 24 ] 2. ANALISI LESSICALE

descr_caratteri : : = stringa [ "-" stringa ]

Un descrittore può essere dato da una stringa di un solo carattere, nelqual caso descrive l’insieme composto da quel solo carattere, oppure da

due caratteri separati da un -, nel qual caso descrive un intervallo checomprende tutti i caratteri, estremi compresi.

2.5 PREFISSI COMUNICi sono tre regole da seguire per scegliere l’espressione regolare da usare

per identificare il prossimo token:

1. l’espressione regolare deve descrivere un prefisso del rimanente

flusso di caratteri in ingresso;

2. se più di un’espressione descrive tale prefisso, allora l’espressione

regolare che descrive il prefisso più lungo viene utilizzata. (Questa

regola si chiama anche “maximal munch rule”.)3. se più di un’espressione regolare descrive il prefisso più lungo, allo-

ra si seleziona l’espressione regolare definita prima delle altre nel

file .jj.

ESEMPIO: Si supponga di dover analizzare codice Java, (ovvero anche C,o C++). Le prossime tre espressioni regolari potrebbero essere previste in

una specifica:

1 TOKEN : { < PLUS : "+" > }2 TOKEN : { < ASSIGN : "=" > }3 TOKEN : { < PLASSIGN : "+=" > }Si supponga anche che l’input stream cominci con "+=1;...". La regola 1taglia fuori la seconda produzione. La regola 2 dice di preferire la terza

alla prima. L’ordine delle produzioni non ha effetto in questo esempio.

ESEMPIO: Soffermandoci su Java, (o C, o C++), si supponga di avere leproduzioni di espressioni regolari

1 TOKEN : { < KWINT : "int" > }2 TOKEN : { < IDENT : ["a"-"z","A"-"Z", "_"] (["a"-"z","A"-"Z","0"-"9","_"])* > }Si supponga anche che il flusso di caratteri in input cominci con "integeri;...", allora la seconda produzione sarebbe preferita per la regola 2.Ma se la parte restante fosse "int i;...", allora tale regola non sarebbed’aiuto, dato che entrambe le produzioni avrebbero in comune un prefis-

so di lunghezza 3. In tal caso la produzione KWINT viene preferita (regola3) perché viene prima nella specifica.

2.6. LA CLASSE DEI TOKEN [ 25 ]

2.6 LA CLASSE DEI TOKENLa classe Token rappresenta il tipo degli oggetti creati dal token managerdopo una scansione dell’ingresso. Tali oggetti sono passati al parser affin-

ché anche le azioni grammaticali possanomanipolarli. I metodi getToken() e getNextToken() del token manager consentono l’accesso agli oggettidi questa classe.

Ci sono due classi di token:

• I token normali sono token che vengono elaborati dal parser.• I token speciali sono altri token che non hanno rilevanza sintat-tica ma non vengono scartati, come si farebbe ad esempio con i

commenti.

Ogni oggetto di tipo Token ha i seguenti campi:• int kind: indice della classe di token nello schema di rappresenta-zione interno di JavaCC. Quando i token hanno una etichetta nella

specifica per JavaCC, ad esempio <PIU: "+" >, questa viene utilizza-ta per generare costanti intere (int) che si possono usare nelle azio-ni. Il valore 0 viene usato sempre per rappresentare il token <EOF>predefinito. Per convenzione, nel file NNConstants.jj si genera unacostante EOF.

• int beginLine, beginColumn, endLine, endColumn: indicano le

posizioni di inizio e fine del token, così come appare nel flusso

d’ingresso.

• String image: rappresenta l’immagine del token così come apparenel flusso d’ingresso.

• Token next: riferimento al prossimo token normale in ingresso. Seè l’ultimo token in ingresso, o se il token manager non ha letto to-

ken dopo di questo, il campo prende il valore null. La descrizioneinterna è valida solo se si tratta di un token normale.

• Token specialToken: si utilizza per accedere ai token speciali cheoccorrono prima del token, ma dopo il token normale (non speciale)

che lo precede immediatamente. Se non esistono tali token speciali,

questo campo prende il valore null. Quando c’è più di un tokenspeciale, questo campo si riferisce all’ultimo di tali token, il quale

farà riferimento al precedente e così di seguito fino ad arrivare al

primo token speciale, il cui campo specialToken è null.• static final Token newToken(int ofKind): per default, il com-portamento consiste nel restituire un nuovo oggetto Token. Se sivogliono far eseguire azioni speciali quando si costruisce un token

o si creano ed istanziano sottoclassi della classe Token, si può ridefi-nire tale metodo in modo appropriato. L’unico vincolo è che questo

metodo restituisca un oggetto di tipo Token (o d’una sua sottoclasse).• public final String toString(): questo metodo restituisce il

valore di image come stringa.

[ 26 ] 2. ANALISI LESSICALE2.7 AZIONI LESSICALI2.7.1 VARIABILIPrima di tutto vediamo quali variabili si possono utilizzare nelle azioni

lessicali:

• StringBuffer image (lettura/scrittura): oggetto, distinto dal campo.image dei token, che contiene tutti i caratteri che sono stati ritro-vati dopo l’ultimo token di tipo SKIP, TOKEN, o SPECIAL_TOKEN. Si èliberi di fare qualunque modifica alla variabile purché non le si as-

segni un valore nullo (dato che questa variabile viene usata anche

dal token manager). Se si fanno cambiamenti ad image, questi siriverberano su tutte le seguenti corrispondenze (se quella corrente

riguarda un token MORE). Il contenuto di image non viene assegna-to automaticamente al campo .image del token trovato. Se si vuoleche questo accada, si deve operare l’assegnazione in modo esplici-

to in un’azione relativa ad un’espressione regolare di tipo TOKEN oSPECIAL_TOKEN.

ESEMPIO: Dato il frammento:1 <DEFAULT> MORE :2 {3 "a" : STATO14 }5

6 <STATO1> MORE :7 {8 "b"9 {10 int l = image.length()-1; // (1)11 image.setCharAt(l,image.charAt(l).toUpperCase()); // (2)12 } : STATO213 }14

15 <STATO2> TOKEN :16 {17 "cd" // (3)18 { x = image; } : DEFAULT19 }si osservi come varia il valore di image nei tre punti contrassegnatidai commenti numerati:

(1) sarà "ab"(2) sarà "aB"(3) sarà "aBcd"

• int lengthOfMatch (sola lettura): lunghezza della stringa correntedi cui è stata trovata la corrispondenza (non si cumula con i tokenMORE). Tale variabile non va modificata.

2.7. AZIONI LESSICALI [ 27 ]

ESEMPIO: usando lo stesso frammento dell’es. precedente, i valoridi lengthOfMatch saranno:(1) 1 (lunghezza di "b")(2) 1 (non cambia a causa delle azioni lessicali)

(3) 2 (lunghezza di "cd")• int curLexState (sola lettura): indice dello stato lessicale corrente.Non si dovrebbe modificare la variabile. Le costanti intere generate

corrispondenti agli stati lessicali sono definite nel file NNConstants.java, per cui ci si può riferire agli stati senza ricordare il loro valoreeffettivo.

• inputStream (sola lettura): indica il tipo stream di input

appropriato. Le alternative sono le seguenti:

– ASCII_CharStream,– ASCII_UCodeESC_CharStream,– UCode_CharStream,– UCode_UCodeESC_CharStream

a seconda delle impostazioni per le opzioni UNICODE_INPUT eJAVA_UNICODE_ESCAPE.Lo stream si trova sempre sull’ultimo carattere consumato per il

match. Si possono chiamare i metodi previsti per InputStream. Adesempio, si possono invocare getEndLine() e getEndColumn() perleggere linea e colonna della corrispondenza trovata. inputStreamnon può essere modificato.

• Token matchedToken (lettura/scrittura): si usa in azioni associate adespressioni regolari per TOKEN e SPECIAL_TOKEN. Questo deve esse-re il token da restituire al parser. Si può modificare questa varia-

bile facendo quindi restituire qualcos’altro al parser invece del to-

ken originale. Qui si può assegnare il valore della variabile imagea matchedToken.image. Questo è il moto tipico di far avere effettiall’esterno delle azioni lessicali ai cambiamenti ad image.

ESEMPIO: se modifichiamo l’ultima specifica di espressione regola-re dell’esempio di cui sopra:

1 <S2> TOKEN :2 {3 "cd" { matchedToken.image = image.toString(); } : DEFAULT4 }il token restituito al parser avrà il valore "aBcd" nel campo .image.Senza l’assegnazione, allora nel campo .image rimarrebbe "abcd".

• void SwitchTo(int): metodo che commuta lo stato lessicale corren-te in quello indicato. Il metodo può essere chiamato anche dalle

[ 28 ] 2. ANALISI LESSICALEazioni del parser (oltre che da quelle lessicali). Tuttavia, bisogna

stare attenti quando lo si invoca dal parser dato che l’analisi lessi-

cale potrebbe essere andata avanti di molti token rispetto al parser

in presenza di lookahead lunghi. Quando si usa il metodo in un’a-

zione lessicale, ci si deve assicurare che la sua chiamata sia l’ultima

istruzione eseguita altrimenti si possono verificare comportamenti

indesiderati. Se c’è un cambiamento di stato già specificato attra-

verso la modalità standard (: NOMESTATO), esso prevale su tutte lechiamate a SwitchTo(). In generale, si dovrebbe ricorrere alla chia-mata di tale metodo solo quando non si può fare altrimenti. Usando

questo metodo di cambiamento di stato si perde un po’ di controllo

sulla semantica da parte di JavaCC rispetto alla sintassi normale.

2.7.2 ESEMPIVediamo due esempi in cui vengono utilizzati alcuni dei costrutti visti

sinora.

Esempio 2.2 (salto dei commenti): Con passaggio di stato lessicale e

uso di token MORE1 SKIP :2 {3 "/*" : InCommento4 }5

6 <InCommento> SKIP :7 {8 "*/" : DEFAULT9 }10

11 <InCommento> MORE :12 {13 <~[]>14 }

Esempio 2.3 (lettura stringhe): Calcolo della lunghezza della stringa

letta:

1 TOKEN_MGR_DECLS :2 {3 int lungStringa;4 }5

6 MORE :7 {8 "\"" { lungStringa = 0;} : InStringa9 }10

11 <InStringa> TOKEN :12 {13 <STRLIT: "\"">

2.7. AZIONI LESSICALI [ 29 ]

14 {System.out.println("|S| = " + lungStringa);} : DEFAULT15 }16

17 <InStringa> MORE :18 {19 <~["\n","\r"]> {lungStringa++;}20 }

2.7.3 TOKEN SPECIALI E PARSERI token speciali sono simili ai token normali tranne che per il fatto di

poter comparire ovunque nel file di input (tra qualsiasi coppia di token).

I token speciali possono essere specificati nel file di grammatica usando

la parola riservata SPECIAL_TOKEN invece di TOKEN:1 SPECIAL_TOKEN :2 {3 <COMMENTO_RIGA: "//" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>4 }Si può accedere ad ogni espressione regolare definita comeSPECIAL_TOKEN in un modo speciale, usando azioni utente nella spe-cifica lessicale e sintattica. Ciò consente di recuperare tali token durante

il parsing mentre essi non vi partecipano. JavaCC è stato addestrato a

usare questa caratteristica per copiare automaticamente i commenti più

rilevanti nei file generati.

Come detto, la classe Token ha un campo Token specialToken che pun-ta al token speciale immediatamente precedente rispetto al token cor-

rente (speciale o normale). Se il token precedente è normale (non è uno

speciale), allora il campo è nullo. I campi .next dei token normali con-tinuano ad avere lo stesso significato; ad es., puntare al prossimo token

normale tranne le caso di un token EOF dove il campo .next risulta nullo.Il campo .next dei token speciali puntano al token speciale che segue im-mediatamente il token corrente. Se il token seguente è normale, il campo.next è impostato al valore nullo.Questo viene ulteriormente chiarito dal seguente esempio.

Esempio 2.4: Si supponga di voler stampare tutti i token speciali prima

del token t (ma solo quelli che seguono il token normale prima di t):1 // ritorno al chiamante: non ci sono token speciali2 if (t.specialToken == null) return;3 // torna indietro nella catena di token speciali fino4 // al primo che segue il token normale precedente5 Token tmp_t = t.specialToken;6 while (tmp_t.specialToken != null)7 tmp_t = tmp_t.specialToken;8

9 // ciclo che percorre la catena in avanti10 // stampando i token man mano11 while (tmp_t != null) {

[ 30 ] 2. ANALISI LESSICALE12 System.out.println(tmp_t.image);13 tmp_t = tmp_t.next;14 }

2.8 ANALISI LESSICALE EFFICIENTECi sono variemaniere per scrivere una specifica lessicale in una gramma-

tica. Le prestazioni del token manager generato variano in modo signifi-

cativo a seconda di come la si scrive. Nel seguito sono presentate alcune

linee guida:

• Si provi a specificare quante più stringhe (letterali) sia possibile.

Queste vengono riconosciute da un automa a stati finiti determini-

stico (Deterministic Finite Automata, DFA), che è molto più veloce diquello non-deterministico (Nondeterministic Finite Automata, NFA)che serve a riconoscere tipi più complessi di espressioni regolari.

Ad esempio, per saltare spaziatura tabulazioni e ritorni a capo:

1 SKIP :2 {3 " " | "\t" | "\n"4 }il token manager risulterà più veloce di quello generato da:

1 SKIP :2 {3 < ([" ", "\t", "\n"])+ >4 }perché nel primo caso si hanno solo stringhe letterali e si genera

un (simulatore di) DFA, mente nel secondo caso verrà generato un

(simulatore di) NFA.

• Si provi ad usare il pattern ~[] da solo il più possibile. Ad esempio,scrivere:

1 MORE :2 {3 < ~[] >4 }è preferibile alla maniera seguente:

1 TOKEN :2 {3 < (~[])+ >4 }Naturalmente se la grammatica impone che uno di questi non possa

essere usato, allora non c’è scelta, ma si deve provare ad usare il

costrutto < ~[] > tutte le volte che sia possibile.

2.8. ANALISI LESSICALE EFFICIENTE [ 31 ]

• Conviene specificare tutte le stringhe (costanti) in ordine di lunghez-

za crescente, ossia le più corte vanno prima delle più lunghe. Questo

aiuta l’ottimizzazione dei vettori di bit utilizzati per tali stringhe.

• Si provi a minimizzare l’uso degli stati lessicali. Dovendoli usa-

re provare a mettere tutte le espressioni regolari più complesse

in un unico stato lessicale, lasciando agli altri il riconoscimento di

stringhe letterali semplici.

• Si raccomanda di usare IGNORE_CASE con attenzione. La cosa miglio-re da fare è impostare quest’opzione a livello grammaticale. Qualo-

ra non fosse possibile, si provi ad impostarla per tutte le espressioni

regolari di uno stato lessicale. In uno stesso stato lessicale si registra

un grosso degrado di prestazioni quando s’imposta IGNORE_CASE conalcune espressioni regolari e non per altre.

• Si provi a saltare (sezione token SKIP) tutto quello che non è neces-sario. In questo caso, serve un po’ di cautela sull’EOF: trovare un EOFdopo un token di tipo SKIP va bene mentre trovare un EOF dopo untoken MORE comporta un errore lessicale.

• Evitare di specificare azioni lessicali con specifiche MORE. Gene-ralmente ogni MORE dovrebbe terminare alla fine con un TOKEN (oSPECIAL_TOKEN) per cui si può compiere un’azione in questo puntoa livello di TOKEN, se possibile.

• Evitare azioni lessicali e cambi di stato lessicale nelle specifiche SKIP(specialmente per SKIP di un singolo carattere come " ", "\t", "\n"ecc.). In tali casi, viene generato un ciclo semplice per consumare

i caratteri singoli saltati. Ovviamente, se c’è un’azione lessicale o

un cambiamento di stato associato con questo, lo stesso non è più

possibile.

• Evitare di avere più scelte di stringhe letterali (costanti) per lo stesso

token, ad esempio:

1 < FINE : "\"fine\"" | "\’fine\’" >Invece, conviene prevedere due distinti token per questo caso

e usare un non-terminale che rappresenta una scelta tra queste

alternative. L’esempio precedente diventa:

1 < FINE1 : "\"fine\"" >2 |3 < FINE2 : "\’fine\’" >Definendo un non-terminale chiamato Fine come segue

1 void Fine() : {}2 {3 <FINE1> | <FINE2>4 }

[ 32 ] 2. ANALISI LESSICALEsi rende il riconoscimento molto più veloce. Notare comunque,

che se la scelta è tra due complicate espressioni regolari, va bene

conservare la scelta.

CAPITOLO

3

ANALISI SINTATTICA

Come anticipato in §1.4.2, l’analisi sintattica segue regole descritte in

EBNF oppure sotto forma di codice Java (produzioni Javacode).

3.1 PRODUZIONI BNFLa maniera standard per specificare la grammatica di un linguaggio

per JavaCC è quella di scrivere produzioni BNF. Esse hanno una forma

descritta dalla seguente meta-regola:

prod_bnf : : = modificatore tipo id "(" l ista_parametri")" ":"blocco "{" scelte_espansione "}"

Ogni produzione BNF ha una parte sinistra che specifica un non-terminale da definire. La produzione definisce tale non-terminale in

termini di espansioni BNF che trovano posto nella parte destra. Il non-

terminale viene scritto esattamente come un metodo Java, dato che ogni

terminale verrà convertito1 esattamente in un metodo del parser risul-

tante. Il nome del non-terminale è il nome del metodo, mentre i parame-

tri ed il tipo specificato servono ad indicare il modo per passare valori su

o giù per l’albero di parsing. Come mostrato in seguito, i non-terminali a

destra sono da intendersi come chiamate dei metodi corrispondenti con

gli opportuni parametri da passare e valori da restituire. La modalità

d’accesso di default di tali metodi è public.Ci sono due sezioni nella parte destra di una produzione BNF, ossia

dopo il simbolo :.1Parsing ricorsivo-discendente (si veda [1]).

[ 33 ]

[ 34 ] 3. ANALISI SINTATTICA1. La prima sezione (blocco) è costituita da un insieme di dichiarazioni

arbitrarie e di codice Java che andranno a far parte del corpo del

metodo. Tale codice viene inserito all’inizio del metodo relativo al

non-terminale. Ogni volta che questo verrà invocato, durante il pro-

cesso di parsing, tali dichiarazioni o codice saranno eseguiti. Le di-

chiarazioni sono visibili per il codice di tutte le azioni inserite nelle

espansioni BNF. JavaCC non modifica in alcun modo tali dichiara-

zioni o codice, ricopiando tutto il testo fino alla chiusura del blocco.

Pertanto, il compilatore Java potrebbe trovare errori in questa se-

zione dopo che questa sia stata ricopiata da JavaCC senza controlliparticolari.

2. La seconda sezione della parte destra è costituita dalle espansioni

BNF da scegliere.

3.1.1 ESPANSIONI BNFLe scelte d’espansione sono scritte come lista di una o più espansioniseparate da |, come specificato dalla meta-regola:scelte_espansione : : = espansione ( "|" espansione ) *L’insieme delle derivazioni corrette consentite da una scelta è costituito

da tutte quelle relative ad una qualsiasi espansione contenuta.

Un’espansione si scrive come sequenza di unità d’espansione:espansione : : = ( unita_espansione ) *

L’espansione s’intende interamente analizzata quando lo siano state tutte

le sue unità componenti.

ESEMPIO: l’espansione "{" decls() "}" consiste di tre parti - "{", decls() e "}". Una corrispondenza per l’espansione equivale alla concatena-zione delle corrispondenze per le singole parti – in tal caso, sarebbe co-

stituita da qualunque stringa che inizi con una "{", termini con una "}" etra queste preveda la corrispondenza con una sotto-stringa riconosciuta

da decls().Più precisamente, un’unità d’espansione ha la forma prescritta dalla

meta-regola seguente:

unita_espansione : : = lookahead_locale

| blocco

| "(" scelte_espansione ")" [ "+" | "*" | "?" ]

| "[" scelte_espansione "]"| [ p_sinistra_assegnazione "=" ] ER

| [ p_sinistra_assegnazione "=" ] id "("l i s ta_espress ion i ")"

• Un’unità può essere data da una direttiva locale di lookahead(cfr. §3.1.2). Questo spiega al parser generato come prendere le

decisioni nei punti di scelta (si veda §4.2).

3.1. PRODUZIONI BNF [ 35 ]

• Un’unità potrebbe essere anche data da un insieme di dichiarazionie codice Java tra graffe (un blocco). Questa forma si dice anche azio-ne del parser. Essa viene generata nel metodo del non-terminale neipunti specifici. Il blocco viene eseguito tutte le volte che il processo

di analisi superi tale punto con successo. Quando JavaCC elabora

il blocco, non opera alcun controllo sintattico o semantico. Pertan-

to è possibile che il compilatore Java trovi errori nelle azioni dopo

che queste siano state elaborate da JavaCC. Si noti che le azioni non

vengono eseguite durante la valutazione del lookahead.

• Una unità, in genere, è costituita da una o più scelte d’espansione, de-limitato da parentesi (...). In tal caso, perché l’unità concorra all’a-nalisi basta che lo si faccia attraverso una delle sue scelte. L’insieme

di scelte può essere seguito dai seguenti suffissi (opzionali):

– + indica la ripetizione di una o più scelte d’espansione– * indica la ripetizione di una o più scelte d’espansione;– ? indica indica l’opzionalità di una scelta d’espansione;in alternativa si può racchiudere le scelte tra parentesi quadre[...].

• Un’unità può essere anche costituita da una espressione regolare. Intal caso ogni token che corrisponda all’espressione è candidato al

match. Quando la corrispondenza viene trovata, si crea un oggetto

di tipo Token accessibile se assegnato ad una variabile, anteponendoall’espressione regolare il simbolo di assegnazione: id_variabile=. In generale, prima di =, si può avere qualunque parte sinistradi assegnazione valida per Java. L’assegnazione non viene eseguita

mentre si effettua la valutazione del lookahead.

• Un’unità, infine, potrebbe essere costituita da un non-terminale. Intal caso, prende la forma di chiamata del metodo relativo a quel

non-terminale. Se l’analisi del non-terminale va a buon fine lavo-

rando sui i parametri della chiamata viene restituito un valore (a

meno che la sua definizione non dichiari che il tipo di valori resti-

tuiti sia void). Il valore restituito può opzionalmente esser assegna-to ad una variabile nel modo visto in precedenza per i token. Anche

in tal caso, l’assegnazione non viene attuata durante la valutazione

del lookahead. I non-terminali non devono essere disposti in mododa introdurre ricorsioni-sinistre. JavaCC effettua questo controllo

per l’utente.

3.1.2 LOOKAHEAD LOCALEUna specifica di lookahead locale serve ad influenzare il modo in cui il

parser generato opererà le scelte nei punti designati della grammatica.

La specifica ha la forma prescritta dalla seguente meta-regola:

lookahead_locale : : = "LOOKAHEAD" "("[ intero_java ] [ "," ]

[ scelte_espansione ]

[ 36 ] 3. ANALISI SINTATTICA[ "," ] [ "{"espressione_java"}" ]")"

Una specifica di lookahead locale inizia con la parola riservata LOOKAHEADseguita da una serie di vincoli di lookahead tra parentesi tonde. Ci sono

tre diversi tipi di vincoli: il limite di lookahead (costante intera), looka-head sintattico (scelte d’espansione) e il lookahead semantico (l’espres-sione tra graffe). Almeno uno di tali vincoli deve essere presente e se ce

n’è più d’uno, essi vanno separati da virgole.

Segue una breve descrizione di ogni tipo di vincolo. In §4 la questione

del lookahead viene trattata in maggior dettaglio:

• Limite di lookahead: massimo numero di token di lookahead da usa-re per la scelta. Questo valore prevale su quello di default specifica-

bile attraverso l’opzione LOOKAHEAD. Il limite di lookahead vale soloper punti di scelta nel punto dato. Se la specifica di lookahead locale

non si trova su un punto di scelta, tale limite viene ignorato.

• Lookahead sintattico: Espansione o scelte d’espansione usata perdeterminare se sia il caso o meno di intraprendere la scelta presso

la quale è stato apposto tale vincolo. Se non viene fornita alcuna

specifica, il parser usa l’espansione da selezionare durante l’elabo-

razione del lookahead. Se la specifica di lookahead locale non si

trova su un punto di scelta, tale limite viene ignorato.

• Lookahead semantico: espressione booleana valutata quando il par-ser passa per il dato punto. Se l’espressione risulta vera, il parsing

continua normalmente. Se l’espressione risulta falsa è la specifica

di lookahead locale è su un punto di scelta, la scelta corrente non

viene intrapresa e si passa a considerare la prossima. Se l’espressio-

ne è false ma la specifica non è su un punto di scelta, allora il par-

sing termina con un errore. Diversamente dai vincoli degli altri due

tipi, che vengono ignorati nei punti di non-scelta, quelli semantici

sono sempre valutati. Di fatto, il lookahead semantico viene valuta-to anche se viene incontrato durante la valutazione di alcuni altri

controlli sintattici sul lookahead (vedi §4).

VALORI DI DEFAULT PER I VINCOLI DI LOOKAHEAD: Se si fornisce una speci-fica locale di lookahead, ma non sono stati inclusi tutti i vincoli, quelli

mancanti si vedranno assegnati valori di default nel modo seguente:

• Se non è stato fornito il limite e si fornisce un vincolo sintattico al-

lora il limite ha per default il massimo intero (2147483647). Que-sto serve ad implementare una sorta di “lookahead infinito” - ossia,si considerano in anticipo tanti token quanti ne sono necessari per

trovare la corrispondenza con il vincolo sintattico fornito.

• Se non è stato fornito né il limite di lookahead né la specifica sin-

tattica (ma solo quella semantica), il limite ha per default 0. Ciò si-gnifica che il lookahead sintattico non viene eseguito ma solo quello

semantico.

3.2. PRODUZIONI JAVACODE [ 37 ]

3.2 PRODUZIONI JAVACODEUna regola di produzione Javacode è una maniera per scrivere alcuneproduzioni sotto forma di codice Java invece delle consuete espansioni

EBNF (vedere §3.1.1). Ciò risulta utile quando si deve riconoscere qual-

cosa che non è esattamente libero da contesto o, per qualsivoglia ragione,

non risulti agevole da scrivere in forma grammaticale.

La meta-regola relativa alle produzioni Javacode è:

prod_javacode : : = "JAVACODE"mod_accesso tipo id "(" listaParam ")"blocco

ESEMPIO: Nel seguito viene mostrato l’uso di una produzione Javaco-

de. Il non-terminale saltaAllaGraffaCorrispondente consuma token delflusso di input fino alla graffa di chiusura (si assume di aver appena

scandito e superato la prima parentesi d’apertura):

1 JAVACODE2 void saltaAllaGraffaCorrispondente() {3 Token tok;4 int annidamento = 1;5 while (true) {6 tok = getToken(1);7 if (tok.kind == GRAFFA_AP)8 annidamento++;9 if (tok.kind == GRAFFA_CH) {10 annidamento--;11 if (annidamento == 0)12 break;13 }14 tok = getNextToken();15 }16 }

Occorre comunquemuoversi usare tali produzioni cautela: mentre da

un lato esse sono molto espressive, JavaCC le considera semplicemente

come scatole nere (che svolgono in qualche modo sconosciuto un com-

pito di parsing). Può sorgere qualche problema quando le produzioni

Javacode appaiono nei punti di scelta.

Ad esempio utilizzando la produzione dell’esempio precedente in

un’altra produzione:

1 void NT() :2 {}3 {4 saltaAllaGraffaCorrispondente()5 |6 altraProduzione()7 }

[ 38 ] 3. ANALISI SINTATTICAJavaCC non saprebbe cosa scegliere tra le due possibilità. D’altro canto, se

la produzione Javacode venisse usata in un punto che non prevede una

scelta non ci sarebbero problemi, come nel seguente esempio:

1 void NT() : {}2 {3 "{" saltaAllaGraffaCorrispondente()4 |5 "(" listaParametri() ")"6 }

Gli usi delle produzioni Javacode potrebbero essere preceduti nei pun-

ti di scelta anche da direttive LOOKAHEAD sintattiche o semantiche,

come mostrato nell’esempio:

1 void NT() : {}2 {3 LOOKAHEAD( {erroreOccorso}4 saltaAllaGraffaCorrispondente()5 |6 "(" listaParametri() ")"7 }

Il modificatore d’accesso di default per le produzioni Javacode èprivate.

CAPITOLO

4

LOOKAHEAD

Questo capitolo illustra più in dettaglio le soluzioni offerte da javaCC al-

le problematiche relative al non-determinismo nel parsing; essa si basa

sugli esempi1 della distribuzione ufficiale di JavaCC.

4.1 LOOKAHEAD: COS’È, A CHE SERVEIl lavoro del parser consiste nel determinare se la sequenza di token

ricevuti dal token manager (costruiti dal flusso di caratteri in input) si

conforma alla grammatica del linguaggio specificato.

Nella sua forma più generale, questo lavoro può risultare com-

putazionalmente molto dispendioso. Si consideri l’esempio seguente

(Example1.jj):1 void Input() : {}2 {3 "a" BC() "c"4 }5

6 void BC() : {}7 {8 "b" [ "c" ]9 }In questo semplice esempio è abbastanza chiaro che ci sono esattamente

due stringhe ammesse per la grammatica data, ossia "abc" e "abcc". Lamaniera generale per costruire la derivazione è quella di utilizzare la

grammatica guidati dalle stringhe in input.

1I file sono nella sotto-directory examples/Lookahead.

[ 39 ]

[ 40 ] 4. LOOKAHEADESEMPIO: Sia "abc" la stringa in input:passo 1. C’è una sola scelta: il primo carattere in input dev’essere una’a’. Dato che è proprio questo il caso, si va avanti.passo 2. Si procede col non-terminale BC. Qui, di nuovo, c’è una sola pos-

sibilità per il prossimo carattere in input: dev’essere una ’b’.L’input corrisponde e si prosegue.

passo 3. Si è ora ad un “punto di scelta” nella grammatica. Si può en-trare nel costrutto [...] e trovare la corrispondenza, oppureignorarlo del tutto. Si decide di provare ad entrare. Per cui il

prossimo carattere dev’essere una ’c’ come risulta dall’input,per cui questo può essere consumato.

passo 4. Si è completato il lavoro con il non-terminale BC e si torna alnon-terminale Input. Ora la grammatica dice che il prossimocarattere dev’essere un altra ’c’. Ma non ci sono più caratteriin input. Pertanto sorge un problema.

passo 5. Con un simile problema, nel caso generale, si conclude che po-

trebbe essere stata operata una scelta sbagliata in precedenza.

In questo caso, si è fatta una scelta al passo 3. Per cui si deve tor-

nare indietro a quella situazione per provare a fare una scelta

diversa. Tale processo si chiama “backtracking”.passo 6. Si torna quindi indietro per operare l’altra scelta al passo 3, os-

sia ignorare il contenuto di [...] (come nella prod. della strin-ga vuota). S’è completato così il lavoro su BC e si torna al non-terminale Input. Ora la grammatica dice che il prossimo carat-tere dev’essere ancora una volta ’c’. Il prossimo carattere ininput è proprio una ’c’, per cui si va avanti.

passo 7. Si constata ora di aver raggiunto con successo la fine dell’ana-

lisi sintattica (fine del non-terminale Input). Ciò significa chesi è riconosciuta correttamente la stringa "abc" in base allagrammatica.

Come indica questo esempio, la soluzione del problema dell’analisi

sintattica in generale potrebbe richiedere molto backtracking e tornare

su precedenti scelte risulta un’attività dispendiosa. Il tempo richiesto di-

pendemolto anche dal modo in cui è definita la grammatica: per lo stesso

linguaggio possono essere proposte molte grammatiche equivalenti.

Ad esempio, la grammatica seguente accelera il parsing dello stesso

linguaggio rispetto alla grammatica data precedentemente:

1 void Input() : {}2 {3 "a" "b" "c" [ "c" ]4 }

Invece la grammatica che segue peggiorerebbe le prestazioni ancora

di più dato che costringe il parser a tornare indietro e ricominciare tutto

daccapo:

4.1. LOOKAHEAD: COS’È, A CHE SERVE [ 41 ]

1 void Input() : {}2 {3 "a" "b" "c" "c"4 |5 "a" "b" "c"6 }

Un’ulteriore grammatica equivalente potrebbe essere la seguente:

1 void Input() : {}2 {3 "a" ( BC1() | BC2() )4 }5

6 void BC1() : {}7 {8 "b" "c" "c"9 }10

11 void BC2() : {}12 {13 "b" "c" [ "c" ]14 }Ma questa grammatica può generare "abcc" in due modi, ed è pertantoconsiderata “ambigua” [1] (oltre al non-determinismo non consentirebbedi assegnare un significato univoco all’albero derivato).

Le prestazioni offerte usando la tecnica del backtracking spesso non

sono accettabili in termine di efficienza in generale ed in particolare per

un parser. Pertanto la maggior parte dei parser non adotta il backtrac-

king in questa o in forma più generale; piuttosto riescono a prendere

decisioni affidabili al prezzo di un limitato quantitativo di informazioni

aggiuntive.

I parser generati da JavaCC prendono le loro decisioni nei punti di

scelta in base all’esplorazione anticipata di token dal flusso di input e,

una volta presa la decisione, vi si affidano completamente senza che ci

sia più bisogno di rivederla in backtracking. Il processo di esplorazione

dei token si chiama “looking ahead” nel flusso di caratteri in ingresso, dacui il termine “LOOKAHEAD”.Dato che alcune di queste decisioni possono in assenza di informa-

zione completa (ma JavaCC fornisce degli avvertimenti in tali situazioni,

per cui non ci si deve preoccupare), si deve conoscere qualcosa in più sul

lookahead per far funzionare il parsing correttamente.

I due modi di base per far sì che il parser possa prendere le decisioni

corrette sono i seguenti:

• modificare la grammatica per renderla più semplice ed adatta al

parsing;

• inserire suggerimenti nei punti di scelta più complessi per aiutare il

parser a fare le scelte giuste.

[ 42 ] 4. LOOKAHEAD4.2 PUNTI DI SCELTA NELLE SPECIFICHECi sono quattro tipi diversi di punti di scelta in JavaCC:

• espansione ( exp1 | exp2 | ... ): in tal caso, il parser generatodeve determinare quale unità selezionare tra exp1, exp2, ecc. percontinuare il parsing.

• espansione ( exp )?. in tal caso, il parser deve capire in qualchemodo se convenga scegliere exp o continuare saltando ( exp )?.Nota: ( exp )? si può scrivere anche [ exp ].

• espansione ( exp )*: in questo caso, il parser deve fare la stessacosa del caso precedente; in più, nel caso si scelga di analizzare exp,dopo aver stato completato tale lavoro su exp, la scelta si ripropone.

• espansione ( exp )+: questo caso è simile al precedente conl’obbligatorietà di analizzare exp almeno la prima volta.

Si rammenti che le specifiche di token che compaiono tra parentesi

angolari <...> possono presentare a loro volta punti di scelta. Tali sceltevengono risolte in modo differente (cfr. §2.4.3).

4.3 DETERMINARE LA SCELTA GIUSTAL’algoritmo per determinare la scelta di default richiede di conoscere in

anticipo un token nel flusso in input al parser e lo usa per prendere la

decisione sul punto di scelta. I seguenti esempi descrivono l’algoritmo in

dettaglio.

ESEMPIO: Si consideri la seguente grammatica (Example2.jj):1 void basic_expr() : {}2 {3 <ID> "(" expr() ")" // Scelta 14 | "(" expr() ")" // Scelta 25 | "new" <ID> // Scelta 36 }La procedura di scelta sarebbe la seguente:

i f ( prossimo_token = <ID>) {

adottare Scel ta 1

} else i f ( prossimo_token = "(" ) {adottare Scel ta 2

} else i f ( prossimo_token = "new" ) {adottare Scel ta 3

} else {

fornisc i un messaggio di errore

}

4.3. DETERMINARE LA SCELTA GIUSTA [ 43 ]

Nell’esempio, la grammatica è stata scritta in modo da far prendere la de-

cisione corretta all’algoritmo. Altra cosa da notare è che l’algoritmo lavo-

ra in modo top-down: se si seleziona Scelta 1, le altre scelte non vengonoaffatto considerate. Mentre ciò non rappresenta un problema in questo

esempio (tranne che per le prestazioni), diventerà un particolare impor-

tante allorché casi locali di non-determinismo richiedano l’inserimento

di suggerimenti sul lookahead.

ESEMPIO: Si supponga che la grammatica di cui sopra venga modificatanel modo seguente (Example3.jj):

1 void basic_expr() :2 {}3 {4 <ID> "(" expr() ")" // Scelta 15 | "(" expr() ")" // Scelta 26 | "new" <ID> // Scelta 37 | <ID> "." <ID> // Scelta 48 }In questo caso l’algoritmo di default sceglierebbe sempre Scelta 1 quandoil prossimo token in input sia <ID> e mai Scelta 4 anche se il token dopo<ID> è un ".". Si tornerà sull’argomento in seguito. Si può provare afar girare il parser generato da Example3.jj sull’input "id1.id2". Essosi lamenterà del fatto di incontrare un "." mentre si aspettava un "(".Notare che quando si genera il parser, il sistema fornisce il messaggio

d’avvertimento:

Warning: Choice conflict involving two expansions at line 25,column 3 and line 31, column 3 respectively.A common prefix is: <ID>Consider using a lookahead of 2 for earlier expansion.In sostanza, JavaCC ci dice che ha trovato nella grammatica una situa-

zione che potrebbe indurre l’algoritmo di lookahead di default ad ave-

re uno strano comportamento. Il parser funziona sempre seguendo tale

algoritmo ma non farà quello che ci si attende.

ESEMPIO: Si consideri ora il seguente esempio (Example4.jj):1 void identifier_list() : {}2 {3 <ID> ( "," <ID> )*4 }Si supponga che il primo <ID> sia stato già trovato corrispondere a quantoatteso e che il parser abbia raggiunto il punto di scelta (il costrutto (...)*). Ecco come funzionerebbe l’algoritmo di scelta:while ( prossimo_token = "," ) {sceg l i espansione annidata , costrutto i tera t ivo

consuma i l token

i f ( prossimo_token = <ID>)

[ 44 ] 4. LOOKAHEADconsumalo ,

else

stampa messaggio di errore

}

Si noti che, nell’esempio riportato, l’algoritmo di scelta non guarda oltre

il costrutto (...)* per prendere la sua decisione.ESEMPIO: Si supponga che ci sia un’altra produzione nella grammatica(Example5.jj):

1 void funny_list() : {}2 {3 identifier_list() "," <INT>4 }Quando l’algoritmo di default deve prendere una decisione nel punto ("," <ID> )*, entrerà sempre in (...)* se il prossimo token è un ",".Lo farà anche quando identifier_list fosse chiamato da funny_list eil token dopo "," fosse un <INT>. Intuitivamente, la cosa giusta da farein tale situazione è di saltare il costrutto (...)* e tornare a funny_list.Torneremo su questo più tardi.

Come esempio concreto, si supponga che l’input sia "id1, id2, 5";il parser lamenterà di aver incontrato un 5 mentre s’aspettava un <ID>.Si noti che alla generazione del parser si ottiene un avvertimento come

quello che segue:

Warning: Choice conflict in (...)* construct at line 25, column 8.Expansion nested within construct and expansion followingconstruct have common prefixes, one of which is: ","Consider using a lookahead of 2 or more for nested expansion.In buona sostanza, JavaCC ci dice di aver trovato una situazione nella

grammatica che potrebbe indurre l’algoritmo di lookahead di default a

comportarsi in modo strano. Il parser funzionerebbe ma non farebbe

ancora quello che ci si aspetta.

Sono stati mostrati esempi di due tipi di punti di scelta: exp1|exp2|... e (exp)*. Con gli altri tipi di punti di scelta, (exp)+ e (exp)?, Ja-vaCC si comporta allo stessomodo di (exp)*, per cui non verranno fornitiulteriori esempi d’uso.

4.3.1 SPECIFICHE MULTIPLE DI LOOKAHEAD PER TOKENFinora si è descritto l’algoritmo di default per il lookahead implementato

nei parser generati. Nella maggior parte delle situazioni tale l’algoritmo

lavora bene. In situazioni più particolari, però, JavaCC fornisce messaggi

d’avvertimento (come quelli mostrati in precedenza). Se la specifica non

provoca avvertimenti da parte di JavaCC allora la grammatica è in forma

LL(1). Le grammatiche LL(1) sono quelle trattabili da parser (ricorsivi)

discendenti usando al più un solo token di lookahead.

Quando, invece, si ricevono messaggi d’avvertimento, ci sono due

azioni alternative:

4.3. DETERMINARE LA SCELTA GIUSTA [ 45 ]

ALTERNATIVA 1Si modifica la grammatica in modo da eliminare i messaggi. Ossia, si devecercare di trasformare la grammatica in forma LL(1).

ESEMPIO: L’esempio (Example6.jj) mostra come cambiare la grammati-ca in Example3.jj per renderla LL(1):

1 void basic_expr() : {}2 {3 <ID> ( "(" expr() ")" | "." <ID> )4 | "(" expr() ")"5 | "new" <ID>6 }In tal caso sono state considerate la prima e la quarta parte destra. Si noti

che è stato messo a fattor comune il loro primo token <ID> fuori delle pa-rentesi, lasciando nelle stesse un punto di scelta che può essere risolto co-

noscendo un solo token in anticipo sul flusso di input confrontandolo con"(" e ".". Questo processo di modifica delle grammatiche per renderleLL(1) si chiama fattorizzazione sinistra [1].

ESEMPIO: Di seguito si mostra (Example7.jj) come la specifica inExample5.jj possa essere modificata per arrivare alla forma LL(1):1 void funny_list() : {}2 {3 <ID> "," ( <ID> "," )* <INT>4 }Si noti che questa modifica è in qualche modo più drastica.

ALTERNATIVA 2Si può fornire al parser qualche suggerimento per aiutarlo nelle situa-zioni non-LL(1) che i messaggi di avvertimento portano all’attenzione.Tutti questi suggerimenti comportano il settaggio del valore globale diLOOKAHEAD ad un numero più grande (vedi sotto) oppure l’uso del costruttoLOOKAHEAD(...) per fornire un suggerimento locale.Va presa una decisione progettuale sull’adozione della prima o della

seconda alternativa. Il solo vantaggio della prima alternativa è che si

rende la grammatica più efficiente. I parser generati da JavaCC gestisconoi costrutti LL(1) molto più velocemente degli altri. Tuttavia, il vantaggio

di scegliere l’alternativa 2 è che la grammatica resta più semplice – ancherispetto a sviluppo e manutenzione – spostando l’onere del lavoro sul

progettista più che sul meccanismo automatico.

A volte l’alternativa 2 è l’unica scelta possibile – sopratutto in presenza

di azioni.

[ 46 ] 4. LOOKAHEADESEMPIO: Supponiamo che la specifica di Example3.jj contenga azionicome mostrato di seguito:

1 void basic_expr() : {}2 {3 { initMethodTables(); } <ID> "(" expr() ")"4 | "(" expr() ")" "new" <ID>5 | { initObjectTables(); } <ID> "." <ID>6 }Dato che le azioni sono diverse, la fattorizzazione non può essere operata

e si dovrà procedere nel secondo modo.

4.3.2 LOOKAHEAD GLOBALESi setta la specifica di lookahead globale tramite l’opzione LOOKAHEAD dallalinea di comando oppure all’inizio del file di specifica nella sezione delle

opzioni. Il valore di tale opzione è un intero che corrisponde al numero di

token da considerare in anticipo per prendere decisioni. Come si intuisce,

il valore di default è 1, da cui discende l’algoritmo di lookahead di defaultdescritto fin qui.

Si supponga di impostare il valore a 2. In tal caso l’algoritmo derivanterichiederebbe due token in anticipo (invece di uno) prima di prendere

una decisione. Per cui, ad esempio, nel codice in Example3.jj, la scelta 1sarebbe presa solo se i prossimi due token fossero <ID> e "(", mentre la 4sarebbe presa se essi fossero <ID> e ".". Quindi, il parser funzionerebbein modo appropriato per la grammatica. Analogamente, il problema con

la grammatica in Example5.jj scomparirebbe poiché il parser entrerebbenel costrutto (...)* solo quando i prossimi due token fossero "," e <ID>.Settando il LOOKAHEAD globale a 2, l’algoritmo di parsing essenzialmentediventa utile alla forma LL(2).

Dato che si può settare l’opzione a qualsiasi valore, i parser generati

da JavaCC sono in generale LL(k).

4.3.3 LOOKAHEAD LOCALESi può settare, in alternativa, anche una specifica di lookahead locale che

abbia effetto solo in specifici punti di scelta. In tal modo, la maggior parte

della grammatica rimane LL(1) ed è quindi più efficiente, mentre allo

stesso tempo si raggiunge la flessibilità delle grammatiche LL(k).

ESEMPIO: Ecco come la grammatica in Example3.jj vamodificata con unlookahead locale per sistemare il problema di non-determinismo nella

scelta (Example8.jj):1 void basic_expr() : {}2 {3 LOOKAHEAD(2)4 <ID> "(" expr() ")" // Scelta 15 | "(" expr() ")" // Scelta 26 | "new" <ID> // Scelta 3

4.3. DETERMINARE LA SCELTA GIUSTA [ 47 ]

7 | <ID> "." <ID> // Scelta 48 }Solo la prima scelta (la prima condizione nella traduzione di seguito ri-

portata) viene interessata dalla specifica di lookahead. Tutte le altre

continuano ad usare un singolo token anticipato:

i f ( prossimi 2 token = <ID> e "(" ) {

sceg l i Scel ta 1

} else i f ( prossimo token = "(" ) {sceg l i Scel ta 2

} else i f ( prossimo token = "new" ) {sceg l i Scel ta 3

} else i f ( prossimo token = <ID>) {

sceg l i Scel ta 4

} else {

stampa messaggio d’errore}

ESEMPIO: Analogamente, Example5.jj può essere modificato comeriportato (Example9.jj):

1 void identifier_list() : {}2 {3 <ID> ( LOOKAHEAD(2) "," <ID> )*4 }Si noti che la specifica LOOKAHEAD deve comparire all’interno di (...)* cherappresenta la scelta che si sta facendo. Di seguito si mostra la traduzione

di questo costrutto (assumendo che il primo <ID> sia stato consumato):while ( prossimi 2 token = "," e <ID>) {sceg l i espansione interna , ossia entra nel costrutto

i tera t ivo

consuma i l token ","consuma i l token <ID>

}

Si scoraggia fortemente la modifica del lookahead globale di default. La

maggior parte delle grammatiche è quasi del tutto LL(1), per cui, con-

vertendo il parser risultante dalla grammatica in uno utile alla forma

LL(k) per facilitare semplicemente alcune porzioni della grammatica che

non sono LL(1), si abbasserebbero notevolmente le prestazioni senza un

reale bisogno. Questo non comporterebbe eccessivi problemi solo se la

grammatica ed i file di input sono corti.

Si dovrebbe anche considerare che i messaggi d’avvertimento che Ja-

vaCC stampa a causa di problemi nei punti di scelta (come i due messaggi

mostrati in precedenza) dicono semplicemente che nei punti specificati

la grammatica non può essere LL(1). JavaCC non verifica la correttezza

della specifica locale di lookahead – assume che si sappia quello che si fa

–ma, di fatto, non può davvero verificare tale correttezza come illustrato

nel seguente esempio:

[ 48 ] 4. LOOKAHEADESEMPIO: Ambiguità nelle regole per l’istruzione if (Example10.jj):

1 void IfStm() : {}2 {3 "if" C() S() [ "else" S() ]4 }5

6 void S() : {}7 {8 ...9 |10 IfStm()11 }Questo è un esempio del noto problema dell’else (dangling else problem).Avendo in input un frammento del tipo: "if C1 if C2 S1 else S2", ilcostrutto "else S2" può essere legato ad entrambi i comandi if. L’in-terpretazione standard è che dovrebbe essere legato al comando più in-

terno (quello ad esso più vicino). Succede che l’algoritmo di default, cer-

cando di determinare la scelta giusta, stamperà comunque il seguente

messaggio d’avvertimento:

Warning: Choice conflict in [...] construct at line 25, column 15.Expansion nested within construct and expansion followingconstruct have common prefixes, one of which is: "else"Consider using a lookahead of 2 or more for nested expansion.Per evitare il messaggio, si potrebbe semplicemente dire a JavaCC di

essere consci di quello che si fa, nel modo seguente:

1 void IfStm() : {}2 {3 "if" C() S() [ LOOKAHEAD(1) "else" S() ]4 }Per forzare il controllo di ambiguità del lookahead in tali casi, si imposta

a true l’opzione FORCE_LA_CHECK.

4.4 LOOKAHEAD SINTATTICOSi consideri la seguente produzione estratta dalla grammatica per il

linguaggio Java:

1 void TypeDeclaration() : {}2 {3 ClassDeclaration()4 |5 InterfaceDeclaration()6 }A livello sintattico, ClassDeclaration può cominciare con un numeroqualsiasi di token "abstract", "final" o "public". Mentre il successi-vo controllo semantico produrrà messaggi d’errore causati dall’utilizzo

4.4. LOOKAHEAD SINTATTICO [ 49 ]

multiplo di uno stesso modificatore, questo non accade fino al comple-

tamento del parsing. Analogamente, InterfaceDeclaration può iniziarecon un numero qualunque di "abstract" o "public".Cosa succederebbe se i successivi token nel flusso di input fossero

rappresentati da un gran numero di "abstract" (es. 100) seguiti da "interface"? È chiaro che specificare un numero fissato di lookahead(come in LOOKAHEAD(100) ad esempio) non sarebbe sufficiente. Si puòobiettare che si tratta di una situazione ben strana che non assicura nes-

sun ragionevole messaggio d’errore e che qualche scelta sbagliata può es-

sere lasciata passare in determinate situazioni patologiche. Nondimeno

si supponga di voler essere precisi su tale questione.

La soluzione ideale sarebbe quella di impostare il LOOKAHEAD a∞, cioèrimuovere ogni limite sul numero di token da considerare in anticipo.

Un modo per implementare questa soluzione consiste nell’utilizzare un

intero molto grande (come il massimo intero) come segue:

ESEMPIO:1 void TypeDeclaration() : {}2 {3 LOOKAHEAD(2147483647)4 ClassDeclaration()5 |6 InterfaceDeclaration()7 }

Si può ottenere lo stesso effetto con il “lookahead sintattico”. Nel loo-kahead sintattico, si specifica un’espansione da provare e, se il tentativo

va a buon fine, allora si intraprende la scelta successiva.

ESEMPIO: L’esempio precedente si riscrive con il lookahead sintattico nelseguente modo:

1 void TypeDeclaration() : {}2 {3 LOOKAHEAD(ClassDeclaration())4 ClassDeclaration()5 |6 InterfaceDeclaration()7 }Essenzialmente, quello che significa è sintetizzabile:

i f ( prossimi token tra quel l i del la prima sce l ta ) {

sceg l i ClassDeclaration ( )

} else i f ( prossimo token tra quel l i del la seconda sce l ta ) {

sceg l i InterfaceDeclaration ( )

} else {

stampa un messaggio di errore

}

Il problema con questa specifica di lookahead sintattico è che il calco-

lo del lookahead richiede molto tempo e compie numerosi controlli non

[ 50 ] 4. LOOKAHEADnecessari. In tal caso, il calcolo può fermarsi non appena si incontri il

token "class", ma la specifica forza il calcolo a continuare fino a quan-do si raggiunga la fine della dichiarazione della classe, il che è molto

dispendioso.

Questo problema può essere risolto mettendo una espansione più

breve da testare nella specifica di lookahead sintattico:

ESEMPIO:1 void TypeDeclaration() : {}2 {3 LOOKAHEAD( ( "abstract" | "final" | "public" )* "class" )4 ClassDeclaration()5 |6 InterfaceDeclaration()7 }In sintesi, i passi da fare diventano:

i f ( prossimi token = sequenza di "abstract" , "final" o "public"seguita da "class" ) {

sceg l i ClassDeclaration ( )

} else i f ( prossimo token tra quel l i di InterfaceDeclaration ) {

sceg l i InterfaceDeclaration ( )

} else {

stampa un messaggio di errore

}

Facendo ciò, si fa fermare l’algoritmo di scelta non appena si incontri il

token "class", cioè si prende la decisione il più presto possibile.Si può altresì mettere un limite al numero di token da consumare nel

lookahead sintattico.

ESEMPIO:1 void TypeDeclaration() : {}2 {3 LOOKAHEAD(10, ( "abstract" | "final" | "public" )* "class" )4 ClassDeclaration()5 |6 InterfaceDeclaration()7 }In questo caso, non si permette all’algoritmo di andare oltre i 10 to-

ken. Se si raggiunge tale limite e si stanno trovando corrispondenze con

l’espressione ("abstract" | "final" | "public" )* "class", allora siseleziona ClassDeclaration.In pratica, quando questo limite non viene specificato, è come se esso

venisse impostato per default al valore dell’intero massimo (2147483647).

4.5. LOOKAHEAD SEMANTICO [ 51 ]

4.5 LOOKAHEAD SEMANTICOTorniamo all’esempio in Example1.jj:

1 void Input() : {}2 {3 "a" BC() "c"4 }5

6 void BC() : {}7 {8 "b" [ "c" ]9 }Supponendo che ci sia una buona ragione per scrivere una specifica in

questo modo (ad esempio a causa delle azioni incorporate). Come notato

in precedenza, la grammatica riconosce le due stringhe "abc" e "abcc".Il problema qui è che l’algoritmo di default per LL(1) sceglie il costrut-

to ["c"] ogni volta che sa di una "c" per cui "abc" non troverà mai unacorrispondenza. Servirebbe specificare che questa scelta dev’essere fat-

ta solo quando il prossimo token è "c" ed il token seguente non è "c".Questa è un’informazione negativa, che non può essere resa attraverso il

lookahead sintattico.

A tale scopo si può usare il lookahead semantico. Con questo tipodi direttiva, si può specificare qualunque espressione booleana la cui

valutazione determini la scelta da fare nel dato punto.

ESEMPIO: L’esempio precedente può essere corredato di una specificasemantica come segue:

1 void BC() : {}2 {3 "b"4 [5 LOOKAHEAD( { getToken(1).kind == C6 && getToken(2).kind != C } ) <C:"c">7 ]8 }Prima di tutto diamo al token "c" l’etichetta C in modo da potercisi rife-rire nella specifica di lookahead semantico. L’espressione booleana es-

senzialmente esprime la proprietà desiderata. La determinazione della

scelta avviene così:

i f ( prossimo token = "c" e successivo token != "c" ) {sceg l i espansione interna , ossia entra nelle quadre

} else {

sa l ta i l costrutto senza entrarvi

}

L’esempio può essere riscritto combinando lookahead sintattico e

semantico come segue:

[ 52 ] 4. LOOKAHEADESEMPIO:

1 void BC() : {}2 {3 "b"4 [ LOOKAHEAD( "c", { getToken(2).kind != C } )5 <C:"c">6 ]7 }Riconosce il primo "c" attraverso il lookahead sintattico e l’assenza delsecondo "c" con il lookahead semantico.

4.6 STRUTTURA GENERALE DELLA DIRETTIVASono stati trattati quasi tutti gli aspetti del lookahead nelle preceden-

ti sezioni. Si prenderanno in considerazione ora un paio di argomenti

avanzati. Si presenterà più formalmente il linguaggio per il lookahead in

JavaCC.

La struttura generale di una specifica di lookahead è data da:

• LOOKAHEAD( numero, espansione, { espressione_booleana } )dove numero specifica il numero di token per il lookahead, espansionespecifica l’espansione da usare per effettuare un lookahead sintattico, eespressione_booleana è l’espressione da usare per il lookahead seman-tico. Almeno uno dei tre argomenti dev’essere presente. Se ce n’è più

d’uno, si separano con delle virgole.

I valori di default per tali argomenti sono definiti come segue:

• numero se è presente anche espansione il default sarà 2147483647altrimenti (è presente espressione_booleana) il default è 0;– quando numero è a 0, non viene effettuato il lookaheadsintattico;

– numero non influenza quello semantico;• espansione: per default, l’espansione presa in considerazione.• espressione_booleana: per default true.

CAPITOLO

5

GESTIONE DEGLI ERRORI

Questo capitolo è dedicato alle componenti messe a disposizione da

JavaCC per la gestione e recupero degli errori.

5.1 INTRODUZIONESi ricorda che le eccezioni in Java sono sottoclassi di Throwable. Esse sidividono in due grandi categorie: errori ed altre eccezioni. Gli errori so-

no situazioni che non ci si aspetta di poter recuperare, come ad esempioThreadDeath o OutOfMemoryError. Essi estendono la superclasse Error enon vanno specificati nella clausola throws delle dichiarazione dei meto-di. Le eccezioni diverse dagli errori sono definite tipicamente estenden-

do la classe Exception. esse sono generalmente gestite dal programma evanno dichiarate nelle clausole throws dell’intestazione dei metodi (nelcaso sia possibile che il metodo lanci la data eccezione).

Per la gestione degli errori, JavaCC introduce due nuove eccezioni:TokenMgrError, ParseException corrispondenti ad eventi che riguardanoproblemi, rispettivamente, di tipo lessicale e sintattico.

Quando il token manager incontra un problema di tipo lessicale, esso

lancia l’eccezione TokenMgrError (con le precedenti versioni veniva stam-pato il messaggio "Lexical Error..." dopo il quale si lanciava comun-que un’eccezione ParseError). Quando il parser incontra un problema,esso lancia l’eccezione ParseException (precedentemente veniva stam-pato il messaggio "Encountered...Was expecting one of..." dopo delquale si lanciava l’eccezione ParseError).Nelle nuove versioni i messaggi d’errore non sono mai stampati espli-

citamente, l’informazione viene conservata nell’oggetto eccezione da

lanciare. Per maggiori dettagli si possono scorrere i file delle classi

[ 53 ]

[ 54 ] 5. GESTIONE DEGLI ERRORIParseException.java e TokenMgrError.java generate da JavaCC insiemeal parser.

Se un’eccezione lanciata non viene catturata e gestita allora ci si affida

all’azione standard della virtual machine che normalmente consiste nellastampa della situazione dello stack e l’invocazione del metodo toString() sull’oggetto eccezione. Se, invece, si cattura l’eccezione, la stampa delmessaggio è a proprio carico.

Si noti che TokenMgrError è sottoclasse di Error, mentreParseException è sottoclasse di Exception. L’idea qui è che non ci

si aspetta che token manager lanci mai una eccezione, per cui bisogna

prestare attenzione alle specifiche dei token in modo da coprire tutti

i casi. Quindi non ci si dovrebbe preoccupare di TokenMgrError: se lespecifiche sono state ben progettate, non dovrebbe mai essere lanciata.

Invece tipicamente si cerca di recuperare le situazioni eccezionali dovute

ad errori del parser.

La sintassi per specificare ulteriori eccezioni lanciabili da parte di me-

todi per non-terminali è identica a quella di Java: "throws...". Ecco unesempio del suo utilizzo:

1 void VariableDeclaration() throws SymbolTableException,IOException :2 {...}3 {4 ...5 }Nell’esempio, VariableDeclaration() può lanciare le eccezioniSymbolTableException e IOException, oltre a ParseException.

5.2 MESSAGGISTICA D’ERRORELo schema di base della messaggistica d’errore (error reporting) prevedela modifica del file ParseException.java per implementare quello chesi vuole. Tipicamente, andrebbe modificato il metodo getMessage() perprodurre la propria messaggistica.

Si possono ricavare tutte l’informazioni riguardo tali metodi dai com-

menti nei file ParseException.java e TokenMgrError.java. Va ancheconsiderata la documentazione Java per la classe Throwable.C’è unmetodo nel parser chiamato generateParseException(). Si può

richiamare tale metodo ogni volta che si voglia generare un oggetto di ti-

po ParseException. Tale oggetto conterrà tutte le scelte tentate dal parserdopo che sia stato consumato con successo l’ultimo token.

5.3 RECUPERO DEGLI ERRORIJavaCC offre due tipi di recupero degli errori (error recovery): il tiposuperficiale e quello profondo.

5.3. RECUPERO DEGLI ERRORI [ 55 ]

• Il recupero superficiale (shallow recovery) entra in azione se nes-suna delle scelte correnti è stata selezionata dall’algoritmo di

selezione;

• il recupero profondo (deep recovery) si presta ai casi in cui sia statopossibile selezionare una scelta, ma si sia verificato un errore ad un

certo punto durante il parsing conseguente a tale scelta.

5.3.1 RECUPERO SUPERFICIALEIl recupero superficiale (o shallow error recovery) può essere illustratoattraverso il seguente esempio:

1 void Stm() : {}2 {3 IfStm()4 |5 WhileStm()6 }Assumendo che IfStm inizi con la parola riservata if e che WhileStm inizicon la parola riservata while, si supponga di voler recuperare gli erroridovuti alla mancata corrispondenza del prossimo token in input con le

possibilità date dai due non-terminali1 (assumendo anche un lookahead

pari a 1), saltando fino al prossimo ";".Per far questo si deve scrivere:

1 void Stm() : {}2 {3 IfStm()4 | WhileStm()5 | error_skipto(SEMICOLON)6 }Ma si deve prima di tutto definire error_skipto. Per JavaCC,error_skipto è semplicemente un altro non-terminale.L’esempio seguente mostra una definizione di error_skipto (usando

una produzione Javacode):

1 JAVACODE2 void error_skipto(int kind) {3 // genera l’oggetto eccezione4 ParseException e = generateParseException();5 // stampa messaggio d’errore6 System.out.println(e.toString());7 Token t;8 do {9 t = getNextToken();10 } while (t.kind != kind);11 }

1Ossia il prossimo token non è né if né while.

[ 56 ] 5. GESTIONE DEGLI ERRORIIl ciclo consuma token fino a uno di tipo kind. Si è scelto un ciclo do-whileperché il token corrente è sempre quello immediatamente precedente a

quello erroneo (nel caso in esame il token immediatamente precedente a

quello che avrebbe dovuto essere if o while).In futuro si prospetta un supporto alla composizione di grammatiche

modulari. In tal caso, si potranno includere routine di recupero erro-

ri in ogni modulo importabile dal file di specifica principale. Per cui è

prevedibile la disponibilità di una libreria di routine di utilità.

5.3.2 RECUPERO IN PROFONDITÀPer illustrare il recupero in profondità (deep error recovery), usiamo lo

stesso esempio conduttore del caso precedente:

1 void Stm() : {}2 {3 IfStm()4 |5 WhileStm()6 }Ora si deve sempre recuperare una situazione d’errore. Tuttavia, si vuole

effettuare il recupero anche a costo che si debba andare più a fondo nel

parsing per ritrovare l’errore.

Ad esempio, si supponga che il prossimo token sia "while" e che quin-di si sia intrapresa la scelta di WhileStm. Ma si supponga anche che du-rante il parsing di WhileStm si incontri un errore, diciamo di avere una

stringa tipo "while(foo { stm; }", ossia manca la parentesi tonda dichiusura. Lo shallow recovery non funzionerebbe in questa situazione.

Serve un recupero che vada a più a fondo. Pertanto, utilizziamo un altro

costrutto in JavaCC, il blocco try-catch-finally.Prima di tutto, riscriviamo l’esempio per il recupero in profondità,

quindi il blocco try-catch-finally verrà spiegato conmaggiore dettaglio:1 void Stm() : {}2 {3 try {4 (5 IfStm()6 |7 WhileStm()8 )9 } catch (ParseException e) {10 error_skipto(SEMICOLON);11 }12 }È tutto quello che serve fare. Se c’è un errore non recuperato nel parsing

di IfStm o WhileStm, entra in azione il blocco catch.Si può avere qualunque numero di blocchi catch ed anche (opzio-

nalmente) un blocco finally (come in Java). In questi blocchi catchva messo codice Java, e non espansioni JavaCC. Ad esempio, la specifica

precedente potrebbe essere riscritta come segue:

5.3. RECUPERO DEGLI ERRORI [ 57 ]

1 void Stm() : {}2 {3 try {4 (5 IfStm()6 |7 WhileStm()8 )9 } catch (ParseException e) {10 System.out.println(e.toString());11 Token t;12 do {13 t = getNextToken();14 } while (t.kind != SEMICOLON);15 }16 }

È buona pratica evitare di inserire troppo codice Java nei blocchicatch e finally dato che questo renderebbe le specifiche meno leggibi-li. È meglio definire metodi che possano essere richiamati dall’interno di

tali blocchi.

Si noti che nella riscrittura dell’esempio precedente, si è essenzial-

mente copiato il codice della implementazione di error_skipto, trala-sciando la prima istruzione – la chiamata a generateParseException.Ciò perché in tal caso il blocco catch lavora già l’eccezione. Tuttaviachiamando tale metodo si otterrebbe un oggetto identico.

[ 58 ] 5. GESTIONE DEGLI ERRORI

CAPITOLO

6

ESEMPI

6.1 FILTROIl problema da risolvere è quello di sostituire certi pattern in ingresso con

un testo diverso. Si supponga che il pattern da cercare siano quello delle

parole alfanumeriche di massimo otto lettere/cifre (ad es. potrebbero es-

sere password contenute in un file) precedute e seguite da due punti, le

parole di lettere maiuscole, i numeri.

Si devono sostituire i pattern in ingresso con un testo variabile a

seconda del pattern.

1 options {2 STATIC = true ;3 }4 PARSER_BEGIN(Filtro)5 import java.io.*;6 import java.util.Arrays;7

8 class Filtro {9 public static void main(String[] args) {10 String in;11 BufferedReader br = new BufferedReader(newInputStreamReader(System.in));12 try {13 System.out.println("immettere riga da filtrare:\n");14 in = br.readLine();15 System.out.println("\n"+sostituzione(in));16 } catch (IOException ioe) {17 System.err.println("IO error");18 System.exit(1);

[ 59 ]

[ 60 ] 6. ESEMPI19 }20

21 Reader sr = new StringReader(in);22 Filtro parser = new Filtro(sr);23 StringBuffer buffer = new StringBuffer();24 try {25 parser.inizio(buffer);26 }27 catch(TokenMgrError e) { throw new IllegalStateException();}28 catch(ParseException e) { throw new IllegalStateException(); }29 return buffer.toString();30 } // main31

32 public static void offusca(StringBuffer b, int n, char c) {33 char[] s = new char[n];34 Arrays.fill(s,c);35 b.append(s);36 } // offusca37 } // classe38 PARSER_END(Filtro)39

40 TOKEN : {41 < NUMERO : ( <CIFRA> )+ >42 | < PAROLA : ( <LETTERA_MAI> )+ >43 | < PASSWORD : <DUEPUNTI>44 ( <MAIUSCOLA> | <MINUSCOLA> | <CIFRA> ){1,8}45 <DUEPUNTI>46 >47 | < #MINUSCOLA : ["a"-"z"] >48 | < #MAIUSCOLA : ["A"-"Z"] >49 | < #CIFRA : ["0"-"9"] >50 | < #DUEPUNTI : ":" >51 | < ALTRO : ~[ ] >52 }53

54 void inizio(StringBuffer buffer) : { Token t; }55 {56 (57 t = <PASSWORD> { offusca(buffer, t.image.length(), ’*’); }58 |59 t = <NUMERO> { offusca(buffer, t.image.length(), ’#’); }60 |61 t = <PAROLA> { offusca(buffer, t.image.length(), ’@’); }62 |63 t = <ALTRO> { buffer.append(t.image); }64 )*65 <EOF>66 }

Nella classe Filtro, la sezione try contenente la chiamata del parserserve a non essere costretti a dichiarare le eccezioni nell’intestazione del

metodo stesso. La ragione è che si vuole che il parser non lanci mai una

6.1. FILTRO [ 61 ]

ParseException (e nemmeno TokenMgrError); ogni sequenza di caratteridovrebbe risultare assolutamente legale.

Vediamo ora nel dettaglio gli aspetti lessicali e sintattici.

PRELIMINARI Preliminarmente viene costruito un BufferedReader perleggere da console una riga (in) che viene passata al parser trasformatain un flusso di caratteri in ingresso (StringReader).Il parser restituisce una stringa offuscata (di tipo StringBuffer) in

uscita che viene stampata.

TOKEN MANAGER La specifica dell’analizzatore lessicale costituisce la

parte cruciale. Si divide il file in token di quattro categorie: numeri, pas-

sword alfanumeriche di max 8 caratteri, parole di lettere maiuscole, e

qualsiasi altro carattere, incluse quelle stringhe non ricomprese nei casi

precedenti. Vi sono anche dei token privati che costituiscono le basi per i

token suddetti.

Si può scrivere un’espressione regolare per la singola lettera (minu-

scola) in molti modi; ad es. con ["a"-"z"]. Per semplicità ci si limita allelettere maiuscole e minuscole. ma si potrebbero includere ad es. quelle

accentate di varie lingue perché trattiamo caratteri Unicode. Maiuscole eminuscole saranno trattati come token privati

1 | < #MINUSCOLA : ["a"-"z"] >2 | < #MAIUSCOLA : ["A"-"Z"] >

Per le cifre altro token privato così come per il carattere dei due punti:

1 | < #CIFRA : ["0"-"9"] >2 | < #DUEPUNTI : ":" >

I primi due token sono semplici:

1 < NUMERO : ( <CIFRA> )+ >2 | < PAROLA : ( <LETTERA_MAI> )+ >

Segue un token più complesso per le password:

1 | < PASSWORD : <DUEPUNTI>2 ( <MAIUSCOLA> | <MINUSCOLA> | <CIFRA> ){1,8}3 <DUEPUNTI> >Le parole di n lettere possono essere specificate facilmente con l’abbre-viazione (x){n} che richiede esattamente n ripetizioni dell’espressioneregolare x. Lo stesso dicasi per i range.Per trovare i token che non fanno parte dei pattern si userà.

1 | < ALTRO : ~[ ]>

[ 62 ] 6. ESEMPIPARSER il parser è molto semplice: effettua una scelta tra le quattro ca-

tegorie di token ammesse, con una traduzione nella stringa in output

che offusca i primi tre tipi di token con chiamate al metodo offusca()con parametri variabili a seconda della lunghezza del token e del carat-

tere di offuscamento. La sequenza viene riconosciuta e filtrata fino al

raggiungimento di EOF.Sia il tokenmanager sia il parser sono “totali”: essi accettano qualsiasi

stringa in ingresso. Dato che il parser accetta qualunque sequenza di

token in ingresso, il parser non potrà mai lanciare una ParseException.

6.2 CONVERTITORE CSV2HTMLSi illustrerà l’idea della traduzione con l’esempio che traduce un file CSV

(Comma Separated Values) in una tabella HTML.

Una tabella CSV è un semplice tipo di struttura dati: tabella di variabili

separate da virgole e ritorni a capo. Un esempio è riportato di seguito:

STUDENT ID , NAME, DATE OF BIRTH

129384 , Davy Jones , 03/04/81

328649 , Clare Manstead , 30/11/81

237090 , Richard Stoppit , 22/06/82

523343 , Brian Hardwick , 15/11/81

908423 , Sal ly Brush , 06/06/81

328453 , El i sa Strudel , 12/09/82

883632 , Peter Smith , 03/05/83

542033 , Ryan Alcot , 04/12/80

Una possibile grammatica dovrebbe prevedere i non-terminali

seguenti:

• file: struttura per l’intero file, composta da una o più linea eterminante con un token EOF;

• linea: struttura fatta da uno o più record. Un token FINELINEA vienegestito dallo scanner;

• record: token RECORD seguito opzionalmente da un token VIRGOLALe relative regole per tali non-terminali sono le seguenti:

file ::= linea ( <FINELINEA> linea)* [<FINELINEA>)] <EOF>linea ::= (record)+record ::= <RECORD> [<VIRGOLA>]Notare che i token a fine-riga (FINELINEA) o fine-file (EOF) non sono seguitida VIRGOLA.Le regole dei pattern per il token manager sono invece le seguenti:

1 SKIP :2 {3 " " | "\t"4 }5

6.2. CONVERTITORE CSV2HTML [ 63 ]

6 TOKEN :7 {8 <VIRGOLA: ",">9 | <RECORD: (~[",","\r","\n"])+ >10 | <FINELINEA: "\r\n" | "\r" | "\n" >11 }

Il main() deve preoccuparsi dei file in ingresso ed uscita (segnalandoerrori) e dell’inizio e fine standard di una pagina HTML da costruire:

1 PARSER_BEGIN(CSV2HTML)2 import java.io.*;3

4 public class CSV2HTML {5 public static void main(String args[]) {6 if(args.length!=2) { errore(); }7 FileInputStream myIn = null;8 PrintStream myOut = null;9 try {10 myIn = new FileInputStream(args[0]);11 myOut = new PrintStream(args[1]);12 } catch(Exception e) {13 System.err.println("errore apertura file.");14 System.exit(0);15 }16

17 String p = "<html>\n <head>\n" +18 "<title>Tabella generata da CSV2HTML </title>\n" +19 " </head>\n <body>\n";20 try {21 CSV2HTML parser = new CSV2HTML(myIn);22 p+= parser.file();23 } catch(ParseException e) {24 System.err.println("errore parsing");25 System.exit(0);26 }27 p += " </body>\n</html>";28 System.out.print("Tabella convertita:\n"+p);29 myOut.print(p); myOut.close();30 } // main31 private static void errore() {32 System.err.println("USO: CSV2HTML inFile outFile");33 System.exit(0);34 } // errore35 } // classe36

37 PARSER_END(CSV2HTML)Le regole per il parser vanno arricchite con azioni che creino le

stringhe utili a riempire la parte centrale del file di output:

1 String file() : { String tab=" <table border=’1’>\n", r; }2 {3 r=riga() <FINELINEA> { tab+=r; }4 ( r=riga() <FINELINEA> { tab+=r; } )*

[ 64 ] 6. ESEMPI5 ( <FINELINEA> )? <EOF>6 { return tab+=" </table>\n"; }7 }8

9 String riga() : { String d, r="\t<tr>\n"; }10 {11 ( d=record() { r+=d; } )+12 { return r+="\t</tr>\n"; }13 }14

15 String record() : { Token t; }16 {17 t=<RECORD> ( <VIRGOLA> )?18 { return "\t\t<td> " + t.image + " </td>\n";}19 }

6.3 CALCOLATRICELa specifica sintattica seguente riguarda una semplice calcolatrice che ac-

cetta dall’input standard espressioni additive e moltiplicative su numeri

reali ottenuti anche attraverso l’applicazione di funzioni:

1 PARSER_BEGIN(Calcolatrice)2 public class Calcolatrice {3 public static void main (String args []) {4 Calcolatrice parser = new Calcolatrice(System.in);5 double v = 0;6 System.out.println("Immettere espressione");7 System.out.print("[op.ammessi:");8 System.out.print("+,-,*,/,abs,exp,log,sin,cos,tan]");9 System.out.print("\n> ");10 try {11 v = parser.start();12 } catch (Exception e) {13 System.err.println("impossibile calcolare il valore.");14 System.exit(1);15 } // catch16 System.out.print("Valore:"+v);17 } // main18 } // class19 PARSER_END(Calcolatrice)20

21 SKIP:22 {23 " " | "\r" | "\t"24 }25

26 TOKEN:27 {28 < EOL: "\n" >29 | < #CIFRA: ["0" - "9"] >30 | < NUMFP:

6.3. CALCOLATRICE [ 65 ]

31 (<CIFRA>)+ "." (<CIFRA>)* (<ESP>)?32 | "." (<CIFRA>)+ (<ESP>)?33 | (<CIFRA>)+ <ESP>34 | (<CIFRA>)+ (<ESP>)?35 >36 | < #ESP: ["e","E"] (["+","-"])? (<CIFRA>)+ >37 }38

39 double start(): { double r; }40 {41 r=espressione() <EOL>42 { return r; }43 }44

45 double espressione(): { double t,r; }46 { // E ::= T RE47 t=termine() r=restoE(t)48 { return r; }49 }50

51 double restoE(double accu): { double t,r; }52 { // RE ::= "+" T RE | "." T RE | epsilon53 "+" t=termine() r=restoE(accu+t)54 { return r; }55 |56 "-" t=termine() r=restoE(accu-t)57 { return r; }58 | // vuota59 { return accu; }60 }61

62 double termine() : { double f,r; }63 { // T ::= F RT64 f=fattore() r=restoT(f)65 { return r; }66 }67

68 double restoT(double accu): { double f,r; }69 { // RE ::= "*" F RT | "/" F RT | epsilon70 "*" f=fattore() r=restoT(accu*f)71 { return r;}72 |73 "/" f=fattore() r=restoT(accu/f)74 { return r; }75 | // vuota76 { return accu; }77 }78

79 double fattore(): {double f; Token t; }80 { // F ::= nfp | "-" F | "fn" F | "(" E ")"81 t=<NUMFP>82 { return Double.parseDouble(t.image); }83 | "-" f=fattore()84 { return -f; }

[ 66 ] 6. ESEMPI85 | "abs" f=fattore()86 { return Math.abs(f); }87 | "exp" f=fattore()88 { return Math.exp(f); }89 | "log" f=fattore()90 { return Math.log(f); }91 | "sin" f=fattore()92 { return Math.sin(f); }93 | "cos" f=fattore()94 { return Math.cos(f); }95 | "tan" f=fattore()96 { return Math.tan(f); }97 | "(" f=espressione() ")"98 { return f; }99 }

Quindi, in tal caso, le azioni associate ai vari costrutti permettono

di aggiungere la semantica attesa ed il parser, oltre ad analizzare leespressioni fornite sarà in grado di restituire il loro risultato.

6.4 MINI LINGUAGGIO ITACostruiamo la grammatica per un linguaggio di programmazione

minimale:

<programma> : : = <blocco>

<blocco> : : = "{" ( <complesso> ) * "}"<complesso> : : = <comando> ";" | <strControllo > | <blocco><comando> : : = < lettura > | <scri t tura > | <assegnazione>

<strControllo > : : = <selezione > | <iterazione >

<assegnazione> : : = <VAR> "=" <espressione ><lettura > : : = "leggi" <VAR><scri t tura > : : = "scrivi" <VAR><selezione > : : = "se" "(" <espressione > ")" <complesso>"altrimenti" <complesso><iterazione > : : = "mentre" "(" <espressione > ")" <complesso><espressione > : : = ( <VAR> | <NUM> ) [ <OP> ( <VAR> | <NUM> ) ]

dove complesso sta per un comando potenzialmente complesso come una

struttura di controllo (strControllo) o un blocco di istruzioni più semplici.

Le espressioni sono volutamente semplificate e mescolano valori boolea-

ni e numerici. I token principali riguarderanno le costanti numeriche, le

parentesi, gli operatori ammessi nelle espressioni, i nomi delle variabili.

Una trasformazione in specifica JavaCC può essere la seguente:

1 options {2 IGNORE_CASE = true;3 STATIC = false;4 }5

6 PARSER_BEGIN(Ita)7 public class Ita {8

6.4. MINI LINGUAGGIO ITA [ 67 ]

9 public static void main(String args[]) {10 System.out.println("immissione da linea di comando:");11

12 Ita parser = new Ita(System.in);13

14 try {15 parser.programma();16 System.out.println("Parsing OK");17 } catch (Exception e) {18 System.err.println("\nERRORE\n"+e);19 } catch (Error e) {20 System.err.println("\nERRORE\n"+e);21 }22 } // main23

24 } // classe25 PARSER_END(Ita)26

27

28 // Spaziatura29

30 SKIP : {31 " " | "\t" | "\n" | "\r"32 }33

34

35 // costanti, operatori, parole chiave, parentesi36

37 TOKEN :38 {39 <#CIFRA: ["0"-"9"]>40 | <#LETTERA: ["A"-"Z"]>41 | <NUM: (<CIFRA>)+ "." (<CIFRA>)* (<ESP>)?42 | "." (<CIFRA>)+ (<ESP>)?43 | (<CIFRA>)+ <ESP>44 | (<CIFRA>)+ (<ESP>)?45 >46 | <#ESP: ["E"] (["+","-"])? (<CIFRA>)+ >47 | <OP: ( "+" | "-" | "*" | "/" | "==" | "<>" | ">=" | "<=" ) >48 | <VAR: "#"<LETTERA> ( <CIFRA> | <LETTERA> )* >49 | <INIZIO : "{" >50 | <FINE : "}" >51 }52

53

54 // SINTASSI55

56 void programma(): {} {57 blocco() <EOF>58 }59

60 void blocco(): {} {61 <INIZIO> ( complesso() )* <FINE>62 }

[ 68 ] 6. ESEMPI63

64 void complesso(): {} {65 comando() ";" | strControllo() | blocco()66 }67

68 void comando(): {} {69 lettura() | scrittura() | assegnazione()70 }71

72 void strControllo(): {} {73 iterazione() | selezione()74 }75

76 void lettura(): {} {77 "leggi" <VAR>78 }79

80 void scrittura(): {} {81 "scrivi" <VAR>82 }83

84 void assegnazione(): {} {85 <VAR> "=" espressione()86 }87

88 void iterazione(): {} {89 "mentre" "(" espressione() ")" complesso()90 }91

92 void selezione(): {} {93 "se" "(" espressione() ")" complesso() "altrimenti" complesso()94 }95

96 void espressione(): {} {97 ( <VAR> | <NUM> ) ( <OP> ( <VAR> | <NUM> ) )?98 }99

100

101 // QUI PER NON INTERFERIRE CON I TOKEN ANONIMI102 TOKEN : { <ERRLEX : ~[] > }

CAPITOLO

7

COSTRUZIONE DI ALBERI

SINTATTICI

7.1 INTRODUZIONEJJTree è un preprocessore per JavaCC che inserisce azioni per la costru-

zione degli alberi di parsing in vari punti del sorgente per JavaCC. L’out-

put di JJTree viene sottoposto a JavaCC per creare il parser. Questo capi-

tolo si propone di descrivere come utilizzare JJTree, e come interfacciare

il proprio parser.

Per default JJTree genera codice per costruire nodi di alberi sintattici

per ogni non-terminale previsto nella grammatica del linguaggio. Questo

comportamento può essere modificato affinché alcuni non-terminali non

richiedano la generazione di nodi, oppure perché si generi un nodo per

una specifica parte dell’espansione di una produzione.

JJTree definisce un’interfaccia Java detta Node implementata da tutti inodi degli alberi sintattici. L’interfaccia fornisce metodi per operazioni

quali l’impostazione del genitore del nodo, l’aggiunta di figli ed il loro

recupero.

JJTree opera in una delle due modalità semplice omultipla:• in modalità semplice ogni nodo è del tipo concreto SimpleNode;• in modalità multipla il tipo del nodo deriva dal nome del nodo.

Se non si forniscono implementazioni per le classi dei nodi, JJTree gene-

rerà implementazioni-standard basate su SimpleNode. Si possono quindimodificare a piacimento tali implementazioni.

[ 69 ]

[ 70 ] 7. COSTRUZIONE DI ALBERI SINTATTICISebbene JavaCC produca parser top-down, JJTree costruisce l’albero

nel verso bottom-up. Per far questo utilizza uno stack dove inserisce

(push) i nodi dopo la loro creazione. Quando si trova il loro genitore, si

possono estrarre (pop) i figli dallo stack ed aggiungere tale genitore all’al-

bero inserendolo anche sullo stack. Lo stack è liberamente utilizzabile da

parte delle azioni nelle grammatiche: si possono inserire o estrarre nodi

oppure effettuare altre operazioni sul contenuto della pila. Si veda §7.2

per altre informazioni in merito.

JJTree fornisce la possibilità di aggiungere decorazioni per due varietàdi base dei nodi e abbreviazioni per facilitarne l’utilizzo:

1. un nodo definito viene ad essere costruito con un numero di fi-gli specificato. Altrettanti nodi sono estratti dallo stack e resi figli

del nuovo nodo, il quale viene a sua volta inserito sullo stack. La

notazione per un nodo siffatto è la seguente:

• #AdefiniteNode(ESPRESSIONE INTERA)L’espressione descrittiva di un nodo definito può essere data da qua-

lunque espressione a valori interi, sebbene molto comunemente si

trovino utilizzate direttamente costanti.

2. un nodo condizionale si costruisce con tutti i figli inseriti sullo stackall’interno del suo ambito di nodo (vedi §7.2) se e solo se la sua con-

dizione risulta vera. Qualora risultasse falsa, il nodo non sarà co-

struito e tutti i figli rimangono sullo stack dei nodi. La notazione

per i nodi condizionali è la seguente:

(a) nodi indefiniti: es. #IndefiniteNode che sta per #IndefiniteNode(true)(b) nodi maggiore-di (greater-than): ad es. #GTNode(>1) che sta per#GTNode(jjtree.arity() > 1)L’abbreviazione dei nodi indefiniti (a) può portare ad ambiguità nel

sorgente per JJTree quando viene seguita da un’espansione tra pa-

rentesi. In tali casi, l’abbreviazione dev’essere sostituita con l’intera

espressone. Ad esempio:(...) #N (a())risulta ambigua; si deve usare la condizione esplicita:(...) #N(true) (a())

Occorre stare attenti al fatto che le espressioni descrittive dei nodi non

dovrebbero avere effetti collaterali. JJTree non assicura che l’espressione

venga valutate per uno specifico numero di volte.

Per default JJTree tratta ogni non-terminale come nodo indefinito e fa

derivare il nome del nodo da quello della sua produzione. Si può anche

assegnare un nome diverso con la sintassi come nell’es. seguente:

• void P1() #MyNode : { ... } { ... }Quando il parser riconosce un non-terminale P1 allora inizializza un no-do indefinito; quindi marca lo stack affinché tutti i nodi creati e inseriti

7.2. AMBITO DEI NODI ED AZIONI UTENTE [ 71 ]

sullo stack da non-terminali nell’espansione di P1 siano estratti e resi figlidel nodo MyNode.Se si volesse evitare la creazione di un nodo per una data produzione

si può usare la notazione dell’es. seguente:

• void P2() #void : { ... } { ... }Qui tutti i nodi dell’albero inseriti da non-terminali nell’espansione di P2rimarranno sullo stack, per essere estratti e resi nodi figli in una produ-

zione successiva (e in posizione superiore) nell’albero. Si può rendere

quest’impostazione il comportamento di default per nodi non decorati

usando l’opzione NODE_DEFAULT_VOID.Vediamo un altro esempio:

Esempio 7.1 (creazione nodi): Sia data la specifica (frammento) se-

guente:

1 void P3() : {}2 {3 P4() ( P5() )+ P6()4 }Qui inizia l’inserimento di un nodo indefinito P3, con la marcatura dellostack, e l’elaborazione di un nodo P4, di uno o più nodi P5 e di un nodoP6. Qualsiasi nodo essi inseriscano sullo stack esso viene estratto e resofiglio di P3.Si può adattare ulteriormente l’albero generato nel seguente modo:

1 void P3() : {}2 {3 P4() ( P5() )+ #ListaDiP5 P6()4 }Ora il nodo P3 avrà come figli un nodo P4, un nodo ListaDiP5 e un nodoP6. Si noti come il costrutto #Nome agisce da operatore postfisso, ossia ilsuo ambito �

7.2 AMBITO DEI NODI ED AZIONI UTENTEAd ogni nodo è associato un ambito comunemente detto anche scope. Leazioni utente in un tale ambito possono accedere al nodo in costruzione

usando l’identificatore speciale jjtThis per riferirsi al nodo. Tale iden-tificatore è dichiarato implicitamente come appartenente al tipo giusto

per il nodo, per cui campi e metodi del nodo possono essere utilizzati

facilmente.

Un ambito è rappresentato dall’unità d’espansione immediatamente

precedente rispetto alla decorazione del nodo. Questa può essere un’e-

spressione tra parentesi. Quando la firma della produzione viene decora-

ta (anche implicitamente col nodo di default), l’ambito è dato dall’intera

parte destra della produzione incluso il blocco delle dichiarazioni.

Si può anche usare un’espressione che coinvolga jjtThis nella partesinistra del riferimento ad un’espansione.

[ 72 ] 7. COSTRUZIONE DI ALBERI SINTATTICIESEMPIO: ... ( jjtThis.my_foo = foo() ) #Baz ...Qui jjtThis si riferisce ad un nodo Baz, che ha un campo chiamatomy_foo. Il risultato del parsing della produzione foo() viene assegnatoa my_foo.L’azione finale nell’ambito d’un nodo è diversa da tutte le altre. Quan-

do il codice relativo viene eseguito, i figli del nodo sono già stati estratti

dallo stack ed aggiunti al nodo, che a sua volta è stato inserto sullo stack.

I figli possono essere manipolati attraverso metodi del nodo padre comejjtGetChild().Azioni utente diverse da quella finale possono manipolare esclusiva-

mente i figli sullo stack. Questi non sono stati aggiunti ancora al nodo,

perciò non sono accessibili tramite i metodi del nodo.

Un nodo condizionale avente un’espressione descrittiva di valore fal-

so non sarà aggiunta allo stack, come pure i suoi figli. L’azione finale nel-

l’ambito di un nodo condizionale può determinare se il nodo è stato crea-

to o meno chiamando i metodo nodeCreated(). Questo restituisce truese la condizione del nodo fosse soddisfatta e il nodo fosse stato creato e

inserito sullo stack, e false altrimenti.

7.3 GESTIONE ECCEZIONIUn’eccezione lanciata da un’espansione all’interno dell’ambito d’influen-

za d’un nodo che non viene gestita nell’ambito viene gestita da JJTree.

Quando ciò succede, i nodi che sono stati inseriti sullo stack nell’ambito

di un nodo sono estratti e scartati. Dopodiché l’eccezione viene rilanciata.

L’intenzione è quella di rendere possibile ai parser di implementare il

recupero degli errori e continuare con lo stack in uno stato noto.

Si deve prestare attenzione al fatto che JJTree in quel momento non

saprebbe determinare se le eccezioni sono state lanciate da azioni utente

nell’ambito di un nodo. Una siffatta eccezione sarebbe probabilmente

gestita in modo non corretto.

7.4 METODI DI SERVIZIO PER LO SCOPE DEI NODISe l’opzione NODE_SCOPE_HOOK viene impostata a true, JJTree genera chia-mate a due metodi definiti dall’utente del parser all’ingresso e all’uscita

dall’ambito di ogni nodo. I metodi devono avere le seguenti intestazioni:

• void jjtreeOpenNodeScope(Node n)• void jjtreeCloseNodeScope(Node n)

Se il parser è stato dichiarato static allora anche questi metodi dovran-no essere dichiarati come static. Entrambi sono invocati con il nodocorrente come parametro. Un loro utilizzo potrebbe essere quello di im-

magazzinare lo stesso oggetto parser nel nodo in modo da fornire lo stato

che dovrebbe essere condiviso da tutti i nodi prodotti dal tale parser.

Esempio 7.2 (symbol table): Ad esempio, il parser potrebbe accedere

ad una symbol table.

7.5. TENER TRACCIA DEI TOKEN [ 73 ]

1 void jjtreeOpenNodeScope(Node n)2 {3 ((SimpleNode)n).jjtSetValue(getSymbolTable());4 }5

6 void jjtreeCloseNodeScope(Node n)7 {8 }dove getSymbolTable() è un metodo definito dall’utente per farsirestituire una struttura symbol table per il nodo. �

7.5 TENER TRACCIA DEI TOKENSpesso è utile tener traccia del primo ed ultimo token di un nodo in modo

da ripristinare facilmente l’input originale.

Settando l’opzione TRACK_TOKENS la classe SimpleNode che vienegenerata conterrà quattro metodi supplementari:

• public Token jjtGetFirstToken()• public void jjtSetFirstToken(Token token)• public Token jjtGetLastToken()• public void jjtSetLastToken(Token token)Per ogni nodo, il primo e l’ultimo token saranno impostati

automaticamente alla partenza del parser.

7.6 CICLO DI VITA DI UN NODOUn nodo passa attraverso una sequenza ben definita di passi alla sua

costruzione. Nella prospettiva del nodo i passi della sequenza sono i

seguenti:

1. viene invocato il costruttore del nodo con un solo parametro intero.

Questo parametro identifica il tipo di nodo ed è utile in modo parti-

colare nella modalità semplice. JJTree genera automaticamente un

file detto parserTreeConstants.java che dichiara le costanti valido.I nomi delle costanti derivano poi facendo precedere il prefisso JJTai nomi inmaiuscolo dei nodi, tramutando i punti (".") in undersco-re ("_"). Per convenienza del programmatore, nello stesso file vienegestito anche un array di variabili String detto jjtNodeName[] chemappa le constanti ai nomi originari non modificati dei nodi.

2. viene invocato il metodo jjtOpen() del nodo.

[ 74 ] 7. COSTRUZIONE DI ALBERI SINTATTICI3. se è stata impostata l’opzione NODE_SCOPE_HOOK, viene invocato ilmetodo del parser definito dall’utente openNodeScope() passando-gli il nodo come parametro. Tale metodo può inizializzare dei cam-

pi del nodo o chiamare i suoi metodi. Ad esempio, potrebbe far

immagazzinare nel nodo il suo primo token.

4. se viene lanciata una eccezione non gestita durante il parsing del

nodo allora il nodo viene abbandonato. JJTree non vi farà mai più

riferimento. Esso non verrà chiuso, né verrà chiamato l’eventua-

le metodo di servizio definito dall’utente closeNodeHook() che ha ilnodo come parametro.

5. altrimenti, se il nodo è condizionale e la sua espressione condizio-

nale ha valore falso il nodo viene parimenti abbandonato. Esso non

viene chiuso ma in tal caso l’eventuale metodo di servizio definito

dall’utente closeNodeHook() potrebbe essere invocata (con il nodocome parametro).

6. altrimenti, tutti i figli del nodo specificati attraverso l’espressione

intera per un nodo definito, o tutti quelli inseriti sullo stack all’inter-

no dello scope di un nodo condizionale, vengono aggiunti al nodo.

L’ordine di tale aggiunta non è specificato.

7. si chiama il metodo jjtClose() del nodo.8. il nodo viene inserito sullo stack.

9. se è impostata l’opzione NODE_SCOPE_HOOK, viene invocato il meto-do definito dall’utente closeNodeScope() cui viene passato il nodocome parametro.

10. se il nodo non è la radice, esso viene aggiunto tra i figli di un altro

nodo e viene invocato il suo metodo jjtSetParent().

7.7 SUPPORTO ALLA VISITAJJTree fornisce un supporto di base alla progettazione della visita. Se è

stata impostata a true l’opzione VISITOR, JJTree inserirà il metodo anj-jtAccept() in tutte le classi di nodo che genera, e genera anche un’inter-faccia per la visita che può essere implementata e passata ai nodi. Il nome

dell’interfaccia si costruisce aggiungendo Visitor al nome del parser.L’interfaccia viene rigenerata ogni volta che si faccia partire JJTree,

in modo da rappresentare accuratamente l’insieme di nodi usati dal

parser. Questo potrebbe ingenerare errori di compilazione se la classe

d’implementazione non viene aggiornata per nuovi nodi.

7.8 OPZIONI PER JJTREEJJTree supporta le seguenti opzioni per la linea di comando o per il

costrutto options di JavaCC:

7.8. OPZIONI PER JJTREE [ 75 ]

• BUILD_NODE_FILES (default: true) Genera implementazioni base perSimpleNode ed ogni alto tipo di nodo usato dalla grammatica.• MULTI (default: false) Genera un albero in modalità multipla. Ildefault fa generare alberi semplici.

• NODE_DEFAULT_VOID (default: false) Invece di fare di ogni

produzione non-decorata un nodo indefinito, lo rende void.• NODE_CLASS (default: "") Se impostata, definisce il nome della classefornita dall’utente che estende SimpleNode. Ogni tipo di nodo creatosarà quindi una sottoclasse di quella indicata con NODE_CLASS.

• NODE_FACTORY (default: "") Specifica una classe contenente unmetodo-factory utile a costruire nodi, con la seguente intestazione:public static Node jjtCreate(int id)Per compatibilità con precedenti versioni, si può anche specifi-

care il valore false, che fa si che SimpleNode venga usato come

class-factory.

• NODE_PACKAGE (default: "") Il package nel quale vengono generate leclassi dei nodi. Il default è il package del parser.

• NODE_EXTENDS (default: "") Deprecata. La superclasse per la classeSimpleNode. Fornendo una superclasse ad hoc, è possibile evitare dieditare il file SimpleNode.java.

• NODE_PREFIX (default: "AST") Prefisso usato per costruire i nomidi classe nodo a partire dagli identificatori dei nodi in modalità

multipla.

• NODE_SCOPE_HOOK (default: false) Inserisce chiamate a metodi delparser definiti dall’utente all’entrata ed all’uscita dallo scope di ogni

nodo. Vedere §7.4.

• NODE_USES_PARSER (default: false) JJTree userà una forma alterna-tiva delle routine di costruzione del nodo nelle quali venga passato

l’oggetto relativo al parser. Ad esempio,public static Node MyNode.jjtCreate(MyParser p, int id);MyNode(MyParser p, int id);• TRACK_TOKENS (default: false) Inserisce in SimpleNode i metodi:

– jjtGetFirstToken(),– jjtSetFirstToken(),– getLastToken(),– jjtSetLastToken()

FirstToken viene automaticamente impostato all’entrata nelloscope di un nodo; analogamente LastToken viene impostato

automaticamente all’uscita.

[ 76 ] 7. COSTRUZIONE DI ALBERI SINTATTICI• STATIC (default: true) Genera codice per un parser static. Tale op-zione va usata coerentemente con le opzioni equivalenti di JavaCC.

Il valore di quest’opzione viene emesso nel sorgente per JavaCC.

• VISITOR (default: false) Inserisce un metodo jjtAccept() nelleclassi nodo e genera una implementazione di Visitor con una entryper ogni tipo di nodo usato dalla grammatica.

• VISITOR_DATA_TYPE (default: "Object") Se l’opzione è impostata,il suo valore viene usato nell’intestazione dei metodi jjtAccept()generati e nei metodi visit() come tipo di argomento.

• VISITOR_RETURN_TYPE (default: "Object") Se l’opzione è impostata,il suo valore viene usato nell’intestazione dei metodi jjtAccept()generati e nei metodi visit() come tipo per il valore restituito datali metodi.

• VISITOR_EXCEPTION (default: "") Se l’opzione è impostata, il suo va-lore viene usato nell’intestazione dei metodi jjtAccept() generati enei metodi visit() come tipo di eccezione lanciata..

• JJTREE_OUTPUT_DIRECTORY (default: si usa il valore diOUTPUT_DIRECTORY) Per default, JJTree generata il suo out-

put nella directory specificata dal valore dell’opzione globaleOUTPUT_DIRECTORY. Impostando esplicitamente questa opzione

permette agli utenti di separare i file per il parser da quelli per la

costruzione degli alberi.

7.9 STATI DI JJTREEJJTree mantiene il suo stato in un campo della classe parser chiamatojjtree. Si possono usare i metodi relativi per manipolare lo stack deinodi.

1 final class JJTreeState {2 /* Chiamata per reinizializzare lo stack. */3 void reset();4 /* Restituisce la radice dell’AST. */5 Node rootNode();6 /* Determina se il nodo corrente sia stato chiuso einserito7 sullo stack */8 boolean nodeCreated();9 /* Restituisce il numero di nodi inseriti sullo stack nello10 scope corrente */11 int arity();12 /* Inserisce un nodo sullo stack */13 void pushNode(Node n);14 /* Restituisce il nodo al top dello stack, rimuovendolodallo15 stesso */16 Node popNode();

7.10. NODI COME OGGETTI [ 77 ]

17 /* Restituisce il nodo al top dello stack */18 Node peekNode();19 }

7.10 NODI COME OGGETTII nodi dell’AST devono implementare l’interfaccia Node. Essa fornisce labase per la costruzione delle relazioni padre-figlio tra i nodi. L’interfaccia

ha la forma seguente:

1 public interface Node {2 /** chiamato dopo che il nodo sia diventato quello corrente.3 Indica che si possono aggiungere ora nodi-figlio . */4 public void jjtOpen();5 /** Chiamato dopo l’aggiunta di figli. */6 public void jjtClose();7 /** Metodi per informare il nodo sul suo padre. */8 public void jjtSetParent(Node n);9 public Node jjtGetParent();10 /** Dice al nodo di aggiungere i suoi argomenti alla lista11 dei figli. */12 public void jjtAddChild(Node n, int i);13 /** Restituisce un nodo figlio. I filgi sono numerati a14 partire da 0, e da sinistra a destra. */15 public Node jjtGetChild(int i);16 /** Restituisce il numero di figli del nodo. */17 int jjtGetNumChildren();18 }La classe SimpleNode implementa l’interfaccia Node e viene generata au-tomaticamente da JJTree qualora non esista ancora. Si può usare tale

classe come template o superclasse per le proprie implementazioni dei

nodi, oppure la si può modificare a piacimento. SimpleNode fornisce inpiù unmeccanismo rudimentale di dumping ricorsivo del nodo e dei suoi

figli. Si può utilizzare questa caratteristica in azioni come:

1 {2 ((SimpleNode)jjtree.rootNode()).dump(">");3 }Il parametro di tipo String in dump() è utilizzato per indicare la gerarchiadell’albero. Un altro metodo d’utilità viene generato se è stata impostata

l’opzione VISITOR:

1 {2 public void childrenAccept(MyParserVisitor visitor);3 }Questo frammento percorre la serie dei nodi-figlio, chiedendo lo-

ro di accettare la visita. Può essere utile quando si implementa

l’attraversamento dell’albero in pre-ordine o in post-ordine.

[ 78 ] 7. COSTRUZIONE DI ALBERI SINTATTICI7.11 ALTRI ESEMPIJJTree viene distribuito con una serie di esempi che contengono una

grammatica per il parsing delle espressioni aritmetiche. Per ulteriori

dettagli si veda il file examples/JJTreeExamples/README.Tra gli esempi c’è anche un interprete per un semplice linguaggio

che usa JJTree per costruire la rappresentazione del programma. Per

ulteriori informazioni, si veda examples/Interpreter/README.Per informazioni su un esempio che usa il supporto alla visita si veda

invece examples/VTransformer/README.

BIBLIOGRAFIA

[1] A.V. Aho, M. Lam, R. Sethi, e J.D. Ullman. Compilers: principles,techniques, and tools. Prentice Hall, 2nd edizione, 1986.[2] Tom Copeland. Generating Parsers with JavaCC. Centennial Books,2007.

[3] Viswanathan Kodaganallur. Incorporating language processing into

java applications: A javacc tutorial. IEEE Software, 21(4):70–77, 2004.[4] J. Levine. Flex & Bison: Text Processing Tools. O’Reilly, 2009.

[ 79 ]

INDICE ANALITICO

#, 22# (nome nodo), 70( ) (esp. BNF), 23, 35* (esp. BNF), 23+ (esp. BNF), 23-, 24: (prod.), 33: (st. lessicale), 21: (token manager), 19: (token), 22< >, 20, 22=, 35? (esp. BNF), 23[ ] (esp. BNF), 35[ ] (ins. caratteri), 23| (esp. BNF), 34| (espr. reg.), 22~, 23ambito, 71

analisi

lessicale, 17

sintattica, 33

azione, 71

lessicale, 18, 26

boiler-plate, 9BUILD_PARSER, 14BUILD_TOKEN_MANAGER, 14CACHE_TOKENS, 15CHOICE_AMBIGUITY_CHECK, 12classe

costanti, 9

parser, 9

token manager, 9closeNodeHook(), 74closeNodeScope(), 74COMMON_TOKEN_ACTION, 15

compiler compiler, 5curLexState, 27DEBUG_LOOKAHEAD, 13DEBUG_PARSER, 12DEBUG_TOKEN_MANAGER, 13deep recovery, [cfr. errori]DEFAULT, 18, 19DFA, 30

EBNF, 7EOF, 19, 22ERROR_REPORTING, 13errori

deep recovery, 56

error reporting, 54

gestione, 53

recupero, 54

shallow recovery, 55

espansione

scelta, 34

espressione regolare

privata, 22

file

custom, 9

prodotti, 9

specifica, 10FORCE_LA_CHECK, 14, 48gestione errori, 53

IGNORE_CASE, 13, 19image, [cfr. Token]image (var.), 26inputStream, 27JAVA_UNICODE_ESCAPE, 9, 13JavaCC, 5

[ 80 ]

INDICE ANALITICO [ 81 ]

parole riservate, [cfr. parole riservate]javacc, comando, 8JAVACODE, 37Javacode, 37jjtClose(), 74jjtGetChild(), 72jjtNodeName[], 73jjtOpen(), 73JJTree, 69

azione, 71

azione finale, 72

eccezioni, 72

nodo, 69jjtSetParent(), 74jjtThis, 71kind, [cfr. Token]lengthOfMatch, 26lessicale

stato, 18LOOKAHEAD, 12, 36, 38, 46lookahead, 7, 39

globale, 46

locale, 46

semantico, 36, 51

sintattico, 36, 48

meta-compilatore, 5MORE, 18, 20NFA, 30Node, 69NODE_DEFAULT_VOID, 71NODE_SCOPE_HOOK, 72, 74nodeCreated(), 72nodo, 69

ambito, 71

condizionale, 70

definito, 70

indefinito, 70

maggiore-di, 70

options, 12opzioni, 12OTHER_AMBIGUITY_CHECK, 12parole riservate, 10ParseError, 53ParseException, 9, 53parsergetNextToken(), 25getToken(), 25PARSER_BEGIN, 10PARSER_END, 10parserTreeConstants, 73produzione

Javacode, 37

punto di scelta, 42( ... )*, 42( ... )+, 42( ... )?, 42

SANITY_CHECK, 14scelta

d’espansione, 34

punto di, 42

sezione

dichiarazioni per token manager, 19

opzioni, 12

shallow recovery, [cfr. errori]SimpleCharStream, 9SimpleNode, 69SKIP, 18, 20SPECIAL_TOKEN, 19, 20STATIC, 12stato lessicale, 18, 20

DEFAULT, 18

struttura

specifica, 10SUPPORT_CLASS_VISIBILITY_PUBLIC, 13SwitchTo(), 27

TOKEN, 18, 20Token, 9, 25beginColumn, 25beginLine, 25endColumn, 25endLine, 25image, 17, 25kind, 17, 25newToken(), 25next, 25specialToken, 25toString(), 25token

classe, 25

espressione regolare, 19

speciale, 25

token manager, 17

dichiarazione, 19TOKEN_EXTENDS, 14TOKEN_FACTORY, 14TOKEN_MANAGER_USES_PARSER, 14TOKEN_MGR_DECLS, 19TokenMgrError, 9, 53TRACK_TOKENS, 73UNICODE_INPUT, 13USER_CHAR_STREAM, 14USER_TOKEN_MANAGER, 13variabile, 26