Java lernen durch Ausprobieren!

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Interpreter zusammen mit Testprogramm ======
<WRAP center round tip 60%>
Nachfolgend der fertige Interpreter zusammen mit einem kleinen Testprogramm. \\ 
Die [[..:start|Beschreibung des Interpreters findest Du hier.]]
</WRAP>


<HTML>
<div class="java-online" style="height: 80vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'Interpretertest', 'speed': 'max'}">

<script type="text/plain" title="Testprogramm.java">
String text = "1 + 2 * (4 * a - 3 * b)";
			
println("Eingabetext:\n" + text, Color.lightgray);
			
Lexer l = new Lexer(text);
			
l.lex();

println("\nTokens:\n" + l.toString(), Color.lightyellow);
			
Parser p = new Parser(l.getTokenListe());
			
p.parse();
			
println("\nParsebaum:\n" + p.toString(), Color.lightblue);

Interpreter i = new Interpreter();
i.belegeVariable("a", 5);
i.belegeVariable("b", 2);

println("Variablenbelegung: \n" + i.getVariablenBelegung());
println("\nTermwert:\n" + i.interpretiere(p.getWurzel()));
</script>

<script type="text/plain" title="Interpreter.java">
public class Interpreter {
 
	/**
	 * Speichert Zuordnungen von Variablenbezeichnern zu Werten:
	 */
  	private HashMap<String, Double> variablenbelegung = new HashMap<>();
 
	/**
	 * Belegt die Variable mit Bezeichner bezeichner mit dem Wert wert.
	 * 
	 * @param bezeichner
	 *            Bezeichner der Variablen
	 * @param wert
	 *            Wert der Variablen
	 */
  	public void belegeVariable(String bezeichner, double wert) {
    		variablenbelegung.put(bezeichner, wert);
  	}
   
   public String getVariablenBelegung() {
      return variablenbelegung.toString();
   }

	/**
	 * Berechnet - ausgehend vom übergebenen Knoten - den Wert des Terms, der
	 * durch den Knoten und den darunterhängenden Teilbaum gegeben ist.
	 * 
	 * @param knoten
	 *            Wurzel des Teilbaums, dessen Termwert berechnet werden soll
	 * @return Wert des Terms
	 */
  	public double interpretiere(Knoten knoten) {
 
      switch(knoten.getToken().getTokenType()) {
         case plus : 
            return interpretiere(knoten.getLinks())
               + interpretiere(knoten.getRechts());

         case minus : 
            return interpretiere(knoten.getLinks())
               - interpretiere(knoten.getRechts());

         case mal : 
            return interpretiere(knoten.getLinks())
               * interpretiere(knoten.getRechts());

         case geteilt : 
            return interpretiere(knoten.getLinks())
               / interpretiere(knoten.getRechts());

         case negation : 
            return - interpretiere(knoten.getLinks());

         case text : 

            String variablenbezeichner = knoten.getToken().getText();

            Double wert = variablenbelegung.get(variablenbezeichner);

            if(wert == null) {
               println("Die Belegung der Variable "
                     + variablenbezeichner + " ist nicht bekannt.", Color.red);
               System.exit(0);
            }

            return wert;

         case zahl : 
            return knoten.getToken().getZahl();

         default : 
            return 0; // sollte nie vorkommen
      }
 
  	}
     
   
}
</script>

<script type="text/plain" title="Parser.java">
public class Parser {
 
	/**
	 * Liste, die vom Lexer kommt
	 */
  	private ArrayList<Token> tokenListe;
 
	/**
	 * Zur Speicherung des Parse-Baums (Abstract Syntax Tree) reicht es, die
	 * Wurzel zu speichern. Über sie bekommt man jeden beliebigen Knoten
	 * darunter.
	 */
  	private Knoten wurzel;
 
	/**
	 * Nummer des Tokens, das gerade analysiert wird (von 0 beginnend)
	 */
  	private int position;
 
	/**
	 * 
	 * @param tokenListe
	 *            Liste von Tokens, die geparst werden soll
	 */
  	public Parser(ArrayList<Token> tokenListe) {
  
    		this.tokenListe = tokenListe;
 
    		position = 0;
 
  	}
 
	/**
	 * Parst die dem Konstruktor übergebene Liste von Tokens und gibt einen
	 * Parse-Baum (Abstract Syntax Tree) zurück.
	 * 
	 * @return Parse-Baum (Abstract Syntax Tree)
	 * 
	 *             Falls die Liste der Tokens nicht der Syntax entspricht
	 */
  	public Knoten parse() {
 
    		wurzel = summeDifferenz(); // Versuche, eine Summe oder Differenz zu finden
 
    		return wurzel;
 
  	}
 
