Crea i tuoi linguaggi con JavaCC

Ti sei mai chiesto come funziona il compilatore Java? Hai bisogno di scrivere parser per documenti di markup che non sottoscrivono formati standard come HTML o XML? O vuoi implementare il tuo piccolo linguaggio di programmazione solo per il gusto di farlo? JavaCCti permette di fare tutto questo in Java. Quindi, se sei interessato solo a saperne di più su come funzionano i compilatori e gli interpreti, o hai ambizioni concrete di creare il successore del linguaggio di programmazione Java, unisciti a me nella ricerca di questo mese da esplorare JavaCC, evidenziata dalla costruzione di un piccolo calcolatrice da riga di comando.

Fondamenti di costruzione del compilatore

I linguaggi di programmazione sono spesso divisi, in qualche modo artificialmente, in linguaggi compilati e interpretati, sebbene i confini siano diventati sfocati. In quanto tale, non preoccuparti. I concetti discussi qui si applicano ugualmente bene ai linguaggi compilati e interpretati. Useremo la parola compilatore di seguito, ma per lo scopo di questo articolo, questo includerà il significato di interprete.

I compilatori devono eseguire tre attività principali quando viene presentato un testo di programma (codice sorgente):

  1. Analisi lessicale
  2. Analisi sintattica
  3. Generazione o esecuzione del codice

La maggior parte del lavoro del compilatore si concentra sui passaggi 1 e 2, che implicano la comprensione del codice sorgente del programma e la garanzia della sua correttezza sintattica. Chiamiamo quel processo parsing , che è responsabilità del parser .

Analisi lessicale (lexing)

L'analisi lessicale dà uno sguardo superficiale al codice sorgente del programma e lo divide in token appropriati . Un token è una parte significativa del codice sorgente di un programma. Esempi di token includono parole chiave, punteggiatura, valori letterali come numeri e stringhe. I non token includono spazi vuoti, spesso ignorati ma utilizzati per separare token e commenti.

Analisi sintattica (parsing)

Durante l'analisi sintattica, un parser estrae il significato dal codice sorgente del programma garantendo la correttezza sintattica del programma e costruendo una rappresentazione interna del programma.

La teoria del linguaggio informatico parla di programmi, grammatica e lingue. In questo senso, un programma è una sequenza di gettoni. Un letterale è un elemento di base del linguaggio del computer che non può essere ulteriormente ridotto. Una grammatica definisce le regole per costruire programmi sintatticamente corretti. Solo i programmi che giocano secondo le regole definite nella grammatica sono corretti. La lingua è semplicemente l'insieme di tutti i programmi che soddisfano tutte le tue regole grammaticali.

Durante l'analisi sintattica, un compilatore esamina il codice sorgente del programma rispetto alle regole definite nella grammatica della lingua. Se viene violata una regola grammaticale, il compilatore visualizza un messaggio di errore. Lungo il percorso, durante l'esame del programma, il compilatore crea una rappresentazione interna facilmente elaborabile del programma del computer.

Le regole grammaticali di un linguaggio per computer possono essere specificate in modo inequivocabile e nella loro interezza con la notazione EBNF (Extended Backus-Naur-Form) (per ulteriori informazioni su EBNF, vedere Risorse). EBNF definisce le grammatiche in termini di regole di produzione. Una regola di produzione afferma che un elemento grammaticale, sia letterali che elementi composti, può essere composto da altri elementi grammaticali. I letterali, che sono irriducibili, sono parole chiave o frammenti di testo statico del programma, come i simboli di punteggiatura. Gli elementi composti sono derivati ​​applicando le regole di produzione. Le regole di produzione hanno il seguente formato generale:

GRAMMAR_ELEMENT: = elenco di elementi grammaticali | elenco alternativo di elementi grammaticali

Ad esempio, diamo un'occhiata alle regole grammaticali per un piccolo linguaggio che descrive espressioni aritmetiche di base:

expr: = numero | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | '(' expr ')' | - expr numero: = cifra + ('.' cifra +)? cifra: = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | "9"

Tre regole di produzione definiscono gli elementi grammaticali:

  • expr
  • number
  • digit

