Syntax und Operatorbäume

RedWing

Erfahrenes Mitglied
Hallo,

hier mal ein Bsp für einen Parser der die Bindung eines arithmethischen
Ausdrucks erkennt und das Ergebniss berechnet.
Dachte mir eignet sich mal ganz gutes Bsp für ein das Forum...

Also als erstes brauchen wir ein paar imports:
Code:
import java.util.Vector;
import java.util.StringTokenizer;
import java.lang.IllegalArgumentException;

Danach brauchen wir ne geeignete DS um den Operatorbaum aufzubauen,
mit dessen Hilfe wir später den Ausdruck berechnen:
(Intressant ist hierbei die Methode getResult() die das Ergebniss
berechnet...)
Code:
/**
 * the data structure which represents the operator tree
 */
class OpTree{
		private OpTree right;
		private OpTree left;
		private String value;
		
		public OpTree(String value){
			right = null;
			left = null;
			this.value = value;
		}

		public void setLeftSon(OpTree left){
			this.left = left;
		}

		public void setRightSon(OpTree right){
			this.right = right;
		}

		/**
		 * generates the result from the created OpTree 
		 * traverses the tree in postorder
		 */
		public int getResult(){
			if(left == null && right == null){
				int res = Integer.parseInt(value);
				return res;
			}
			else{
				if(value.equals("+"))
					return left.getResult() + right.getResult();
				else if(value.equals("-"))
					return left.getResult() - right.getResult();
				else if(value.equals("/"))
					return left.getResult() / right.getResult();
				else
					return left.getResult() * right.getResult();
			}
				
		}
}

Aber zuerst muessen wir den Syntaxbaum aufbauen welcher dann
auch gleich intern den Operatorbaum nach folgende Grammatik kreirt:

Code:
 * expressiom ::= term | term '+' expression | term '-' expression
 * term ::= factor | factor '*' term | factor '/' term 
 * factor ::= int | '(' expression ')'

Code:
class SyntaxTree{
	
		private Vector<String> elements;
		private OpTree root;
		
		/**
		 * returns the postion of each closing bracket which belongs to a opening bracket
		 * if there is no closing bracket a  IllegalArgumentException is thrown
		 */
		private int getClosingBracketPosition(Vector<String> tooperate, int beginIndex) throws IllegalArgumentException{
			int number_opening_brackets = 0;
			int number_closing_brackets = 0;
			int ret = beginIndex;
			while(ret < tooperate.size()){
				if(tooperate.get(ret).equals("(")) number_opening_brackets++;
				if(tooperate.get(ret).equals(")")) number_closing_brackets++;
				if(number_opening_brackets ==  number_closing_brackets) break;	
				ret++;
			}
			if(number_opening_brackets != number_closing_brackets)
				throw new IllegalArgumentException("There was a bracket missmatch");
			return ret;
		}

