Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
Jon Bud
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 21504
84
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Henry Wong
author
Marshal
Pie
Posts: 21504
84
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 21504
84
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic