Open Source im professionellen Einsatz
Linux-Magazin 04/2005
699

BNF-Produktionen

Ab Zeile 61 folgen so genannte BNF-Produktionen. BNF steht für Backus-Naur-Form, eine formale Notation, um die Syntax einer Sprache festzulegen. John Backus beschrieb mit einer Vorversion die Sprache Algol58, Peter Naur erweiterte sie und beschrieb Algol60. Eine hervorragende Übersicht zum Thema BNF und Parser gibt[4]. Eine Variante der BNF-Notation ist die EBNF, die die Möglichkeit bietet, Wiederholungen ohne Rekursion zu definieren. JavaCC verwendet EBNF in einer speziellen funktionalen Notation, die eng mit Java verknüpft ist.

Das Prinzip der BNF ist einfach: Ein Symbol ist entweder terminal oder es wird durch andere Symbole definiert. Im Beispiel ist das Toplevel-Symbol »processInput« (Zeile 61), es besteht aus beliebig vielen »keyspec« (Zeile 64). Nach der Definition des Symbols folgt ein Block mit beliebigem Java-Code (etwa Zeile 62), der im Beispiel aber stets leer ist. Die funktionale Notation erlaubt es auch, Parameter zu übergeben und Werte zurückzugeben.

Semantische Aktionen

Anhand der Grammatik hangelt man sich am Baum entlang: Ein »keyspec« besteht entweder aus »titleSpec«, »firstnameSpec« oder »lastnameSpec« (Zeile 71). Letztere bestehen aus den vorher definierten Token (Zeilen 77, 83 und 89). Es ist wichtig, die JavaCC-Syntax zu verstehen und die Grammatik formal korrekt zu formulieren.

Listing 3 zeigt einen typischen Ablauf: Erzeugen des Parsers über »javacc« (Zeilen 1 bis 5), Kompilieren mittels »javac« (Zeile 6) und Ausführen (Zeilen 7 bis 30). Der im Debug-Modus generierte Parser zeigt alle Methodenaufrufe und erkannte Token.

Damit der Parser mehr macht, als nur eine Datei syntaktisch zu analysieren, braucht er so genannte semantische Aktionen. Es gibt zwar auch lexikalische Aktionen, die immer dann ausgeführt werden, wenn ein Token erkannt wird. Aber sie sind meist nur für Spezialanwendungen sinnvoll, etwa für einen Parser, der die Anzahl von »STRING_LITERAL«-Vorkommnissen zählt.

Listing 3: Parser generieren,
kompilieren, ausführen

01 $ /usr/local/javacc-3.2/bin/javacc -OUTPUT_DIRECTORY=src/hello HelloWorld.jj
02 Java Compiler Compiler Version 3.2 (Parser Generator)
03 (type "javacc" with no arguments for help)
04 Reading from file HelloWorld.jj . . .
05 Parser generated successfully.
06 $ javac -d build src/hello/*
07 $ cat helloworld.txt | java -cp build/ hello.HelloWorld
08 Call:   processInput
09   Call:   keyspec
10     Call:   titleSpec
11       Consumed token: <<TITLE>: "title">
12       Consumed token: <<EQ>: "=">
13       Consumed token: <<STRING_LITERAL>: "Herr">
14     Return: titleSpec
15   Return: keyspec
16   Call:   keyspec
17     Call:   firstnameSpec
18       Consumed token: <<FIRSTNAME>: "firstname">
19       Consumed token: <<EQ>: "= ">
20       Consumed token: <<STRING_LITERAL>: "Bernhard">
21     Return: firstnameSpec
22   Return: keyspec
23   Call:   keyspec
24     Call:   lastnameSpec
25       Consumed token: <<LASTNAME>: "lastname">
26       Consumed token: <<EQ>: "= ">
27       Consumed token: <<STRING_LITERAL>: "Bablok">
28     Return: lastnameSpec
29   Return: keyspec
30 Return: processInput

Listing 4: Semantische
Produktionen

27 PARSER_BEGIN(HelloWorld)
28
29 package hello;
30
31 public class HelloWorld {
32   private static String iTitle, iFirstname, iLastname;
33
34   public static void main(String args[]) throws ParseException {
35     HelloWorld parser = new HelloWorld(System.in);
36     parser.processInput();
37     parser.doHello();
38   }
39
40   private void doHello() {
41     System.out.println("Hello " + iTitle + " " + iFirstname + " " + iLastname);
42   }
43 }
44
45 PARSER_END(HelloWorld)
79
80 void titleSpec() :
81 { }
82 {
83   <TITLE> <EQ> <STRING_LITERAL>
84   { iTitle = getToken(0).image; }
85 }
86
87 void firstnameSpec() :
88 { }
89 {
90   <FIRSTNAME> <EQ> <STRING_LITERAL>
91   { iFirstname = getToken(0).image; }
92 }
93
94 void lastnameSpec() :
95 { }
96 {
97   <LASTNAME> <EQ> <STRING_LITERAL>
98   { iLastname = getToken(0).image; }
99 }

Parser für Programmiersprachen bauen typischerweise Bäume auf, die ein Backend danach weiterverarbeitet. Die semantische Aktion besteht in diesem Fall darin, das Token am passenden Ort im Baum einzuhängen. Für einfachere Fälle eignet sich die direkte Verarbeitung. Das Hello-World-Beispiel speichert den Wert des Token einfach in einer Stringvariablen. Listing 5 zeigt die gegenüber Listing 4 entsprechend geänderten Codeabschnitte.

Abbildung 1: Nach der Generierung der Parser-Dateien gibt das Tool JJTree den erzeugten Baum aus.

Die Klasse »HelloWorld« besitzt in dieser Implementation einige Felder (Zeile 32) und eine Methode »doHello()«, um das Ergebnis auszugeben. Interessanter sind aber die Zeilen 84, 91 und 98. Sie enthalten die hier wichtigen semantischen Aktionen. Das Programm speichert den Wert des Token in den Instanzvariablen »iTitle«, »iFirstname« und »iLastname«. Die »getToken()«-Methode gibt mit dem Argument 0 das bereits verarbeitete Token zurück. Bei größeren Argumenten (1, 2 ...) liefert der Tokenmanager die folgenden Token.

Abbildung 2: Die Grammatik des Beispiels in BNF-Notation als HTML-Ansicht.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Wir können auch anders

    Bisher vorgestellte Programme waren in funktionaler Weise implementiert. Schemes Stärken liegen zwar hauptsächlich in diesem Bereich, jedoch gibt es auch die Möglichkeit, objektorientiert vorzugehen.

  • Hello, World!

    Programmiersprachen, Bibliotheken, Tools, Entwicklungsumgebungen: Das Linux-Magazin widmet sich in einer eigenen Rubrik den Fragen rund ums Programmieren.

  • Haskell

    Haskell ist keine Skriptsprache, sondern wird in der Regel kompiliert. Mit einigen Handgriffen lassen sich aber Shellskripte in die funktionale Sprache einbinden. Haskells starkes Typensystem greift dann ein, um Fehler durch Argumente in falscher Anzahl oder Art zu verhindern.

  • Shell scripting with type-safety using Haskell

    Why is scripting usually done in dynamically typed languages? This article applies strong typing in Haskell to shell programs. The end result can still be light-weight but also save time by reducing runtime errors.

  • Übersetzungskünstler

    Lexer und Parser in Perl schreiben ist keineswegs langbärtigen Gurus vorbehalten. Am Beispiel eines mathematischen Formelparsers nimmt dieser Perl-Snapshot die Angst vor Token und RPN.

comments powered by Disqus

Stellenmarkt

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.