Parser basteln mit CUP

[eddi1983]

Hallo. Ich muß ein Parser basteln der die Verschachtelungstiefe der Kommentare erkennt.
z.B:

/**/ = Tiefe 1
/*/**/*/ = Tiefe 2
...

Parser-Code:

import java_cup.runtime.*;

/* Terminalsymbole */
terminal    START, END;
terminal    BORDER;
terminal    CHAR;

/* Nichtterminalsymbole */
non terminal   begin;
non terminal Integer comment;
non terminal Integer content;
non terminal   folge;

/*  Produktionen */

start with begin;

begin      ::= folge;

folge      ::= folge comment:a {: System.out.println("Ok; max. Tiefe des Kommentars: "+a); :} BORDER 
               |
               comment:a {: System.out.println("Ok; max. Tiefe des Kommentars: "+a); :} BORDER 
               |
               error BORDER;

comment    ::= START content:a END {:RESULT = a; :} ;

content    ::= content:a comment {:RESULT = a+1; :}
               |
	       content:a CHAR {:RESULT = a; :}           
	       |
                {:RESULT = 1; :};

Die Grammatik stimmt soweit.

Meine Frage bezieht sich darauf, wie ich das denn nu berechne. Also die Sachen mit RESULT. Ich komm da nie auf die richtigen Ergenisse.

Vielen Dank

 

[duncan]

Hallo eddi1983,
konntest du das Problem mit der maximalen Tiefe lösen?
Wenn ja schreibe bitte mal wie,
würde mich sehr interessieren........

gruß,
duncan

 

[eddi1983]

Hui. Den Thread hier habe ich ja total vergessen 🙂

Man muß einfach ein paar If-Schleifen einbauen, dann läufts. Wenn ich so an die anderen Aufgaben denke, die wir machen mußten, war das dann hier doch Pillepalle 😀

import java_cup.runtime.*;

/* Terminalsymbole */
terminal    START, END;
terminal    BORDER;
terminal    CHAR;

/* Nichtterminalsymbole */
non terminal   begin;
non terminal Integer comment;
non terminal Integer content;
non terminal Integer folge;

/*  Produktionen */

start with begin;

begin      ::= folge:d 
	       {: System.out.println("Ok; max. Tiefe der Kommentarfolge: "+d); :};

folge      ::= folge:b comment:a {: System.out.println("Ok; max. Tiefe des Kommentars: "+a); 
				    if (a>b) RESULT = a;
				    else RESULT = b; :} BORDER 
               |
               comment:a {: System.out.println("Ok; max. Tiefe des Kommentars: "+a); 
			    RESULT = a; :} BORDER 
               |
               error BORDER;

comment    ::= START content:a END {:RESULT = a+1; :} ;

content    ::= content:a comment:b {:
				    if (a>=b) RESULT = a; 
				    else RESULT = b;
				    :}
               |
	           content:a CHAR {:RESULT = a; :}           
	           |
               {:RESULT = 0; :};

 

[duncan]

A ja,
danke dir lass mich mal raten. Die zweite Aufage hat was mit Listen zu tun?

Gruß,
Duncan

 

[eddi1983]

Nee. Der Scanner und Parser sollte die entsprechende Grammatik erkennen und daraus einen EBNF-Scanner und -Parser bauen. Danach sollten dann diese die Grammatiken erkennen oder nen Fehler ausgeben. Genau weiß ich es auch nicht mehr. Schon wieder zu lange her 😉 Brauch man ja auch nicht jeden Tag.

 

[duncan]

Nee. Der Scanner und Parser sollte die entsprechende Grammatik erkennen und daraus einen EBNF-Scanner und -Parser bauen. Danach sollten dann diese die Grammatiken erkennen oder nen Fehler ausgeben. Genau weiß ich es auch nicht mehr. Schon wieder zu lange her 😉 Brauch man ja auch nicht jeden Tag.

Hallo eddi1983,
das hört sich sehr interessant an. Ich muss an meiner Uni ein Fach names "Compilerbau" belegen und hier
habe ich es auch mit Cup und Lex zu tun.

-> leider 🙂🙂

Kanst du mir mal posten, wie der entsprechende Quellcode für den EBNF-Scanner und -Parser
aussehen sollte????

Dein Parser für die Kommentare habe ich mal getest, der Scanner war relativ leicht abzuleiten.

Danke dir schon mal im Voraus.

Gruß,
Duncan

 

[eddi1983]

Kein Problem.
Erstmal den Scanner:

import java_cup.runtime.Symbol;

/* metacharacters in " einschliessen,
   keine Kommentare in den folgenden Abschnitten,
   keine white spaces im regulaeren Ausdruck
*/