		/**
		 * creates the non terminal expression according to the grammar rules
		 */
		private void expression(Vector<String> tooperate) throws IllegalArgumentException{
			term(tooperate);
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("+") || tooperate.get(0).equals("-")){
					OpTree oldRoot = root;
					root = new OpTree(tooperate.get(0));
					root.setLeftSon(oldRoot);
					OpTree oldRoot2 = root;
					tooperate.remove(0);
					expression(tooperate);
					oldRoot2.setRightSon(root);
					root = oldRoot2;
				}
			}
		}
		
		/**
		 * creates the non terminal term according to the grammar rules
		 */
		private void term(Vector<String> tooperate) throws IllegalArgumentException{
			factor(tooperate);
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("*") || tooperate.get(0).equals("/")){
					OpTree oldRoot = root;
					root = new OpTree(tooperate.get(0));
					root.setLeftSon(oldRoot);
					tooperate.remove(0);
					OpTree oldRoot2 = root;
					term(tooperate);
					oldRoot2.setRightSon(root);
					root = oldRoot2;
				}
			}
		}
	
		/**
		 * creates the non terminal factor according to the grammar rules
		 * if one input value which is expected as number is no number a   llegalArgumentException is thrown
		 */
		private void factor(Vector<String> tooperate) throws IllegalArgumentException{
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("(")){
					int begin_pos = 0;
					int end_pos = getClosingBracketPosition(tooperate, begin_pos);
					Vector<String> new_expression = new Vector<String>(tooperate.subList(begin_pos + 1, end_pos));
					expression(new_expression);
					for(int i = begin_pos; i <= end_pos; i++)
						tooperate.remove(0);
				}
				else{
					if((tooperate.get(0)).charAt(0) > '9' || (tooperate.get(0)).charAt(0) < '0')
						throw new IllegalArgumentException("No number where a number was expected!");
					root = new OpTree(tooperate.get(0));
					tooperate.remove(0);
				}
			}
		}

		/**
		 * creates a new syntax tree which represent the given grammar 
		 * @param expression the expression from which the syntax tree should be build
		 */
		public SyntaxTree(String expression) throws IllegalArgumentException{
			StringTokenizer token = new StringTokenizer(expression, " ");
                        if(token.countTokens() % 2 == 0) throw new IllegalArgumentException("Unknown Syntax error occured!");
			elements = new Vector<String>();
			while(token.hasMoreTokens())
				elements.add(token.nextToken());
		}
		
		/**
		 * computes the syntax tree and creates the OpTree
		 * @see OpTree
		 */
		void buildTree() throws IllegalArgumentException{
			Vector<String> tooperate = new Vector<String>(elements);
			expression(tooperate);
		}

		int getResult(){
			if(root != null)
				return root.getResult();
			else
				return 0;
		}
}

Und zum Schluss das Testprogramm:

Code:
class Parser{
	public static void main(String[] args){
		String expression = "3 * ( 15 - 6 / ( 2 + 1 ) )";
		try{
                        SyntaxTree t = new SyntaxTree(expression);
			t.buildTree();
			System.out.println(t.getResult());
		}catch(IllegalArgumentException e){
			System.out.println(e.getMessage());
			e.printStackTrace();
		}
	}
}

Brauchbar oder nicht? Nur ein Produkt der Langeweile :)
Verbesserungsvorschläge sind natuerlich willkommen.

Viel Spass damit

RedWing
 
Zuletzt bearbeitet:

kabel2

Erfahrenes Mitglied
oje :) *syntaxanalyse wissen hervorkram*

brauchbar? wer noch parser selbst schreibt ist selber schuld ;)

zu deinem parser (vorsicht, technisch):
ist ein rekursiver abstieg. keine fehlerbehandlung. wenn die grammatik frei von linksrekursion wäre (ist leicht herzustellen), dann ist die grammatik SLL(1) ( untermenge von LL(1) ). so ist sie nicht LL(k) für beliebiges k. dein parser benutzt bereits die linksfaktorisierte grammatik, sonst würde das so nicht funktionieren ;)

ok, falls das jemand bestätigen kann ...

guck dir mal das expression antlr beispiel an. fyc das eclipseprojekt als anhang. zum kompilieren der grammatik brauchst du noch das (sehr schöne) eclipse antlr plugin

ebenfalls viel spass! ;-)
 

Anhänge

  • AntlrExpression.zip
    6,2 KB · Aufrufe: 25

RedWing

Erfahrenes Mitglied
Hey,
dein parser benutzt bereits die linksfaktorisierte grammatik, sonst würde das so nicht funktionieren
War schon so bedacht :)

guck dir mal das expression antlr beispiel an. fyc das eclipseprojekt als anhang. zum kompilieren der grammatik brauchst du noch das (sehr schöne) eclipse antlr plugin

Das is natürlich sehr geschickt das ganze über eine Metasprache zu lösen, bei der man sich aufs wesentliche,
die Grammatik konzentrieren kann.

