Rekursives Parsen (ohne Reg Expressions)

[Joggal]

Hallo an alle,

Ich möchte gerne einen String wie zum Beispiel eine Uhrzeit rekursiv parsen und auf die Syntax überprüfen.

Zum Beispiel ein Ascii Datum:

asctime-date = wkday SP date3 SP time SP 4DIGIT

date3 = month SP ( 2DIGIT | ( SP 1DIGIT ))
; month day (e.g., Jun 2)

time = 2DIGIT ":" 2DIGIT ":" 2DIGIT
; 00:00:00 - 23:59:59

wkday = "Mon" | "Tue" | "Wed"
| "Thu" | "Fri" | "Sat" | "Sun"

month = "Jan" | "Feb" | "Mar" | "Apr"
| "May" | "Jun" | "Jul" | "Aug"
| "Sep" | "Oct" | "Nov" | "Dec"

Wie gesagt, möchte ich das ganze rekursiv mit Methoden lösen (eine ruft die andere auf) und so prüfen ob das eingegebene Datum stimmt. (z.B. gültig: Mon Jun 22 12:24:01 )

Mein Problem allerdings: Ich habe überhaupt keinen Plan wie ich das ganze umsetzen soll...
Ich weiß natürlich, dass ich mit einem StringTokenizer parsen muss, aber dann das ganze rekursiv zu machen ... da weiß ich nicht weiter!

Wäre schön wenn mir hier jemand weiterhelfen könnte!

lG

 

[DarXun]

Ich verstehe nicht so ganz wo du da Rekursion benötigen würdest?

Du hast Rekursion auch als "eine Methode ruft eine andere auf" beschrieben.
Rekursion bedeutet jedoch, dass eine Methode sich selbst aufruft.

MfG

DarXun

 

[Joggal]

Hallo,

Ich weiß, ich habs ein bisschen blöd erklärt, aber vielleicht hilft diese "Musterlösung" weiter:

Main:

package theMain;

import ahit4.ebnf.ArithmetikParser;

public class TheMain {

	public TheMain() {

		String arith = "3 * ( 5 + 1 ) ";
		//String arith = "5 ? 1";
		ArithmetikParser par = new ArithmetikParser(arith);

	}

	public static void main(String[] args) {
		new TheMain();

	}

}

Interface:

package ahit4.interf;

public interface Ebnf {

	public enum Symbols {
	    NumSy,PlusSy,MinSy,DivSy,MulSy,ModSy,EndSy,ErrSy,StartSy,LeftParanthesesSy,RightParanthesesSy
	}
	
}

Parser: Es wird eine Arithmetik überprüft (z.B. 2 * (3 + 6) etc. )

/**
 * 
 */
package ahit4.ebnf;

import java.util.StringTokenizer;

import ahit4.interf.Ebnf;

/**
 * @author franzr
 * 
 *         sum : product [{ (’+’|’-’) product }];
product : term [{ (’*’|’/’|’%’) term }];
term : [{’+’|’-’}] ( Number | ’(’ sum ’)’ ) ;
Number : digit | Number digit ;
digit : ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ ;
 * 
 * 
 */

public class ArithmetikParser implements Ebnf {

	private class Lexer {
		private StringTokenizer token = null;
		private String curSym = "";
		private String text;

		public Lexer(String text) {
		
			this.text = text;
			token = new StringTokenizer(text);

		}

		public Symbols getNextSym() {

			if (token.hasMoreTokens()) {
				curSym = token.nextToken();

				if (curSym.matches("[0-9]+"))
					return Symbols.NumSy;

				switch (curSym) {

				case "/":
					return Symbols.DivSy;
				case "*":
					return Symbols.MulSy;
				case "%":
					return Symbols.ModSy;
				case "+":
					return Symbols.PlusSy;
				case "-":
					return Symbols.MinSy;
				case "(":
					return Symbols.LeftParanthesesSy;
				case ")":
					return Symbols.RightParanthesesSy;
				default:
					return Symbols.ErrSy;
				}

			}
			return Symbols.EndSy;
		}

		public final String getText() {
			return text;
		}

		public final String getLastScannedSymbol() {
			return curSym;
		}

	}

	private Lexer lexer = null;
	private Symbols currentSym = Symbols.StartSy;

	
	
	
	public ArithmetikParser(String text) {
		lexer = new Lexer(text);
		currentSym = lexer.getNextSym(); // scanned symbol
		
		if (sum()) {
			System.out.println("Der Ausdruck <<" + lexer.getText()
					+ ">> wurde erfolgreich überprüft.");
		} else {
			System.out.println("Der Ausdruck <<" + lexer.getText()
					+ ">>  ist fehlerhaft.");
		}
	}

