Startseite − Sitemap − Downloads − Hilfe − Impressum − Lastenheft − Chat


Startseite

Setty−Syntaxbaum

Setty's Syntaxbaum

Um den Setty-Syntaxbaum gemäß der Produktionen P folgender Grammatik SG aufbauen zu können, müssen Klassen (Knotentypen) zur Verfügung stehen, welche jeweils Informationen entsprechender Produktionen repräsentieren.

Die Grammatik der Setty−Sprache

Setty-Grammatik SG = (N, T, P, S) mit

N = {Program, SetU, SetI, SetD, Set, From, To},

T = {LPAREN1      := '(',     RPAREN1      := ')',
     LPAREN2      := '[',     RPAREN2      := ']',
     LPAREN3      := '{',     RPAREN3      := '}',
     PLUS         := '+',     MINUS        := '-',
     SEMICOLON    := ';',     QUESTIONMARK := '?',
     COMPLEMENT   := 'C',     UNION        := 'u'|'v',
     INTERSECTION := 'n',     DIFFERENCE   := '\',
     IS           := 'Is',    IN           := 'in',
     NOT          := 'not',
     NUMBER       := ['+'|'-']('0'-'9')+['.'('0'-'9')+],
     INFINITY     := 'inf'},

P = {Program ::= IS NUMBER [ NOT ] IN SetU QUESTIONMARK,
     SetU    ::= SetI ( UNION SetI )*,
     SetI    ::= SetD ( INTERSECTION SetD )*,
     SetD    ::= Set [ DIFFERENCE Set ],
     Set     ::= COMPLEMENT LPAREN1 SetU RPAREN1
               | LPAREN1 SetU RPAREN1
               | LPAREN3 [ NUMBER ( SEMICOLON NUMBER )* ] RPAREN3
               | From SEMICOLON To,
     From    ::= RPAREN2 ( NUMBER | MINUS INFINITY )
               | LPAREN2 NUMBER,
     To      ::= NUMBER ( LPAREN2 | RPAREN2 )
               | [ PLUS ] INFINITY LPAREN2} und

S = Program.

Unabhängigkeit des Syntaxbaumes

Die Klassen des Syntaxbaumes können aber auch unabhänigig vom Parser verwendet werden. Der Parser erzeugt nämlich einen Syntaxbaum in Abhägigkeit eines gegebenen Programms (hier Setty−Code). Der Syntaxbaum kann auch manuell, also ohne Parser, erzeugt werden.



Implementierung

Klassenhierarchie

Im Folgenden sehen Sie die Klassenhierarchie der einzelnen Bestandteile des Setty−Syntaxbaumes. Die eben beschriebenen Klassen werden im Folgenden implementiert.

Node

/**
 * Diese Klasse ist eine abstrakte Basisklasse zur Erzeugung von
 * Knoten des Setty-Syntaxbaumes.
 */
abstract public class Node {

  /**
   * Generiert eine Phrase in der Sprache C.
   * @return C-Code als Zeichenkette.
   */
  abstract public String generateCCode();

  /**
   * Generiert eine Phrase in der Sprache Pascal.
   * @return Pascal-Code als Zeichenkette.
   */
  abstract public String generatePascalCode();

  /**
   * Generiert eine Phrase in der Sprache SML.
   * @return SML-Code als Zeichenkette.
   */
  abstract public String generateSmlCode();

  /**
   * Reine Hilfsmethode zur Konvertierung von double in SML-real.
   * @param element Ein Java-Double-Wert.
   * @return Den entsprechende SML-Wert als Zeichenkette.
   */
  protected String doubleToSmlReal(double element) {
    String result = "";
    if (element < 0.0) {
      result += '~';
    }
    result += Math.abs(element);
    return result;
  }
}

SetNode

/**
 * Diese Klasse ist eine abstrakte Basisklasse zur Erzeugung einer Menge
 * des Setty-Syntaxbaumes.
 */
abstract public class SetNode extends Node {

  /**
   * Prüft, ob ein Wert in der Menge liegt oder nicht.
   * @param element Der zu prüfende Wert.
   * @return true, falls der Wert in der Menge enthalten ist.
   */
  abstract public boolean contains(double element);
}

LowerSetNode: {x|x<limit}

public class LowerSetNode extends SetNode {

