Arithmetic expressions w. recursive descent parser?

Hi!


I'm new to parsing and compiling and just starting out here.
I'm trying to make a simple java program to parse arithmetic
expressions. To keep it simple, only integers are used in the
expression, together with * / + - ( ) as terminals.
I want the parser to be a predictive recursive descent parser, with 1
lookahead.


The problem is that I cant get the implementation right with +,- in
combination w. numbers starting w. + or -, eg. -45, +3, etc.
I would appreciate any help, pointers, tips, on how to get the + and -
operator correctly implemented with numbers that could start with + or
- .


Typical expressions that I want to parse:
(12--21)
5+4-1-2


A made a grammar but it was left-recursive, but I removed it and this
is the resulting grammar:


E -> TX | T
X -> +TX | +T | -TX | -T
T -> FY | F
Y -> *FY | /FY | /F | *F
F -> number
F -> (E)


I made a class, ArithmeticEvaluator, and below is the relevant
functions of that class. It is not very good design but I was only
interested to see if I understood the theory enough to implement it.


public void S()
{
if (this.input == null)
{
result = "No data to evaluate!";
}
else
{
try
{
this.result = String.valueOf(U());
}
catch (ExpressionException e)
{
result = e.toString();
}
}
}




private double E() throws ExpressionException
{
double tempus = T();


if (isAdditionOP(current()))
{
return tempus + X();
}
else if (isSubtractionOP(current()))
{
return tempus - X();
}
else
{
return tempus;
}
}


private double X() throws ExpressionException
{
double tempus = 0.0;


if (current() == '+')
{
nextToken();


tempus = T();


if (current() == '-')
{
tempus = tempus - X();
}
else if (current() == '+')
{
tempus = tempus + X();
}
}
else if (current() == '-')
{
nextToken();


tempus = T();


if (current() == '-')
{
tempus = tempus - X();
}
else if (current() == '+')
{
tempus = -tempus + X();
}
}
return tempus;
}


private double T() throws ExpressionException
{
double tempus = F();


if (isDivisionOP(current()))
{
double denominator = Y();
if (denominator == 0)
{
throw new ExpressionException("Not defined, cannot divide by zero");
}
return tempus / Y();
}
else if (isMultiplicationOP(current()))
{
return tempus * Y();
}
else
{
return tempus;
}
}


private double Y() throws ExpressionException, BufferUnderflowException
{
double tempus = F();


if (isMultiplicationOP(current()))
{
                                // some code...
}
else if (isDivisionOP(current()))
{
                                // some code...
}
return tempus;
}


private double F() throws ExpressionException
{
if (isLeftParanthesis(current()))
{
nextToken();


double tempus = U();


if (!isRightParanthesis(current()))
{
throw new ExpressionException("Expected right paranthesis, got: "
+current());
}
else if (input.position() == (input.limit()-1))
{
/* no more data */
return tempus;
}


nextToken();


return tempus;
}
else
{
return N();
}
}


private double N() throws ExpressionException, BufferUnderflowException


{
String number = new String();


/* must check for +,- since a number can start with those, eg. -4, +42
*/
if (isAdditionOP(current()) || isSubtractionOP(current()))
{
try
{
number += current();
nextToken();
}
catch (BufferUnderflowException e)
{
throw new ExpressionException("Expected a number after operator: "
+input.get(input.position()-1));
}
}


if (isDigit(current()))
{
number += getNumber();
return Double.parseDouble(number);
}
else
{
throw new ExpressionException("Expected a number!");
}
}


private int getNumber()
{
String number = new String();


while (isDigit(current()))
{
number += current();
try
{
nextToken();
}
catch(ExpressionException e)
{
/* if we get here, we have at least one digit */
return Integer.parseInt(number);
}
}
return Integer.parseInt(number);
}




/Regards
B.Mildh

Return to the comp.compilers page.
Search the comp.compilers archives again.