BNF grammar using recursive descent parsing

[carolain79@hotmail.com]

help with BNF Grammar program using recursive descent parsing
Consider the following BNF grammar:

A -> I = E
E -> T + E | T - E | T
T -> P * T | P / T | P
P -> I | L | (E)
I -> a | b | ... | y | z
L -> 0 | 1 | ... | 8 | 9

implement a recursive descent parser that recognizes strings in this language.

An example session might look like this:

String read from file: a=a+b-c*d
The string "a=a+b-c*d" is in the language.
String read from file: a=a**b++c
The string "a=a**b++c" is not in the language.

The problem with the following code is that for any string that I input even if it is in the language , it shows the message is not in the language, I dont know where the error in my code is.
I would really appreciate your help!!

public class BnfGrammar {


public static void main(String[] args) {

s = args.length == 1 ? args[0] : "a=a+b-c*d";

if (A() && i == s.length()) {
System.out.println("The string \"" + s + "\" is in the language.");
}
else {
System.out.println("The string \"" + s + "\" is not in the language.");
}
}

private static boolean A() {

if (I()) {
if (i < s.length() && s.charAt(i) == '=') {
++i;
if (E()) {

return true;

}
}
}

return false;
}

private static boolean E() {

if(T()){
if (i < s.length() && s.charAt(i) == '+') {
++i;
if(E()){

return true;
}
}
}
else if(T()){
if (i < s.length() && s.charAt(i) == '-'){
i++;
if(E()){

return true;
}

}

}
else if(T()){

return true;
}

return false;
}

private static boolean T(){
if (P()){
if (i < s.length() && s.charAt(i) == '*'){
i++;
if(T()){

return true;
}
}
}
else if(P()){
if(i < s.length() && s.charAt(i) == '/'){
i++;
if(T()){

return true;
}
}
}
else if(P()){

return true;
}

return false;
}

private static boolean P(){
if(I()){
return true;
}
else if (L()){
return true;
}
else if(i < s.length() && s.charAt(i) == '('){
++i;
if (E()){
if (i < s.length() && s.charAt(i) == ')') {
++i;
return true;
}
}
}


return false;
}

private static boolean I() {

if (i < s.length() && s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
++i;
return true;
}

return false;
}

private static boolean L(){
if (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
++i;
return true;
}

return false;

}


private static String s;
private static int i;






}

[CodesAway]

First thing I noticed is that in your E() method, you have three branches that all call method T to see whether to precede. This shouldn't be done, since if T() is false the first time, T() should be false the second, and the third as well. The same problem occurs in your T function, where you call P() for each of the three branches.

Second thing I noticed is that even if a method returns false, if it "partially" matches, then the "cursor" is moved forward, but if the method returns false, then the "cursor" shouldn't move at all, correct?


For example, given your test input "a=a+b-c*d", here are the steps

1) Call A
2) A calls I
3) I checks to see if the current character is a letter between 'a' and 'z'
3a) It is an 'a', so you advance the cursor and return true
4) Back in A, I is true, so you check for an '='
4a) It is, so you call E
5) In E, you call T
6) In T, you call P
7) In P, you call I
8) You check for a letter between 'a' and 'z'. The next character is 'a', so true
8a) Advance cursor, and return true
9) Back in P, I returns true
9a) So, P returns true
10) Back in T, P is true, so you check for a '*'. This is false, since a '+' occurs
10b) T returns false!
10c) It should return true, since the third branch for T says that P is a valid match. However, your code doesn't try this branch. Your code, instead, uses an "if-else" branching, whereas parsing tries ALL branches.

[carolain79@hotmail.com]

thank u so much ! my code works now