  private double limit;

  public LowerSetNode(double limit) {
    this.limit = limit;
  }

  public boolean contains(double element) {
    return element < limit;
  }

  public String generateCCode() {
    return "element < " + this.limit;
  }

  public String generatePascalCode() {
    return "Element < " + this.limit;
  }

  public String generateSmlCode() {
    return "set (fn x => x < " + this.doubleToSmlReal(this.limit) + ")";
  }
}

LowerEqualSetNode: {x|x<=limit}

public class LowerEqualSetNode extends SetNode {

  private double limit;

  public LowerEqualSetNode(double limit) {
    this.limit = limit;
  }

  public boolean contains(double element) {
    return element <= limit;
  }

  public String generateCCode() {
    return "element <= " + this.limit;
  }

  public String generatePascalCode() {
    return "Element <= " + this.limit;
  }

  public String generateSmlCode() {
    return "set (fn x => x <= " + this.doubleToSmlReal(this.limit) + ")";
  }
}

GreaterSetNode: {x|x>limit}

public class GreaterSetNode extends SetNode {

  private double limit;

  public GreaterSetNode(double limit) {
    this.limit = limit;
  }

  public boolean contains(double element) {
    return element > limit;
  }

  public String generateCCode() {
    return "element > " + this.limit;
  }

  public String generatePascalCode() {
    return "Element > " + this.limit;
  }

  public String generateSmlCode() {
    return "set (fn x => x > " + this.doubleToSmlReal(this.limit) + ")";
  }
}

GreaterEqualSetNode: {x|x>=limit}

public class GreaterEqualSetNode extends SetNode {

  private double limit;

  public GreaterEqualSetNode(double limit) {
    this.limit = limit;
  }

  public boolean contains(double element) {
    return element >= limit;
  }

  public String generateCCode() {
    return "element >= " + this.limit;
  }

  public String generatePascalCode() {
    return "Element >= " + this.limit;
  }

  public String generateSmlCode() {
    return "set (fn x => x >= " + this.doubleToSmlReal(this.limit) + ")";
  }
}

ElementsSetNode: {z1,z2,…,zn}

import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;

public class ElementsSetNode extends SetNode {

  private LinkedList elements;

  public ElementsSetNode() {
    this.elements = new LinkedList();
  }

  public void addElement(double element) {
    if (!this.elements.contains(new Double(element))) {
      this.elements.add(new Double(element));
    }
  }

  public boolean contains(double element) {
    Iterator iterator = this.elements.listIterator();
    while (iterator.hasNext()) {
      Double nextElement = (Double)iterator.next();
      if (nextElement.doubleValue() == element) {
        return true;
      }
    }
    return false;
  }

  public String generateCCode() {
    String result = "";

    if (this.elements.size() <= 0) { // die leere Menge

      result += "0";

    } else if (this.elements.size() == 1) { // einelementige Menge

      result += "element == " + this.elements.getFirst();

    } else { // mehrelementige Menge

      ListIterator listIterator = this.elements.listIterator();
      while (listIterator.hasNext()) {
        if (listIterator.hasPrevious()) {
          result += " || ";
        }
        result += "(element == " + listIterator.next() + ")";
      }
    }

    return result;
  }

  public String generatePascalCode() {
    String result = "";

    if (this.elements.size() <= 0) { // die leere Menge

      result += "false";

    } else if (this.elements.size() == 1) { // einelementige Menge

      result += "Element = " + this.elements.getFirst();

    } else { // mehrelementige Menge

      ListIterator listIterator = this.elements.listIterator();
      while (listIterator.hasNext()) {
        if (listIterator.hasPrevious()) {
          result += " or ";
        }
        result += "(Element = " + listIterator.next() + ")";
      }
    }

    return result;
  }

  public String generateSmlCode() {
    String result = "elemN [";
    ListIterator listIterator = this.elements.listIterator();
    while (listIterator.hasNext()) {
      if (listIterator.hasPrevious()) {
        result += ", ";
      }
      Double nextElement = (Double)listIterator.next();
      result += this.doubleToSmlReal(nextElement.doubleValue());
    }
    result += "]";
    return result;
  }
}

UnionSetNode: s1 v s2 v … v sn

import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;

public class UnionSetNode extends SetNode {

