Erstellen Sie Ihre eigenen Sprachen mit JavaCC

Haben Sie sich jemals gefragt, wie der Java-Compiler funktioniert? Müssen Sie Parser für Markup-Dokumente schreiben, die keine Standardformate wie HTML oder XML abonnieren? Oder möchten Sie Ihre eigene kleine Programmiersprache nur zum Teufel implementieren? JavaCCermöglicht es Ihnen, all dies in Java zu tun. Egal, ob Sie nur mehr über die Funktionsweise von Compilern und Interpreten erfahren möchten oder konkrete Ambitionen haben, den Nachfolger der Java-Programmiersprache zu schaffen, begleiten Sie mich bitte auf der Suche nach diesem Monat JavaCC, hervorgehoben durch die Erstellung eines praktischen kleinen Befehlszeilenrechner.

Grundlagen der Compilerkonstruktion

Programmiersprachen werden oft etwas künstlich in kompilierte und interpretierte Sprachen unterteilt, obwohl die Grenzen verschwommen sind. Mach dir also keine Sorgen. Die hier diskutierten Konzepte gelten sowohl für kompilierte als auch für interpretierte Sprachen. Wir werden das Wort Compiler unten verwenden, aber für den Umfang dieses Artikels muss dies die Bedeutung des Interpreters enthalten.

Compiler müssen drei Hauptaufgaben ausführen, wenn sie einen Programmtext (Quellcode) erhalten:

  1. Lexikalische Analyse
  2. Syntaktische Analyse
  3. Codegenerierung oder -ausführung

Der Großteil der Arbeit des Compilers konzentriert sich auf die Schritte 1 und 2, bei denen der Programmquellcode verstanden und seine syntaktische Korrektheit sichergestellt wird. Wir nennen diesen Prozess Parsing , für den der Parser verantwortlich ist.

Lexikalische Analyse (Lexing)

Die lexikalische Analyse wirft einen flüchtigen Blick auf den Programmquellcode und unterteilt ihn in geeignete Token. Ein Token ist ein wesentlicher Bestandteil des Quellcodes eines Programms. Token-Beispiele sind Schlüsselwörter, Interpunktion, Literale wie Zahlen und Zeichenfolgen. Nicht-Token enthalten Leerzeichen, die häufig ignoriert, aber zum Trennen von Token und Kommentaren verwendet werden.

Syntaktische Analyse (Parsing)

Während der syntaktischen Analyse extrahiert ein Parser dem Programmquellcode eine Bedeutung, indem er die syntaktische Korrektheit des Programms sicherstellt und eine interne Darstellung des Programms erstellt.

Die Computersprachtheorie spricht von Programmen, Grammatik und Sprachen. In diesem Sinne ist ein Programm eine Folge von Token. Ein Literal ist ein grundlegendes Element der Computersprache, das nicht weiter reduziert werden kann. Eine Grammatik definiert Regeln zum Erstellen syntaktisch korrekter Programme. Nur Programme, die nach den in der Grammatik definierten Regeln spielen, sind korrekt. Die Sprache ist einfach die Menge aller Programme, die alle Ihre Grammatikregeln erfüllen.

Während der syntaktischen Analyse untersucht ein Compiler den Programmquellcode hinsichtlich der in der Grammatik der Sprache definierten Regeln. Wenn eine Grammatikregel verletzt wird, zeigt der Compiler eine Fehlermeldung an. Während der Prüfung des Programms erstellt der Compiler eine einfach zu verarbeitende interne Darstellung des Computerprogramms.

Die Grammatikregeln einer Computersprache können eindeutig und vollständig mit der EBNF-Notation (Extended Backus-Naur-Form) angegeben werden (weitere Informationen zu EBNF finden Sie unter Ressourcen). EBNF definiert Grammatiken anhand von Produktionsregeln. Eine Produktionsregel besagt, dass ein Grammatikelement - entweder Literale oder zusammengesetzte Elemente - aus anderen Grammatikelementen bestehen kann. Literale, die nicht reduzierbar sind, sind Schlüsselwörter oder Fragmente statischen Programmtextes, wie z. B. Interpunktionssymbole. Zusammengesetzte Elemente werden durch Anwendung von Produktionsregeln abgeleitet. Produktionsregeln haben das folgende allgemeine Format:

GRAMMAR_ELEMENT: = Liste der Grammatikelemente | alternative Liste von Grammatikelementen

Schauen wir uns als Beispiel die Grammatikregeln für eine kleine Sprache an, die grundlegende arithmetische Ausdrücke beschreibt:

Ausdruck: = Nummer | Ausdruck '+' Ausdruck | Ausdruck '-' Ausdruck | Ausdruck '*' Ausdruck | Ausdruck '/' Ausdruck | '(' Ausdruck ')' | - Ausdrucksnummer: = Ziffer + ('.' Ziffer +)? Ziffer: = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Drei Produktionsregeln definieren die Grammatikelemente:

  • expr
  • number
  • digit