	/**
	 * Versucht, eine Summe oder Differenz zu parsen. Parst zunächst den ersten
	 * Operanden (unter der Annahme, dass es eine Multiplikation oder Division
	 * ist) und sieht dann nach, ob ein Pluszeichen oder ein Minuszeichen kommt.
	 * Falls "ja", parst es den zweiten Operanden und fügt alle drei zu einem
	 * Baum zusammen.
	 * 
	 * Folgt ein weiteres Plus oder Minus, wird der Baum als erster Operand
	 * einer weiteren Summe/Differenz gedeuet und nach dem zweiten Operanden
	 * dazu gesucht usw.
	 * 
	 * Folgt kein weiteres Plus oder Minus, so endet die Methode und der
	 * aktuelle Baum wird zurückgegeben.
	 * 
	 * @return Geparster Teilbaum
	 * 
	 */
  	private Knoten summeDifferenz() {
 
    		Knoten linkerOperand = produktQuotient(); // Versuche, eine Multiplikation
												// oder Division zu finden
 
    		while(peek() == TokenType.plus || peek() == TokenType.minus) {
 
      			Token operator = nextToken();
 
      			Knoten rechterOperand = produktQuotient();
 
      			Knoten neuerKnoten = new Knoten(operator, linkerOperand,
       					rechterOperand);
 
      			linkerOperand = neuerKnoten;
 
    		}
 
    		return linkerOperand;
 
  	}
 
	/**
	 * Wie PlusMinus, jedoch für Mal und geteilt. Als erster bzw. zweiter
	 * Operand wird nach einem einfachen Term (Klammerterm, Zahl, Variable oder
	 * Negation) gesucht.
	 * 
	 * @return
	 * 
	 */
  	private Knoten produktQuotient() {
 
    		Knoten linkerOperand = einfacherTerm();
 
    		while(peek() == TokenType.mal || peek() == TokenType.geteilt) {
 
      			Token operator = nextToken();
 
      			Knoten rechterOperand = einfacherTerm();
 
      			Knoten neuerKnoten = new Knoten(operator, linkerOperand,
       					rechterOperand);
 
      			linkerOperand = neuerKnoten;
 
    		}
 
    		return linkerOperand;
 
  	}
 
  	private Knoten einfacherTerm() {
 
    		if(peek() == null) {
       		println("Parserfehler: unerwartetes Ende");
         System.exit(0);
    		}
 
    		switch(peek()) {
       		case klammerAuf : // Klammerterm
         			nextToken();
         			Knoten knoten = summeDifferenz(); // In der Klammer kann sich wieder eine
											// Summe/Differenz befinden...
         			erwarte(TokenType.klammerZu); // Überliest die schließende Klammer
         			return knoten;
       		case text : 
         			return new Knoten(nextToken());
       		case zahl : 
         			return new Knoten(nextToken());
       		case minus : 
         			Knoten knoten1 = new Knoten(new Token(TokenType.negation));
         			nextToken(); // überliest das Minuszeichen
         			knoten1.setLinks(einfacherTerm()); // die Negation wirkt auf den einfachen
										// Term danach
         			return knoten1;
       		default : 
         			println("Das Token " + peek() + " ist fehl am Platz.");
            System.exit(0);
    		}
 
  	}
 
	/**
	 * Gibt das nächste Token aus der Tokenliste zurück, erhöht aber nicht die
	 * Leseposition
	 * 
	 * @return
	 */
  	public TokenType peek() {
 
    		if(position < tokenListe.size()) {
 
      			return tokenListe.get(position).getTokenType();
 
    		}
 
    		return null;
  	}
 
	/**
	 * Gibt das nächste Token aus der Tokenliste zurück und erhöht(!) die
	 * Leseposition
	 * 
	 * @return
	 */
  	public Token nextToken() {
 
    		if(position < tokenListe.size()) {
 
      			Token token = tokenListe.get(position);
 
      			position++;
 
      			return token;
 
    		}
 
    		return null;
 
  	}
 
	/**
	 * Wirft eine Exception, wenn das nächste Token in der Tokenliste nicht dem
	 * übergebenen Typ entspricht.
	 * 
	 * @param tokenType
	 * 
	 */
  	public void erwarte(TokenType tokenType) {
 
    		if(peek() == null) {
      			println(
       					"Parserfehler: unerwartetes Ende. Erwartet wird: "
        							+ tokenType);
         System.exit(0);
    		}
 
    		if(peek() != tokenType) {
      			println("Parserfehler: Erwartet wird: " + tokenType);
         System.exit(0);
    		}
 
    		nextToken();
 
  	}
 
	/**
	 * Nur zu Debuggingzwecken
	 */
  	public String toString() {
 
    		return toString(wurzel, "");
  
  	}
 
