Der Parser analysiert die Liste der Tokens anhand einer gegebenen Syntax und erstellt eine Baumstruktur ("Abstract Syntax Tree"), die die Bedeutung ("Semantik") des Programmtextes wiedergibt. Die Syntax unserer einfachen Beispielsprache entspricht der einfacher mathematischer Terme:

• Eine Summe besteht aus dem linken Summanden gefolgt vom Zeichen + gefolgt vom rechten Summanden
• Entspechend mit Produkt, Differenz und Quotient
• Es gilt "Punkt vor Strich"
• Teilterme in Klammern werden zuerst berechnet.
• Steht ein Minuszeichen vor einem Term, so wird der Termwert mit -1 multipliziert (Negation)

Wie man eine solche Syntax besser aufschreibt (Backus-Naur-Form) beschreibe ich später. Für das Verständnis des Compilers reicht die Beschreibung oben.

Aus dem Term 1 + 2 * (4 * -a1 - 3) macht der Lexer folgende Tokens:

zahl[1.0] plus zahl[2.0] mal klammerAuf zahl[4.0] mal minus text[a1] minus zahl[3.0] klammerZu

Man beachte, dass der Lexer noch nicht zwischen einer Differenz (zweites "minus") und einer Negation (erstes "Minus") unterscheiden kann. Der Parser erzeugt aus der Liste von Tokens folgende Baumstruktur:

Die rechteckig umrahmten Teile des Baums nennt man Knoten, die Verbindungslinien Kanten. Der Knoten ganz oben heißt Wurzel. Der Baum wird traditionell mit der Wurzel nach oben gezeichnet, da man beim Zeichnen auf Papier anfangs nicht weiß, wie hoch der Baum wird. Für unsere einfache Programmiersprache hat jeder Knoten maximal 2 Kanten, wir können die Knoten also durch folgende klasse abbilden:

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;
	}
 
}