	private boolean sum() {

		if (!product()) {
			System.out.println("EIngabe entspricht nicht der Grammatik.");
			return false;
		}
		if (currentSym == Symbols.PlusSy || currentSym == Symbols.MinSy) {
			currentSym = lexer.getNextSym();
			if (!product()) {
				System.out.println("EIngabe entspricht nicht der Grammatik.");
				return false;
			}

		}
		if (currentSym == Symbols.ErrSy) {
			String errSym = lexer.getLastScannedSymbol();
			printErrMsg1("sum", errSym);
			return false;
		}
		return true;
	}

	private boolean product() {

		if (!term())
			return false;
		if (currentSym == Symbols.MulSy || currentSym == Symbols.DivSy
				|| currentSym == Symbols.ModSy) {
			currentSym = lexer.getNextSym();
			if (!term())
				return false;

			
		}

		return true;

	}

	private boolean term() {
		if (currentSym == Symbols.PlusSy || currentSym == Symbols.MinSy)
			currentSym = lexer.getNextSym();
		if (currentSym == Symbols.LeftParanthesesSy) {
			currentSym = lexer.getNextSym();
			if (!sum()) {
				return false;
			}
			if (currentSym != Symbols.RightParanthesesSy) {
				printErrMsg("term", Symbols.RightParanthesesSy, currentSym);
				return false;
			}
			currentSym = lexer.getNextSym();
			return true;

		}
		if (!number()) {
			return false;
		}
		// currentSym = lexer.getNextSym();

		return true;
	}

	private boolean number() {
		if (!digit())
			return false;

		return true;
	}

	private boolean digit() {
		if (currentSym == Symbols.NumSy) {
			currentSym = lexer.getNextSym();
			return true;
		}
		printErrMsg("digit", Symbols.NumSy, currentSym);
		return false;
	}

	private void printErrMsg(String produktion, Symbols exp, Symbols found) {
		System.out.println("Produktion: " + produktion + ", erwarte Symbol: "
				+ exp + ", gefunden: " + found);
	}

	private void printErrMsg1(String produktion, String found) {
		System.out.println("Produktion: " + produktion
				+ ", ungültiges Symbol  <<" + found + ">> gefunden.");

	}
}

Mein Problem: Ich verstehe den Ablauf überhaupt nicht... Sprich, die Methoden sum(), term(), ... etc.
Ich habe versucht so einen Arithmetik Prüfer nachzumachen, aber ich bin gescheitert da ich mir den Ablauf nicht vorstellen kann, wie das ganze immer nacheinander das einzelne Token in den jeweiligen Methoden rekursiv überprüft.

Hoffe ich konnte mein Problem ein bisschen besser erklären und vielleicht kann mir ja jetzt jemand helfen.

lG

 

[Joggal]

Hat vllt jemand so ähnliche Beispiele ??

 

[diggaa1984]

Mein Problem: Ich verstehe den Ablauf überhaupt nicht... Sprich, die Methoden sum(), term(), ... etc.

Also wenn du Grammatiken verstehst ist doch der Algorithmus leicht nachzuvollziehen:

sum : product [{ (’+’|’-’) product }];

Summe ist also ein "product", welches optional mit einem weiteren "product" durch "plus" oder "minus" verknüpft ist.

private boolean sum() {
    //muss ein product sein
    if (!product()) {       
        System.out.println("EIngabe entspricht nicht der Grammatik.");            
        return false;        
    }        
    
    //optional mit PlusSy oder MinusSy mit
    if (currentSym == Symbols.PlusSy || currentSym == Symbols.MinSy) {            
        currentSym = lexer.getNextSym(); 

        //weiterem product verknuepft           
        if (!product()) {
            System.out.println("EIngabe entspricht nicht der Grammatik.");  
            return false;            
        }
    }

    if (currentSym == Symbols.ErrSy) {
        String errSym = lexer.getLastScannedSymbol();
        printErrMsg1("sum", errSym);
        return false;
    }

    return true;
}

analog für die anderen methoden

 

[Joggal]

Hallo,

Danke vielmals für deine Hilfe, das hat mir schon ein wenig weitergeholfen!

Ich werde versuchen das so nach zu programmieren und vielleicht wirds ja was


EDIT: Die Methode "term()" ist mir noch nicht ganz klar...

wieso wird da abgefragt if(!sum()) return false; ???

lg

 

[Joggal]

Hallo,

Ich habe das Programm selbst nach programmiert, und stoße leider auf folgendes Problem:

Wenn ich z.B 4 * 3 überprüfe, erkennt es: zahl mal zahl , allerdings gibt es mir dann ständig "Falsche Syntax" aus... :/

Vielleicht bin ich einfach nur schon blind wegen zu viel vor dem PC sitzen.. aber es wäre schön wenn mal jemand drüber schauen könnte und mir vielleicht weiterhelfen könnte.

Hier der Code:

Lexer Klasse: Gibt immer das nächste Symbol zurück

package ahit4.lexer;

import java.util.StringTokenizer;

public class Lexer {
	
	private StringTokenizer sT;
	private String currentSymbol;
	