	/**
	 * Traversiert vom übergebenen Knoten ausgehend den Teilbaum in pre-order
	 * Reihenfolge, d.h. zuerst wird der Konten selbst besucht, dann der
	 * komplette linke Teilbaum, der dranhängt, dann der komplette rechte
	 * Teilbaum, der dranhängt.
	 * 
	 * @param knoten
	 * @param einruecken
	 * @param sb
	 */
  	private String toString(Knoten knoten, String einruecken) {

      String sb = "";
      
      sb += einruecken;
      sb += knoten.getToken().toString() + "\n";

      if(knoten.getLinks() != null) {
         sb += toString(knoten.getLinks(), einruecken + "   ");
      }

      if(knoten.getRechts() != null) {
         sb += toString(knoten.getRechts(), einruecken + "   ");
      }
 
      return sb;

  	}
 
  	public Knoten getWurzel() {
    		return wurzel;
  	}
 
}
</script>

<script type="text/plain" title="Knoten.java">
public class Knoten {
 
	/**
	 * Im Token steckt der Inhalt des Knotens drin, also ein Operator, eine Zahl oder ein 
	 * Variablenbezeichner. Der Einfachheit halber verwenden wir hier die Klasse Token. 
	 */
	private Token token; 
 
	/**
	 * Kindknoten linkerhand
	 */
	private Knoten links;
 
	/**
	 * Kindknoten rechterhand
	 */
	private Knoten rechts;
 
	public Knoten(Token token) {
		this.token = token;
	}
 
	public Knoten(Token token, Knoten linkerOperand, Knoten rechterOperand) {
		this.token = token;
		this.links = linkerOperand;
		this.rechts = rechterOperand;
	}
 
	public Knoten getLinks() {
		return links;
	}
 
	public void setLinks(Knoten links) {
		this.links = links;
	}
 
	public Knoten getRechts() {
		return rechts;
	}
 
	public void setRechts(Knoten rechts) {
		this.rechts = rechts;
	}
 
	public Token getToken() {
		return token;
	}
 
}
</script>

<script type="text/plain" title="Lexer.java">
public class Lexer {
 
	/**
	 * Die Zeichenkette wird von links nach rechts abgearbeitet. Hier ist
	 * gespeichert, das wievielte Zeichen gerade angesehen wird:
	 */
  	private int position;
 
	/**
	 * Liste zur Speicherung der ermittelten Tokens
	 */
  	private ArrayList<Token> tokenListe;
 
	/**
	 * Wir speichern den Programmtext in einem Attribut der Klasse, damit er
	 * nachher nicht von Methode zu Methode weitergereicht werden muss.
	 */
  	private String text;
 
	/**
	 * 
	 * @param text
	 *            Programmtext, der in Tokens zerlegt werden soll
	 */
  	public Lexer(String text) {
 
    		this.text = text;
 
    		position = 0; // Wir beginnen mit dem Zeichen ganz links
 
    		tokenListe = new ArrayList<Token>(); // Liste zur Aufnahme der gelesenen Tokens instanzieren
 
  	}

/**
	 * Zerlegt den Programmtext, der dem Konstruktor übergeben wurde
	 * 
	 * @return Liste mit Tokens
	 * @throws Exception
	 *             Eine Exception wird ausgelöst, wenn der Programmtext Passagen
	 *             enthält, aus denen keine Token gebildet werden können.
	 */
  	public ArrayList<Token> lex() {
 
		/**
		 * Wiederholung, die den Programmtext von links nach rechts abarbeitet:
		 */
    		while(position < text.length()) {
 
			/**
			 * peek() liest das nächste Zeichen im Programmtext, erhöht die
			 * Variable position aber nicht. Ruft man peek() mehrmals
			 * hintereinander auf, liefert es also immer dasselbe Zeichen.
			 */
      			char c = peek();
 
      			if(istZiffer(c)) {
        				lexZahl();
      			} else if(istBuchstabe(c)) {
        				lexText();
      			} else {
        				switch(c) {
           				case '+' : 
             					addToken(TokenType.plus);
             					break;
           				case '-' : 
             					addToken(TokenType.minus);
             					break;
           				case '*' : 
             					addToken(TokenType.mal);
             					break;
           				case '/' : 
             					addToken(TokenType.geteilt);
             					break;
           				case '(' : 
             					addToken(TokenType.klammerAuf);
             					break;
           				case ')' : 
             					addToken(TokenType.klammerZu);
             					break;
           				case ' ' : 
           				case '\n' : 
           				case '\r' : 
					// Leerzeichen werden einfach überlesen
             					break;
           				default : 
             					println("Fehler: Der Lexer kann mit dem Zeichen '" + c
                 							+ "' an Position " + position + " nichts anfangen.");
                  System.exit(0);
        				}
 
        				position++; // Das von peek() oben gelesene Zeichen ist
							// verarbeitet, also jetzt das nächste holen.
 
      			}
 
    		}
 
    		return tokenListe;
 
  	}