  private LinkedList setNodes;

  public UnionSetNode() {
    this.setNodes = new LinkedList();
  }

  public void addSetNode(SetNode setNode) {
    if (setNode != null) {
      this.setNodes.add(setNode);
    }
  }

  public boolean contains(double element) {
    Iterator iterator = this.setNodes.listIterator();
    while (iterator.hasNext()) {
      if (((SetNode)iterator.next()).contains(element)) {
        return true;
      }
    }
    return false;
  }

  public String generateCCode() {
    String result = "";

    if (this.setNodes.size() <= 0) {

      result += "0";

    } else if (this.setNodes.size() == 1) {

      result += ((SetNode)this.setNodes.getFirst()).generateCCode();

    } else {

      ListIterator listIterator = this.setNodes.listIterator();
      while (listIterator.hasNext()) {
        if (listIterator.hasPrevious()) {
          result += " || ";
        }
        result += "(";
        result += ((SetNode)listIterator.next()).generateCCode();
        result += ")";
      }
    }

    return result;
  }

  public String generatePascalCode() {
    String result = "";

    if (this.setNodes.size() <= 0) {

      result += "false";

    } else if (this.setNodes.size() == 1) {

      result += ((SetNode)this.setNodes.getFirst()).generatePascalCode();

    } else {

      ListIterator listIterator = this.setNodes.listIterator();
      while (listIterator.hasNext()) {
        if (listIterator.hasPrevious()) {
          result += " or ";
        }
        result += "(";
        result += ((SetNode)listIterator.next()).generatePascalCode();
        result += ")";
      }
    }

    return result;
  }

  public String generateSmlCode() {
    String result = "unionN [";
    ListIterator listIterator = this.setNodes.listIterator();
    while (listIterator.hasNext()) {
      if (listIterator.hasPrevious()) {
        result += ", ";
      }
      result += "(" + ((SetNode)listIterator.next()).generateSmlCode() + ")";
    }
    result += "]";
    return result;
  }
}

IntersectionSetNode: s1 n s2 n … n sn

import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;

public class IntersectionSetNode extends SetNode {

  private LinkedList setNodes;

  public IntersectionSetNode() {
    this.setNodes = new LinkedList();
  }

  public void addSetNode(SetNode setNode) {
    if (setNode != null) {
      this.setNodes.add(setNode);
    }
  }

  public boolean contains(double element) {
    Iterator iterator = this.setNodes.listIterator();
    while (iterator.hasNext()) {
      if (!((SetNode)iterator.next()).contains(element)) {
        return false;
      }
    }
    return (this.setNodes.size() > 0);
  }

  public String generateCCode() {
    String result = "";

    if (this.setNodes.size() <= 0) {

      result += "0";

    } else if (this.setNodes.size() == 1) {

      result += ((SetNode)this.setNodes.getFirst()).generateCCode();

    } else {

      ListIterator listIterator = this.setNodes.listIterator();
      while (listIterator.hasNext()) {
        if (listIterator.hasPrevious()) {
          result += " && ";
        }
        result += "(";
        result += ((SetNode)listIterator.next()).generateCCode();
        result += ")";
      }
    }

    return result;
  }

  public String generatePascalCode() {
    String result = "";

    if (this.setNodes.size() <= 0) {

      result += "false";

    } else if (this.setNodes.size() == 1) {

      result += ((SetNode)this.setNodes.getFirst()).generatePascalCode();

    } else {

      ListIterator listIterator = this.setNodes.listIterator();
      while (listIterator.hasNext()) {
        if (listIterator.hasPrevious()) {
          result += " and ";
        }
        result += "(";
        result += ((SetNode)listIterator.next()).generatePascalCode();
        result += ")";
      }
    }

    return result;
  }

  public String generateSmlCode() {
    String result = "interN [";
    ListIterator listIterator = this.setNodes.listIterator();
    while (listIterator.hasNext()) {
      if (listIterator.hasPrevious()) {
        result += ", ";
      }
      result += "(" + ((SetNode)listIterator.next()).generateSmlCode() + ")";
    }
    result += "]";
    return result;
  }
}

DifferenceSetNode: s1 \ s2

public class DifferenceSetNode extends SetNode {

  private SetNode setNode1;
  private SetNode setNode2;