brauchbar? wer noch parser selbst schreibt ist selber schuld
Die 3 Dinge die man im Leben mal gemacht haben sollte: Ein Kind zeugen, einen Baum pflanzen und nen
Parser schreiben :)

Gruß

RedWing
 

kabel2

Erfahrenes Mitglied
Was ist der Unterschied zwischen Syntaxbäumen und Operatorbäumen?

Welche Überlegung steckt hinter getClosingBracketPosition()? Warum nicht einfach
Code:
tooperate.remove( 0 );
expression( tooperate );
if( tooperate.get( 0 ).equals( ")") ) {
	tooperate.remove( 0 );
} else {
	throw new SyntaxErrorException( ")", tooperate.get( 0 ) );
}
mit
Code:
public class SyntaxErrorException extends RuntimeException {
	
	private String expected;
	private String got;
	
	public SyntaxErrorException(String expected, String got) {
		this.expected= expected;
		this.got= got;
	}
	
	public String toString() {
		return "Syntax Error: expected [" + expected + "] got [" + got + "]";
	}

	private static final long serialVersionUID = -7469838979422601574L;
}
 

RedWing

Erfahrenes Mitglied
Was ist der Unterschied zwischen Syntaxbäumen und Operatorbäumen?

Also ich definiere einen Syntaxbaum als den Ableitungsbaum der aus der gegebenen Grammatik und einen
gegebenen Eingabewort (einschließlich aller Terminalen und Nichtterminalen) gebildet werden kann. Die
Knoten eines Operatorbaums (einschließlich Blätter) werden meiner Ansicht nach aus den Blättern des
Ableitungs bzw Syntaxbaumes gebildet...

Welche Überlegung steckt hinter getClosingBracketPosition()?
Diese Methode verwende ich um aus dem vorhandenen Vector einen neuen Subvector (inhalt innerhalb der Klammern) zu erstellen um diesen dann wieder Rekursiv als neue expression zu verabeiten,
Code:
factor ::= int | '(' expression ')'
Also es geht mir nicht allein nur um die Überprüfung eines Syntaxfehlers oder wie meintest du das?

Ein Verbessrungsvorschlag is mir noch aufgefallen:

anstatt:
Code:
if(tooperate.get(0).equals("(")){
					int begin_pos = 0;
					int end_pos = getClosingBracketPosition(tooperate, begin_pos);
					Vector<String> new_expression = new Vector<String>(tooperate.subList(begin_pos + 1, end_pos));
					expression(new_expression);
					for(int i = begin_pos; i <= end_pos; i++)
						tooperate.remove(0);
				}
				else{
					if((tooperate.get(0)).charAt(0) > '9' || (tooperate.get(0)).charAt(0) < '0')
						throw new IllegalArgumentException("No number where a number was expected!");
					root = new OpTree(tooperate.get(0));
					tooperate.remove(0);
				}
Code:
if(tooperate.get(0).equals("(")){
					int begin_pos = 0;
					int end_pos = getClosingBracketPosition(tooperate, begin_pos);
					Vector<String> new_expression = new Vector<String>(tooperate.subList(begin_pos + 1, end_pos));
					expression(new_expression);
					for(int i = begin_pos; i <= end_pos; i++)
						tooperate.remove(0);
				}
				else{
                                       for(int i = 0; i < tooperate.get(0).size(); i++){
					  if((tooperate.get(0)).charAt(i) > '9' || (tooperate.get(0)).charAt(i) < '0')
						 throw new IllegalArgumentException("No number where a number was expected!");
                                       }
					root = new OpTree(tooperate.get(0));
					tooperate.remove(0);
				}
zu verwenden, So wird nämlich die Komplette Zahl auf gültigkeit überprüft und nich nur die erste Stelle :)

//edit:
kabel2 hat gesagt.:
Code:
tooperate.remove( 0 );
expression( tooperate );
if( tooperate.get( 0 ).equals( ")") ) {
	tooperate.remove( 0 );
} else {
	throw new SyntaxErrorException( ")", tooperate.get( 0 ) );
}
mit
Code:
public class SyntaxErrorException extends RuntimeException {
	
