recursive decent parser

Anyone happen to have a RDP program that handles the following grammar?

Code:

---

<elist>  ->  <elist>,<e>|<e>     
<e>      ->  <n>^<e>|<n>
<n>    ->    <n><d>|<d>
<d>    ->    0|1|2|3|4|5|6|7|8|9

---

I wrote some pseudocode which I think will do the trick. I just need some help converting this into Java. I must use Java for this project. If it were me I would have done this in Perl or PHP, something I am more familar with, but I can't. Here is the pseudcode.

Code:

---

procedure RDPARSER;
  while NOT EOF do
  SUCCEEDED = TRUE;
  GET_INP_LINE; //reads in the next input line
  GET_NEXT_SYMBOL; //returns the next input symbol
  ELIST;
 if SUCCEEDED
then SUCCESS_MESSAGE;
else FAILURE_MESSAGE enif
endwhile
end RDPARSER

---

Code:

---

procedure ELIST;
E;
if SUCCEEDED
 then ELIST_TAIL endif
end ELIST;

---

Code:

---

procedure ELIST_TAIL;
if EOL
then print E_Value
else if next_inp_symbol = ","
then print E_Value;
GET_NEXT_SYMBOL;
ELIST;
else SUCCEEDED = FALSE endif
endif
end ELIST_TAIL;

---

Code:

---

procedure E;
N_value = 0;
N;
if SUCCEEDED
then ETAIL endif
end E;

---

Code:

---

procedure ETAIL
if(NOT((next_inp_symbol = ",") OR EOL))
then if next_inp_symbol = '^'
then GET_NEXT_SYMBOL;
E;
E_value = N_value ** E_value;
else SUCCEEDED = FALSE endif
else E_value = N_value enidf
end ETAIL;

---

Code:

---

procedure N;
D;
if SUCCEEDED
then N_value = N_value * 10 + D_value;
NTAIL endif
end N;

---

Code:

---

procedure NTAIL;
if(NOT((next_inp_symbol = '^' | ',') OR EOL))
then N endif
end NTAIL;

---

Code:

---

procedure D;
if next_inp_symbol is a digit
then compute D_value;
GET_NEXT_SYMBOL
else SUCCEEDED = FALSE endif
end D;

---

any help converting this pseudocode I wrote into Java would be greatly appriciated.

I didn't look at your pseudocode, but some grammars with left-recursion can be modified so they are suitable for recursive descent parsing. The grammar productions you show are among them.

Is this for a compiler class? Your text should have a section on "eliminating left recursion".
Your two problem productions are <elist> and <n>. To eliminate left recursion, you want to transform a grammar production of the form

Code:

---

<lrecursor>    ->  <lrecursor><Alt1> | <Alt2>

---

into the two alternatives

Code:

---

<lrecursor>    ->  <Alt2><rrecursor>
<rrecursor>  ->  <Alt1><rrecursor> | NULL

---

to eliminate the roadblock.

Hope this helps.

I know but our prof wants us to implement the RDP just as I have it in the pseudocode. The class is called Theoretical Concepts of Programming Languages. We are studying lexical and syntactical analysis.

Well maybe I should also mention that our prof wants us to have the user of the program be able to enter a string such as 2^2^3,15,2^2. Notice the comma seperated list. This string is what gets handled by the regular langauge I showed. So this would translate to
2^2^3(+|-|*)15(+|-|*)2^2

I see (I think). I did not previously look at your pseudocode but you have already used the suggested mechanism or something similar to eliminate the left recursion.

About the only thing I can offer then would be to use the return values from your procedures to construct the numerical values rather than having global values. More importantly, you'll probably get a cleaner implementation if you use Java's exception mechanism to handle syntax/parse errors, because then you won't have to obscure intermediate procedures with error handling.

Be sure your code follows the grammar as closely as possible: I'm mildly suspicious of the pseudocode for <etail>. I would expect to <etail> to be

Code:

---

<etail>  ->  ^<e><etail> | NULL

---

but the pseudocode has a test for a comma and end-of-line in addition to the ^.
Also the eol seems to be a non-whitespace character in the language, but it does not appear in the grammar.

Sorry not to be more helpful... I haven't done anything significant with Java in many years.

Posted all over the internet.
http://forums.sun.com/thread.jspa?threadID=5432690
http://www.dreamincode.net/forums/in...owtopic=163179
http://www.cplusplus.com/forum/general/21208/
http://www.javaprogrammingforums.com...nt-parser.html
http://www.java-forums.org/advanced-...nt-parser.html

db

Now also on the Ranch as a thread hijack:
[http://www.coderanch.com/t/487691/Ja...escent-Parser]

db