  public DifferenceSetNode(SetNode setNode1, SetNode setNode2) {
    this.setNode1 = setNode1;
    this.setNode2 = setNode2;
  }

  public boolean contains(double element) {
    return this.setNode1.contains(element) & (!this.setNode2.contains(element));
  }

  public String generateCCode() {

    SetNode notNode2 = new ComplementSetNode(this.setNode2);

    String result = "";

    result += "(" + notNode2.generateCCode() + ")";
    result += " && ";
    result += "(" + this.setNode1.generateCCode() + ")";

    return result;
  }

  public String generatePascalCode() {

    SetNode notNode2 = new ComplementSetNode(this.setNode2);

    String result = "";

    result += "(" + notNode2.generatePascalCode() + ")";
    result += " and ";
    result += "(" + this.setNode1.generatePascalCode() + ")";

    return result;
  }

  public String generateSmlCode() {
    String result = "minus (" + this.setNode1.generateSmlCode() + ") ";
    result += "(" + this.setNode2.generateSmlCode() + ")";
    return result;
  }
}

ComplementSetNode: C(s)

public class ComplementSetNode extends SetNode {

  private SetNode setNode;

  public ComplementSetNode(SetNode setNode) {
    this.setNode = setNode;
  }

  public boolean contains(double element) {
    return !this.setNode.contains(element);
  }

  public String generateCCode() {
    return "!(" + this.setNode.generateCCode() + ")";
  }

  public String generatePascalCode() {
    return "not(" + this.setNode.generatePascalCode() + ")";
  }

  public String generateSmlCode() {
    return "compl (" + this.setNode.generateSmlCode() + ")";
  }
}

ProgramNode

public class ProgramNode extends Node {

  private double element;
  private boolean not;
  private SetNode setNode;

  public ProgramNode(double element, boolean not, SetNode setNode) {
    this.element = element;
    this.not = not;
    this.setNode = setNode;
  }

  public String getResult() {
    SetNode node = this.setNode;
    if (this.not) {
      node = new ComplementSetNode(node);
    }
    if (node.contains(this.element)) {
      return "yes";
    } else {
      return "no";
    }
  }

  public String generateCCode() {

    SetNode node = this.setNode;
    if (this.not) {
      node = new ComplementSetNode(node);
    }

    String result = "";

    result += "#include <stdio.h>\r\n";
    result += "\r\n";
    result += "int main(void) {\r\n";
    result += "  \r\n";
    result += "  double element = " + this.element + ";\r\n";
    result += "  \r\n";
    result += "  if (" + node.generateCCode() + ") {\r\n";
    result += "    printf(\"yes\\n\");\r\n";
    result += "  } else {\r\n";
    result += "    printf(\"no\\n\");\r\n";
    result += "  }\r\n";
    result += "  \r\n";
    result += "  return 0;\r\n";
    result += "}";

    return result;
  }

  public String generatePascalCode() {

    SetNode node = this.setNode;
    if (this.not) {
      node = new ComplementSetNode(node);
    }

    String result = "";

    result += "program a_setty;\r\n";
    result += "\r\n";
    result += "var Element: Extended;\r\n";
    result += "\r\n";
    result += "begin\r\n";
    result += "  \r\n";
    result += "  Element := " + this.element + ";\r\n";
    result += "  \r\n";
    result += "  if " + node.generatePascalCode() + "\r\n";
    result += "    then writeln('yes')\r\n";
    result += "    else writeln('no');\r\n";
    result += "  \r\n";
    result += "end.";

    return result;
  }

