# Recursive Descent Parsing in Java

• 10-06-2010, 03:50 PM
hypnoticohm
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:

The string "a=a+b-c*d" is in the language.
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!!
• 10-06-2010, 04:06 PM
Norm
Do you have the algorithm for solving your problem?
• 10-06-2010, 04:12 PM
hypnoticohm
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
• 10-06-2010, 04:14 PM
JosAH
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:

The string "a=a+b-c*d" is in the language.
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