wood burning stoves*
The moose likes Java in General and the fly likes What is a recursive decent parser and how does it work? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "What is a recursive decent parser and how does it work?" Watch "What is a recursive decent parser and how does it work?" New topic
Author

What is a recursive decent parser and how does it work?

Jon Bud
Greenhorn

Joined: Jan 29, 2009
Posts: 12
I've tried reading multiple books. And they all give these crazy algorithms were they uses all these in general variables and set theory to describe how it parses the language.
If someone could list in some steps how this this works, it would be great. O the type of language I'm reading is basically assignment statements like a=b+c*d-e/d.
I also list the lauguage to so someone could explain that to me also.
Consider the following BNF grammar:

A -> I = E
E -> T + E | T - E | T
T -> P * T | P / T | P
P -> I | (E)
I -> a | b | ... | y | z

I've got down that I need to read to read in a stream of characters from some string. Basically, I get a char from that string and that is the character I am analyzing at that time. Also, I have down that I need a method for each rule in the language. I'm very confused though especially on the return values of the methods. The book I was reading, Programming Languages Principles and Paradigms, was using a lot of objects like "Token", and it seemed as if every single non-terminal value had an object dedicated to it. Like expression was a class. So, I asked someone else about this and his best answer was "Yeah you can use objects but you don't have too". Could someone elaborate on the significance of objects in implementing a recursive decent parser. Basically, what kind of return type should these methods return.

Also, does anyone know of any websites where this whole process is illustrated, like in a diagram or flowchart or something? Not, a parse tree because I already know how that works and it really doesn't help me in implementing this parser.

Finally, was this question place in the right forum or should it be in the intermediate?

And just so this is related to Java, I'm implementing in Java.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18545
    
  40

IMO, the best way to desribe a recursive decent parser, is a parser who methods only handle a small portion of the expression, and rely on recursion to deal with the rest.

For example, to process a math expression, it is possible to have a method that only does add and subtract, and since mult and div has higher precedence, to do it recursively. Something like this in pseudo code....



To continue... the mult and div can depend on the exponent method, because that has higher precedence...



And of course, the exponent can just get a value, as all the expressions has already been done.



Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18545
    
  40

Oops. I forgot that exponent have right to left association... so that is probably better handled by a recursive decent to itself....



Henry
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18545
    
  40

To make this even cooler, you can actually have the handleValue() method deal with open parens too... And have a recursive call right back to the top, since everything in the paren has it's own precedence....



Henry
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: What is a recursive decent parser and how does it work?
 
Similar Threads
Question for Herb (or anyone else) on Generics and unknown object types
Recursive Descent Parser Question
Parsing Commands from String Input
Get rid of line numbers
Can you explain what these parts of code mean?