javaccAnalisi Sintattica
Nicola FanizziCorso di Linguaggi di ProgrammazioneDipartimento di Informatica
Università degli Studi di Bari
15 maggio 2014
Sommario
1 Introduzione
Parsing top-down
ricorsivo
Costruire un Parser
LL(1)
2 Specifica e prodotti
File di specifica
Metodi del parser
Costanti ed Eccezioni
Token, scanner e flusso
di input
Catena dei token
3 Ricorsione e Iterazione
Iterazioni
Esempi
4 Scelta delle produzioni
Lookahead locale
Algoritmo di scelta
Lookahead Sintattico e
Semantico
5 EsempiNL_XlatorBowdCSV2HTMLCalcolatore
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 2 / 85
Introduzione
Sommario
1 Introduzione
Parsing top-down ricorsivo
Costruire un Parser LL(1)
2 Specifica e prodotti
3 Ricorsione e Iterazione
4 Scelta delle produzioni
5 Esempi
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 3 / 85
Introduzione
Parsing I
L’analizzatore sintattico (o parser) verifica se la sequenza di
token in input costituisca un programma corretto:
Definizione (Obiettivo del Parsing)
Determinare se la stringa di token in input può essere generata dauna determinata grammatica libera da contesto
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 4 / 85
Introduzione
Parsing II
Il generatore di parser top-down:
produce codice (Java) che si avvale del token manager
metodo getNextToken()determina se una sequenza di token possa essere generata da
una data grammatica libera da contesto
altrimenti segnala l’errore
grammatiche LL(k)
costruendo l’albero di derivazione a partire dal simbolo inizialefino alle foglie (token)
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 5 / 85
Introduzione Parsing top-down ricorsivo
Parsing top-down ricorsivo
Grammatica con produzioni:S −→ print(E);S −→ while(E) do SS −→ { L }E −→ idE −→ numL−→ S LL−→ ε
Implementazioneper ogni non-terminale della
grammatica, una funzione
ricorsiva:
parseS() terminanormalmente se la stringa
di token successiva nella
sequenza di input può
essere derivata da S
parseE terminanormalmente se la stringa
di token successiva può
essere derivata da E
parseL terminanormalmente se la stringa
di token successiva può
essere derivata da L
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 6 / 85
Introduzione Parsing top-down ricorsivo
Inizializzazione e controllo token
1 Token currentToken = ParseTokenManager.getNextToken();2
3 boolean checkToken(int expectedTokenType) {4 if (currentToken.kind == expectedTokenType) {5 currentToken = ParseTokenManager.getNextToken();6 } else {7 error("Parse error"); }8 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 7 / 85
Introduzione Parsing top-down ricorsivo
Esempio: Parse.java / IS −→ print(E); | while ( E ) do S | { L }
1 void ParseS() {2 switch(currentToken.kind) {3 case ParseConstants.PRINT:4 checkToken(ParseConstants.PRINT);5 checkToken(ParseConstants.LEFT_PARENTHESIS);6 ParseE();7 checkToken(ParseConstants.RIGHT_PARENTHESIS);8 checkToken(ParseConstants.SEMICOLON);9 break;10 case ParseConstants.WHILE:11 checkToken(ParseConstants.WHILE);12 checkToken(ParseConstants.LEFT_PARENTHESIS);13 ParseE();14 checkToken(ParseConstants.RIGHT_PARENTHESIS);15 checkToken(ParseConstants.DO);16 ParseS();17 break;N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 8 / 85
Introduzione Parsing top-down ricorsivo
Esempio: Parse.java / II
18 case ParseConstants.LEFT_BRACE:19 checkToken(ParseConstants.LEFT_BRACE);20 ParseL();21 checkToken(ParseConstants.RIGHT_BRACE);22 break;23 default:24 error("Errore nella derivazione di S"); }25 }26 }
S −→ print(E); | while ( E ) do S | { L }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 9 / 85
Introduzione Parsing top-down ricorsivo
Esempio: Parse.java / IIIE −→ id | num
1 void ParseE() {2 switch(currentToken.kind) {3 case ParseConstants.ID:4 checkToken(ParseConstants.ID);5 break;6 case ParseConstants.NUM:7 checkToken(ParseConstants.NUM);8 break;9 default:10 error("Errore di parsing");11 }12 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 10 / 85
Introduzione Parsing top-down ricorsivo
Esempio: Parse.java / IV
L−→ S L | ε1 void ParseL() {2 switch(currentToken.kind) {3 case RIGHT_BRACE: // simbolo nel FOLLOW4 /* nessuna azione: stringa vuota */5 break;6 default:7 ParseS();8 ParseL();9 }10 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 11 / 85
Introduzione Costruire un Parser LL(1)
Costruire un Parser LL(1)
1 Creare una grammatica EBNF libera per il linguaggio
2 Rimuovere ambiguità, ricorsione sinistra e casi fattorizzabili
(a sinistra)
3 Determinare gli insiemi FIRST e FOLLOW
4 Costruire la tabella di parsing
5 Usare la tabella per creare la suite di funzioni che
implementano il parser
6 Convertire la grammatica in funzioni di parsing
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 12 / 85
Specifica e prodotti
Sommario
1 Introduzione
2 Specifica e prodotti
File di specifica
Metodi del parser
Costanti ed Eccezioni
Token, scanner e flusso di input
Catena dei token
3 Ricorsione e Iterazione
4 Scelta delle produzioni
5 Esempi
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 13 / 85
Specifica e prodotti File di specifica
File di specifica
options{/* codice per settare varie opzioni */}PARSER_BEGIN(NomeParser)public class NomeParser {/* segmento per la classe del parse, anche vuoto */}PARSER_END(NomeParser)TOKEN_MGR_DECLS :{ /* eventuali dichiarazioni usate dal token manager */}/* Espr. regolari per i token & azioni *//* Regole sintattiche & azioni */
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 14 / 85
Specifica e prodotti File di specifica
Regole per il parser I
Forma tipica di una regola grammaticale JavaCC:
void nonTerminalName() : { /* Dichiarazioni Java */ }{ /* Definizione delle regole di produzione */}sezione /*Dichiarazioni Java */ :
anche vuota;
usata tipicamente per inizializzare variabili,
ad es., per la costruzione di un albero di parsing astratto
sezione regole EBNF (parti destre, separate da ”|”)Non-terminali sono seguiti da ”()”corrispondono infatti a metodi JavaTerminali (token) compresi tra parentesi angolari < e >
es. <WHILE>, <STRINGA>, <MINORE_O_UGUALE>possono contenere anche azione sem.: blocco di codice Java
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 15 / 85
Specifica e prodotti File di specifica
Regole per il parser II
Espressioni regolari ammesse:
[e] o (e)? indicano che e è opzionale(e1 | e2 | e3 | ... ) scelta tra e1, e2, e3, ...(e)+ una o più occorrenze di e(e)* zero o più occorrenze di e
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 16 / 85
Specifica e prodotti File di specifica
Regole per il parser III
Esempio
S −→ while(E) SS −→ V = E;Corrispondente rappresentazione JavaCC:
S = statement; E = expression; V = variablevoid statement() : {}{ <WHILE> <LPAREN> expression() <RPAREN> statement()| variable() <GETS> expression() <SEMICOLON>}
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 17 / 85
Specifica e prodotti File di specifica
Linea di comando
Con debugging del parser:
javacc -debug_parser NomeParser.jjjavac NomeParser*.javajava NomeParsersegnala le chiamate dei metodi e l’uscita
Con debugging del token manager:
javacc -debug_token_manager NomeParser.jjjavac NomeParser*.javajava NomeParserproduce molte informazioni diagnostiche ed è tipicamente
usato per osservare il trace, un singolo token per volta
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 18 / 85
Specifica e prodotti File di specifica
File prodotti da JavaCC
Elaborando il file di specifica Parser1.jj, si ottengono i file:Parser1.javaParseException.javaToken.javaParser1Constants.javaParser1TokenManager.javaTokenMgrError.javaSimpleCharStream.java
Parser1.java contiene, nella classe Parser1il codice Java fornito nel blocco PARSER_BEGIN/PARSER_ENDil codice prodotto da JavaCC per la grammatica
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 19 / 85
Specifica e prodotti File di specifica
Esempi semplici I
1 PARSER_BEGIN(Simple1)2 public class Simple1 {3 public static void4 main(String args[]) throws ParseException {5 Simple1 parser = new Simple1(System.in);6 parser.input();7 }8 }9 PARSER_END(Simple1)10
11 void input() :12 {}13 { matchedBraces() ("\n"|"\r")* <EOF> }14
15 void matchedBraces() :16 {}17 { "{" [ matchedBraces() ] "}" }non ammette spazi
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 20 / 85
Specifica e prodotti File di specifica
Esempi semplici II
1 PARSER_BEGIN(Simple2)2 public class Simple2 {3 public static void4 main(String args[])5 throws ParseException {6 Simple2 parser7 = new Simple2(System.in);8 parser.input();9 }10 }11 PARSER_END(Simple2)12
13 SKIP :14 {15 " " | "\t" | "\n" | "\r"16 }
17
18
19 void input() :20 {}21 {22 matchedBraces() <EOF>23 }24
25 void matchedBraces() :26 {}27 {28 "{" [ matchedBraces() ] "}"29 }30
31
32 // fine Simple2
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 21 / 85
Specifica e prodotti File di specifica
Esempi semplici III
1 PARSER_BEGIN(IdList)2
3 /** ID lister. */4 public class IdList {5
6 /** Main entry point. */7 public static void8 main(String args[])9 throws ParseException {10 IdList parser11 = new IdList(System.in);12 parser.Input();13 }14
15 }16
17 PARSER_END(IdList)18
19 SKIP :20 {
21 " "22 | "\t"23 | "\n"24 | "\r"25 }26
27 TOKEN :28 {29 < Id: ["a"-"z","A"-"Z"]30 ( ["a"-"z","A"-"Z","0"-"9"] )*31 >32 }33
34 /** Top level production. */35 void Input() :36 {}37 {38 ( <Id> )+ <EOF>39 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 22 / 85
Specifica e prodotti File di specifica
Esempi semplici IV
1 PARSER_BEGIN(FormaPrefissa)2 public class FormaPrefissa {3 /* segue */4 }5 PARSER_END(FormaPrefissa)6
7 SKIP :8 {9 " " | "\n"10 }11
12 TOKEN :13 {14 < PIU: "+"> | < MENO: "-">15 | < PER: "*"> | < DIVISO: "/">16 | < INTERO: (["0"-"9"])+ >17 }18
19
20 void formula():21 {}22 { espr() <EOF>23 }24
25
26 void espr():27 {}28 {29 (<PIU> | <MENO>30 | <PER> | <DIVISO>)31 espr() espr()32 | <INTERO>33 }34
35
36 // fine FormaPrefissa
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 23 / 85
Specifica e prodotti File di specifica
Esempi semplici V
1 public static void main(String args[]) {2 FormaPrefissa parser;3
4 if (args.length < 1) {5 System.out.print("Uso: java FormaPrefissa <nomefile>");6 return;7 }8 try {9 parser = new FormaPrefissa(new java.io.FileInputStream(args[0]));10 } catch (java.io.FileNotFoundException e) {11 System.out.println("File " + args[0] + " non trovato.");12 return;13 }14 try {15 parser.formula();16 System.out.println("Corretta");17 } catch (ParseException e) {18 System.out.println(e.getMessage());19 System.out.println("Errata");20 }21 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 24 / 85
Specifica e prodotti Metodi del parser
Metodo getToken() I
Parser1.java contiene anche il metodo getToken() che forniscetoken senza fare avanzare l’input
getToken(i) restituisce l’i-esimo token:getToken(1) token correntegetToken(2) token successivo, . . .
L’argomento passato dev’essere un intero non negativo
getToken(0) token precedente
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 25 / 85
Specifica e prodotti Metodi del parser
Metodo getToken() II
Il token restituito da getToken() dipende dal contesto dellachiamata:
1 void printfStatement(): {Token t;} {2 "printf"3 ...4 ")"5 { t=getToken(1);}6 "+"7 }getToken(1) restituisce ")"
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 26 / 85
Specifica e prodotti Costanti ed Eccezioni
Costanti ed Eccezioni
La classe Parser1 implementa l’interfacciaParser1Constants;tutte le costanti sono disponibili al parser
Quando il parser incontra un errore, genera una
ParseException definita nell’omonimo file .java
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 27 / 85
Specifica e prodotti Token, scanner e flusso di input
Token
Token.java contiene i campi dei tokenkind, image, next,beginLine, beginColumn, endLine, endColumncampi addizionali che supportano ulteriori funzionalità
L’array tokenImage fornisce una stringa stampabile per ognitoken
includono i doppi apici per facilitare la stampa di errori
tranne che per <EOF>, <UNSIGNED>, <ID>in una grammatica,
il nome d’un token tra < > denota un oggetto Token;senza, denota il valore del campo kind(o l’indice per tokenImage)
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 28 / 85
Specifica e prodotti Token, scanner e flusso di input
Token manager e stream di input
Il token manager è definito nella classe Parser1TokenManagercontiene il metodo getNextToken()
chiamato dal parser per richiedere un token (oggetto)
in caso di errore, getNextToken() lancia un’eccezioneTokenErrorException, definita in TokenMgrError.java.Si genera anche la classe SimpleCharStreamper il flusso usato dal token manager per l’input di caratteri
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 29 / 85
Specifica e prodotti Catena dei token
Catena dei token
Gli oggetti restituiti al parser dal token manager sono concatenati
attraverso il campo next che contiene un riferimento al prossimotoken:
"a"imagenext
"b" "c"null
Questo permette di scorrere la catena in avanti
Se il parser salva dei riferimenti ai token potrà sempre avervi
accesso più tardi
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 30 / 85
Ricorsione e Iterazione
Sommario
1 Introduzione
2 Specifica e prodotti
3 Ricorsione e Iterazione
Iterazioni
Esempi
4 Scelta delle produzioni
5 Esempi
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 31 / 85
Ricorsione e Iterazione Iterazioni
Iterazioni con * e +Per ripetere un pattern senza usare la ricorsione,
si possono usare operatori ad hoc,
ad es.:
expr−→ term ("+"term)*invece di
expr−→ term termListtermlist−→ "+"term termListtermList−→ ε
Con gli operatori * e + il codice diventa più efficiente delleversioni ricorsive equivalenti
Inoltre, si può usare anche l’operatore ?
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 32 / 85
Ricorsione e Iterazione Esempi
Iterazioni – esempi I
Esempio
1 void expr() : { }2 {3 term()4 termList()5 }6
7 void termList(): {}8 {9 "+"10 term()11 termList()12 |13 {}14 }diventa:
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 33 / 85
Ricorsione e Iterazione Esempi
Iterazioni – esempi II
1 void expr() : {}2 {3 term()4 (5 "+"6 term()7 )*8 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 34 / 85
Ricorsione e Iterazione Esempi
Iterazioni – esempi III
Esempio con addizione e sottrazione
1 void expr() : {}2 {3 term()4 termList()5 }6
7 void termList (): {}8 {9 "+" // addizione10 term ()11 termList ()12 |13 "-" // sottrazione14 term ()15 termList ()16 |17 {}18 }N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 35 / 85
Ricorsione e Iterazione Esempi
Iterazioni – esempi IV
Se si cercasse di semplificare
1 void expr() : {}2 {3 term()4 termList()5 }6
7 void termList (): {}8 {9 "+"10 term ()11 // gen codice per l’addizione12 termList ()13 |14 "-"15 term ()16 // gen codice per la sottrazione17 termList ()18 |19 {}20 }N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 36 / 85
Ricorsione e Iterazione Esempi
Iterazioni – esempi V
1 void expr() : {}2 {3 term()4 (5 ("+"|"-")6 // gen codice ???7 term()8 )*9 }generare codice per somma o differenza? Meglio:
1 void expr() : {Token t;}2 {3 term()4 (5 (t="+"|t="-")6 // gen codice sceglie in base a t7 term ()8 )*9 }e.g. sfruttando kind del token e costanti
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 37 / 85
Scelta delle produzioni
Sommario
1 Introduzione
2 Specifica e prodotti
3 Ricorsione e Iterazione
4 Scelta delle produzioni
Lookahead locale
Algoritmo di scelta
Lookahead Sintattico e Semantico
5 Esempi
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 38 / 85
Scelta delle produzioni
Punti di scelta I
Dato il nonterminale da espandere secondo la propria disciplina
in generale il parser deve scegliere tra più parti destre delle
produzioni del nonterminale,
nei cosiddetti punti di sceltaad ogni punto corrisponde un insieme di scelta contenente i(prefissi di) token generabili a partire da quel punto
se gli insiemi sono disgiunti, la scelta è deterministica
cfr. grammatiche LL(k)
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 39 / 85
Scelta delle produzioni
Punti di scelta II
Si supponga di specificare la grammatica: S −→ bcd | def1 PARSER_BEGIN(G2)2 class G23 {4 }5 PARSER_END(G2)6 void S(): {}7 {8 // qui un punto di scelta9 "b" "c" "d" // ins. di selezione {"b"}10 |11 "d" "e" "f" // ins. di selezione {"d"}12 }Ad un punto di scelta il parser sceglie sulla base del prossimotoken e dell’insieme di selezione per ogni produzione
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 40 / 85
Scelta delle produzioni
Punti di scelta III
Se la grammatica è LL(1), ad ogni punto di scelta, questa è
determinata univocamente dal prossimo token. Altrimenti:
1 void S(): {}2 {3 "b" "c" "d" // ins. di selezione {"b"}4 |5 "b" "e" "f" // ins. di selezione {"b"}6 }stesso insieme di selezione: un token non basta.
Conoscendo in anticipo (look ahead) il token successivo, sipotrebbe determinare l’alternativa corretta.
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 41 / 85
Scelta delle produzioni
Punti di scelta IV
Per default si considera solo il token corrente ad ogni puntodi scelta
In caso di alternative multiple, si sceglie la prima elencataEsempio per la grammatica precedente:
se l’input fosse "b""c""d", il parser sceglierebbe la primastrada e completerebbe il lavoro
anche se fosse "b""e""f", il parser seguirebbe la primastrada, ma poi con "e" sarebbe lanciata un’eccezione
Sebbene la specifica sia problematica,
JavaCC compila comunque un parserma genera anche messaggi di avvertimento del tipo:
Warning: choice conflict...
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 42 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale I
Per ovviare ai casi precedenti, si usa la direttiva LOOKAHEAD1 void S(): {}2 {3 LOOKAHEAD(2) // nel punto di selezione4 "b" "c" "d"5 |6 "b" "e" "f"7 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 43 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale II
Altra variazione
1 void S(): {}2 {3 "bcd" // ins. di selezione {"bcd"}: token unico4 |5 "bef" // ins. di selezione {"bef"}: token unico6 }nessun problema: grammatica LL(1)
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 44 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale III
La direttiva LOOKAHEAD va solo nei punti di scelta:1 quando si usa |2 quando si usano *, +, ?
1 void S(): {}2 {3 // qui NO4 B()5 // qua NO6 (7 // qui OK8 C()9 |10 D()11 )12 }N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 45 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale IV
1 void S(): {}2 {3 (4 // p.d.s. primo |5 B()6 |7 // p.d.s. secondo |8 C()9 |10 D()11 )12
13 (14 // p.d.s. per ?15 E()16 )?
17
18 (19 // p.d.s. per +20 F()21 )+22
23 (24 // p.d.s. per *25 G()26 )*27
28 }29
30
31
32
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 46 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale – esempi I
Per il frammento
( "b" "c" )* "d"il parser generato conterrà:
1 while (tokenCorrente == "b")2 {3 consuma "b"4 consuma "c"5 }6 consuma "d"
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 47 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale – esempi II
inserendo una direttiva LOOKAHEAD(2) nel punto di scelta,la struttura cambia:
1 while (tokenCorrente == "b" && tokenSucc == "c")2 {3 consuma "b"4 consuma "c"5 }6 consuma "d"ma è superflua;
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 48 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale – esempi III
serve invece nel caso seguente
(LOOKAHEAD (2) "b" "c" )* "b" "d"interpretato con
1 while (tokenCorrente == "b" && tokenSucc == "c")2 {3 consuma "b"4 consuma "c"5 }6 consuma "b"7 consuma "d"
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 49 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale – esempi IV
Lo stesso vale anche per l’operatore +la specifica
(LOOKAHEAD (2) "b" "c" )+ "b"genera un ciclo:
1 do {2 consuma "b"3 consuma "c"4 } while (tokenCorrente == "b" && tokenSucc == "c")5 consuma "b"
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 50 / 85
Scelta delle produzioni Lookahead locale
Lookahead locale – esempi V
Infine nel caso di ?:("b")?il codice sarebbe del tipo:
1 if (tokenCorrente == "b")2 {3 consuma "b"4 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 51 / 85
Scelta delle produzioni Algoritmo di scelta
Algoritmo di scelta – esempi I
In una grammatica LL(1)al più una parte destra è annullabile (può derivare ε)Consideriamo una grammatica LL(1)P −→ QP −→ RP −→ TSupponiamo sia annullabile T.Quindi l’insieme di selezione per T è FIRST(T) + FOLLOW(P).Per le altre, gli ins. corrispondono ai FIRST delle parti destre.
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 52 / 85
Scelta delle produzioni Algoritmo di scelta
Algoritmo di scelta – esempi II
In un parser ricorsivo discendente (pseudo-codice) si avrebbe:
1 void P()2 {3 switch(tokenCorrente) {4 case tokenCorrente in FIRST(Q):5 Q(); break;6 case tokenCorrente in FIRST(R):7 R(); break;8 case tokenCorrente in FIRST(T)+FOLLOW(P):9 T(); break;10 default:11 solleva eccezione;12 }13 }Nota: Ultimo test inutile, si può semplificare il default:
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 53 / 85
Scelta delle produzioni Algoritmo di scelta
Algoritmo di scelta – esempi III
1 void P()2 {3 switch(tokenCorrente) {4 case tokenCorrente in FIRST(Q):5 Q(); break;6 case tokenCorrente in FIRST(R):7 R(); break;8 default:9 T(); break;10 }11 }
I test precedono le chiamate di Q() e R(), ma non di T().Il default deve sempre corrispondere alla derivazione di ε:quindi non servirà calcolare i FOLLOW , bastano i FIRST
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 54 / 85
Scelta delle produzioni Algoritmo di scelta
Algoritmo di scelta in JavaCC I
JavaCC adotta la seconda strategia:
il codice generato non esegue test sui token nei FOLLOWi test sulle alternative annullabili vanno previsti per ultimi
altrimenti il funzionamento del parser sarebbe compromesso
Esempio
1 PARSER_BEGIN(Gram)2 import java.io.*;3 class Gram4 {5 public static void main (String[] args)6 throws IOException, ParseException {7 Gram parser = new Gram(FileInputStream(args[0]));8 parser.S();9 }10 }11 PARSER_END(Gram)12 // da saltareN. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 55 / 85
Scelta delle produzioni Algoritmo di scelta
Algoritmo di scelta in JavaCC II
13 SKIP:14 {15 " " | "\n" | "\r" | "\t"16 }17 // grammatica18 void S() : {}19 {20 { System.out.println("fine");} // ins. sel. {EOF}21 |22 "z" S() // ins. sel. {"z"}23 }
Prima alternativa: produzione vuota (solo un’azione sem.)
si doveva mettere alla fineJavaCC dà un warning:
can expand to the empty token sequenceil parser viene generato ma la parte relativa a "z" vieneeliminata perché irraggiungibile
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 56 / 85
Scelta delle produzioni Algoritmo di scelta
Algoritmo di scelta in JavaCC III
L’assenza di warning da parte di JavaCC non garantisce che la
specifica sia corretta
Esempio JavaCC compila senza warning
1 void S() : {}2 {3 Q() "z"4 }5 // --------------------6 void Q() : {}7 {8 "z" // ins. selezione {"z"}9 |10 {} // ins. selezione {"z"}11 }tuttavia il parser ottenuto risconosce "zz"ma non "z"(pur essendo entrambe accettabili)
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 57 / 85
Scelta delle produzioni Algoritmo di scelta
Algoritmo di scelta in JavaCC IV
Per l’input "z", il parser usa la prima alternativa di Q(),ma poi non ci sono altre occorrenze di "z" nell’input per ilconsumo della "z" nella prod. di S()
si doveva perseguire la seconda alternativa in Q() cherichiede ε e non consuma la "z" sull’input,lasciandola disponibile per la regola di S()
La grammatica non è LL(1)
Gli ins. di selezione delle alternative in Q() coincidonoJavaCC non calcola tale insieme per la seconda,
quindi non si accorge della violazione della proprietà delle
grammatiche LL(1)
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 58 / 85
Scelta delle produzioni Lookahead Sintattico e Semantico
Lookahead Sintattico e Semantico
Oltre alla direttiva LOOKAHEAD(n) che specifica il numero n ditoken da esaminare in anticipo per decidere in un punto di scelta:
lookahead sintattico specifica sintattica dell’espansione attesa
per la scelta della prima alternativa
se si verifica, si prende la prima strada
altrimenti si procede alla prossima scelta
lookahead semantico specifica una condizione booleana(tra graffe)
true il parser segue la prima alternativafalse considera la prossima
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 59 / 85
Scelta delle produzioni Lookahead Sintattico e Semantico
Lookahead Sintattico I
Esempio lookahead sintattico
1 void S() : {}2 {3 LOOKAHEAD(C() "a")4 A()5 |6 B()7 }8
9 void A() : {}10 {11 C() "a" "a"12 }
13
14 void B() : {}15 {16 C() "b" "b"17 }18
19 void C() : {}20 {21 "c" "c"22 }23
24
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 60 / 85
Scelta delle produzioni Lookahead Sintattico e Semantico
Lookahead Sintattico II
Data l’espansione specificata C()"a"il parser cerca sul flusso di input una sottostringa
che corrisponde a C() seguita da un token "a"In caso di successo, si segue la prima alternativa A()altrimenti si considera la successiva
Esempio se si avesse in input "c""c""a""a",si sceglierebbe la prima prod.
Usando invece la direttiva LOOKAHEAD(3) non vi sarebberoproblemi perché la stringa per C() ha lunghezza 2.
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 61 / 85
Scelta delle produzioni Lookahead Sintattico e Semantico
Lookahead Sintattico III
Se, invece, la regola di C() fosse:1 void C (): {}2 {3 ("c")+4 }nessuna direttiva di lookahead numerico funzionerebbe,
al contrario di quello sintattico
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 62 / 85
Scelta delle produzioni Lookahead Sintattico e Semantico
Lookahead Semantico I
Esempio lookahead semantico
1 void S() : {}2 {3 LOOKAHEAD({ getToken(1).kind == ID &&4 getToken(2).kind == ASGN })5 A()6 |7 D()8 }9
10 void A() : {}11 {12 <ID> <ASGN> E()13 }14
15 void D() : {}16 {17 <ID> <ID>18 }N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 63 / 85
Scelta delle produzioni Lookahead Sintattico e Semantico
Lookahead Semantico II
Nota il metodo getToken() non consuma token in inputgetToken(1) restituisce il token corrente;getToken(2) restituisce il token che lo segue
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 64 / 85
Esempi
Sommario
1 Introduzione
2 Specifica e prodotti
3 Ricorsione e Iterazione
4 Scelta delle produzioni
5 EsempiNL_XlatorBowdCSV2HTMLCalcolatore
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 65 / 85
Esempi NL_XlatorEsempi: NL_Xlator I
1 PARSER_BEGIN(NL_Xlator2)2
3 /** New line translator. */4 public class NL_Xlator2 {5
6 /** Main entry point. */7 public static void main(String args[]) throws ParseException {8 NL_Xlator parser = new NL_Xlator(System.in);9 parser.ExpressionList();10 }11
12 }13
14 PARSER_END(NL_Xlator)15
16 SKIP :17 {18 " " | "\t" | "\n" | "\r"19 }20
21 TOKEN :N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 66 / 85
Esempi NL_XlatorEsempi: NL_Xlator II
22 {23 < ID: ["a"-"z","A"-"Z","_"] ( ["a"-"z","A"-"Z","_","0"-"9"] )* >24 | < NUM: ( ["0"-"9"] )+ >25 }26
27 /** Top level production. */28 void ExpressionList() : { String s; }29 {30 {31 System.out.println("Please type in an expression32 followed by a \";\" or ^D to quit:"); System.out.println("");33 }34 ( s=Expression() ";"35 {36 System.out.println(s); System.out.println("");37 System.out.println("Please type in another expression38 followed by a \";\" or ^D to quit:"); System.out.println("");39 }40 )*41 <EOF>42 }43
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 67 / 85
Esempi NL_XlatorEsempi: NL_Xlator III
44 /** An Expression. */45 String Expression() :46 {47 java.util.Vector termimage = new java.util.Vector();48 String s;49 }50 {51 s=Term()52 { termimage.addElement(s); }53 ( "+" s=Term()54 { termimage.addElement(s); }55 )*56 {57 if (termimage.size() == 1) {58 return (String)termimage.elementAt(0);59 } else {60 s = "the sum of " + (String)termimage.elementAt(0);61 for (int i = 1; i < termimage.size()-1; i++) {62 s += ", " + (String)termimage.elementAt(i);63 }64 if (termimage.size() > 2) { s += ","; }65 s += " and " + (String)termimage.elementAt(termimage.size()-1);N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 68 / 85
Esempi NL_XlatorEsempi: NL_Xlator IV
66 return s;67 }68 }69 }70
71 /** A Term. */72 String Term() :73 {74 java.util.Vector factorimage = new java.util.Vector();75 String s;76 }77 {78 s=Factor()79 { factorimage.addElement(s); }80 ( "*" s=Factor()81 { factorimage.addElement(s); }82 )*83 {84 if (factorimage.size() == 1) {85 return (String)factorimage.elementAt(0);86 } else {87 s = "the product of " + (String)factorimage.elementAt(0);N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 69 / 85
Esempi NL_XlatorEsempi: NL_Xlator V
88 for (int i = 1; i < factorimage.size()-1; i++) {89 s += ", " + (String)factorimage.elementAt(i);90 }91 if (factorimage.size() > 2) { s += ","; }92 s += " and " + (String)factorimage.elementAt(factorimage.size()-1);93 return s;94 }95 }96 }97
98 /** A Factor. */99 String Factor() : { Token t; String s; }100 {101 t=<ID> { return t.image; }102 | t=<NUM> { return t.image; }103 | "(" s=Expression() ")" { return s; }104 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 70 / 85
Esempi BowdEsempi: Bowd I
1 PARSER_BEGIN(Bowd)2 import java.io.* ;3
4 class Bowd {5 public static void main(String args [])6 throws IOException {7 System.out.print:("Lettura da standard input");8 BufferedReader in = new BufferedReader(9 new InputStreamReader(System.in));10 String linea = in.readLine();11 System.out.print(sostituzione(linea));12 }13
14 static String sostituzione(String inStringa) {15 Reader sr = new StringReader(inStringa);16 Bowd parser = new Bowd(sr);17 StringBuffer buffer = new StringBuffer();N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 71 / 85
Esempi BowdEsempi: Bowd II
18 try { parser.inizio(buffer); }19 catch(TokenMgrError e)20 {throw new IllegalStateException();}21 catch(ParseException e)22 {throw new IllegalStateException();}23 return buffer.toString();24 } // sostituzione25 } // classe26 PARSER_END(Bowd)27
28 TOKEN :29 {30 < PAROLA_DI_4_LETTERE : (<LETTERA>){4}>31 | < PAROLA_DI_PIU_DI_4_LETTERE :32 (<LETTERA>){5} (<LETTERA>)* >33 | < #LETTERA : ["a"-"z","A"-"Z"] >34 | < ALTRO : ~[] >N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 72 / 85
Esempi BowdEsempi: Bowd III
35 }36
37 void inizio(StringBuffer buffer) :38 { Token t; }39 {40 ( <PAROLA_DI_4_LETTERE>41 { buffer.append("****"); }42 | ( t=<PAROLA_DI_PIU_DI_4_LETTERE> | t=<ALTRO>)43 { buffer.append(t.image); }44 )*45 <EOF>46 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 73 / 85
Esempi CSV2HTMLEsempi: CSV2HTML ICSV: Formato standard (export da fogli elettronici)Esempio
1 STUDENT, ID NAME, DATE OF BIRTH2 129384, Davy Jones, 03/04/813 328649, Clare Manstead, 30/11/814 237090, Richard Stoppit, 22/06/825 523343, Brian Hardwick, 15/11/816 908423, Sally Brush, 06/06/817 328453, Elisa Strudel, 12/09/828 883632, Peter Smith, 03/05/839 542033, Ryan Alcot, 04/12/80Grammatica
1 file: riga() ( <FINELINEA> riga())* [<FINELINEA>)] <EOF>2 linea: (record)+3 record: <RECORD> [<VIRGOLA>]N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 74 / 85
Esempi CSV2HTMLEsempi: CSV2HTML II
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";N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 75 / 85
Esempi CSV2HTMLEsempi: CSV2HTML III
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)38
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 76 / 85
Esempi CSV2HTMLEsempi: CSV2HTML IV
39 SKIP :40 {41 " " | "\t"42 }43
44 TOKEN :45 {46 <VIRGOLA: ",">47 | <RECORD: (~[",","\r","\n"])+ >48 | <FINELINEA: "\r\n" | "\r" | "\n" >49 }50
51 String file() : { String tab=" <table border=’1’>\n", r; }52 {53 r=riga() <FINELINEA> { tab+=r; }54 ( r=riga() <FINELINEA> { tab+=r; } )*55 ( <FINELINEA> )? <EOF>56 { return tab+=" </table>\n"; }57 }N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 77 / 85
Esempi CSV2HTMLEsempi: CSV2HTML V
58
59 String riga() : { String d, r="\t<tr>\n"; }60 {61 ( d=record() { r+=d; } )+62 { return r+="\t</tr>\n"; }63 }64
65 String record() : { Token t; }66 {67 t=<RECORD> ( <VIRGOLA> )?68 { return "\t\t<td> " + t.image + " </td>\n";}69 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 78 / 85
Esempi Calcolatore
Esempi: Calcolatore I
1 PARSER_BEGIN(Calcolatore)2 public class Calcolatore {3 public static void main (String args []) {4 Calcolatore parser = new Calcolatore(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 } // classN. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 79 / 85
Esempi Calcolatore
Esempi: Calcolatore II
19 PARSER_END(Calcolatore)20
21 SKIP:22 { " " | "\r" | "\t"23 }24
25 TOKEN:26 {27 < EOL: "\n" >28 | < #CIFRA: ["0" - "9"] >29 | < NUMFP:30 (<CIFRA>)+ "." (<CIFRA>)* (<ESP>)?31 | "." (<CIFRA>)+ (<ESP>)?32 | (<CIFRA>)+ <ESP>33 | (<CIFRA>)+ (<ESP>)?34 >35 | < #ESP: ["e","E"] (["+","-"])? (<CIFRA>)+ >36 }37
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 80 / 85
Esempi Calcolatore
Esempi: Calcolatore III
38 double start(): { double r; }39 {40 r=espressione() <EOL>41 { return r; }42 }43
44 double espressione(): { double t,r; }45 { // E ::= T RE46 t=termine() r=restoE(t)47 { return r; }48 }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)N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 81 / 85
Esempi Calcolatore
Esempi: Calcolatore IV
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 | // vuotaN. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 82 / 85
Esempi Calcolatore
Esempi: Calcolatore V
76 { 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; }85 | "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); }N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 83 / 85
Esempi Calcolatore
Esempi: Calcolatore VI
95 | "tan" f=fattore()96 { return Math.tan(f); }97 | "(" f=espressione() ")"98 { return f; }99 }
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 84 / 85
Riferimenti
Riferimenti
D. Galles: Modern Compiler Design. Scott/Jones PublishingA.J. Dos Reis: Compiler Construction Using Java, JavaCC, andYacc, Wiley-IEEE Computer Society PressT. S. Norvell. JavaCC TutorialN. Fanizzi: Manualetto JavaCC
N. Fanizzi Linguaggi di prog.+Lab javacc – Analisi Sintattica 15 maggio 2014 85 / 85
Top Related