%%

%cup

WHITE_SPACE_CHAR = [\r\n\ \t\b\012]
TERMINALE =[^\"<>:=\|\{\}\[\];#\r\n\ \t\b\012\\]
META = [\"<>:=\|\{\}\[\];#\\]
%%

";"                {return new Symbol(sym.SEMI); }
"#"                {return new Symbol(sym.HASH); }
"::="              {return new Symbol(sym.PFEIL); }
"|"                {return new Symbol(sym.ODER); }
"\""{META}"\""       {return new Symbol(sym.TERM_META, yytext()); }
"<"[a-zA-Z0-9]+">" {return new Symbol(sym.NICHTTERMINAL, yytext() ); }
{TERMINALE}+       {return new Symbol(sym.TERM, yytext()); }
"{"                {return new Symbol(sym.REP_AUF); }
"}"                {return new Symbol(sym.REP_ZU); }
"["                {return new Symbol(sym.OPT_AUF); }
"]"                {return new Symbol(sym.OPT_ZU); }
\^d                {return new Symbol(sym.EOF);  }

{WHITE_SPACE_CHAR}+ { }

. { System.err.println("Illegal character: "+yytext()); }

Und der Parser:

import java_cup.runtime.*;
import java.util.* ;
import java.io.*;


action code {:
  String scannerFilename = "gen/escanner.lex";
  String parserFilename = "gen/eparser.cup";

  PrintStream s = null; //Scanner
  PrintStream p = null; //Parser

  void openTargetStreams ()
  {
    // Zielstream fuer die generierten Komponenten oeffnen
    try
    {
      s = new PrintStream (new FileOutputStream(scannerFilename));
    }
    catch (FileNotFoundException e) {}
    finally {}
    try
    {
       p = new PrintStream (new FileOutputStream(parserFilename));
    }
    catch (FileNotFoundException e) {}
    finally {}
  }
  void closeTargetStreams ()
  {
    // Zielstream fuer die generierten Komponenten schliessen
    s.close();
    p.close();
  }


  Vector t_tab = new Vector(); //Vektor für Terminal
  Vector nt_tab = new Vector(); //Vektor für Nichtterminale

  int i = 1;
  int j = 1;

  String neue_regel="";
  int art;

  class Eintrag
  {
    String alt, neu;
    // Konstruktor
    Eintrag( String alt , String neu )
    {
      this.alt = alt; this.neu = neu;
    }
    // Methoden
    public boolean equals( Object anderes )
    {
      return alt.equals( ((Eintrag)anderes).alt );
    }
    public String toString()
    {
      return neu;
    }
  }

  //Nichtterminale auf Vorhandensein prüfen und in Vektor schreiben
  public String exist_NT( String alt , String neu)
  {
    int index = nt_tab.indexOf( new Eintrag( alt, "") ) ;
    if ( index >= 0 )
      return ((Eintrag) nt_tab.elementAt(index)).neu  ;
    else
    {
      nt_tab.addElement( new Eintrag( alt, neu) );				
      i++; //Laufvaribale um die Nichtterminale zu inkrementieren
      return neu;
    }
  }
  //Terminale auf Vorhandensein prüfen und in Vektor schreiben
  public String exist_T( String alt , String neu)
  {
    int index = t_tab.indexOf( new Eintrag( alt, "") ) ;
    if ( index >= 0 )
      return ((Eintrag) t_tab.elementAt(index)).neu  ;
    else
    {
      t_tab.addElement( new Eintrag( alt, neu) );				
      j++;//Laufvaribale um die Terminale zu inkrementieren
      return neu;
    }
  }
:}

/* Terminalsymbole */
terminal SEMI, HASH,PFEIL,REP_AUF, REP_ZU, OPT_AUF, OPT_ZU, ODER;
terminal String NICHTTERMINAL, TERM_META,TERM;


/* Nichtterminalsymbole */
non terminal anfang;
non terminal String regel, regeldef, linke_Seite, rechte_Seite;
non terminal String alternative, komponente, wiederholung, option;

/* Produktionen */

start with anfang;

anfang ::= regel:reg HASH 
           {:openTargetStreams();          
 
           //Ausgabe in eparser.cup
           int nt_size = nt_tab.size(); //Grösse vom Vektor nt ermitteln
           p.println("/* Generierte Parser-Beschreibung */\n");
           p.println("/* ##### Imports ##### */");
           p.println("import java_cup.runtime.*;\n");
           p.println("/* ##### Nichtterminalsymbole ##### */");
           for (int i = 0; i<nt_size; i++) 
             p.println("non terminal" + ((Eintrag) nt_tab.elementAt(i)).neu + ";"); //Nichtterminale ausgeben
           int t_size = t_tab.size(); //Grösse vom Vektor t ermitteln
           p.println("\n/* ##### Terminalsymbole ##### */");
           for (int i = 0; i<t_size; i++) 
             p.println("terminal" + ((Eintrag) t_tab.elementAt(i)).neu + ";"); //Terminale ausgeben
           p.println("\n/* ###### Regeln ##### */");
           p.println(reg+"\n"); //Regeln ausgeben
           p.println("/* ##### Generierte Regeln ##### */");
           p.println(neue_regel); //Neue Regeln ausgeben
 
           //Ausgabe in escanner.lex 
           s.println("/* Generierte Scanner-Beschreibung */\n");
           s.println("import java_cup.runtime.Symbol;\n");
           s.println("%%\n");
           s.println("%cup\n");
           s.println("WHITE_SPACE_CHAR = [\\r\\n\\ \\t\\b\\012]\n");
           s.println("%%\n");
           for (int i = 0; i<t_size; i++) 
           { //Sonderbehandlung für die Metazeichen \ und "
           if (((Eintrag) t_tab.elementAt(i)).alt.equals("\"")) 
             s.println("\"\\"+((Eintrag) t_tab.elementAt(i)).alt+"\" { return new Symbol(sym."+((Eintrag) t_tab.elementAt(i)).neu+"); }"); 
           else if (((Eintrag) t_tab.elementAt(i)).alt.equals("\\"))
             s.println("\\"+((Eintrag) t_tab.elementAt(i)).alt+" { return new Symbol(sym."+((Eintrag) t_tab.elementAt(i)).neu+"); }");
           else
            s.println("\""+((Eintrag) t_tab.elementAt(i)).alt+"\" { return new Symbol(sym."+((Eintrag) t_tab.elementAt(i)).neu+"); }");
           }
           s.println("{WHITE_SPACE_CHAR}+ { }\n");
           s.println(". { System.err.println(\"Illegal character: \"+yytext()); }");
 
           closeTargetStreams();
           System.out.println("ok");:}; 

regel ::= regel:reg regeldef:rd {:RESULT = reg + rd;:} 
          | 
          regeldef:rd  {:RESULT = rd;:}; /* Folge von Regeln*/

regeldef ::= linke_Seite:ls PFEIL rechte_Seite:rs SEMI {:RESULT = ls+" ::="+rs+" ;\n";:}; /* Regeldefinition*/

linke_Seite ::= NICHTTERMINAL:nt {:RESULT = exist_NT(nt," _N"+i); :};

rechte_Seite ::= alternative:al ODER rechte_Seite:rs {:RESULT = al+" |"+rs;:} 
                 |
                 alternative:al {:RESULT = al;:};

alternative ::= komponente:komp alternative:al {:RESULT = komp+al+ "";:}
                | /*leer*/ {:RESULT = "";:};

komponente ::= TERM:t {:RESULT = exist_T(t," _T"+j);:}
               | 
               NICHTTERMINAL:nt {:RESULT = exist_NT(nt," _N"+i);:} 
               | 
               TERM_META:tm {: //Metasymbole z.B. "{" werden auch als Terminale gespeichert
                               //Es müssen aber die Anführungsstriche entfernt werden
                               String tm_neu = tm.substring(1,2);
                               RESULT = exist_T(tm_neu," _T"+j);
                            :}
               |
               wiederholung:w {:RESULT = w;:}
               | 
               option:o {:RESULT = o;:} ;

//Generierte Regeln für Wiederholungen
wiederholung ::= REP_AUF rechte_Seite:rs REP_ZU
{:
  String nt_1 = " _N"+i++, nt_2=" _N"+i;
  exist_NT(nt_1,nt_1); 
  exist_NT(nt_2,nt_2); 
  RESULT = nt_1;

  neue_regel = neue_regel + nt_1+" ::="+nt_2+nt_1+" | /*empty*/ ;\n";
  neue_regel = neue_regel + nt_2+" ::="+rs+" ;\n";
  --i; //Verringerung um 1 um eine fortlaufende Nummerierung zu erreichen
:};

//Generierte Regeln für Optionen
option ::= OPT_AUF rechte_Seite:rs OPT_ZU
{:
  String nt_1 = " _N"+i;
  exist_NT(nt_1,nt_1); 
  RESULT = nt_1;

  neue_regel = neue_regel +nt_1+" ::="+rs+" | /*empty*/ ;\n";
:};

Bitte schön