     	/**
	 * 
	 * @param c
	 *            beliebiges zeichen
	 * @return true, falls c eine Ziffer ist
	 */
  	private boolean istZiffer(char c) {
    		return c >= '0' && c <= '9';
  	}

	/**
	 * 
	 * @param c
	 *            beliebiges Zeichen
	 * @return true, falls c ein Buchstabe ist
	 */
  	private boolean istBuchstabe(char c) {
    		return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
  	}


/**
	 * Die Methode lexText geht davon aus, dass das nächste zu verarbeitende
	 * Zeichen ein Buchstabe ist. Solange weitere Buchstaben oder Ziffern
	 * kommen, liest sie sie und setzt sie zu einem Variablennamen zusammen.
	 */
  	private void lexText() {
 
    		String variablenBezeichner = "";
 
    		do {
      			char c = peek();
      			variablenBezeichner += c;
      			position++;
    		} while(Character.isLetter(peek()) || Character.isDigit(peek()) || peek() == '_');
 
    		tokenListe.add(new Token(variablenBezeichner));
 
  	}
 
	/**
	 * Die Methode lexZahl liest eine Zahl
	 */
  	private void lexZahl() {
 
    		String zahlAlsString = "";
 
    		do {
      			char c = peek();
      			zahlAlsString += c;
      			position++;
    		} while(Character.isDigit(peek()) || peek() == '.');
 
		/**
		 * Hier machen wir es uns leicht und lassen Java den String in eine Zahl
		 * konvertieren. Die Methode parseDouble ist für sich genommen natürlich
		 * auch ein Lexer.
		 */
    		double zahl = Double.parseDouble(zahlAlsString);
 
    		tokenListe.add(new Token(zahl));
 
  	}

   /**
	 * Fügt der tokenListe das übergebene Token hinzu
	 * 
	 * @param tokenType
	 */
  	private void addToken(TokenType tokenType) {
    		tokenListe.add(new Token(tokenType));
 
  	}
   
   /**
	 * peek() liest das nächste Zeichen im Programmtext, erhöht die Variable
	 * position aber nicht. Ruft man peek() mehrmals hintereinander auf, liefert
	 * es also immer dasselbe Zeichen.
	 * 
	 * @return nächstes Zeichen im Programmtext
	 */
  	private char peek() {
    		if(position < text.length()) {
      			return text.charAt(position);
    		} else {
      			return (char)0x;
    		}
  	}
   
/**
	 * Vorsicht: Die übergebene Liste ist nur dann gefüllt, wenn zuvor die
	 * Methode lex aufgerufen wurde.
	 * 
	 * @return Liste mit den Tokens, in die der Lexer den Programmtext zerlegt
	 *         hat.
	 */
  	public ArrayList<Token> getTokenListe() {
    		return tokenListe;
  	}
 
	/**
	 * Nur zu Debuggingzwecken
	 */
  	public String toString() {
 
    		String s = "";
 
    		for(Token token : tokenListe) {
      			s += token.toString() + " ";
    		}
 
    		if(!s.isEmpty()) {
      			s = s.substring(0, s.length() - 1);
    		}
 
    		return s;
 
  	}


}
</script>

<script type="text/plain" title="TokenType, Token.java">
public enum TokenType {
  	zahl, text, plus, minus, mal, geteilt, klammerAuf, klammerZu,
 
	/**
	 * Nur als Knotentyp für Knoten des Syntaxbaums:
	 */
  	negation
}

public class Token {
 
  	private TokenType tokenType; 		// Art des Tokens (z.B. zahl, klammerAuf usw.)
  	private double zahl;				// Wird nur belegt, wenn tokenType == zahl
  	private String text;	// Wird nur belegt, falls tokenType == bezeichner
 
  	public Token(double zahl) {
    		this.zahl = zahl;
    		tokenType = TokenType.zahl;
  	}
 
  	public Token(String text) {
    		this.text = text;
    		tokenType = TokenType.text;
  	}
 
  	public Token(TokenType tokenType) {
    		this.tokenType = tokenType;
  	}
 
  	public TokenType getTokenType() {
    		return tokenType;
  	}
 
  	public double getZahl() {
    		return zahl;
  	}
 
  	public String getText() {
    		return text;
  	}
 
	/**
	 * Die toString()-Methode dient nur Debuggingzwecken
	 */
  	@Override
  	public String toString() {
 
    		String s = "" + tokenType;
 
    		switch(tokenType) {
       		case zahl : 
         			s += "[" + zahl + "]";
         			break;
       		case text : 
         			s += "[" + text + "]";
         			break;
       		default : 
         			break;
    		}
 
    		return s;
 
  	}
 
}
</script>

</div>
</HTML>