  public String generateSmlCode() {

    String result = "";

    result += "abstype 'a SET = Set of 'a -> bool\r\n";
    result += " with\r\n";
    result += "  fun set b = Set b\r\n";
    result += "\r\n";
    result += "  val EmptySet = Set (fn x => false)\r\n";
    result += "  val RealSet = Set (fn x => true)\r\n";
    result += "\r\n";
    result += "  fun union (Set s) (Set t) = Set (fn x => s x orelse t x)\r\n";
    result += "  fun unionN [] = EmptySet\r\n";
    result += "    | unionN (s::sl) = union s (unionN sl)\r\n";
    result += "\r\n";
    result += "  fun inter (Set s) (Set t) = Set (fn x => s x andalso t x)\r\n";
    result += "  fun interN [] = RealSet\r\n";
    result += "    | interN (s::sl) = inter s (interN sl)\r\n";
    result += "\r\n";
    result += "  fun elem e = Set (fn x => Real.==(x, e))\r\n";
    result += "  fun elemN [] = EmptySet\r\n";
    result += "    | elemN (e::el) = union (elem e) (elemN el)\r\n";
    result += "\r\n";
    result += "  fun compl (Set s) = Set (not o s)\r\n";
    result += "\r\n";
    result += "  fun minus S T = inter (compl T) S\r\n";
    result += "\r\n";
    result += "  fun isin e (Set s) = s e\r\n";
    result += "  fun isnotin e (Set s) = (not o s) e\r\n";
    result += " end;\r\n";
    result += "\r\n";
    result += "fun yesorno true = print(\"yes\\n\")\r\n";
    result += "  | yesorno false = print(\"no\\n\");\r\n";
    result += "\r\n";
    result += "yesorno (";
    if (this.not) {
      result += "isnotin ";
    } else {
      result += "isin ";
    }
    result += this.doubleToSmlReal(this.element);
    result += " (" + this.setNode.generateSmlCode() + "));";

    return result;
  }
}



Anwendung

Um die Node−Klassen des Setty−Syntaxbaumes testen zu können, benötigt man keinen Scanner und auch keinen Parser und eigentlich gar nichts, was das folgende Java−Programm beweist.

ParseTreeTest.java

/**
 * Einfacher Test einiger Node-Klassen des Setty-Syntaxbaumes
 * ohne dem Setty-Parser.
 */
public class ParseTreeTest {

  public static void main(String[] arguments) {

    // {1.0;2.0;3.0}
    ElementsSetNode e123 = new ElementsSetNode();
    e123.addElement(1.0);
    e123.addElement(2.0);
    e123.addElement(3.0);

    // {x|x>=2}
    GreaterEqualSetNode ge2 = new GreaterEqualSetNode(2.0);

    // {1.0;2.0;3.0} und {x|x>=2}
    IntersectionSetNode e123_and_ge2 = new IntersectionSetNode();
    e123_and_ge2.addSetNode(e123);
    e123_and_ge2.addSetNode(ge2);

    // Prüfe, ob 5.0 in der Menge {1.0;2.0;3.0} und {x|x>=2} enthalten ist
    ProgramNode program = new ProgramNode(5.0, false, e123_and_ge2);

    // Ausgabe des dazugehörigen SML-Programms
    System.out.println(program.generateSmlCode());
  }
}
Im Folgenden finden Sie die Ausgabe des kleinen Syntaxbaum−Testes vor. Dabei sei erwähnt, dass dieser Test nicht vollständig ist; dieser Test verifiert nicht alles!

java ParseTreeTest

abstype 'a SET = Set of 'a -> bool
 with
  fun set b = Set b

  val EmptySet = Set (fn x => false)
  val RealSet = Set (fn x => true)

  fun union (Set s) (Set t) = Set (fn x => s x orelse t x)
  fun unionN [] = EmptySet
    | unionN (s::sl) = union s (unionN sl)

  fun inter (Set s) (Set t) = Set (fn x => s x andalso t x)
  fun interN [] = RealSet
    | interN (s::sl) = inter s (interN sl)

  fun elem e = Set (fn x => Real.==(x, e))
  fun elemN [] = EmptySet
    | elemN (e::el) = union (elem e) (elemN el)

  fun compl (Set s) = Set (not o s)

  fun minus S T = inter (compl T) S

  fun isin e (Set s) = s e
  fun isnotin e (Set s) = (not o s) e
 end;

fun yesorno true = print("yes\n")
  | yesorno false = print("no\n");

yesorno (isin 5.0 (interN [(elemN [1.0, 2.0, 3.0]), (set (fn x => x >= 2.0))]));



Info

stefan−baur.de / Setty−Syntaxbaum
  • besucht am Donnerstag, den 11. März 2010 um 4:42 Uhr
  • geändert am Sonntag, den 15. März 2009 von Stefan K. Baur






Startseite

Copyright © 2004-2009 Stefan K. Baur − Druck − 2004 − 2005 − 2006 − 2007 − 2008 − 2009 − 2010 − 2011