Manuale Java

73
Manualetto Manualetto JavaCC JavaCC ver. 0. ver. 0.736 736 del del 10-05-12 10-05-12-16.30 16.30 Nicola Fanizzi Nicola Fanizzi

description

Manuale di Java, appunti di Java

Transcript of Manuale Java

  • ManualettoManualetto JavaCCJavaCC

    ver. 0.ver. 0.736736 del del 10-05-1210-05-12--16.3016.30

    Nicola FanizziNicola Fanizzi

  • IndiceIndice[1] Introduzione..................................................................................5

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

    1.2 Linea di Comando........................................................................7

    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............................................................................16

    2.1 L'Analizzatore Lessicale................................................................16

    2.2 Funzionamento del Token Manager...................................................17

    2.3 Dichiarazioni.............................................................................18

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

    2.4.1 Stati Lessicali......................................................................19

    2.4.2 Tipi di Espressioni Regolari......................................................19

    2.4.3 Specifica di Espressioni Regolari................................................19

    2.5 Prefissi Comuni..........................................................................22

    2.6 La Classe dei Token.....................................................................23

    2.7 Azioni Lessicali..........................................................................24

    2.7.1 Variabili............................................................................24

    2.7.2 Esempi..............................................................................26

    2.7.3 Token Speciali e Parser..........................................................27

    2.8 Evoluzione della Classe dei Token....................................................27

    2.9 Analisi Lessicale Efficiente............................................................28

    [3] Analisi Sintattica............................................................................30

    3.1 Produzioni Javacode....................................................................30

    3.2 Produzioni BNF..........................................................................32

    3.2.1 Espansioni BNF....................................................................32

    3.2.2 Lookahead Locale.................................................................33

    [4] Lookahead...................................................................................36

    2

  • 4.1 Lookahead: Cos', a che Serve........................................................36

    4.2 Punti di Scelta nelle Specifiche.......................................................39

    4.3 Determinare la Scelta Giusta..........................................................39

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

    4.3.2 Lookahead Globale...............................................................43

    4.3.3 Lookahead Locale ................................................................43

    4.4 Lookahead Sintattico...................................................................45

    4.5 Lookahead Semantico..................................................................48

    4.6 Struttura Generale di Lookahead.....................................................49

    [4] Gestione degli Errori.......................................................................50

    4.7 Messaggistica d'Errore..................................................................51

    4.8 Recupero degli Errori...................................................................52

    4.8.1 Recupero Superficiale............................................................52

    4.8.2 Recupero in Profondit..........................................................53

    [5] Esempi.......................................................................................55

    5.1 Calcolatrice..............................................................................55

    5.2 Bowdlerizer..............................................................................57

    5.2.1 Il Token Manager..................................................................58

    5.2.2 Sequenze Massimali..............................................................59

    5.2.3 Parsing..............................................................................59

    5.3 CSV2HTML................................................................................60

    [6] Costruzione di alberi sintattici con JJTree.............................................63

    6.1 Introduzione.............................................................................63

    6.2 Ambito dei Nodi ed Azioni Utente....................................................66

    6.3 Gestione Eccezioni......................................................................66

    6.4 Metodi di Servizio per lo Scope dei Nodi............................................67

    6.5 Tener Traccia dei Token................................................................67

    6.6 Ciclo di Vita di un Nodo................................................................67

    6.7 Supporto alla Visita.....................................................................68

    6.8 Opzioni...................................................................................69

    6.9 Stati di JJTree ..........................................................................70

    3

  • 6.10 Nodi come Oggetti....................................................................71

    6.11 Esempi..................................................................................72

    Questo manuale basato sulla documentazione ufficiale di JavaCC.

    Java, JavaCC e JJTree sono marchi registrati.

    4

  • IINTRODUZIONENTRODUZIONE [1] [1]

    [1] [1] INTRODUZIONEINTRODUZIONE

    Un meta-compilatore o generatore di parser un sistema che, a partire dalla specifica di un linguaggio, costruisce un programma (analizzatore) 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 semantico viene lasciato al lavoro (aggiuntivo) del progettista, anche se sono previsti costrutti che permettono di arricchire il parser con azioni legate all'aspetto semantico e scritte nello stesso linguaggio di programmazione del programma generato.

    1.11.1 JavaCCJavaCCQuesto manualetto si propone di illustrare l'utilizzo di JavaCC ("Java Compiler Compiler"), uno strumento open-source per la costruzione automatica di analizzatori lessicali e sintattici in Java. A partire da una specifica formale 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'implementazione dei linguaggi di programmazione - da qui il termine "compilatore di compilatori" - ma trova applicazione anche per linguaggi pi semplici e di tipo diverso (scripting, markup, ecc.). JavaCC non automatizza anche la costruzione esplicita degli alberi sintattici ma

    5

  • 1.11.1 JJAVAAVACCCC

    esistono (almeno) due altri strumenti a corredo di JavaCC che possono essere utilizzati a tale scopo: JJTree e JTB. Risulta facile, inoltre, estendere le specifiche per automatizzare la costruzione delle tabelle dei simboli.

    Sia JavaCC sia i parser generati con questo strumento girano su numerose 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 strumenti come YACC e Bison. Ci consente di trattare un gran numero di grammatiche libere di forma diversa (sebbene la ricorsione sinistra sia vietata). Inoltre i parser discendenti sono pi semplici per quel che riguarda il loro debugging e si prestano all'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 Java, con centinaia di migliaia di download ed una platea stimata di circa qualche decina di migliaia di utenti professionali, come testimoniato anche dal numero dei partecipanti alle varie mailing-list e newsgroup.

    SPECIFICA LESSICALE E SINTATTICA IN UNO STESSO FILE: Le specifiche lessicali in forma di espressioni regolari, stringhe, ecc. e quelle sintattiche (in EBNF) sono scritte insieme in uno stesso file. Ci rende la grammatica di facile lettura (si possono usare espressioni regolari - inline - nella specifica della grammatica) ed anche pi facile di manutenere.

    PREPROCESSORE PER LA COSTRUZIONE DEGLI ALBERI SINTATTICI: 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 caratteri Unicode per il flusso di caratteri in input, il numero di token per il controllo di ambiguit, ecc.

    100% PURO JAVA: JavaCC gira su tutte le piattaforme Java-compliant. Viene utilizzato su tanti tipi di macchine con nessuno sforzo relativo al porting - a testimoniare la filosofia "Write Once, Run Everywhere" di Java.

    GENERAZIONE DI DOCUMENTAZIONE: JavaCC include lo strumento 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 documentazione, costituiscono un valido ausilio all'apprendimento di JavaCC.

    6

  • IINTRODUZIONENTRODUZIONE [1] [1]

    INTERNAZIONALIZZAZIONE: Uno scanner generato da JavaCC pu manipolare input Unicode e le sue specifiche lessicali possono includere qualunque carattere Unicode. Ci facilita la descrizione degli elementi di un linguaggio, come Java, che ammette caratteri Unicode (in numero maggiore rispetto a quelli ASCII).

    SPECIFICHE DI LOOKAHEAD SINTATTICHE E SEMANTICHE: Per default, JavaCC genera un parser LL(1). Tuttavia, ci potrebbero essere molte parti non LL(1) nella grammatica. JavaCC offre le capacit di lookahead sintattico e semantico per risolvere le ambiguit shift-shift1 in modo locale nei punti esatti, ad esempio quando il parser LL(k) solo in certi punti ed LL(1) altrove. I casi di ambiguit shift-reduce2 e reduce-reduce3, tipici dei parser ascendenti, non costituiscono un problema per parser top-down.

    SPECIFICHE IN BNF ESTESA: JavaCC consente le specifiche in EBNF - come (A)*, (A)+, ecc. - nelle regole lessicali e sintattiche. L'uso dell'EBNF solleva, in parte, dalla necessit di usare la ricorsione 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 Lex. 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 lessicale sono ignorati in fase di analisi sintattica, ma possono essere elaborati da altri strumenti. Un'applicazione utile potrebbe essere quella relativa all'elaborazione dei commenti ai fini della documentazione.

    DEBUGGING ESTESO: Attraverso opzioni quali DEBUG_PARSER, DEBUG_LOOKAHEAD, e DEBUG_TOKEN_MANAGER, si pu ottenere una analisi dettagliata del processo di parsing e/o di elaborazione dei token.

    GESTIONE OTTIMALE ERRORI: La gestione degli errori con JavaCC tra le migliori tra i vari generatori automatici di parser. JavaCC genera parser capaci di indicare il punto di errore e fornire informazioni diagnostiche complete.

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

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

    7

  • 1.21.2 LLINEAINEA DIDI C COMANDOOMANDO

    1.21.2 Linea di ComandoLinea di ComandoDigitando semplicemente il comando "javacc" su una console si pu ottenere facilmente un aiuto sulla sintassi corretta per la sua invocazione. Il risultato il seguente:

    % javaccJava Compiler Compiler Version 4.1d1 (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)

    8

  • IINTRODUZIONENTRODUZIONE [1] [1]

    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 (java.lang.Object) TOKEN_FACTORY (java.lang.Object) JDK_VERSION (1.5) GRAMMAR_ENCODING (default file.encoding)

    EXAMPLE: javacc -STATIC=false -LOOKAHEAD:2 -debug_parser mygrammar.jj

    %

    Ogni opzione pu essere impostata sulla linea di comando come mostrato 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 grammatica, impostazione della linea di comando ha la precedenza.

    1.31.3 File Prodotti da JavaCCFile Prodotti da JavaCCJavaCC legge una specifica generalmente contenuta in un file di estensione ".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'analizzatore lessicale (token manager);

    ParseException.java - eccezione che evidenzia un input non conforme alla grammatica del parser;

    file customizzati (nel seguito il prefisso XXX indica un generico prefisso scelto dall'utente):

    XXX.java - la classe del parser;

    XXXTokenManager.java - la classe del token manager;

    XXXConstants.java - interfaccia che associa le classi di token a nomi simbolici.

    9

  • 1.31.3 FFILEILE P PRODOTTIRODOTTI DADA J JAVAAVACCCC

    Altri file possono essere prodotti a seconda delle opzioni contenute nel file di specifica. Ad es., se si usa l'opzione JAVA_UNICODE_ESCAPE allora invece di SimpleCharStream.java sar prodotto JavaCharStream.java. Se si usa l'opzione USER_CHAR_STREAM, allora si produce l'interfaccia CharStream.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 per il 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 richiamare 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; dato che JavaCC non li sovrascrive, si pu star sicuri che i file non saranno modificati tacitamente.

    1.41.4 Struttura di una Specifica JavaCCStruttura 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 valore esadecimale - vengono convertite nel corrispondente carattere Unicode prima dell'elaborazione del file).

    A questa disciplina fanno eccezione gli operatori Java "", ">>>", "=", e ">>>=" che non sono token validi per JavaCC in modo da consentire un uso opportuno di specifiche di token annidate.

    Infine, JavaCC considera riservate le seguenti parole:

    EOF IGNORE_CASE JAVACODE LOOKAHEAD

    MORE PARSER_BEGIN PARSER_END SKIP

    SPECIAL_TOKEN TOKEN TOKEN_MGR_DECLS

    I file di specifica per JavaCC hanno generalmente l'estensione ".jj". Volendo rappresentare formalmente la struttura di un file di specifica nello stesso linguaggio utilizzato da JavaCC, si pu scrivere:

    specifica ::= sezione_opzioni"PARSER_BEGIN" "(" ")"unit_di_compilazione_java"PARSER_END" "(" ")"( produzione )*

    Il file di specifica inizia con una lista di opzioni (facoltativa) che seguita da una unit di compilazione (codice) Java racchiusa tra PARSER_BEGIN(nome) e PARSER_END(nome), dove il nome dato da un identificatore valido. Poi c' una lista di produzioni della grammatica che si chiude con un end-of-file.

    10

  • IINTRODUZIONENTRODUZIONE [1] [1]

    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 generati saranno:

    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:

    options{/* codice per settare i vari flag delle opzioni *//* (questa sezione opzionale) */}

    PARSER_BEGIN(Prova)

    public class Prova {/* Qui definizione metodi aggiuntivi per il parser *//* Pu anche essere lasciato vuoto *//* Pu essere inserito qui il metodo main() */}

    PARSER_END(Prova)

    TOKEN_MGR_DECLS :{/* Dichiarazioni ad uso dello scanner *//* (opzionale, serve per usi speciali) */}

    /* Sezione per le regole dei token ed azioni */

    Tra i costrutti PARSER_BEGIN e PARSER_END si pu inserire un'unit di compilazione Java (ossia l'intero contenuto di un file Java). Essa dovrebbe contenere la dichiarazione di una classe con lo stesso nome utilizzato nelle direttive ("Prova" nell'esempio). PARSER_BEGIN(NOME)...class NOME {...}...PARSER_END(NOME)

    JavaCC non compie controlli particolari su tale unit, per cui possibile 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 incluse 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.

    11

  • 1.41.4 SSTRUTTURATRUTTURA DIDI UNAUNA S SPECIFICAPECIFICA J JAVAAVACCCC

    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 possibile - 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.

    1.4.11.4.1 OOPZIONIPZIONI

    Se 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.

    sezione_opzioni ::= [ "options" "{" ( impostazione )* "}" ]

    Ogni importazione specifica il settaggio di una opzione. Una stessa opzione non pu essere impostata pi volte. Come detto in precedenza, le opzioni possono anche essere impostate sulla riga di comando (queste ultime vengono considerate come impostazioni a maggiore precedenza sulle altre modalit)

    Le impostazioni si scrivono secondo la regola:

    impostazione :: nomeOpzione "=" costante_java ";"

    dove le possibili opzioni sono:

    LOOKAHEAD: Numero di token da considerare in anticipo per prendere 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 vedr, 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'ambiguit di scelte del tipo "A | B | ". Ad esempio, se esistesse un prefisso comune di due token (assumendo l'opzione impostata a 3) JavaCC saprebbe dire se usare un lookahead pari a 3 per la disambiguazione. Inoltre se A e B hanno un prefisso comune di 3 token allora 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 grammatiche (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) rappresenta il numero di token considerati nel controllo di ambiguit di altri tipi di scelte (ad es., della forma "(A)*", "(A)+", e "(A)?"). Ci richiede pi tempo del controllo della scelta pertanto il default viene impostato a 1 piuttosto che a 2.

    12

  • IINTRODUZIONENTRODUZIONE [1] [1]

    STATIC: Opzione booleana (default true). Se posta a true, tutti i metodi e le variabili delle classi parser e token manager sono indicate come static in nel codice generato. ci consente di avere un solo oggetto parser ma questo risulter pi efficiente. Per avere la possibilit di analisi sintattiche diverse tramite lo stesso programma si dovr chiamare il metodo ReInit() per ri-inizializzare il parser quando 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 ottenere informazioni di debug dal parser generato. Posta a true fa s che il parser generi un trace delle proprie azioni. La tracciatura pu essere disabilitata attraverso il metodo disable_tracing() nella classe del parser generato. La si pu riprendere in seguito chiamando enable_tracing().

    DEBUG_LOOKAHEAD: Opzione booleana (default false) che posta a true fa s che il parser generi tutte le informazioni di tracing fornite a causa dell'opzione DEBUG_PARSER ed in pi anche il tracciamento delle azioni eseguite nelle operazioni di lookahead.

    DEBUG_TOKEN_MANAGER: Opzione booleana (default false) usata per ottenere informazione sul debugging dal token manager generato. Settata a true induce il token manager a generare un trace delle proprie 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 false fa s che gli errori di tipo sintattico vengano riportati in minor dettaglio. L'unica ragione per metterla a false l'aumento di efficienza.

    JAVA_UNICODE_ESCAPE: Opzione booleana (default false). Quando settata a true, il parser usa un oggetto inputstream che elabora sequenze di escape di Java Unicode (\u...) prima di mandare i caratteri al token manager. Per default, le sequenze di escape non vengono elaborate. L'opzione viene ignorata se posta a true l'opzione USER_TOKEN_MANAGER, oppure USER_CHAR_STREAM.

    UNICODE_INPUT: Opzione booleana (default false). Quando settata a true, il parser usa un oggetto inputstream che legge file Unicode. Per default, si assume di avere in input file ASCII. L'opzione viene ignorata se posta a true l'opzione USER_TOKEN_MANAGER, oppure USER_CHAR_STREAM.

    IGNORE_CASE: Opzione booleana (default false) che posta a vero induce il token manager ad ignorare la differenza tra maiuscole e minuscole nella specifica dei token e dei file in input. Ci utile nella scrittura di grammatiche per linguaggi come PASCAL e HTML. anche possibile localizzare l'effetto di IGNORE_CASE tramite un meccanismo spiegato nel seguito.

    13

  • 1.41.4 SSTRUTTURATRUTTURA DIDI UNAUNA S SPECIFICAPECIFICA J JAVAAVACCCC

    USER_TOKEN_MANAGER: Opzione booleana (default false) che induce il token manager a lavorare con i token specificati. Se messa a true, il parser accetter token da qualsiasi token manager di tipo TokenManager - un'interfaccia generata nella directory del parser.

    SUPPORT_CLASS_VISIBILITY_PUBLIC: Opzione booleana (default true). Fa generare le classi di supporto (Token, ParseException, ecc.) con visibilit public. Se messa a false, esse saranno private a livello di package.

    USER_CHAR_STREAM: Opzione booleana (default false). l'azione di default di generare un lettore del flusso di caratteri come specificato dalle opzioni JAVA_UNICODE_ESCAPE e UNICODE_INPUT. Il token manager riceve caratteri da tale stream reader. Se viene messa a true, il token manager legger i caratteri da qualunque flusso di caratteri del tipo CharStream. Tale file viene generato nella directory del parser. L'opzione viene ignorata se USER_TOKEN_MANAGER posta a true.

    BUILD_PARSER: Opzione booleana (default true) che induce a generare il file del parser. Se messa a false, il file del parser non viene 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 a far generare il file per il token manager. Se messa a false, il file del token 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) che messa a true, fa includere nel token manager un campo parser che si riferisce all'istanza del parser corrispondente. Lo scopo di un parser in un token manager sta nell'uso di parte della sia logic nelle azioni lessicali. Quest'opzione non ha effetto se STATIC posta a true.

    TOKEN_EXTENDS: Opzione che richiede una stringa (default ""). La classe 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 ""). Essa indica che i Token andranno creati chiamando Token.newToken(). Va settata per indicare una classe Token-factory che contiene un metodo public static Token newToken(int ofKind, String image).

    SANITY_CHECK: Opzione booleana (default true). JavaCC effettua molti controlli sintattici e semantici sul file di specifica durante la generazione del parser. Alcuni rilevamenti, come quello della ricorsione 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

    14

  • IINTRODUZIONENTRODUZIONE [1] [1]

    rilevati per via dell'opzione posta a false) pu causare un comportamento inatteso da parte del parser.

    FORCE_LA_CHECK: Opzione booleana che controlla il rilevamento dell'ambiguit tramite lookahead effettuato da JavaCC. Per default (false), il rilevamento viene effettuato per tutti i punti di scelta dove il lookahead di default pari a 1, mentre non viene effettuato nei punti dove c' un'esplicita specifica di lookahead oppure se l'opzione LOOKAHEAD sia settata ad un valore diverso da 1. Mettendo l'opzione a true si effettuano i controlli in ogni punto a prescindere dalle specifiche di lookahead nel file.

    COMMON_TOKEN_ACTION: Opzione booleana (default false). Quando viene settata a true, ogni chiamata al metodo getNextToken() causa una chiamata ad un metodo CommonTokenAction() definito dall'utente, dopo che il token sia stato accettato dal token manager. L'utente deve definire questo metodo nella sezione TOKEN_MGR_DECLS. La firma del metodo la seguente: void CommonTokenAction(Token t)

    CACHE_TOKENS: Opzione booleana (default false). Quando viene settata a true, il parser effettua il lookahead di token supplementari in anticipo. 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 default la directory corrente. Serve a cambiare la directory ove andranno posti i file generati.

    In maniera forse contro-intuitiva, i nomi delle opzioni non sono case-sensitive.

    1.4.21.4.2 PPRODUZIONIRODUZIONI

    Le produzioni del file di specifica sono di quattro tipi, come evidenziato dalla meta-regola:

    produzione ::= prod_javacode | prod_espr_regolare | prod_bnf | dic_token_manager

    Le produzioni JAVACODE (prod_javacode) e le BNF (prod_bnf) sono usate per definire la grammatica dalla quale si genera il parser. Le produzioni di espressioni regolari (prod_espr_regolare) vengono usate per indicare i token della grammatica dai quali si genera il token manager (assieme alle specifiche di token inserite direttamente nelle regole grammaticali (inline) per il parser). Infine le dichiarazioni per il token manager (dic_token_manager) vengono usate per introdurre dichiarazioni da inserire nel token manager da generare.

    15

  • [2] [2] AANALISINALISI L LESSICALEESSICALE

    [2] [2] ANALISI LESSICALEANALISI LESSICALE

    2.12.1 L'Analizzatore LessicaleL'Analizzatore LessicaleIn un compilatore convenzionale l'analisi lessicale viene svolta da un modulo detto scanner o lexer. JavaCC usa il termine token manager (gestore dei token). Il token manager analizza il flusso di caratteri in input separando spezzoni detti token e assegnando ad ogni token un suo tipo. Ad esempio, consideriamo il seguente frammento di codice:

    int main() {/* programmino */

    return 0; }

    Il token manager potrebbe suddividere la stringa come segue: "int", " ", "main", "(", ")", " ", "{", "\n", "\t", "/* programmino */", "\n", "return", " ", "0", ";", " ", "}" e EOF.

    La spaziatura ed i commenti sono in genere scartati subito, quindi i token veri e propri saranno: "int", "main", "(", ")", "{", "return", "0", ";", "}" e EOF. Ognuno viene classificato in base al tipo. Ad es.: PCINT, ID, PARS, PARD, GRAFS, PCRETURN, COSTINT, PEV, GRAFD. Ogni spezzone di testo viene rappresentato da un oggetto di classe Token dai seguenti attributi:

    .kind: il tipo di token codificato come intero; .image: la stringa estratta dall'input

    16

  • AANALISINALISI L LESSICALEESSICALE [2] [2]

    ed alcuni altri.

    La sequenza di oggetti Token viene prodotta basandosi sulle espressioni regolari nel file .jj. Tale sequenza viene quindi inviata ad un oggetto di tipo Parser per ulteriori elaborazioni.

    2.22.2 Funzionamento del Token ManagerFunzionamento del Token ManagerLa specifica lessicale di JavaCC organizzata in un insieme di stati lessicali. Ogni stato lessicale denominato con un identificatore. C' uno stato standard detto DEFAULT. Il token manager in ogni istante in uno di questi stati. Quando il token manager viene inizializzato, si parte con lo stato DEFAULT. Lo stato iniziale pu essere modificato come parametro nella costruzione dell'oggetto token manager.

    Ogni stato lessicale contiene una lista ordinata di espressioni regolari; l'ordine deriva da quello in cui esse compaiono nella specifica. Ci sono quattro tipi di espressioni regolari: SKIP, MORE, TOKEN, e SPECIAL_TOKEN.

    Tutte le espressioni regolari che occorrono nelle unit di espansione della sintassi (cfr. 3.2.1) sono considerate appartenere allo stato DEFAULT ed il loro ordine di occorrenza dipende dalla loro posizione nel file di specifica.

    La corrispondenza con un token viene trovata come segue: tutte le espressioni regolari nello stato lessicale corrente sono considerate come candidate potenziali. Il token manager consuma il massimo numero di caratteri del flusso di input che corrispondano a quelli previsti dall'espressione. Ossia, il token manager preferisce la corrispondenza pi lunga possibile. Se ci sono diverse possibilit di pari lunghezza, l'espressione regolare trovata quella che viene prima nell'ordine di apparizione nel file di specifica.

    Come detto, il token manager sempre in un unico stato lessicale. In ogni dato momento, il token manager considera esclusivamente le espressioni regolari relative allo stato corrente. Dopo averne trovato uno, si pu specificare un'azione da eseguire ed anche un nuovo stato in cui transitare. 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 corrispondenza con l'espressione viene trovata:

    SKIP semplicemente scarta la stringa trovata (dopo aver eseguito l'eventuale azione lessicale).

    MORE continua portandosi dietro la stringa trovata (eventualmente 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).

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

    17

  • 2.22.2 FFUNZIONAMENTOUNZIONAMENTO DELDEL T TOKENOKEN M MANAGERANAGER

    Quando si riscontra la fine del file, questo causa la creazione del token (a prescindere dallo stato corrente dell'analizzatore lessicale). per, se viene trovato un in mezzo alla corrispondenza con un'espressione regolare, o subito dopo il match con un'espressione regolare MORE, viene riportato un errore.

    Dopo che stata trovata la corrispondenza con un'espressione regolare, l'eventuale azione lessicale viene eseguita. Tutte le variabili e i metodi dichiarati nella sezione TOKEN_MGR_DECLS (cfr. 2.7) sono disponibili per l'uso. In aggiunta, le variabili e i metodi elencati di seguito possono essere utilizzati. Subito dopo, il token manager cambia lo stato se ne specificato uno nuovo. Quindi si intraprende l'azione specificata dal tipo di espressione regolare (SKIP, MORE, ... ). Se il tipo TOKEN, il token trovato viene restituito. Se SPECIAL_TOKEN, il token trovato viene salvato per essere restituito assieme al prossimo token trovato.

    2.32.3 DichiarazioniDichiarazioniRiprendendo il discorso fatto per le produzioni (cfr. 1.4.2) la regola per le dichiarazioni del token manager risulta la seguente:

    dic_token_manager ::= "TOKEN_MGR_DECLS" ":" blocco

    La sezione delle dichiarazioni del token manager inizia con la parola riservata TOKEN_MGR_DECLS seguita da ":" e quindi da un blocco di dichiarazioni e istruzioni in Java (blocco). Tali dichiarazioni ed istruzioni verranno trascritte nel token manager e sono accessibili attraverso le azioni lessicali (descritte nel seguito). In ogni file di specifica ci pu essere una sola sezione delle dichiarazioni.

    2.42.4 Token: Regole per Espressioni RegolariToken: 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 ::= [lista_stati_lessicali]tipo_ER [ "[" "IGNORE_CASE" "]" ] ":"

    "{" specificaER ( "|" specificaER )* "}"

    Una regola per espressioni regolari inizia con la specifica (opzionale) di stati lessicali ai quali si applica (lista_stati_lessicali). Lo stato lessicale standard viene denominato DEFAULT. Qualora non esistano altri stati tutto implicitamente avviene in tale stato. Segue una descrizione del tipo di espressone regolare. Quindi, pu essere presente l'indicazione opzionale IGNORE_CASE ad indicare che non si far differenza tra minuscole e maiuscole nel riconoscimento dell'espressione regolare - stesso effetto dell'opzione IGNORE_CASE, tranne che nella regola si applica localmente anzich globalmente per tutte le espressioni regolari. Segue infine una lista di specifiche di espressioni regolari che descrivono in maggior dettaglio le entit lessicali di questa regola.

    18

  • AANALISINALISI L LESSICALEESSICALE [2] [2]

    2.4.12.4.1 SSTATITATI L LESSICALIESSICALI

    La 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:

    lista_stati_lessicali ::= "" | ""

    Usando la forma "", la regola si applica a tutti gli stati. Altrimenti si applica a tutti gli stati nella lista di identificatori, separati da virgole, posta tra parentesi angolari.

    2.4.22.4.2 TTIPIIPI DIDI E ESPRESSIONISPRESSIONI R REGOLARIEGOLARI

    Per 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 linguaggio. Il token manager crea un oggetto Token per ogni corrispondenza trovata con tale espressione e lo restituir al parser;

    SPECIAL_TOKEN: l'espressione regolare descrive token speciali che sono simili ai token tranne che per il fatto di non avere significato ai fini del parsing - le produzioni BNF li ignorano. I token speciali sono 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 commenti che non hanno significato per il parsing ma servono al file in input;

    SKIP: le corrispondenti espressioni regolari della regola vengono semplicemente saltate (ignorate) dal token manager;

    MORE: A volte utile costruire gradualmente un token da passare al parser. Le corrispondenze con questo tipo di espressioni regolari viene salvata in un buffer fino alla corrispondenza con TOKEN o SPECIAL_TOKEN. Quindi tutte le corrispondenze nel buffer e i TOKEN/SPECIAL_TOKEN finali vengono concatenate per formare un unico TOKEN/SPECIAL_TOKEN che viene passato al parser. Se invece si incontra una corrispondenza con una regola di SKIP il contenuto del buffer viene eliminato.

    2.4.32.4.3 SSPECIFICAPECIFICA DIDI E ESPRESSIONISPRESSIONI R REGOLARIEGOLARI

    La specifica delle espressioni regolari inaugura la sezione dedicata alle entit che fanno parte del lessico. Ogni produzione per un'espressione regolare pu contenere un qualunque numero di specifiche di espressioni regolari. Le specifiche seguono la meta-regola:

    19

  • 2.42.4 TTOKENOKEN: R: REGOLEEGOLE PERPER E ESPRESSIONISPRESSIONI R REGOLARIEGOLARI

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

    Ogni specifica contiene un'espressione regolare, eventualmente seguita da un blocco di istruzioni Java (azione lessicale). Si pu infine indicare uno stato lessicale d'arrivo (separato dai due punti). 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).ER ::= stringa_java | "" | "" | ""

    Le espressioni regolari possono essere inserite in due punti del file della grammatica:

    In una specifica di espressione regolare come parte di una regola di produzione relativa;

    In un'unit d'espansione. In questo caso come se l'espressione regolare fosse definita nella posizione data:

    TOKEN:

    { ER

    }

    e quindi si pu poi farvi riferimento attraverso la sua etichetta (riutilizzo).

    Il primo tipo di espressione regolare quello del letterale-stringa. Il flusso di caratteri in input trova corrispondenza con una simile espressione regolare se il token manager in uno stato lessicale per il quale prevista tale espressione e la prossima stringa di caratteri uguale alla stringa (a volte senza riferimento alla differenza maiuscole/minuscole).

    Una espressione regolare potrebbe di tipo complesso. Questo tipo di espressioni vengono inserite tra parentesi angolari "" ed essere etichettate 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 preceduta da una "#", si tratta di una espressione regolare privata, e si potr usare l'etichetta solo da parte di altre espressioni e non di espansioni.

    Un'espressione regolare pu fare da riferimento ad altre espressioni etichettate nel qual caso viene scritta come l'etichetta racchiusa tra parentesi angolari "".

    Infine, un'espressione regolare pu rappresentare un riferimento all'espressione regolare predefinita che corrisponde alla condizione di fine file.

    Le espressioni regolari private non sono trattate come i token da parte del token manager. Il loro scopo esclusivamente la facilitazione della definizione di altre

    20

  • AANALISINALISI L LESSICALEESSICALE [2] [2]

    espressioni pi complesse. Si consideri ad esempio la seguente definizione dei letterali floating-point in Java:

    TOKEN :{< LETTERALE_FLOATING_POINT:

    (["0"-"9"])+ "." (["0"-"9"])* ()? (["f","F","d","D"])?

    | "." (["0"-"9"])+ ()? (["f","F","d","D"])?| (["0"-"9"])+ (["f","F","d","D"])?| (["0"-"9"])+ ()? ["f","F","d","D"]>| < #ESP: ["e","E"] (["+","-"])? (["0"-"9"])+ >}

    Nell'esempio, il token LETTERALE_FLOATING_POINT definito usando la definizione di un altro token, ESP. Il carattere "#" che precede l'etichetta ESP indica che questa esiste solo allo scopo di definire altri token (LETTERALE_FLOATING_POINT in tal caso). La definizione di LETTERALE_FLOATING_POINT non influenzata dalla presenza o assenza di "#". Tuttavia, ci ha conseguenze per il comportamento del token manager. Se si omette "#", il token manager riconoscer erroneamente stringhe come E123 come token di tipo ESP (anzich come identificatori Java).

    scelte_complesse_ER ::= ER_complessa ( "|" ER_complessa )*

    Le scelte per le espressioni regolari complesse sono fatte da una lista di una o pi espressioni complesse separate da "|". Per la corrispondenza basta il match con una delle espressioni regolari costituenti.

    ER complessa ::= ( unit_ER_complesse )*

    Una espressione regolare complessa data da una sequenza di unit_ER_complessa. Per il match bisogna trovare la corrispondenza multipla di pi unit complesse concatenate.

    Queste unit sono descritte dalla meta-regola:

    unit_ER_complessa ::= stringa| ""| lista_caratteri| "(" scelte_ER_complesse ")" [ "+" | "*" | "?" ]

    Una unit di espressione regolare complessa pu essere un letterale stringa, nel qual caso il token manager deve trovare la corrispondenza esatta con la stringa.

    Una unit di espressione regolare complessa pu essere un riferimento ad un'altra espressione regolare che sar stata etichettata per cui possiamo farvi riferimento. I riferimenti non devono creare cicli nei mutui rapporti di dipendenza tra i token.

    Una unit di espressione regolare complessa pu essere costituita da una lista di caratteri (da intendersi come insieme). La corrispondenza che deve essere trovata con uno dei caratteri consentiti dalla lista.

    21

  • 2.42.4 TTOKENOKEN: R: REGOLEEGOLE PERPER E ESPRESSIONISPRESSIONI R REGOLARIEGOLARI

    Una unit di espressione regolare complessa pu essere data da un insieme di scelte di espressioni complesse poste tra parentesi. In tal caso, la corrispondenza da trovare con una delle scelte. Le scelte tra parentesi possono avere uno dei tre suffissi (opzionali):

    "+": la corrispondenza avviene con una o pi ripetizioni delle espressioni tra parentesi;

    "*": la corrispondenza avviene con zero o pi ripetizioni delle espressioni tra parentesi;

    "?": la corrispondenza avviene con la stringa vuota o con una delle espressioni tra parentesi.

    Si noti che diversamente dalle espansioni BNF, l'espressione regolare "[...]" non equivale a "(...)?". Ci perch si usa il costrutto [...] per descrivere liste di caratteri nelle espressioni regolari.

    Una lista di caratteri descrive un set di caratteri, ed definita attraverso la seguente meta-regola:

    lista_caratteri ::= [ "~" ] "[" [ descrittore_caratteri ( ","

    descrittore_caratteri )* ] "]"

    Essa consiste in una lista di descrittori di caratteri separati da virgole ed includa tra quadre. Ogni descrittore descrive un singolo carattere od un intervallo Se viene anteposto il prefisso "~", l'insieme da intendersi complementato (rispetto all'insieme dei caratteri UNICODE).

    Formalmente il descrittore segue la meta-regola:

    descrittore_caratteri ::= stringa [ "-" stringa ]

    Un descrittore pu essere dato da una stringa di un solo carattere, nel qual caso descrive l'insieme composto da quel solo carattere, oppure da due caratteri separati da un "-", nel qual caso descrive un intervallo che comprende tutti i caratteri, estremi compresi.

    2.52.5 Prefissi ComuniPrefissi 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, allora l' si usa l'espressione regolare che viene prima nel file .jj.

    22

  • AANALISINALISI L LESSICALEESSICALE [2] [2]

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

    TOKEN : { < PLUS : "+" > }TOKEN : { < ASSIGN : "=" > }TOKEN : { < PLASSIGN : "+=" > }

    Si supponga anche che l'input stream cominci con "+=1; ..." .La regola 1 taglia 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 le produzioni di espressioni regolari

    TOKEN : { < KWINT : "int" > }TOKEN : { < IDENT : ["a"-"z","A"-"Z", "_"]

    (["a"-"z","A"-"Z","0"-"9","_"])* > }

    Si supponga anche che l'input stream cominci con "integer i; ", allora la seconda produzione sarebbe preferita per la regola 2. Ma se la parte restante fosse "int i; ...", allora tale regola non sarebbe d'aiuto, dato che entrambe le produzioni avrebbero in comune un prefisso di lunghezza 3. In tal caso la produzione KWINT viene preferita (regola 3) perch viene prima nella specifica.

    2.62.6 La Classe dei TokenLa Classe dei TokenLa classe Token rappresenta il tipo degli oggetti creati dal token manager dopo una scansione dell'ingresso. Tali oggetti sono passati al parser ed anche le azioni grammaticali possono manipolarli. I metodi getToken() e getNextToken() del token manager consentono l'accesso agli oggetti di questa classe.

    Ci sono due classi di token: normali e speciali:

    I token normali sono token che vengono elaborati dal parser.

    I token speciali sono altri token che non hanno rilevanza sintattica 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 rappresentazione interno di JavaCC. Quando i token hanno una etichetta nella specifica per JavaCC, ad esempio , questa viene utilizzata per generare costanti intere (int) che si possono usare nelle azioni. Il valore 0 viene usato sempre per rappresentare il token predefinito. Per convenzione, nel file XXXConstants.jj si genera una costante "EOF".

    int beginLine, beginColumn, endLine, endColumn indicano le posizioni di inizio e fine del token, cos come appare nel flusso d'ingresso.

    23

  • 2.62.6 LLAA C CLASSELASSE DEIDEI T TOKENOKEN

    String image rappresenta l'immagine del token cos come appare nel 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 token dopo di questo, il prende il valore null. La descrizione interna valida solo se il token normale.

    Token specialToken si utilizza per accedere ai token speciali che occorrono 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 token speciale, questo campo si riferisce all'ultimo dei detti token speciali, il qual fa riferimento al precedente, e cos nel seguito fino ad arrivare al primo token speciale, il cui campo campo specialToken null. I successivi campi di token speciali si riferiscono ad altri token speciali che lo seguono immediatamente (senza frapposizione di un token normale). Se tale token non esiste, il campo prende il valore null.

    static final Token newToken(int ofKind) per default, il comportamento consiste nel restituire un nuovo oggetto Token. Se si vogliono far eseguire azioni speciali quando si costruisce un token o si creano ed istanziano sottoclassi della classe Token, si pu ridefinire tale metodo in modo appropriato. L'unica restrizione che questo metodo restituisce un oggetto di tipo Token (o una sottoclasse di Token).

    public final String toString() questo metodo restituisce il valore di image.

    2.72.7 Azioni LessicaliAzioni Lessicali

    2.7.12.7.1 VVARIABILIARIABILI

    Prima di tutto vediamo quali variabili sono utilizzabili nelle azioni lessicali:

    1. StringBuffer image (READ/WRITE): variabile di classe StringBuffer (diversa dal campo "image" dei token) che contiene tutti i caratteri che sono stati ritrovati dopo l'ultimo token di tipo SKIP, TOKEN, o SPECIAL_TOKEN. Si liberi di fare qualunque cambiamento purch non le si assegni un valore nullo (dato che questa variabile viene usata anche dal token manager). Se si fanno cambiamenti ad image, questi si riverberano su tutti le seguenti corrispondenze (se quella corrente con un token MORE). Il contenuto di image non viene assegnato automaticamente al campo image del token trovato. Se si vuole che questo accada, si deve operare l'assegnazione in modo esplicito in un'azione relativa ad un'espressione regolare di tipo TOKEN o SPECIAL_TOKEN. Esempio:

    24

  • AANALISINALISI L LESSICALEESSICALE [2] [2]

    MORE : { "a" : STATO1 }

    MORE :{ "b"{ int l = image.length()-1;^1 image.setCharAt(l,image.charAt(l).toUpperCase()); } ^2 : STATO2}

    TOKEN :{ "cd" { x = image; } : DEFAULT ^3}

    In questo esempio, il valore di image nei tre punti contrassegnati da ^1, ^2, e ^3 sono:

    In ^1: "ab"

    In ^2: "aB"

    In ^3: "aBcd"

    2. int lengthOfMatch (READ ONLY): lunghezza del la stringa corrente di cui stata trovata la corrispondenza (non si cumula con i token MORE). Tale variabile non va modificata. Esempio: usando lo stesso esempio di prima, i valori di "lengthOfMatch" sono:

    In ^1: 1 ( lunghezza di "b")

    In ^2: 1 (non cambia a causa delle azioni lessicali)

    In ^3: 2 (lunghezza di "cd")

    3. int curLexState (READ ONLY): indice dello stato lessicale corrente. Non si dovrebbe modificare la variabile. Le costanti intere corrispondenti agli stati lessicali sono generate nel file XXXConstants.java, per cui ci si pu riferire agli stati senza ricordare il loro valore effettivo.

    4. inputStream (READ ONLY): input stream di tipo appropriato (a scelta tra ASCII_CharStream, ASCII_UCodeESC_CharStream, UCode_CharStream, o UCode_UCodeESC_CharStream a seconda del valore delle opzioni UNICODE_INPUT e JAVA_UNICODE_ESCAPE). Lo stream si trova sempre sull'ultimo carattere consumato per la corrispondenza. Si possono chiamare i metodi previsti per inputStream. Ad esempio, si possono invocare getEndLine e getEndColumn per leggere linea e colonna della corrispondenza trovata. inputStream non pu essere modificato.

    5. Token matchedToken (READ/WRITE): si usa in azioni associate ad espressioni regolari per TOKEN e SPECIAL_TOKEN. Questo deve essere il token

    25

  • 2.72.7 AAZIONIZIONI L LESSICALIESSICALI

    da restituire al parser. Si pu modificare questa variabile facendo quindi restituire qualcos'altro al parser invece del token originale. Qui si pu assegnare il valore della variabile image a matchedToken.image. Questo il moto tipico di far avere effetti all'esterno delle azioni lessicali ai cambiamenti ad image. Esempio: se modifichiamo l'ultima specifica di espressione regolare dell'esempio di cui sopra:

    TOKEN :{ "cd" { matchedToken.image = image.toString(); } : DEFAULT}

    Quindi il token restituito al parser avr il suo campo .image impostato a "aBcd". Se tale assegnazione non fosse effettuata, allora nel campo .image rimarrebbe "abcd".

    6. void SwitchTo(int): metodo che commuta lo stato lessicale corrente in quello indicato. Il metodo pu essere chiamato anche dalle azioni del parser (oltre che da quelle lessicali). Tuttavia, bisogna stare attenti quando lo si invoca dal parser dato che l'analisi lessicale potrebbe essere andata avanti di molti token rispetto al parser in presenza di lookahead lunghi. Quando si usa il metodo in un'azione lessicale, ci si deve assicurare di esso sia l'ultima istruzione eseguita altrimenti si possono verificare comportamenti indesiderati. Se c' un cambiamento di stato gi specificato con la sintassi ": stato", esso prevale su tutte le chiamate a SwitchTo. In generale, si dovrebbe ricorrere alla chiamata di tale metodo solo quando non si pu fare altrimenti. Usando questo metodo di cambiamento di stato si perde un po' di controlli sulla semantica che JavaCC esegue con la sintassi normale.

    2.7.22.7.2 EESEMPISEMPI

    Esempio 1: CommentiEsempio 1: CommentiSKIP :{ "/*" : InCommento}

    SKIP :{ "*/" : DEFAULT}

    MORE :{ }

    26

  • AANALISINALISI L LESSICALEESSICALE [2] [2]

    Esempio 2: Stringhe con azioni per stamparne la lunghezzaEsempio 2: Stringhe con azioni per stamparne la lunghezzaTOKEN_MGR_DECLS :{ int lungStringa;}

    MORE :{ "\"" { lungStringa = 0;} : InStringa}

    TOKEN :{

  • 2.82.8 EEVOLUZIONEVOLUZIONE DELLADELLA C CLASSELASSE DEIDEI T TOKENOKEN

    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 immediatamente il token corrente. Se il token seguente normale, il campo next impostato al valore nullo.

    Questo pu risultare pi chiaro dal seguente esempio. Si supponga di voler stampare tutti i token speciali prima del token "t" (ma solo quelli che seguono il token normale prima di "t"): // ritorno al chiamante: non ci sono token speciali if (t.specialToken == null) return; // torna indietro nella catena di token speciali fino // al primo che segue il token normale precedente Token tmp_t = t.specialToken; while (tmp_t.specialToken != null) tmp_t = tmp_t.specialToken;

    // ciclo che percorre la catena in avanti // stampando i token man mano while (tmp_t != null) { System.out.println(tmp_t.image); tmp_t = tmp_t.next; }

    2.92.9 Analisi Lessicale EfficienteAnalisi Lessicale EfficienteCi sono varie maniere per scrivere la specifica lessicale in una grammatica. Le prestazioni del token manager generato variano in modo significativo a seconda di come la si scrive. Nel seguito sono presentata alcune linee guida:

    Si provi a specificare quante pi stringhe (letterali) sia possibile. Queste vengono riconosciute da un automa a stati finiti deterministico (Deterministic Finite Automata, DFA), che molto pi veloce di quello 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:

    SKIP : { " " | "\t" | "\n" }

    il token manager risulter pi veloce del caso:

    SKIP : { < ([" ", "\t", "\n"])+ > }

    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: MORE : { < ~[] > }

    va meglio della maniera seguente:

    TOKEN : { < (~[])+ > }

    28

  • AANALISINALISI L LESSICALEESSICALE [2] [2]

    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.

    Conviene specificare tutte le stringhe letterali in ordine di lunghezza 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 usare 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 giudizio. La cosa migliore da fare impostare quest'opzione a livello grammaticale. Qualora 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 con alcune espressioni regolari e non per altre.

    Si provi a saltare (sezione token SKIP) il pi possibile, se certi pattern non interessano. Qui, serve un po' di cautela sull'EOF: trovare un EOF dopo un token di tipo SKIP va bene mentre trovare un EOF dopo un token MORE comporta un errore lessicale.

    Evitare di specificare azioni lessicali con specifiche MORE. Generalmente ogni MORE dovrebbe terminare alla fine con un TOKEN (o SPECIAL_TOKEN) per cui si pu compiere un'azione in questo punto a livello di TOKEN, se possibile.

    Evitare anche azioni lessicali e cambi di stato lessicale con le 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. Cos ovviamente, se c' un'azione lessicale o un cambiamento di stato associato con questo, non possibile far cos.

    Evitare di avere una scelta di stringhe letterali per lo stesso token, ad esempio:

    < NONE : "\"none\"" | "\'none\'" >

    Invece, conviene prevedere due diversi tipi di token per questo caso e usare un non-terminale che rappresenta una scelta tra queste possibilit. L'esempio precedente diventa:

    < NONE1 : "\"none\"" > | < NONE2 : "\'none'\" >

    definendo un non-terminale chiamato None() come segue :

    void None() : {} { | }

    Questo rende il riconoscimento molto pi veloce. Notare comunque, che se la scelta tra due complicate espressioni regolari, va bene conservare la scelta.

    29

  • [3] [3] AANALISINALISI S SINTATTICAINTATTICA

    [3] [3] ANALISI SINTATTICAANALISI SINTATTICA

    3.13.1 Produzioni JavacodeProduzioni JavacodeUna regola di produzione Javacode una maniera per scrivere alcune produzioni sotto forma di codice Java invece delle consuete espansioni EBNF (vedere 3.2.1). Ci risulta utile quando si deve riconoscere qualcosa che non esattamente libero da contesto o, per qualsivoglia ragione, non risulti agevola da scrivere in forma grammaticale. La meta-regola relativa alle produzioni Javacode:

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

    Un esempio d'uso di una produzione Javacode viene mostrato di seguito. nell'esempio, il non-terminale "saltaAllaGraffaCorrispondente" consuma token del flusso di input fino alla graffa di chiusura (si assume di aver appena scandito quella d'apertura):

    JAVACODE

    30

  • AANALISINALISI S SINTATTICAINTATTICA [3] [3]

    void saltaAllaGraffaCorrispondente() { Token tok; int annidamento = 1; while (true) { tok = getToken(1); if (tok.kind == GRAFFAS)

    annidamento++; if (tok.kind == GRAFFAD) { annidamento--; if ( annidamento == 0) break; } tok = getNextToken(); } }

    Occorre comunque muoversi con cautela: mentre da un lato tali produzioni sono molto espressive, JavaCC le considera semplicemente come scatole nere (che svolgono in qualche modo sconosciuto un compito 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:

    void NT() : {} { saltaAllaGraffaCorrispondente() | altraProduzione() }

    JavaCC non saprebbe cosa scegliere tra le due possibilit. D'altro canto, se la produzione JAVACODE venisse usata in un punto senza scelta non ci sarebbero problemi, come nel seguente esempio:

    void NT() : {} { "{" saltaAllaGraffaCorrispondente() | "(" listaParametri() ")" }

    Gli usi delle produzioni JAVACODE potrebbero essere preceduti nei punti di scelta anche da direttive LOOKAHEAD sintattiche o semantiche, come mostrato nell'esempio:

    void NT() : {} { LOOKAHEAD( {erroreOccorso}

    saltaAllaGraffaCorrispondente() |

    "(" listaParametri() ")"}

    Il modificatore d'accesso di default per le produzioni JAVACODE privato.

    31

  • 3.23.2 PPRODUZIONIRODUZIONI BNF BNF

    3.23.2 Produzioni BNFProduzioni 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 "("lista_parametri")" ":"blocco "{" scelte_espansione "}"

    Ogni produzione BNF ha una parte sinistra che specifica un non-terminale. 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 convertito esattamente in un metodo nel parser risultante. Il nome del non-terminale il nome del metodo, mentre i parametri 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. La prima sezione 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 processo di parsing, tali dichiarazioni o codice saranno eseguiti. Le dichiarazioni sono visibili da parte del codice di tutte le azioni inserite nelle espansioni BNF. JavaCC non modifica in alcun modo tali dichiarazioni o codice, ricopiando tutto il testo fino alla chiusura del blocco. Pertanto, il compilatore Java potrebbe trovare errori in questa sezione dopo che questa sia stata elaborata da JavaCC. La seconda sezione della parte destra costituita dalle espansioni BNF.

    3.2.13.2.1 EESPANSIONISPANSIONI BNF BNF

    Un'espansione si scrive come sequenza di unit d'espansione:

    espansione ::= ( unit_espansione )*

    L'espansione s'intende interamente analizzata quando lo siano state tutte le sue unit componenti.

    Ad esempio, l'espansione "{" decls() "}" consiste di tre unit - "{", decls() e "}". Una corrispondenza per l'espansione equivale alla concatenazione delle corrispondenze per le singole unit in tal caso, sarebbe costituita da qualunque stringa che inizi con una "{", termini con una "}" e tra queste preveda la corrispondenza con una sotto-stringa riconosciuta da decls().

    In dettaglio un'unit d'espansione ha la forma prescritta dalla meta-regola seguente:

    unit_espansione ::= lookahead_locale | blocco | "(" scelte_espansione ")"

    [ "+" | "*" | "?" ]

    32

  • AANALISINALISI S SINTATTICAINTATTICA [3] [3]

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

    "(" lista_espressioni ")"

    Un'unit pu essere data da una specifica locale di lookahead (cfr. 3.2.2). Questo spiega al parser generato come effettuare le scelte nei punti idonei.

    Un'unit potrebbe essere anche data da un insieme di dichiarazioni Java e codice tra graffe (un blocco). Questa forma si dice anche azione del parser. Essa viene generata nel metodo del non-terminale in punti 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. Pertanto 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 potrebbe essere costituita da un insieme posto tra parentesi di una o pi scelte d'espansione. In tal caso, perch l'unit sia stata correttamente analizzata basta che lo sia stata 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. In tal caso ogni token che corrisponda all'espressione va bene per il parsing. Quando la corrispondenza viene trovata, si crea un oggetto di tipo Token accessibile se assegnato ad una variabile anteponendo all'espressione regolare "id_variabile =". In generale, si pu avere qualunque parte sinistra di assegnazione valida prime di "=". Tale assegnazione non viene attuata durante la valutazione del lookahead.

    Un'unit, infine, potrebbe essere costituita da un non-terminale. In tal caso, prende la forma di chiamata del metodo relativo a quel non-terminale. Se l'analisi del non-terminale va a buon fine lavorando sui i parametri della chiamata viene restituito un valore (a meno che il tipo restituito dal metodo non sia "void"). Il valore restituito pu opzionalmente esser assegnato ad una variabile nel modo visto in precedenza. Anche in tal caso, Tale assegnazione non viene attuata durante la valutazione del lookahead. I non-terminali non possono essere usati in un espansione in modo da introdurre ricorsione-sinistra. JavaCC effettua questo controllo per l'utente.

    3.2.23.2.2 LLOOKAHEADOOKAHEAD L LOCALEOCALE

    Una 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:

    33

  • 3.23.2 PPRODUZIONIRODUZIONI BNF BNF

    lookahead_locale ::= "LOOKAHEAD" "(" [ intero ]

    [ ","[ scelte_espansione ][ "," [ "{"espressione"}" ]")"

    Una specifica di lookahead locale inizia con la parola riservata "LOOKAHEAD" seguita da una serie di vincoli di lookahead tra parentesi tonde. Ci sono tre diversi tipi di vincoli il limite di lookahead (costante intera), lookahead sintattico (scelte d'espansione) e il lookahead semantico (l'espressione 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 usare per la scelta. Questo valore prevale su quello di default specificabile attraverso l'opzione LOOKAHEAD. Il limite di lookahead vale solo per 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 per determinare 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'elaborazione 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 parser 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'espressione false ma la specifica non su un punto di scelta, allora il parsing 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 valutato 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 specifica 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 allora il limite ha per default il massimo intero (2147483647). Questo 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 ne la specifica sintattica (ma solo quella semantica), il limite ha per default 0. ci significa che il lookahead sintattico non viene eseguito ma solo quello semantico.

    34

  • AANALISINALISI S SINTATTICAINTATTICA [3] [3]

    Se il vincolo sintattico non viene fornito, ha per default la scelta per la quale si applica la specifica locale di lookahead. Se tale specifica non presso un punto di scelta, allora il lookahead sintattico viene ignorato - per cui il valore di default non rilevante.

    Se il lookahead semantico non viene fornito, il default pari a "true".

    35

  • [4] [4] LLOOKAHEADOOKAHEAD

    [4] [4] LOOKAHEADLOOKAHEAD

    Questo capitolo si basa sugli esempi della distribuzione ufficiale di JavaCC contenti nella sotto-directory examples/Lookahead della directory degli esempi.

    4.14.1 Lookahead: Cos', a che Serve.Lookahead: Cos', a che Serve.Il lavoro del parser consiste nel leggere da un flusso di caratteri in input e determinare se tale input si conforma alla grammatica del linguaggio specificato.

    Questo lavoro potrebbe essere, nella sua forma pi generale, molto dispendioso. Si consideri l'esempio seguente (Example1.jj): void Input() : {} { "a" BC() "c" }

    void BC() : {} { "b" [ "c" ] }

    In questo semplice esempio, abbastanza chiaro che ci sono esattamente due stringhe che corrispondano alla grammatica, e cio abc e abcc.

    36

  • LLOOKAHEADOOKAHEAD [4] [4]

    La maniera generale per trovare questa corrispondenza quella di muoversi attraverso la grammatica basandosi sulle stringhe, come segue. Nel seguito si user "abc" come stringa di input:

    Passo 1. C' una sola scelta il primo carattere in input dev'essere una 'a' e dato che proprio il nostro caso, si va avanti.

    Passo 2. Si procede col non-terminale BC. Qui, di nuovo, c' una sola possibilit per il prossimo carattere in input dev'essere una 'b'. L'input corrisponde e si va avanti.

    Passo 3. Si ora ad un punto di scelta" nella grammatica. Si pu entrare nel costrutto [...] e trovare la corrispondenza, oppure ignorarlo del tutto. Decidiamo di provare ad entrare. Per cui il prossimo carattere dev'essere una 'c'. Si va avanti.

    Passo 4. Si completato il lavoro con il non-terminale BC e si torna al non-terminale Input. Ora la grammatica dice che il prossimo carattere dev'essere un altro 'c'. Ma non ci sono pi caratteri in input. Pertanto sorge un problema.

    Passo 5. Con un simile problema nel caso generale, si conclude che potrebbe essere stata operata una scelta sbagliata in passato. In questo caso, si sbagliato al Passo 3. Per cui si torna indietro al Passo 3 e si prova a fare una scelta diversa. Tale processo si chiama "backtracking".

    Passo 6. Si torna quindi indietro per operare l'altra scelta al Passo 3 - cio, ignorare il contenuto di [...]. S' completato cos il lavoro su BC e si torna al non-terminale Input. Ora la grammatica dice che il prossimo carattere dev'essere ancora un altra 'c'. Il prossimo carattere in input proprio una 'c', per cui si va avanti.

    Passo 7. Si constata ora di aver raggiunto con successo la fine dell'analisi sintattica (fine del non-terminale Input). Ci significa che si riconosciuta correttamente la stringa "abc" in base alla grammatica.

    Come indica questo esempio, la soluzione del problema dell'analisi sintattica in generale potrebbe richiedere molto backtracking e tornare su vecchie scelte risulta un'attivit dispendiosa. Il tempo richiesto dipende molto 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:

    void Input() : {} { "a" "b" "c" [ "c" ] }

    invece la grammatica che segue peggiorerebbe le prestazioni ancora di pi dato che costringe il parser a tornare indietro e ricominciare tutto daccapo:

    37

  • 4.14.1 LLOOKAHEADOOKAHEAD: C: COSOS'', , AA CHECHE S SERVEERVE..

    void Input() : {} { "a" "b" "c" "c" | "a" "b" "c" }

    Un'ulteriore grammatica equivalente potrebbe essere la seguente:

    void Input() : {} { "a" ( BC1() | BC2() ) }

    void BC1() : {} { "b" "c" "c" }

    void BC2() : {} { "b" "c" [ "c" ] }

    Questa grammatica pu generare "abcc" in due modi, ed pertanto considerata ambigua".

    Le prestazioni offerte dal meccanismo di backtracking non sono accettabili in generale ed in particolare per un parser. Per cui la maggior parte dei parser non adotta il backtracking in questa forma o in generale, ma piuttosto riesce a prendere decisioni affidabili sulla base 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 alcuni token dell'input stream, ed una volta presa la decisione vi si affidano completamente senza che ci sia bisogno di tornarvi sopra in backtracking. Il processo di esplorazione dei token si chiama "looking ahead" nel flusso di caratteri in ingresso da cui il termine "LOOKAHEAD".

    Dato che alcune di queste decisioni possono essere prese con quantitativi di informazioni minori rispetto al caso ideale (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 operare correttamente le decisioni 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.

    38

  • LLOOKAHEADOOKAHEAD [4] [4]

    4.24.2 Punti di Scelta nelle SpecifichePunti di Scelta nelle SpecificheCi sono quattro tipi diversi di punti di scelta in JavaCC:

    1. Un'espansione della forma: ( exp1 | exp2 | ... ). In tal caso, il parser generato deve determinare in qualche quale unit selezionare tra exp1, exp2, ecc. per continuare il parsing.

    2. Un'espansione della forma: ( exp )?. In tal caso, il parser deve capire in qualche modo se convenga scegliere exp o continuare passando oltre ( exp )?. Nota: ( exp )? si pu scrivere anche [ exp ].

    3. Un'espansione della forma: ( exp )*. In questo caso, il parser deve fare la stessa cosa del caso precedente, ed inoltre, nel caso che si scelta di analizzare exp, dopo che sia stato completato tale lavoro su exp, la scelta si ripropone.

    4. Un'espansione della forma: ( exp )+. Questo caso simile al precedente con l'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 scelte vengono risolte in modo differente (cfr. 2.4.3).

    4.34.3 Determinare la Scelta GiustaDeterminare la Scelta GiustaL'algoritmo per determinare la scelta di default richiede di conoscere in anticipo un token nell'input stream e lo usa per prendere la decisione sul punto di scelta. I seguenti esempi descrivono l'algoritmo in dettaglio.

    Si consideri la seguente grammatica (Example2.jj):

    void basic_expr() : {} { "(" expr() ")" // Scelta 1 | "(" expr() ")" // Scelta 2 | "new" // Scelta 3 }

    La procedura di scelta sarebbe la seguente:

    if (prossimo_token ) { adottare Scelta 1 } else if (prossimo_token "(") { adottare Scelta 2 } else if (prossimo_token "new") { adottare Scelta 3 } else { fornisci un messaggio d'errore }

    Nell'esempio, la grammatica stata scritta in modo da far prendere la decisione corretta all'algoritmo. Altra cosa da notare che l'algoritmo lavora in modo top-down

    39

  • 4.34.3 DDETERMINAREETERMINARE LALA S SCELTACELTA G GIUSTAIUSTA

    se si seleziona Scelta 1, le altre scelte non vengono affatto considerate. Mentre questo non rappresenta un problema in questo esempio (tranne che per le prestazioni), diventer un particolare importante quando ambiguit locali richiedano l'inserimento di suggerimenti sul lookahead.

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

    void basic_expr() : {} { "(" expr() ")" // Scelta 1 | "(" expr() ")" // Scelta 2 | "new" // Scelta 3 | "." // Scelta 4 }

    Allora l'algoritmo di default sceglierebbe sempre Scelta 1 quando il prossimo token in input sia e mai Scelta 4 anche se il token dopo un ".". Torneremo sull'argomento in seguito.

    Si pu provare a far girare il parser generato da Example3.jj sull'input "id1.id2". Esso si lamenter del fatto di incontrare un "." quando 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: Consider using a lookahead of 2 for earlier expansion.

    In sostanza, JavaCC ci dice che ha trovato una situazione nella grammatica che potrebbe indurre l'algoritmo di lookahead di default ad uno strano comportamento. Il parser funziona sempre seguendo tale algoritmo ma non far quello che ci si attende.

    Si consideri ora il seguente esempio (Example 4.jj): void identifier_list() : {} { ( "," )* }

    Si supponga che il primo sia stato gi trovato corrispondere a quanto atteso e che il parser abbia raggiunto il punto di scelta (il costrutto (...)*). Ecco come funzionerebbe l'algoritmo di scelta:

    while ( prossimo_token = ",") {scegli l'espansione annidata (ossia, entra nel costrutto (...)* )

    consuma il token if (prossimo_token = )

    consumalo,

    40

  • LLOOKAHEADOOKAHEAD [4] [4]

    else stampa messaggio d'errore

    }

    Si noti che nell'esempio riportato l'algoritmo per la scelta non guarda oltre il costrutto (...)* per prendere la sua decisione. Si supponga che ci sia un altra produzione nella grammatica (Example5.jj): void funny_list() : {} { identifier_list() "," }

    Quando l'algoritmo di default sta prendendo la scelta al punto ( "," )*, entrer sempre in (...)* se il prossimo token un ",". Lo far anche quando identifier_list fosse chiamato da funny_list e il token dopo "," fosse un . Intuitivamente, la cosa giusta da fare in 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 . 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 following construct 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 aspetta che faccia.

    Sono stati mostrati esempi di due tipi di punti di scelta - "exp1 | exp2 | ...", e "(exp)*". Gli altri tipi di punti di scelta - "(exp)+" e "(exp)?" - si comportano allo stesso modo di (exp)* per cui non verranno forniti ulteriori esempi d'uso.

    4.3.14.3.1 SSPECIFICHEPECIFICHE M MULTIPLEULTIPLE DIDI L LOOKAHEADOOKAHEAD PERPER T TOKENOKEN

    Finora si descritto l'algoritmo di default per il lookahead implementato nei parser generati. Nella maggior parte di situazioni l'algoritmo di default lavora bene. In situazioni particolari per, JavaCC fornisce messaggi d'avvertimento come quelli mostrati. Se la specifica non provoca avvertimenti da parte di JavaCC allora 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 si ci sono due alternative:

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

    41

  • 4.34.3 DDETERMINAREETERMINARE LALA S SCELTACELTA G