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.
ParseException
vorgestellt.
ParseException
wird nur dann geworfen, wenn der Parser auf einen syntaktischen Fehler im
Setty-Programm
stoßen sollte.
Deshalb wird auch nur der erste, vorkommende Fehler im
Setty-Programm
erkannt.
Weitere Fehler werden nach und nach durch erneutes Parsen, erst nach Korrektur des jeweiligen Vorgängerfehlers, ermittelt.
1
/**
* Die Klasse ParseException ist eine Exception, welche nur von einem Parser
* während des Parse-Vorgangs geworfen werden sollte.
*/
public class ParseException extends Exception {
/**
* Erzeugt eine neue ParseException mit einer Nachricht.
* @param message Die Nachricht.
*/
public ParseException(String message) {
super(message);
}
}
Program()
SetU()
SetI()
SetD()
Set()
From()
To()
Program()
den gesamten Syntaxbaum zurückgibt.
/**
* Die Klasse Parser ist ein Top-Down-Parser,
* der die Tokenfolge eines Setty-Programm gemäß der Setty-Grammatik zu einem
* Setty-Syntaxbaum zusammenfasst.
*/
public class Parser {
/**
* Der Scanner, der sein Setty-Programm tokenweise lesen kann.
*/
private Scanner scanner;
/**
* Veranlasst den Scanner das nächste Token zu lesen, falls es sich um ein
* unbekanntes Token handeln sollte, wird eine ParseException geworfen.
* @throws ParseException Quellprogramm ist fehlerhaft.
*/
private void tryNextToken() throws ParseException {
this.scanner.nextToken();
if (this.scanner.getToken() == Token.UNKNOWN) {
throw new ParseException("Unbekanntes Zeichen: '"
+ this.scanner.getTokenValue() + "'");
}
}
/**
* Erzeugt und initialisiet den Parser mit einem Setty-Scanner.
* @param scanner Der Setty-Scanner.
*/
public Parser(Scanner scanner) {
this.scanner = scanner;
}
/**
* Stößt den Parse-Vorgang an und gibt den Syntaxbaum zurück.
* @throws ParseException Quellprogramm ist syntaktisch fehlerhaft.
* @return Der Syntaxbaum.
*/
public ProgramNode parse() throws ParseException {
this.tryNextToken();
return this.Program();
// Das anschließende Token müsste EOS sein und wird hier nicht geprüft,
// d.h. nach dem Fragezeichen dürfen noch weitere Zeichen vorkommen.
}
/**
* Program ::= IS NUMBER [ NOT ] IN SetU QUESTIONMARK
* @throws ParseException Quellprogramm ist syntaktisch fehlerhaft.
* @return Der Syntaxbaum.
*/
private ProgramNode Program() throws ParseException {
// Parse IS (required)
if (this.scanner.getToken() == Token.IS) {
this.tryNextToken();
} else {
throw new ParseException("'Is' erwartet!");
}
// Parse NUMBER (required)
double number = 0.0;
if (this.scanner.getToken() == Token.NUMBER) {
number = Double.parseDouble(this.scanner.getTokenValue());
this.tryNextToken();
} else {
throw new ParseException("Zahl erwartet!");
}
// Parse NOT (optional)
boolean not = false;
if (this.scanner.getToken() == Token.NOT) {
not = true;
this.tryNextToken();
}
// Parse IN (required)
if (this.scanner.getToken() == Token.IN) {
this.tryNextToken();
} else {
throw new ParseException("'in' erwartet!");
}
// Parse SetU (required)
SetNode setNode = this.SetU();
// Parse QUESTIONMARK (required)
if (this.scanner.getToken() == Token.QUESTIONMARK) {
this.tryNextToken();
} else {
throw new ParseException("Mengenoperation oder '?' erwartet!");
}
// Rückgabe des gesamten Syntaxbaumes!
return new ProgramNode(number, not, setNode);
}
/**
* SetU ::= SetI ( UNION SetI )*
* @throws ParseException Quellprogramm ist syntaktisch fehlerhaft.
* @return Vereinigung aller Mengen SetI als Teilbaum des Syntaxbaumes.
*/
private SetNode SetU() throws ParseException {
// Parse SetI (required)
SetNode setNode = this.SetI();
// Parse UNION (optional)
if (this.scanner.getToken() == Token.UNION) {
UnionSetNode unionSetNode = new UnionSetNode();
unionSetNode.addSetNode(setNode);
do {
this.tryNextToken();
// Parse SetI (required)
unionSetNode.addSetNode(this.SetI());
} while (this.scanner.getToken() == Token.UNION);
// Rückgabe der Vereinigung der Mengen.
return unionSetNode;
} else {
// Ansonsten lediglich die Rückgabe von setNode
return setNode;
}
}
/**
* SetI ::= SetD ( INTERSECTION SetD )*
* @throws ParseException Quellprogramm ist syntaktisch fehlerhaft.
* @return Schnitt aller Mengen SetD als Teilbaum des Syntaxbaumes.
*/
private SetNode SetI() throws ParseException {
// Parse SetD (required)
SetNode setNode = this.SetD();
// Parse INTERSECTION (optional)
if (this.scanner.getToken() == Token.INTERSECTION) {
IntersectionSetNode intersectionSetNode = new IntersectionSetNode();
intersectionSetNode.addSetNode(setNode);
do {
this.tryNextToken();
// Parse SetD (required)
intersectionSetNode.addSetNode(this.SetD());
} while (this.scanner.getToken() == Token.INTERSECTION);
// Rückgabe des Durchschnitts der Mengen.
return intersectionSetNode;
} else {
// Ansonsten lediglich die Rückgabe von setNode
return setNode;
}
}
/**
* SetD ::= Set [ DIFFERENCE Set ]
* @throws ParseException Quellprogramm ist syntaktisch fehlerhaft.
* @return Differenz zweier Mengen Set als Teilbaum des Syntaxbaumes.
*/
private SetNode SetD() throws ParseException {
// Parse Set (required)
SetNode setNode1 = this.Set();
// Parse DIFFERENCE (optional)
if (this.scanner.getToken() == Token.DIFFERENCE) {
this.tryNextToken();
// Parse Set (required)
SetNode setNode2 = this.Set();
// Rückgabe des Schnitts beider Mengen.
return new DifferenceSetNode(setNode1, setNode2);
} else {
// Ansonsten lediglich die Rückgabe von setNode1
return setNode1;
}
}
/**
* Set ::= COMPLEMENT LPAREN1 SetU RPAREN1
* | LPAREN1 SetU RPAREN1
* | LPAREN3 [ NUMBER ( SEMICOLON NUMBER )* ] RPAREN3
* | From SEMICOLON To
* @throws ParseException Quellprogramm ist syntaktisch fehlerhaft.
* @return Eine Menge als Teilbaum des Syntaxbaumes.
*/
private SetNode Set() throws ParseException {
// Parse COMPLEMENT or LPAREN1 or LPAREN3 or First(From) (required)
if (this.scanner.getToken() == Token.COMPLEMENT) {
this.tryNextToken();
// Parse LPAREN1 (required)
if (this.scanner.getToken() == Token.LPAREN1) {
this.tryNextToken();
} else {
throw new ParseException("'(' erforderlich!");
}
// Parse SetU (required)
SetNode setNode = this.SetU();
// Parse RPAREN1 (required)
if (this.scanner.getToken() == Token.RPAREN1) {
this.tryNextToken();
} else {
throw new ParseException("Mengenoperation oder ')' erforderlich!");
}
// Rückgabe der aktuell ermittelten Menge
return new ComplementSetNode(setNode);
} else if (this.scanner.getToken() == Token.LPAREN1) {
this.tryNextToken();
// Parse SetU (required)
SetNode setNode = this.SetU();
// Parse RPAREN1 (required)
if (this.scanner.getToken() == Token.RPAREN1) {
this.tryNextToken();
} else {
throw new ParseException("Mengenoperation oder ')' erforderlich!");
}
// Rückgabe der aktuell ermittelten Menge
return setNode;
} else if (this.scanner.getToken() == Token.LPAREN3) {
this.tryNextToken();
// Parse NUMBERs (optional)
ElementsSetNode elementsSetNode = new ElementsSetNode();
if (this.scanner.getToken() == Token.NUMBER) {
double element = Double.parseDouble(this.scanner.getTokenValue());
elementsSetNode.addElement(element);
this.tryNextToken();
}
while (this.scanner.getToken() == Token.SEMICOLON) {
this.tryNextToken();
// Parse Element (required)
if (this.scanner.getToken() == Token.NUMBER) {
double element = Double.parseDouble(this.scanner.getTokenValue());
elementsSetNode.addElement(element);
this.tryNextToken();
} else {
throw new ParseException("Zahl erwartet!");
}
}
// Parse RPAREN3 (required)
if (this.scanner.getToken() == Token.RPAREN3) {
this.tryNextToken();
} else {
throw new ParseException("';' oder '}' erwartet!");
}
return elementsSetNode;
} else { // First(From)
// Parse From (required)
SetNode from = this.From();
// Parse SEMICOLON (required)
if (this.scanner.getToken() == Token.SEMICOLON) {
this.tryNextToken();
} else {
throw new ParseException("';' erwartet!");
}
// Parse To (required)
SetNode to = this.To();
if ((from == null) && (to == null)) {
return new ComplementSetNode(new ElementsSetNode());
} else if (from == null) {
return to;
} else if (to == null) {
return from;
} else {
IntersectionSetNode intersectionSetNode = new IntersectionSetNode();
intersectionSetNode.addSetNode(from);
intersectionSetNode.addSetNode(to);
return intersectionSetNode;
}
}
}
/**
* From ::= RPAREN2 ( NUMBER | MINUS INFINITY )
* | LPAREN2 NUMBER
* @throws ParseException Quellprogramm ist syntaktisch fehlerhaft.
* @return Eine Menge als Teilbaum des Syntaxbaumes.
*/
private SetNode From() throws ParseException {
// Parse RPAREN2 or LPAREN2 (required)
if (this.scanner.getToken() == Token.RPAREN2) {
this.tryNextToken();
// Parse NUMBER or MINUS (required)
if (this.scanner.getToken() == Token.NUMBER) {
double number = Double.parseDouble(this.scanner.getTokenValue());
this.tryNextToken();
return new GreaterSetNode(number);
} else if (this.scanner.getToken() == Token.MINUS) {
this.tryNextToken();
// Parse INFINITY (required)
if (this.scanner.getToken() == Token.INFINITY) {
this.tryNextToken();
return null;
} else {
throw new ParseException("Zahl oder 'inf' erwartet!");
}
} else {
throw new ParseException("Zahl oder '-inf' erwartet!");
}
} else if (this.scanner.getToken() == Token.LPAREN2) {
this.tryNextToken();
// Parse NUMBER (required)
if (this.scanner.getToken() == Token.NUMBER) {
double number = Double.parseDouble(this.scanner.getTokenValue());
this.tryNextToken();
return new GreaterEqualSetNode(number);
} else {
throw new ParseException("Zahl erwartet!");
}
} else {
throw new ParseException("Menge erwartet!");
}
}
/**
* To ::= NUMBER ( LPAREN2 | RPAREN2 )
* | [ PLUS ] INFINITY LPAREN2
* @throws ParseException Quellprogramm ist syntaktisch fehlerhaft.
* @return Eine Menge als Teilbaum des Syntaxbaumes.
*/
private SetNode To() throws ParseException {
// Parse NUMBER or else (required)
if (this.scanner.getToken() == Token.NUMBER) {
double number = Double.parseDouble(this.scanner.getTokenValue());
this.tryNextToken();
// Parse LPAREN2 or RPAREN2 (required)
if (this.scanner.getToken() == Token.LPAREN2) {
this.tryNextToken();
return new LowerSetNode(number);
} else if (this.scanner.getToken() == Token.RPAREN2) {
this.tryNextToken();
return new LowerEqualSetNode(number);
} else {
throw new ParseException("']' oder '[' erwartet!");
}
} else {
// Parse PLUS (optional)
if (this.scanner.getToken() == Token.PLUS) {
this.tryNextToken();
}
// Parse INFINITY (required)
if (this.scanner.getToken() == Token.INFINITY) {
this.tryNextToken();
} else {
throw new ParseException("Zahl oder 'inf' erwartet!");
}
// Parse LPAREN2 (required)
if (this.scanner.getToken() == Token.LPAREN2) {
this.tryNextToken();
return null;
} else {
throw new ParseException("'[' erwartet!");
}
}
}
}
SetNode setNode = new UnionSetNode();
SetNode setNode = kit.getUnionSetNode();