	private String expected;
	private String got;
	
	public SyntaxErrorException(String expected, String got) {
		this.expected= expected;
		this.got= got;
	}
	
	public String toString() {
		return "Syntax Error: expected [" + expected + "] got [" + got + "]";
	}

	private static final long serialVersionUID = -7469838979422601574L;
}

Das mit der Syntaxexception wäre in Erwägung zu ziehen :)

Gruß

RedWing

P.S. Danke für deine Gedanken
 
Zuletzt bearbeitet:

RedWing

Erfahrenes Mitglied
Also habs jetzt nochmal a weng verbessert und auf kabel2s SyntaxErrorException angepasst

Code:
class SyntaxTree{
	
		private Vector<String> elements;
		private OpTree root;
		
		/**
		 * returns the postion of each closing bracket which belongs to a opening bracket
		 * if there is no closing bracket a InputFormatException is thrown
		 * @see InputFormatException
		 */
		private int getClosingBracketPosition(Vector<String> tooperate, int beginIndex){
			int number_opening_brackets = 0;
			int number_closing_brackets = 0;
			int ret = beginIndex;
			while(ret < tooperate.size()){
				if(tooperate.get(ret).equals("(")) number_opening_brackets++;
				if(tooperate.get(ret).equals(")")) number_closing_brackets++;
				if(number_opening_brackets ==  number_closing_brackets) break;	
				ret++;
			}
			if(number_opening_brackets != number_closing_brackets) throw new SyntaxErrorException(")", "(");
			return ret;
		}

		/**
		 * creates the non terminal expression according to the grammar rules
		 */
		private void expression(Vector<String> tooperate){
			term(tooperate);
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("+") || tooperate.get(0).equals("-")){
					OpTree oldRoot = root;
					root = new OpTree(tooperate.get(0));
					root.setLeftSon(oldRoot);
					OpTree oldRoot2 = root;
					tooperate.remove(0);
					expression(tooperate);
					oldRoot2.setRightSon(root);
					root = oldRoot2;
				}
				else if(!tooperate.get(0).equals("*") && !tooperate.get(0).equals("/"))
					throw new SyntaxErrorException("+,-,* or /", tooperate.get(0));
			}
		}
		
		/**
		 * creates the non terminal term according to the grammar rules
		 */
		private void term(Vector<String> tooperate){
			factor(tooperate);
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("*") || tooperate.get(0).equals("/")){
					OpTree oldRoot = root;
					root = new OpTree(tooperate.get(0));
					root.setLeftSon(oldRoot);
					tooperate.remove(0);
					OpTree oldRoot2 = root;
					term(tooperate);
					oldRoot2.setRightSon(root);
					root = oldRoot2;
				}
				else if(!tooperate.get(0).equals("+") && !tooperate.get(0).equals("-"))
					throw new SyntaxErrorException("+,-,* or /", tooperate.get(0));
			}
		}
	
		/**
		 * creates the non terminal factor according to the grammar rules
		 * if one input value which is expected as number is no number a InputFormatException is thrown
		 * @see InputFormatException
		 */
		private void factor(Vector<String> tooperate){
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("(")){
					int begin_pos = 0;
					int end_pos = getClosingBracketPosition(tooperate, begin_pos);
					Vector<String> new_expression = new Vector<String>(tooperate.subList(begin_pos + 1, end_pos));
					expression(new_expression);
					for(int i = begin_pos; i <= end_pos; i++)
						tooperate.remove(0);
				}
				else{
					for(int i = 0; i < tooperate.get(0).length(); i++){
						if((tooperate.get(0)).charAt(i) > '9' || (tooperate.get(0)).charAt(i) < '0')
							throw new SyntaxErrorException("Number", tooperate.get(0));
					}
					root = new OpTree(tooperate.get(0));
					tooperate.remove(0);
				}
			}
		}

		/**
		 * creates a new syntax tree which represent the given grammar 
		 * @param expression the expression from which the syntax tree should be build
		 */
		public SyntaxTree(String expression){
			StringTokenizer token = new StringTokenizer(expression, " ");
			if(token.countTokens() % 2 == 0) throw new SyntaxErrorException("Number of terms and operators should be odd", "Number of terms and operators is even");
			elements = new Vector<String>();
			while(token.hasMoreTokens())
				elements.add(token.nextToken());
		}
		/**
		 * computes the syntax tree and creates the OpTree
		 * @see OpTree
		 */
		void buildTree(){
			Vector<String> tooperate = new Vector<String>(elements);
			expression(tooperate);
		}

		int getResult(){
			if(root != null)
				return root.getResult();
			else
				return 0;
		}
}

Gruß

RedWing
 

kabel2

Erfahrenes Mitglied
RedWing hat gesagt.:
Also ich definiere einen Syntaxbaum als den Ableitungsbaum der aus der gegebenen Grammatik und einen
gegebenen Eingabewort (einschließlich aller Terminalen und Nichtterminalen) gebildet werden kann. Die
Knoten eines Operatorbaums (einschließlich Blätter) werden meiner Ansicht nach aus den Blättern des
Ableitungs bzw Syntaxbaumes gebildet...

Bei uns heisst der Syntaxbaum konkreter Syntaxbaum und der Operatorbaum abstrakter Syntaxbaum (so ungefähr). Eine andere Unterteilung erscheint mir nicht sinnvoll, lasse mich aber gerne eines Besseren belehren. :)

ad getClosingBracketPosition():

- Es zählt die Klammern mit und muss somit einen potenziell unendlich langen Lookup durchführen. Die Funktion hat eine worst case Laufzeit von O(n) (z.B. beim Ausdruck "( 2 + 2 )" ). Durch den Lookup geht der Hauptvorteil dieser Parser dahin: linear mit der Eingabe zu sein (Der Parser geht zweimal drüber: einmal in getClosingBracketPosition(), einmal beim Parsen selbst).

- Dabei ist das völlig unnötig, wie mein Codeschnippsel zeigt. Wenn ein Token "(" ankommt, bist du dir sicher, dass danach ein Ausdruck kommt. Dein Code erstellst eine Kopie des abgedeckten Eingabevektors, lässt diesen abarbeiten und nimmst dann soviele Elemente vom Originalvektor weg, wie die Kopie hat. Mein Code benutzt einfach den Originalvektor. Im Endeffekt machen beide Codes das gleiche.

- Dein Code schmeisst früher einen Syntax Error, und zwar nur, wenn die Eingabe mehr "(" als ")" enthält, so dass nie ein balancierter Zustand eingenommen wird. Denn: Zuerst siehst du immer ein "(". Wenn sich das Verhältnis danach irgendwann ausbalanciert, geht dein Code übers break aus der Schleife raus. Was danach kommt, interessiert die Methode nicht. Wenn mehr "(" als ")" vorhanden sind, und nie ein ausbalancierter Zustand eingenommen wird, dann läuft der Code bis zum Ende der Tokenfolge; die Bedingung ist nicht mehr erfüllt, und du schmeisst die entsprechende SyntaxErrorException. Eine kleine Codeverschönerung:
Code:
while(ret < tooperate.size()){
  if(tooperate.get(ret).equals("(")) number_opening_brackets++;
  if(tooperate.get(ret).equals(")")) number_closing_brackets++;
  if(number_opening_brackets ==  number_closing_brackets) return ret;	
  ret++;
}
throw new SyntaxErrorException(")", "(");

Wobei eine Unterklasse von SyntaxErrorException angebracht wäre, die dem Benutzer sagt, wieviele Klammern er denn vergessen hat.
 

RedWing

Erfahrenes Mitglied
Bei uns heisst der Syntaxbaum konkreter Syntaxbaum und der Operatorbaum abstrakter Syntaxbaum (so ungefähr). Eine andere Unterteilung erscheint mir nicht sinnvoll, lasse mich aber gerne eines Besseren belehren.

