javacc Analisi Sintattica - LACAM

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

http://www.di.uniba.it/~fanizzi

http://www.di.uniba.it/~fanizzi/corsi/lp

Introduzione

Sommario

1 Introduzione

Parsing top-down ricorsivo

Costruire un Parser LL(1)




5 Esempi




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




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)




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





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 }





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




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 }





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 }





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 }




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




Specifica e prodotti

Sommario

1 Introduzione


File di specifica

Metodi del parser


Token, scanner e flusso di input

Catena dei token



5 Esempi




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 */





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





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





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>}





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





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





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





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





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 }





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





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 }




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




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 ")"




Specifica e prodotti 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




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)




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




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




Ricorsione e Iterazione

Sommario

1 Introduzione



Iterazioni

Esempi


5 Esempi




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 ?




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:





Iterazioni – esempi II

1 void expr() : {}2 {3 term()4 (5 "+"6 term()7 )*8 }





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




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




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




Scelta delle produzioni

Sommario

1 Introduzione




Lookahead locale

Algoritmo di scelta

Lookahead Sintattico e Semantico

5 Esempi





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)





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





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.





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




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 }





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)





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




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





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"





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;





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"





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"





Lookahead locale – esempi V

Infine nel caso di ?:("b")?il codice sarebbe del tipo:

1 if (tokenCorrente == "b")2 {3 consuma "b"4 }




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.





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:





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





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




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





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)





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)




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





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





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.





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





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




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




Esempi

Sommario

1 Introduzione




5 EsempiNL_XlatorBowdCSV2HTMLCalcolatore




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




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 }




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 }




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




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 }




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




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 }




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


http://www.cs.usfca.edu/~galles/compilerdesign/

http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470949597.html

http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470949597.html

http://www.engr.mun.ca/~theo/JavaCC-Tutorial

http://lacam.di.uniba.it/~nico/corsi/lingpro/materiale/Manualetto-JavaCC.pdf



javacc Analisi Sintattica - LACAM

Documents

Transcript of javacc Analisi Sintattica - LACAM