Compilerbau: JLex Scanner und LALR(1) CUP Parser für Arithmetische Ausdrücke
| Compilerbau: JLex Scanner und LALR(1) CUP Parser für Arithmetische Ausdrücke |
|
|
In diesem Beispiel wird eine Sprache für Arithmetische Ausdrücke definiert und verarbeitet. Es werden Ausdrücke mit int und double Zahlen, mit den 2-stelligen Operatoren +, -, * und / mit Prioritäten, mit einstelligen Operatoren für + und - und mit Konversionsoperatoren verarbeitet. Für diese Ausdrücke wird ein Programmbaum aufgebaut. Es werden Klassen für den Programmbaum analog zu dem Beispiel aus der Java-Vorlesung: Verarbeitung von Ausdrücken verwendet. In diesem Beispiel ist keinerlei Fehlerbehandlung für Syntaxfehler enthalten, es ist also nur für syntaktisch korrekte Eingaben brauchbar. Für ernsthaft einsetzbare Progamme müssen noch Erweiterungen und Verbesserungen zur Fehlerbehandlung gemacht werden. |
|
import java_cup.runtime.Symbol;
%%
%cup
%class scanner
%implements java_cup.runtime.Scanner
%function next_token
%type Symbol
digit=[0-9]
digits={digit}+
digits0={digit}*
%%
"+" { return
new Symbol(sym.PLUS);
}
"-" { return
new Symbol(sym.MINUS);
}
"*" { return
new Symbol(sym.TIMES);
}
"/" { return
new Symbol(sym.DIVIDE);
}
"(" { return
new Symbol(sym.LPARENT);
}
")" { return
new Symbol(sym.RPARENT);
}
"double"
{ return
new Symbol(sym.DOUBLE);
}
"int"
{ return
new Symbol(sym.INT);
}
{digits}
{ return
new Symbol(sym.NUMBER,
new String(yytext()));
}
({digits}"."{digits0})|({digits0}"."{digits})
{ return
new Symbol(sym.REAL,
new String(yytext()));
}
[ \t\r\n\f]
{
/* ignore white space. */
}
. { System.err.println("Illegal character: "
+ yytext());
}
|
|
Die Festlegung der Prioritäten der Arithmetischen Operatoren sind hier durch Grammatik-Regeln gemacht worden, bei umfangreicheren Grammatiken können Prioritäten und Assoziativitäten für Operatoren verwendet werden, so dass die Parser-Tabellen dadurch verkleinert werden. import java_cup.runtime.*;
parser code {:
public
static
void
main(String args[])
throws Exception {
new parser(new scanner(System.in)).parse();
}
:}
terminal PLUS, MINUS, TIMES, DIVIDE, LPARENT, RPARENT, DOUBLE, INT;
terminal String NUMBER, REAL;
non terminal prog;
non terminal Expr expr, term, factor;
prog ::= expr:e
{: System.out.println( e
+ " = "
+ e.eval());
:}
;
expr ::= expr:l PLUS term:r
{: RESULT =
new BinaryPlus(l,r);
:}
| expr:l MINUS term:r
{: RESULT =
new BinaryMinus(l,r);
:}
| term:t
{: RESULT = t; :}
;
term ::= term:l TIMES factor:r
{: RESULT =
new Mult(l,r);
:}
| term:l DIVIDE factor:r
{: RESULT =
new Divide(l,r);
:}
| factor:f
{: RESULT = f; :}
;
factor ::= LPARENT expr:e RPARENT
{: RESULT = e;
:}
| NUMBER:n
{: RESULT =
new Const(
new Integer(n));
:}
| REAL:n
{: RESULT =
new Const(
new Double(n));
:}
| PLUS factor:f
{: RESULT =
new UnaryPlus(f);
:}
| MINUS factor:f
{: RESULT =
new UnaryMinus(f);
:}
| LPARENT DOUBLE RPARENT factor:f
{: RESULT =
new IntToDouble(f);
:}
| LPARENT INT RPARENT factor:f
{: RESULT =
new DoubleToInt(f);
:}
;
|
Expr/** $Id: Expr.java,v 1.2 2007-01-02 17:49:52 uwe Exp $
* eine abstrakte Klasse fuer die Konstruktion
* beliebiger Ausdruecke
* und zum Auswerten dieser Ausdruecke
*
*/
//--------------------
public
abstract
class Expr {
// die eval Funktion
// liefert ein beliebiges Objekt als Resultat
// damit koennen nicht nur arithmetische Ausdruecke
// sondern Ausdruecke mit beliebigem Resultat
// behandelt werden
public
abstract
Object eval();
}
//--------------------
BinaryExpr/** $Id: BinaryExpr.java,v 1.2 2007-01-02 17:49:52 uwe Exp $
* eine abstrakte Klasse fuer binaere Ausdruecke
*
*/
//--------------------
abstract
class BinaryExpr extends Expr {
// die Operanden
protected
Expr left;
protected
Expr right;
//--------------------
// der Konstruktor ist protected
// da er nur von Subklassen aus aufgerufen wird
protected
BinaryExpr(Expr left, Expr right) {
this.left = left;
this.right = right;
}
}
//--------------------
BinaryPlus/** $Id: BinaryPlus.java,v 1.2 2007-01-02 17:49:52 uwe Exp $
* eine Klasse fuer das binaere Plus
*
*/
//--------------------
public
class BinaryPlus extends BinaryExpr {
//--------------------
public
BinaryPlus(Expr left, Expr right) {
super(left, right);
}
//--------------------
public
Object eval() {
// beide Operanden auswerten
Object value1
= left.eval();
Object value2
= right.eval();
// + fuer int
if ( value1 instanceof Integer
&&
value2 instanceof Integer ) {
return
new Integer( ((Integer)value1).intValue()
+
((Integer)value2).intValue() );
}
// + fuer double
if ( value1 instanceof Double
&&
value2 instanceof Double ) {
return
new Double( ((Double)value1).doubleValue()
+
((Double)value2).doubleValue() );
}
// nicht erlaubtes Argument
throw
new IllegalArgumentException("binary + : illegal operand types");
}
//--------------------
public
String toString() {
return
"(" + left.toString() +
" + " + right.toString() +
")";
}
}
//--------------------
Die anderen Operatoren werden durch analoge Klassen dargestellt. UnaryExpr/** $Id: UnaryExpr.java,v 1.2 2007-01-02 17:49:52 uwe Exp $
* eine abstrakte Klasse fuer unaere Ausdruecke
*
*/
//--------------------
abstract
class UnaryExpr extends Expr {
// der Operanden-Ausdruck
protected
Expr operand;
//--------------------
protected
UnaryExpr(Expr operand) {
this.operand = operand;
}
}
//--------------------
UnaryMinus/** $Id: UnaryMinus.java,v 1.2 2007-01-02 17:49:52 uwe Exp $
* eine Klasse fuer das unaere Minus
*
*/
//--------------------
public
class UnaryMinus extends UnaryExpr {
//--------------------
public
UnaryMinus(Expr operand) {
super(operand);
}
//--------------------
// eval wertet den Operanden aus
// und negiert den Wert
// Operation erlaubt fuer int und double Werte
public
Object eval() {
// operand auswerten
Object value
= operand.eval();
// - fuer int
if ( value instanceof Integer ) {
return
new Integer(- ((Integer)value).intValue());
}
// - fuer double
if ( value instanceof Double ) {
return
new Double(- ((Double)value).doubleValue());
}
// nicht erlaubtes Argument
throw
new IllegalArgumentException("unary - : illegal operand type");
}
//--------------------
public
String toString() {
return
"-(" + operand.toString() + ")";
}
}
//--------------------
IntToDouble/** $Id: IntToDouble.java,v 1.1 2000/01/10 17:05:54 uwe Exp $
* eine Klasse zum Konvertieren von int Operanden
* in double Operanden
*
*/
//--------------------
public
class IntToDouble extends UnaryExpr {
//--------------------
public
IntToDouble(Expr operand) {
super(operand);
}
//--------------------
// eval wertet den Operanden aus
// und konvertiert ihn nach double
public
Object eval() {
// operand auswerten
Object value
= operand.eval();
// int to double Konversion
if ( value instanceof Integer ) {
return
new Double( ((Integer)value).doubleValue() );
}
if ( value instanceof Double ) {
return
value;
}
// nicht erlaubtes Argument
throw
new IllegalArgumentException("int to double: illegal operand type");
}
//--------------------
public
String toString() {
return
"((double)" + operand.toString() + ")";
}
}
//--------------------
Die anderen Operatoren werden durch analoge Klassen dargestellt. |
|
JCP := $(PWD)/../../../software:$(PWD)/../../../software/CUP:.:$(CLASSPATH)
JAVA := java -classpath $(JCP)
JAVAC := javac -classpath $(JCP)
JLEX := java -classpath $(JCP) JLex.Main
CUP := java -classpath $(JCP) java_cup.Main
lexsrc := $(shell echo *.lex)
cupsrc := $(shell echo *.cup)
javagen := scanner.java parser.java sym.java
javasrc := \
Test.java \
Expr.java Const.java UnaryExpr.java BinaryExpr.java \
UnaryPlus.java UnaryMinus.java IntToDouble.java DoubleToInt.java \
BinaryPlus.java BinaryMinus.java Mult.java Divide.java
classes := $(javagen:.java=.class) $(javasrc:.java=.class)
tests = test0 test1
all : examples
examples : $(javagen) $(classes) $(tests)
scanner.java : expr.lex sym.java
$(JLEX) $<
mv $<.java scanner.java
parser.java sym.java : expr.cup
$(CUP) $<
test0 : $(classes)
echo "1" | $(JAVA) parser
test1 : $(classes)
echo "(3 + - - 8 / 2) * (8 - 2) * (int)((double)12 / 10.0)" | $(JAVA) parser
%.java : %.lex
$(JLEX) $<
%.class : %.java
$(JAVAC) $<
.SUFFIXES : .class .java .lex .cup
clean :
rm -f $(javagen) *.class *~ .*~
|
|
java ... java_cup.Main expr.cup
Opening files...
Parsing specification from standard input...
Checking specification...
Building parse tables...
Computing non-terminal nullability...
Computing first sets...
Building state machine...
Filling in tables...
Checking for non-reduced productions...
Writing parser...
Closing files...
------- CUP v0.10k Parser Generation Summary -------
0 errors and 0 warnings
12 terminals, 5 non-terminals, and 15 productions declared,
producing 29 unique parse states.
0 terminals declared but not used.
0 non-terminals declared but not used.
0 productions never reduced.
0 conflicts detected (0 expected).
Code written to "parser.java", and "sym.java".
---------------------------------------------------- (v0.10k)
java ... JLex.Main expr.lex
Processing first section -- user code.
Processing second section -- JLex declarations.
Processing third section -- lexical rules.
Creating NFA machine representation.
NFA comprised of 62 states.
Creating DFA transition table.
Working on DFA states..........................
Minimizing DFA transition table.
21 states after removal of redundant states.
Outputting lexical analyzer code.
mv expr.lex.java scanner.java
javac ... scanner.java
javac ... parser.java
javac ... Test.java
# a very simple test run
echo "1" | java ... parser
1 = 1
# a bit more complex expression
echo "(3+--8/2)*(8-2)*(int)((double)12/10.0)" \
| java ... parser
(((3 + (-(-(8)) / 2)) * (8 - 2)) * ((int)(((double)12) / 10.0))) = 42
|
| Letzte Änderung: 14.02.2012 | © Prof. Dr. Uwe Schmidt |