Was soll das bedeuten "abstrakter Syntaxbaum"?
Also ein Operator hat jeweils immer 2 Operanden => Ein Operatorbaum ist
ein klassischer Binärbaum...
Ein Knoten eines Syntaxbaums (oder auch Ableitungsbaum welches Wort
mir hier sinnvoler erscheint) hat je nachdem wie hoch die Anzahl an
Nichtterminalen und Terminalen seiner dazugehörigen Produktion
ist dementsprechend viele Unterbäume...
Wenn nun einmal der Ableitungsbaum aus einem gegebenen Eingabewort
erstellt ist betrachtet man alle '(' ')' Terminale sowie alle Nichtterminale
als unwichtig und bildet aus dem Rest den Operatorbaum...

- Es zählt die Klammern mit und muss somit einen potenziell unendlich langen Lookup durchführen. Die Funktion hat eine worst case Laufzeit von O(n) (z.B. beim Ausdruck "( 2 + 2 )" ). Durch den Lookup geht der Hauptvorteil dieser Parser dahin: linear mit der Eingabe zu sein (Der Parser geht zweimal drüber: einmal in getClosingBracketPosition(), einmal beim Parsen selbst).

- Dabei ist das völlig unnötig,

Hat mich überzeugt :)

Nochmal nen update:

Code:
class BadSyntaxException extends RuntimeException {
		
	private String expected;
	private String got;

	public BadSyntaxException(String expected, String got) {
		this.expected= expected;
		this.got= got;
	}

	public String toString() {
		return "Syntax Error: expected [" + expected + "] got [" + got + "]";
	}

	private static final long serialVersionUID = -7469838979422601574L;
}

class ParenthesisOutOfBalanceException extends BadSyntaxException{
	private int numberOfForgottenBrackets;
	public ParenthesisOutOfBalanceException(String expected, String got, int number) {
		super(expected, got);
		numberOfForgottenBrackets = number;
	}

	public String toString() {
		String message = super.toString();
		return message += ", you need to close [" + numberOfForgottenBrackets + "] brackets!";
	}
		
}
/**
 * creates a syntax tree from the following grammar:
 * expressiom ::= term | term '+' expression | term '-' expression
 * term ::= factor | factor '*' term | factor '/' term 
 * factor ::= T | '(' expression ')'
 */
class SyntaxTree{
	
		private Vector<String> elements;
		private OpTree root;
		private int numberOfOpeningBrackets = 0;
		private int numberOfClosingBrackets = 0;
		
