Auswertung von Ausdrücken in Java

  Zum Interpretieren oder übersetzen eines Ausdrucks (Terms) wird
  dieser in lexikalische Einheiten (Token, Wörter) zerlegt, die
  dann von einem syntaktischen Zerleger in ein "Symbol"
  (Syntaxbaum) strukturiert werden. Dieses Symbol kann dann
  ausgewertet oder in eine andere Darstellung übersetzt werden.
  
  Die syntaktische Zerlegung entspricht den Regeln für den Aufbau
  eines Ausdrucks, die oft durch sogenannte "Produktionsregeln" der
  EBNF (erweiterte Backus-Nauer-Form) gegeben werden, die
  manchmal linksrekursiv sind.
  Beim Schreiben eines syntaktischen Analysators bereiten diese
  linksrekursiven Produktionsregeln oft Kopfzerbrechen, denn es ist
  nicht klar, wie hier eine unbeschränkte Rekursion vermieden
  werden kann. Die Lösung ist es, sie in rechtsrekursive
  Produktionsregeln umzuschreiben:
  Die Addition mit einem binären zwischengestellten Operator ist
  beispielsweise linksassoziativ. Allerdings ist es technisch
  einfacher, rechtsassoziativ zu analysieren. Daher analysiert
  man das ganze rechtsassoziativ und realisiert das Analysat
  linksassoziativ.
  Eine gewuenschte linksassoziative Grammatik lautet
  beispielsweise:
<numeral> ::= '2' | '4' | '5'.
<expression> ::= <numeral> | <expression> '+' <numeral>.
Startsymbol: <expression>.
  Zum Analysieren mit einem rekursiv absteigenden Analysator
  verwendet man aber lieber folgende Grammatik:
<numeral> ::= '2' | '4' | '5'.
<expression> ::= <numeral>[ '+' <expression> ].
Startsymbol: <expression>.
  Das kann man auch iterativ schreiben:
<numeral> ::= '2' | '4' | '5'.
<expression> ::= <numeral>{ '+' <numeral> }.
Startsymbol: <expression>.
  Dabei baut man aber ein Analysat im Sinne der ersten
  Grammatik auf. Beispielcode hierzu:
class Scan
{ final static java.lang.String source = "5+4+2)";
  static int pos = 0;
  static char get(){ return source.charAt( pos++ ); }}
  
class Parse
{ 
  static int numeral(){ return Scan.get() - '0'; }
  
  static int expression(){ int result = numeral();
    while( '+' == Scan.get() )result += numeral();
    return result; }}
  
public final class Start
{ 
  public static void main( final java.lang.String[] args )
  { java.lang.System.out.println( Parse.expression() ); }}
  Um nun noch Ausdrücke mit höherem Vorrange lesen zu 
  können, kann die Grammatik erweitert werden.
<numeral> ::= '2' | '4' | '5'.
<product> ::= <numeral> | <product> '*' <numeral>.
<sum> ::= <product> | <sum> '+' <product>.
Startsymbol: <sum>.
  In iterativer Schreibweise:
  
<numeral> ::= '2' | '4' | '5'.
<product> ::= <numeral>{ '*' <numeral> }.
<sum> ::= <product>{ '+' <product> }.
Startsymbol: <sum>.
  In Java:
class Scan
{ final static java.lang.String source = "5+4*2)";
  static int pos = 0;
  static char get( final boolean advance )
  { return source.charAt( advance ? pos++ : pos ); }}
  
class Parse
{ 
  static int numeral(){ return Scan.get( true ) - '0'; }
  
  static int product(){ int result = numeral();
    while( '*' == Scan.get( false )){ Scan.get( true ); result *= numeral(); }
    return result; }
  static int sum(){ int result = product();
    while( '+' == Scan.get( true ))result += product();
    return result; }}
  
public final class Start
{ 
  public static void main( final java.lang.String[] args )
  { java.lang.System.out.println( Parse.sum() ); }}
  Übungsaufgaben
  - Welche Ausgabe erzeugen die obigen Programme jeweils?
  - Erweitern Sie die letzte Grammatik und das letzte 
    Programm um die Subtraktion.
  - Erweitern Sie das Ergebnis der letzten Übungsaufgabe
    um die Division.
  
  - Erweitern Sie das Ergebnis der letzten Übungsaufgabe
    so, daß auch Zahlen mit mehreren Ziffern akzeptiert
    werden.
  - Erweitern Sie das Ergebnis der letzten Übungsaufgabe
    so, daß in den Termen auch Leerräume (Leerzeichen)
    in der üblichen Weise verwendet werden können.
  - Erweitern Sie das Ergebnis der letzten Übungsaufgabe
    so, daß auch eingeklammerte Terme akzeptiert werden.
    ("(2+4)*5)" sollte das Ergebnis "30" liefern.)
  
  - Erweitern Sie das Ergebnis der letzten Übungsaufgabe
    so, daß auch das Vorzeichen "-" erkannt wird.
  
  - Erweitern Sie das Ergebnis der letzten Übungsaufgabe
    so, daß weitere Operatoren und Methoden akzeptiert
    werden.
  - Erweitern Sie das Ergebnis der letzten Übungsaufgabe so,
    daß sinnvolle Fehlermeldungen für alle möglichen
    Eingaben, die nicht den Regeln der Eingabesprache
    entsprechen, erzeugt werden.
  - Erweitern Sie das Ergebnis der letzten Übungsaufgabe so,
    daß die Fehlermeldungen, die Stelle anzeigen, an der
    der Fehler bemerkt wurde. Es sollen auch Ausdrücke
    akzeptiert werden, die über mehrere Zeilen gehen und
    bei Fehlern die Nummer der Zeile mit dem Fehler 
    angezeigt werden.
  Neben den rekursiv absteigenden Zergliederern gibt es auch
  noch die Zweikellerzergliederer. Einen solchen habe ich in
  meinen kleinen BASIC-Interpretierer gebaut:
https://www.purl.org/stefan_ram/java/RamBasic657.java
  Mein Zergliederer ist insofern recht »konservativ« als
  er einem alten Verfahren von Bauer folgt:
      Sequential Formula Translation
      K. Samelson and F. L. Bauer
      Communications of the ACM
      Volume 3,  Issue 2 (February 1960)
      Pages: 76 - 83
      ISSN:0001-0782
  Den Algorithmus habe ich etwas abgewandelt in der Klasse
  »Enroller« notiert:
class Enroller
{ public static void enrollOperator
  ( final OperatorSymbol self,
    final OperatorStack operatorStack,
    final DesignationStack designationStack )
  { while
    ( operatorStack.containsAnOperator() &&
      operatorStack.top().leftPriority() > self.rightPriority() )
    { OperatorSymbol operator = operatorStack.pop(); 
      operator.reduce( operatorStack, designationStack ); }
    operatorStack.accept( self ); }
  public static void enrollDesignation
  ( final Designation self,
    final OperatorStack operatorStack,
    final DesignationStack designationStack )
  { designationStack.accept( self ); }}
  Wenn man sich die Parameterdeklarationen und die langen
  Bezeichner wegdenkt, ist dieser Code wirklich winzig.
  In Worten: 
  Ich verwende zwei Keller: einen Operatorkeller und einen
  Wertekeller (»designationStack«). Dann wird das jeweils nächste
  Symbol aus der Eingabe hinzugefügt:
    - wenn es ein Operator ist, dann:
        - Solange der Operator auf dem Operatorkeller höheren
          Vorrang hat, wende ihn auf seine Argumente 
          auf dem Wertekeller an (»reduce«) und lege das Ergebnis
          dann wieder auf den Wertekeller. (»reduce« ist für
          jeden Operator anders, für »+« ersetzt es
          beispielsweise  die beiden oberen Werte durch ihre Summe.)
        - Lege den neuen Operator auf den Operatorkeller
    - wenn es ein Operand ist, dann
        - Lege ihn auf dem Argumentkeller
  Das Verfahren von Samelson und Bauer wird oft benutzt
  und gelehrt, aber die obige Quelle wird dabei selten 
  angegeben.
  
Glossar:
 "NLR grammar" = "non left-recursive grammar"
 pre-order traversal = (node, left, right)
 
Quellen:
JEP - Java Mathematical Expression Parser
http://www.singularsys.com/jep/
Steven Metsker: Building Parsers with Java.
Addison-Wesley 2001, ISBN 0201719622.
A.W. Appel: Modern Compiler Implementation in Java. 
Cambridge University Press 1998, ISBN 0521586542.
Niklaus Wirth: Grundlagen und Techniken des Compilerbaus.
ISBN 3486243748
http://www.oberon.ethz.ch/WirthPubl/CBEAll.pdf
Aho, Sethi, Ullman: Compilerbau, Tl. 1. Oldenbourg 1999
ISBN 3486252941
Aho, Sethi, Ullman: Compilerbau, Tl. 2. Oldenbourg 1999
ISBN 3486252666
  Steven Metsker
  Building Parsers with Java
  Addison-Wesley 2001
  http://www.awprofessional.com/title/0201719622
Compiler-Compiler JACCIE
http://www2-data.informatik.unibw-muenchen.de/Research/Tools/JACCIE/downloadEN/download.html
  Implementing a scripting engine
http://www.flipcode.com/articles/scripting_issue01.shtml
  Ein Einführung in den Compilerbau mit modernen Standardwerkzeugen:
http://staff.polito.it/silvano.rivoira/HowToWriteYourOwnCompiler.htm
Quellen zu speziellen Einzelthemen:
Quellen zu BNF:
Erklärung einer Form der EBNF
https://www.purl.org/stefan_ram/pub/bnf-ebnf
  Die ursprüngliche BNF findet sich AFAIK in
Naur, Peter (ed.), "Revised Report on the Algorithmic Language ALGOL 60.",
Communications of the ACM, Vol. 3 No.5, pp. 299-314, May 1960.
  Eine aktuelle EBNF-Variante in:
ISO/IEC 14977:1996(E), Information technology: Syntactic metalanguage ISO/I
EC 14977 : 1996(E), EXTENDED BNF
  oder:
Crocker, Overell, "Augmented BNF for Syntax Specifications: ABNF", RFC 2234
, November 1997.
Quellen und BNF zu PL/0:
http://www.inf.hs-zigr.de/~wagenkn/TI/Berechenbarkeit/rekabstieg.html
http://www.246.dk/pl0.html
http://www.inf.hs-zigr.de/~wagenkn/TI/Berechenbarkeit/rekabstieg.html
  
  Ein PL/0-Übersetzer in Pascal:
http://www.246.dk/pl0.html
  Zu PL/0 (mit PL/0-Synax [sic!]):
http://www.inf.hs-zigr.de/~wagenkn/TI/Berechenbarkeit/rekabstieg.html
  Einführung mit PL/0:
http://www.htw-dresden.de/~s2536/Compiler/Vorlesung_CI.pdf
http://www.htw-dresden.de/~s2536/Compiler/Vorlesung_CI.pdf
Guide to the PL/0 Compiler, http://www.cs.rochester.edu/courses/254/PLzero/guide.pdf 
PL0/E - Pascal-ähnliche Programmiersprache (executables only), http://www.s-direktnet.de/homepages/neumann/Data/pl0/pl0.zip 
Parboiled is an open-source Java library released under an Apache License. It provides support for defining PEG parsers directly in Java source code.