Die durch diese Grammatik definierte Sprache ermöglicht es uns, arithmetische Ausdrücke anzugeben. An exprist entweder eine Zahl oder einer der vier Infix-Operatoren, die auf zwei exprs angewendet werden , eine exprin Klammern oder eine negative expr. A numberist eine Gleitkommazahl mit optionalem Dezimalbruch. Wir definieren a digitals eine der bekannten Dezimalstellen.

Codegenerierung oder -ausführung

Sobald der Parser das Programm ohne Fehler erfolgreich analysiert hat, existiert es in einer internen Darstellung, die vom Compiler einfach verarbeitet werden kann. Es ist jetzt relativ einfach, Maschinencode (oder Java-Bytecode) aus der internen Darstellung zu generieren oder die interne Darstellung direkt auszuführen. Wenn wir das erstere tun, kompilieren wir; Im letzteren Fall sprechen wir über Dolmetschen.

JavaCC

JavaCC, kostenlos erhältlich, ist ein Parser-Generator. Es bietet eine Java-Spracherweiterung zum Festlegen der Grammatik einer Programmiersprache. JavaCCwurde ursprünglich von Sun Microsystems entwickelt, wird aber jetzt von MetaMata verwaltet. Wie jedes anständige Programmierwerkzeug wurde JavaCCes tatsächlich verwendet, um die Grammatik des JavaCCEingabeformats anzugeben .

Darüber hinaus JavaCCkönnen wir Grammatiken ähnlich wie EBNF definieren, wodurch es einfach ist, EBNF-Grammatiken in das JavaCCFormat zu übersetzen . Darüber hinaus JavaCCist es der beliebteste Parser-Generator für Java, mit einer Vielzahl vordefinierter JavaCCGrammatiken, die als Ausgangspunkt verwendet werden können.

Entwicklung eines einfachen Taschenrechners

Wir überdenken jetzt unsere kleine arithmetische Sprache, um mithilfe von Java einen einfachen Befehlszeilenrechner zu erstellen JavaCC. Zuerst müssen wir die EBNF-Grammatik ins JavaCCFormat übersetzen und in der Datei speichern Arithmetic.jj:

Optionen {LOOKAHEAD = 2; } PARSER_BEGIN (Arithmetik) öffentliche Klasse Arithmetik {} PARSER_END (Arithmetik) SKIP: "\ t" TOKEN: double expr (): {} term () ("+" expr () double term (): {} "/" term ()) * double unary (): {} "-" element () double element (): {} "(" expr () ")"  

Der obige Code soll Ihnen eine Vorstellung davon geben, wie Sie eine Grammatik für angeben können JavaCC. Der optionsAbschnitt oben gibt eine Reihe von Optionen für diese Grammatik an. Wir geben einen Lookahead von 2 an. Zusätzliche Optionen steuern JavaCCdie Debugging-Funktionen und mehr. Diese Optionen können alternativ in der JavaCCBefehlszeile angegeben werden.

Die PARSER_BEGINKlausel gibt an, dass die Parser-Klassendefinition folgt. JavaCCgeneriert für jeden Parser eine einzelne Java-Klasse. Wir nennen die Parser-Klasse Arithmetic. Im Moment benötigen wir nur eine leere Klassendefinition. JavaCCwird später parsing-bezogene Deklarationen hinzufügen. Wir beenden die Klassendefinition mit der PARSER_ENDKlausel.

Der SKIPAbschnitt identifiziert die Zeichen, die wir überspringen möchten. In unserem Fall sind dies die Leerzeichen. Als nächstes definieren wir die Token unserer Sprache im TOKENAbschnitt. Wir definieren Zahlen und Ziffern als Token. Beachten Sie, dass JavaCCzwischen Definitionen für Token und Definitionen für andere Produktionsregeln unterschieden wird, die sich von EBNF unterscheiden. Die Abschnitte SKIPund TOKENgeben die lexikalische Analyse dieser Grammatik an.

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.

Wir haben den Rückgabetyp der ursprünglichen Grammatikelemente geändert, um zurückzukehren double. Wir führen entsprechende Berechnungen genau dort durch, wo wir sie analysieren, und übergeben die Berechnungsergebnisse an den Aufrufbaum. Wir haben auch die Grammatikelementdefinitionen transformiert, um ihre Ergebnisse in lokalen Variablen zu speichern. Zum Beispiel a=element()parst ein elementdas Ergebnis in den Variablen und speichert a. Dadurch können wir die Ergebnisse der analysierten Elemente im Code der Aktionen auf der rechten Seite verwenden. Aktionen sind Blöcke von Java-Code, die ausgeführt werden, wenn die zugehörige Grammatikregel eine Übereinstimmung im Eingabestream gefunden hat.

Bitte beachten Sie, wie wenig Java-Code wir hinzugefügt haben, um den Taschenrechner voll funktionsfähig zu machen. Darüber hinaus ist das Hinzufügen zusätzlicher Funktionen wie eingebauter Funktionen oder sogar Variablen einfach.