[java] New Hampshire (tree) parsen

[Tjeerd]

Ik wil in Java een boom kunnen bouwen van het volgende:
(de eerste regel met tekens is de string die ik moet omzetten naar een boom)

(((One:0.2,Two:0.3):0.3,(Three:0.5,Four:0.3):0.2):0.3,Five:0.7):0.0;

+-+ One
+--+
| +--+ Two
+--+
| | +----+ Three
| +-+
| +--+ Four
+
+------+ Five

( Zie http://evolution.genetics...du/phylip/newick_doc.html )

Ik weet niet precies waar ik moet beginnen, alleen dat je ahw elk nieuw haakje als een nieuw kind moet zien en dat een haakje-sluiten het eind van en kind betekent. En zo moet ik dus de hele string doorlopen om uiteindelijk bij het laatste haakje te komen om de boom helemaal te hebben gebouwd. Maar...wat is de beste manier om dit te gaan doen? Regular expressions lijken me handig, maar of dat in dit geval odig is? Iemand die er ervaring heeft met het omzetten van bijv. een New Hampshire (string) naar een tree (object) in Java?

(ik zal gelijk maar toegeven dat ik begrjip wat boomstructuren / datastructuren zijn, maar dat ik er nog geen heb moeten bouwen )

[ Voor 13% gewijzigd door Tjeerd op 21-10-2004 12:56 ]

[Janoz]

Regular expressions zijn niet de heilige graal. Het is tegenworodig het eerste waar iedereen aan denkt. Je eerste gedachte bij zoiets zou moeten zijn "Parsen". In dit geval is het het makkelijkste om gewoon iets te schrijven dat 1 node inleest en vult en deze recursief aan laten roepen voor de kinderen. In het kort komt het dan op het volgende neer:

code:

leesnode {
 lees token
 als token==( {
  links = leesnode 
  lees ,
  rechts =leesnode aan
  return new node(links,rechts)
 }
 anders
 {
  lees leaf waarde
  return new leaf(waarde)
 }
}

[Alarmnummer]

Ik zou eens gaan kijken naar parser generators zoals SableCC en ANTLR.

[esf]

Een parser generator lijkt me wel een beetje overbodig voor alleen het omzetten naar een boom.. Een simplele recursive descent parser is ook zo opgezet in java

[Alarmnummer]

esf schreef op 21 oktober 2004 @ 13:06:
Een parser generator lijkt me wel een beetje overbodig voor alleen het omzetten naar een boom.. Een simplele recursive descent parser is ook zo opgezet in java

(Als je er ervaring mee hebt) zet je echt in notime een parser generator op. Zelfs voor de kleine dingen is dit wel te doen..

[esf]

Ja dat is wel zo.. al ben ik persoonlijk dat bijvoorbeeld Antlr, waarmee ik heb gewerkt, code genereert die niet gemakkelijk is om aan te passen en denk dat als je een boom wilt hebben en daar in een programma verder mee wilt gaan werken, je die code wilt kunnen beheren voor het geval dat je iets wilt wijzigen in bijvoorbeeld de boom. En zo bijster moelijk is het maken van een simpele parser nou ook weer niet..

[ Voor 11% gewijzigd door esf op 21-10-2004 13:27 ]

[Tjeerd]

Ok, ik ben wat wezen uitzoeken ondertussen, maar momenteel heb ik een erg brakke parser die ook niet echt ver komt.

Java:

public class Newick2stc
{
private static String nodeName, nodeLength;
private static int nodeLevel=0;
private static String workingString;
private static String lookaheadString, currentString;
private static int stringPos = 0;
private static final String LPARENT = "(";
private static final String RPARENT = ")";
private static final String COMMA   = ",";
private static final String EMPTY   = "";
 
    public Newick2stc(String theNewickString) 
    {
        this.workingString = theNewickString;
        lookaheadString    = String.valueOf( workingString.charAt(stringPos) );
       // ^^ get first character of newick string
    }
    
    public void parse()
    {
        while ( !lookaheadString.equals(EMPTY) )
        {           
            advanceToken();
        }
    }   

    public static void advanceToken()
    {       
        
        if ( stringPos<workingString.length() ) // while not at end of string
        {                   
            lookaheadString = String.valueOf( workingString.charAt(stringPos) );
            stringPos++;                
        
            if ( lookaheadString.equals(LPARENT) ) 
            {
                nodeLevel++;
                lParent();
            } else
            if ( lookaheadString.equals(COMMA) )
            {   
                advanceToken();
            } else
            if ( Character.isLetter(lookaheadString) )
            {
                lParent();
            }       
        } else
          lookaheadString = EMPTY;// end of string was found          
    }
    
    public static void lParent() // opening parenthesis
    {
        String nodes = new String();
        currentString = String.valueOf( workingString.charAt(stringPos) );
        
        if ( currentString.equals(LPARENT) ) advanceToken(); // check for opening parenthesis
         else        
            {
                while ( !currentString.equals(RPARENT) ) // not at end of closing parenthesis
                {
                    nodes = nodes + currentString;
                    currentString = String.valueOf( workingString.charAt(++stringPos) );
                }                               
                
                nodeLevel--; // leaving closing parenthesis
                
                System.out.println("das:" + nodes + " [level " + nodeLevel + "]");
            }
    }
    
    public static void rParent() // closing parenthesis
    {
        if ( lookaheadString.equals( RPARENT) ) advanceToken();
    }
    
}

Dit is deels gebaseerd op deze code en verder deels deze theorieen.

De levels kloppen sowieso al niet en ik ben nu al de mist ingegaan volgens mij op de manier waarop ik aan het parsen ben. Op internet is over het inlezen van het Newick formaat ook niet erg veel te vinden (iig geen Java broncode) en ik zit dan ook vast op dit moment. Enige hulp van een diehard figuur zou welkom zijn

[ Voor 3% gewijzigd door Tjeerd op 27-10-2004 11:11 ]

[Alarmnummer]

Parser opzetten in ANTLR/SableCC is niet zo lastig.

SableCC genereerd zelfs een databinding framework voor je (op basis van de AST) en hoef je dus zelf niets meer te parsen. Je kan mooi die boom uitlezen en laat het parsen maar mooi aan de parser over.

[ Voor 67% gewijzigd door Alarmnummer op 27-10-2004 11:25 ]