Il linguaggio definito da quella grammatica ci permette di specificare espressioni aritmetiche. An exprè un numero o uno dei quattro operatori infisso applicati a due exprs, una exprtra parentesi o un negativo expr. A numberè un numero a virgola mobile con frazione decimale facoltativa. Definiamo digita come una delle cifre decimali familiari.

Generazione o esecuzione del codice

Una volta che il parser analizza correttamente il programma senza errori, esiste in una rappresentazione interna che è facile da elaborare dal compilatore. Ora è relativamente facile generare codice macchina (o bytecode Java per quella materia) dalla rappresentazione interna o eseguire direttamente la rappresentazione interna. Se facciamo il primo, stiamo compilando; in quest'ultimo caso si parla di interpretariato.

JavaCC

JavaCC, disponibile gratuitamente, è un generatore di parser. Fornisce un'estensione del linguaggio Java per specificare la grammatica di un linguaggio di programmazione. JavaCCè stato sviluppato inizialmente da Sun Microsystems, ma ora è mantenuto da MetaMata. Come ogni decente strumento di programmazione, è JavaCCstato effettivamente utilizzato per specificare la grammatica del JavaCCformato di input.

Inoltre, JavaCCci consente di definire le grammatiche in modo simile a EBNF, semplificando la traduzione delle grammatiche EBNF nel JavaCCformato. Inoltre, JavaCCè il generatore di parser più popolare per Java, con una serie di JavaCCgrammatiche predefinite disponibili da utilizzare come punto di partenza.

Sviluppare una semplice calcolatrice

Ora rivisitiamo il nostro piccolo linguaggio aritmetico per creare una semplice calcolatrice da riga di comando in Java usando JavaCC. Innanzitutto, dobbiamo tradurre la grammatica EBNF in JavaCCformato e salvarla nel file Arithmetic.jj:

opzioni {LOOKAHEAD = 2; } PARSER_BEGIN (Aritmetica) classe pubblica Aritmetica {} PARSER_END (Aritmetica) SKIP: "\ t" TOKEN: double expr (): {} term () ("+" expr () double term (): {} "/" termine ()) * double unary (): {} "-" element () double element (): {} "(" expr () ")"  

Il codice sopra dovrebbe darti un'idea su come specificare una grammatica per JavaCC. La optionssezione in alto specifica una serie di opzioni per quella grammatica. Specifichiamo un lookahead di 2. Opzioni aggiuntive controllano JavaCCle funzionalità di debug e altro ancora. Tali opzioni possono essere specificate in alternativa sulla JavaCCriga di comando.

La PARSER_BEGINclausola specifica che segue la definizione della classe parser. JavaCCgenera una singola classe Java per ogni parser. Chiamiamo la classe parser Arithmetic. Per ora, abbiamo bisogno solo di una definizione di classe vuota; JavaCCaggiungerà in seguito dichiarazioni relative all'analisi. Terminiamo la definizione della classe con la PARSER_ENDclausola.

La SKIPsezione identifica i caratteri che vogliamo saltare. Nel nostro caso, quelli sono i caratteri spazi bianchi. Successivamente, definiamo i token della nostra lingua nella TOKENsezione. Definiamo numeri e cifre come gettoni. Si noti che JavaCCdifferenzia tra definizioni per i token e definizioni per altre regole di produzione, che differiscono da EBNF. Le sezioni SKIPe TOKENspecificano l'analisi lessicale di questa grammatica.

Next, we define the production rule for expr, the top-level grammar element. Notice how that definition markedly differs from the definition of expr in EBNF. What's happening? Well, it turns out that the EBNF definition above is ambiguous, as it allows multiple representations of the same program. For example, let us examine the expression 1+2*3. We can match 1+2 into an expr yielding expr*3, as in Figure 1.

Or, alternatively, we could first match 2*3 into an expr resulting in 1+expr, as shown in Figure 2.

With JavaCC, we have to specify the grammar rules unambiguously. As a result, we break out the definition of expr into three production rules, defining the grammar elements expr, term, unary, and element. Now, the expression 1+2*3 is parsed as shown in Figure 3.

From the command line we can run JavaCC to check our grammar:

javacc Arithmetic.jj Java Compiler Compiler Version 1.1 (Parser Generator) Copyright (c) 1996-1999 Sun Microsystems, Inc. Copyright (c) 1997-1999 Metamata, Inc. (type "javacc" with no arguments for help) Reading from file Arithmetic.jj . . . Warning: Lookahead adequacy checking not being performed since option LOOKAHEAD is more than 1. Set option FORCE_LA_CHECK to true to force checking. Parser generated with 0 errors and 1 warnings. 

The following checks our grammar definition for problems and generates a set of Java source files:

TokenMgrError.java ParseException.java Token.java ASCII_CharStream.java Arithmetic.java ArithmeticConstants.java ArithmeticTokenManager.java 

Together these files implement the parser in Java. You can invoke this parser by instantiating an instance of the Arithmetic class:

public class Arithmetic implements ArithmeticConstants { public Arithmetic(java.io.InputStream stream) { ... } public Arithmetic(java.io.Reader stream) { ... } public Arithmetic(ArithmeticTokenManager tm) { ... } static final public double expr() throws ParseException { ... } static final public double term() throws ParseException { ... } static final public double unary() throws ParseException { ... } static final public double element() throws ParseException { ... } static public void ReInit(java.io.InputStream stream) { ... } static public void ReInit(java.io.Reader stream) { ... } public void ReInit(ArithmeticTokenManager tm) { ... } static final public Token getNextToken() { ... } static final public Token getToken(int index) { ... } static final public ParseException generateParseException() { ... } static final public void enable_tracing() { ... } static final public void disable_tracing() { ... } } 

If you wanted to use this parser, you must create an instance using one of the constructors. The constructors allow you to pass in either an InputStream, a Reader, or an ArithmeticTokenManager as the source of the program source code. Next, you specify the main grammar element of your language, for example:

Arithmetic parser = new Arithmetic(System.in); parser.expr(); 

However, nothing much happens yet because in Arithmetic.jj we've only defined the grammar rules. We have not yet added the code necessary to perform the calculations. To do so, we add appropriate actions to the grammar rules. Calcualtor.jj contains the complete calculator, including actions:

options { LOOKAHEAD=2; } PARSER_BEGIN(Calculator) public class Calculator { public static void main(String args[]) throws ParseException { Calculator parser = new Calculator(System.in); while (true) { parser.parseOneLine(); } } } PARSER_END(Calculator) SKIP :  "\t"  TOKEN:    void parseOneLine(): { double a; } { a=expr()  { System.out.println(a); } |  |  { System.exit(-1); } } double expr(): { double a; double b; } { a=term() ( "+" b=expr() { a += b; } | "-" b=expr() { a -= b; } )* { return a; } } double term(): { double a; double b; } { a=unary() ( "*" b=term() { a *= b; } | "/" b=term() { a /= b; } )* { return a; } } double unary(): { double a; } { "-" a=element() { return -a; } | a=element() { return a; } } double element(): { Token t; double a; } { t= { return Double.parseDouble(t.toString()); } | "(" a=expr() ")" { return a; } } 

The main method first instantiates a parser object that reads from standard input and then calls parseOneLine() in an endless loop. The method parseOneLine() itself is defined by an additional grammar rule. That rule simply defines that we expect every expression on a line by itself, that it is OK to enter empty lines, and that we terminate the program if we reach the end of the file.

Abbiamo modificato il tipo di ritorno degli elementi grammaticali originali da restituire double. Eseguiamo calcoli appropriati proprio dove li analizziamo e passiamo i risultati del calcolo all'albero delle chiamate. Abbiamo anche trasformato le definizioni degli elementi grammaticali per memorizzare i loro risultati in variabili locali. Ad esempio, a=element()analizza un elemente memorizza il risultato nella variabile a. Ciò ci consente di utilizzare i risultati degli elementi analizzati nel codice delle azioni sul lato destro. Le azioni sono blocchi di codice Java che vengono eseguiti quando la regola grammaticale associata ha trovato una corrispondenza nel flusso di input.

Si noti quanto poco codice Java abbiamo aggiunto per rendere la calcolatrice completamente funzionale. Inoltre, l'aggiunta di funzionalità aggiuntive, come funzioni integrate o anche variabili è facile.