	public enum Symbol{
		lKlammer, rKlammer, zahl, plus,minus,sp, div, mal, mod, ende;
	}
	
	public Lexer(String text) {
		
		sT = new StringTokenizer(text);
	}
	
	public Symbol getNextSymbol(){

		
		if(sT.hasMoreTokens()){
			
			currentSymbol = sT.nextToken();
			
			if(currentSymbol.matches("[1-9]+")){
				return Symbol.zahl;
			}
			
			switch(currentSymbol){
			
			case " ":
				return Symbol.sp;
			case "+":
				return Symbol.plus;
			case "-":
				return Symbol.minus;
			case "/":
				return Symbol.div;
			case "*":
				return Symbol.mal;
			case "%":
				return Symbol.mod;
			case "(":
				return Symbol.lKlammer;
			case ")":
				return Symbol.rKlammer;
	
			}
		}
		
		return Symbol.ende;
		
	}

}

Parser Klasse: Hauptklasse, prüft die Syntax, sprich jedes einzelne Zeichen welches vom Lexer zurück gegeben wird

package ahit.parser;

/**
 * @author franzr
 * 
 *         sum : product [{ (’+’|’-’) product }];
product : term [{ (’*’|’/’|’%’) term }];
term : [{’+’|’-’}] ( Number | ’(’ sum ’)’ ) ;
Number : digit | Number digit ;
digit : ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ ;
 * 
 * 
 */



import ahit4.lexer.Lexer;
import ahit4.lexer.Lexer.Symbol;

public class Parser {
	
	private Lexer lexer;
	private Symbol currentSymbol;

	
	public Parser(Lexer lexer) {
		// TODO Auto-generated constructor stub
		this.lexer = lexer;
	}
	
	
	public void parseText(){
		
		if(!sum()){
			System.out.println("Falsche Syntax");
		}
		else System.out.println("Richtig");
		
	}


	private boolean sum() {
		// TODO Auto-generated method stub
		
		currentSymbol = lexer.getNextSymbol();
		System.out.println(currentSymbol.toString());
		
		if(!product()){
			return false;
		}
		
		if(currentSymbol == Symbol.minus || currentSymbol == Symbol.plus){
			
			currentSymbol = lexer.getNextSymbol();
			System.out.println(currentSymbol.toString());
			
			if(!product()){
				return false;
			}
		}
		
		return false;
	}


	private boolean product() {
		// TODO Auto-generated method stub

		if(!term()){
			return false;
		}
		
		if(currentSymbol == Symbol.mal || currentSymbol == Symbol.div || currentSymbol == Symbol.mod){
			
			currentSymbol = lexer.getNextSymbol();
			System.out.println(currentSymbol.toString());
			if(!term()){
				return false;
			}
		}
		
		return true;
	}


	private boolean term() {
		// TODO Auto-generated method stub
		
		if(currentSymbol == Symbol.minus || currentSymbol == Symbol.plus){
			currentSymbol = lexer.getNextSymbol();
			System.out.println(currentSymbol.toString());
		}
		
		if (currentSymbol == Symbol.lKlammer) {
			currentSymbol = lexer.getNextSymbol();
			
			if (!sum()) {
				return false;
			}
			if (currentSymbol != Symbol.rKlammer) {
			
				return false;
			}
			currentSymbol = lexer.getNextSymbol();
			return true;

		}
	
		if(!number()){
			return false;
		}
		
		return true;
	}


	private boolean number() {
		// TODO Auto-generated method stub
		
		if(!digit()){
			return false;
		}
		return true;
	}


	private boolean digit() {
		// TODO Auto-generated method stub
		
		if(currentSymbol == Symbol.zahl){
			currentSymbol = lexer.getNextSymbol();
			System.out.println(currentSymbol.toString());
			return true;
		}
		
		return false;
	}
	

}

TheMain: Testet das Ganze

package ahit4.main;

import ahit.parser.Parser;
import ahit4.lexer.Lexer;

public class TheMain {

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		final String text = "4 * 3";
		
		Lexer lexer = new Lexer(text);
		
		Parser parser = new Parser(lexer);
		parser.parseText();

	}

}

 

[diggaa1984]

private boolean sum() {
        // TODO Auto-generated method stub
       
        currentSymbol = lexer.getNextSymbol();
        System.out.println(currentSymbol.toString());
       
        if(!product()){
            return false;
        }
       
        if(currentSymbol == Symbol.minus || currentSymbol == Symbol.plus){
           
            currentSymbol = lexer.getNextSymbol();
            System.out.println(currentSymbol.toString());
           
            if(!product()){
                return false;
            }
        }
       
        return false; //<<------ muss return true; sein
    }

Ohne das jetzt länger analysiert zu haben, sollte der Fehler erstmal darin liegen (siehe Kommentar)

 

[Joggal]

Oh man... ich war echt schon zu blind ^^

Danke dir vielmals! Hast mir echt super geholfen!

lg