Recursive Descent Parsing in Java

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


Using the technique described in class implement a recursive descent parser that recognizes strings in this language. Input should be from a file called input.dat and output should be to the console. 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.


im really confused on what exactly i am suppose to do.

I don't know where to start and I am unsure of what this program is suppose to do. PLEASE HELP!!

Do you have the algorithm for solving your problem?
Given that, we can help you implement it in java.

I have been doing some research and this is what i found:


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.

-All credit above goes to CodesAway ~ Senior Member

Quote:

---

Originally Posted by hypnoticohm

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


Using the technique described in class implement a recursive descent parser that recognizes strings in this language. Input should be from a file called input.dat and output should be to the console. 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.


im really confused on what exactly i am suppose to do.

I don't know where to start and I am unsure of what this program is suppose to do. PLEASE HELP!!

---

Your teacher/professor wants to see methods like this:

Code:

---

private void parseAssignment(Reader r) {
  parseIdentifier(r);
  if (r.read() != '=')
      throw new ParseException("= expected");
  parseExpression(r);
}

private void parseExpression(Reader r) {
  parseTerm(r);
  int op= r.read();
  if (op == '+' || op == '-')
      parseExpression(r);
}

---

etc. etc. for the other grammar rules.

kind regards,

Jos