		/**
		 * creates the non terminal expression according to the grammar rules
		 */
		private void expression(Vector<String> tooperate){
			term(tooperate);
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("+") || tooperate.get(0).equals("-")){
					OpTree oldRoot = root;
					root = new OpTree(tooperate.get(0));
					root.setLeftSon(oldRoot);
					OpTree oldRoot2 = root;
					tooperate.remove(0);
					expression(tooperate);
					oldRoot2.setRightSon(root);
					root = oldRoot2;
				}
			}
		}
		
		/**
		 * creates the non terminal term according to the grammar rules
		 */
		private void term(Vector<String> tooperate){
			factor(tooperate);
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("*") || tooperate.get(0).equals("/")){
					OpTree oldRoot = root;
					root = new OpTree(tooperate.get(0));
					root.setLeftSon(oldRoot);
					tooperate.remove(0);
					OpTree oldRoot2 = root;
					term(tooperate);
					oldRoot2.setRightSon(root);
					root = oldRoot2;
				}
			}
		}
	
		/**
		 * creates the non terminal factor according to the grammar rules
		 */
		private void factor(Vector<String> tooperate){
			if(tooperate.size() > 0){
				if(tooperate.get(0).equals("(")){
					numberOfOpeningBrackets++;
					tooperate.remove(0);
					expression(tooperate);
					if( tooperate.size() == 0)
						throw new ParenthesisOutOfBalanceException( ")", "endofexpression" , numberOfOpeningBrackets - numberOfClosingBrackets );
					if( tooperate.get( 0 ).equals( ")") ){
						tooperate.remove(0);
						numberOfClosingBrackets++;
					}
					else throw new ParenthesisOutOfBalanceException( ")", tooperate.get( 0 ), numberOfOpeningBrackets - numberOfClosingBrackets );
				}
				else{
					for(int i = 0; i < tooperate.get(0).length(); i++){
						if((tooperate.get(0)).charAt(i) > '9' || (tooperate.get(0)).charAt(i) < '0')
							throw new BadSyntaxException("Number", tooperate.get(0));
					}
					root = new OpTree(tooperate.get(0));
					tooperate.remove(0);
				}
			}
		}

		/**
		 * creates a new syntax tree which represent the given grammar 
		 * @param expression the expression from which the syntax tree should be build
		 */
		public SyntaxTree(String expression){
			StringTokenizer token = new StringTokenizer(expression, " ");
			if(token.countTokens() % 2 == 0) throw new BadSyntaxException("Number of terms and operators should be odd", "Number of terms and operators is even");
			elements = new Vector<String>();
			while(token.hasMoreTokens())
				elements.add(token.nextToken());
		}
		/**
		 * computes the syntax tree and creates the OpTree
		 * @see OpTree
		 */
		void buildTree(){
			Vector<String> tooperate = new Vector<String>(elements);
			expression(tooperate);
		}

		int getResult(){
			if(root != null)
				return root.getResult();
			else
				return 0;
		}
}
Gruß

RedWing
 
Zuletzt bearbeitet:

Thomas Darimont

Erfahrenes Mitglied
Hallo!

Wie wär's denn mit einer BadSyntaxException statt SyntaxErrorException
und einer InappropriateBracketException statt einer BracketErrorException
(Sind ja keine java.lang.Errors, sondern java.lang.RuntimeExceptions ...) ;-)

Gruß Tom
 

kabel2

Erfahrenes Mitglied
RedWing hat gesagt.:
Was soll das bedeuten "abstrakter Syntaxbaum"?
Also ein Operator hat jeweils immer 2 Operanden => Ein Operatorbaum ist
ein klassischer Binärbaum...
Ein Knoten eines Syntaxbaums (oder auch Ableitungsbaum welches Wort
mir hier sinnvoler erscheint) hat je nachdem wie hoch die Anzahl an
Nichtterminalen und Terminalen seiner dazugehörigen Produktion
ist dementsprechend viele Unterbäume...
Wenn nun einmal der Ableitungsbaum aus einem gegebenen Eingabewort
erstellt ist betrachtet man alle '(' ')' Terminale sowie alle Nichtterminale
als unwichtig und bildet aus dem Rest den Operatorbaum...

Sorry, meine Begriffe kommen aus dem Compilerbau, deine aus der Theorie formaler Sprachen (oder allgemeiner: woandersher ;) ). Über den Begriff des Syntaxbaumes sind wir uns jetzt jedenfalls einig.

Der Operatorbaum macht nur bei Ausdrücken Sinn. Dabei kannst du die Klammern nur deswegen weglassen, weil die Struktur des Baumes bereits die Information enthält.

Dieselbe Idee steckt hinter dem konkreten Syntaxbaum und dem abstraktem Syntaxbaum. Der konkrete enthält alle Zeichen der Eingabe, der abstrakte nur noch die Zeichen, die sich nicht aus der Struktur des Baumes oder aus Eigenschaften der inneren Knoten herleiten lassen.

@Tom: Über Namen könnten wir uns endlos streiten ;) Ok, dass die SyntaxErrorException ein Error im Namen hat ist unglücklich. InappropriateBracketException hingegen deutet zu wenig auf den Gebrauch der Exception hin, wie wärs mit dem pedantischem OutOfBalanceParenthesisException?