Hey guys,
Been awhile since I've done any JAVA, so I'm looking for some help. I'm trying to implement a recursive descent parser with three terminals ( @ , ?, @@). I could use some help on a couple issues:
1) The @ operator is supposed to be a unary prefix operator (i.e. @ a should evaluate to (a*a+11)mod(a+3)). I am having trouble switching the parseD and parseD1 functions around to make it recognize this. At this point it only recognizes a number then the @ function (i.e. 2 @ ), which is backwards.
2) What is the best way to give precedence to operators, so that @@>?>@? For example, if
a ? b @@ c, then c @@ b should be evaluated first.
3) Finally, is there anyway to tokenize without having to put a space in between each character? I would like to be able to write strings like this: a?b@@c instead of a ? b @@ c.
Thanks for any help you guys can provide on any of these three points.
import java.io.*;
import java.util.*;
public class ParseE {
static StringTokenizer st;
static String curr;
/** read the next token into curr */
static void next() {
try {
curr=st.nextToken().intern();
// use of intern() allows us to check equality with ==.
} catch( NoSuchElementException e) {
curr=null;
}
}
static void error(String msg) {
System.err.println(msg);
System.exit(-1);
}
static int parseD() {
int x=parseE();
return parseD1(x);
}
static int parseD1(int x) {
if (curr=="@") {
next();
return parseD1((x * x +11)%(x+3));
} else if(curr==")" || curr=="$") {
return x;
} else {
error("Unexpected :"+curr);
return x; // to make compiler happy
}
}
static int parseE() {
// E -> T E1
int x=parseT();
return parseE1(x);
}
static int parseE1(int x) {
// E1 -> T E1 | epsilon
if (curr=="?") {
next();
int y = parseT();
return parseE1(max(x,y));
} else if(curr==")" || curr=="$" || curr=="@" ) {
return x;
} else {
error("Unexpected :"+curr);
return x; // to make compiler happy
}
}
static int parseT() {
// T -> F T1
int x=parseF();
return parseT1(x);
}
static int parseT1(int x) {
// T1 -> * F T1 | epsilon
if (curr=="@@") {
next();
int y=parseF();
x = x + 27;
y = y*6;
return parseT1(gcd(x,y));
} else if(curr=="?" || curr==")" || curr=="$" || curr=="@") {
return x;
} else {
error("Unexpected :"+curr);
return x; // to make compiler happy
}
}
static int parseF() {
// F -> ( E ) | a
if( curr=="(") {
next();
int x=parseD();
if(curr==")") {
next();
return x;
} else {
error (") expected.");
return -1; // to make compiler happy
}
} else try {
int x=Integer.valueOf(curr).intValue();
next();
return x;
} catch(NumberFormatException e) {
error("Number expected.");
return -1; // to make compiler happy
}
}
static int max(int x, int y)
{
if((x+19) > (2 * y + 6))
return (x+19);
else
return (2 * y + 6);
}
static int gcd(int x, int y)
{
if (y==0)
{
return x;
}
else
return gcd(y, x%y);
}
public static void main(String args []) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader (System.in));
String line=in.readLine();
st = new StringTokenizer(line+" $");
next();
int x=parseD();
if(curr=="$") {
System.out.println("OK "+x);
} else {
error("End expected");
}
}
}