aspose file tools*
The moose likes Java in General and the fly likes Recursive Descent Parser Question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Recursive Descent Parser Question" Watch "Recursive Descent Parser Question" New topic
Author

Recursive Descent Parser Question

Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

I have a recursive descent parser that I've built to check the syntax of a program that I am interpreting. My parser is set up as a chain of private methods that are of type void.
Is it wrong for me to use a return statement to exit a void method?

-Hunter


"If the facts don't fit the theory, get new facts" --Albert Einstein
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18994
    
  40



Having written a ton of recursive decent parsers... if it is anything like the ones that I wrote, I say "why not"? The individual methods are generally really small, no more than 20 lines, with comments, that it is not going to confuse anyone, by having a return from mid method.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Well, there is a school of thought that says that a method should have a single point of exit. That means only one return at the end of the method - unless the method is void, in which case, no returns at all. Also no break or continue statements. According to this school of thought, multiple returns, breaks, and continues all can result in code that is less readable to humans, and thus more prone to errors.

Now personally, I don't agree with this school of thought. I agree completely with Henry's post above. Most any problems with multiple returns, or break or continue, are best resolved by keeping your methods short. Which tends to produce other nice results as well. If your 100-line method is hard to understand because you didn't notice a return statement at line 47, the first step is to split it up into smaller methods and reduce the line count per method. After that, the extra return is much less likely to be a problem.

However, people do still exist who will tell you that multiple returns are bad. You may have to either convince them otherwise, ignore them, or obey them - depending on your relative powers of persuasion, and on who is paying your salary. So it's good to be aware that such viewpoints exist. For more historical background, start with Structured Programming. Or for more discussion and articles, google "single exit point".
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

Well in this case all of my methods are short since I am only traversing tokens that I have preivously identified. Thank you for the link though.

-Hunter
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

I'm also in the "multiple returns are fine" until they're not camp.
Matthew Fierro
Greenhorn

Joined: Mar 20, 2010
Posts: 16
Henry Wong wrote:

Having written a ton of recursive decent parsers... if it is anything like the ones that I wrote, I say "why not"? The individual methods are generally really small, no more than 20 lines, with comments, that it is not going to confuse anyone, by having a return from mid method.

Henry


Would you happen to have an RDP program that can handle the following grammar?



***NOTE This grammar says that something like the following could be an acceptable input string

2^2^3,15,2^20



Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18994
    
  40

Matthew Fierro wrote:
Would you happen to have an RDP program that can handle the following grammar?


Well, with the amount that I did, I could probably churn one out in 15 minutes. Maybe 3 or 4 methods -- one for each rule, except for maybe the digit one. And a couple of support methods, getchar, ungetchar, etc. But that is not the point....


What have you done so far? And what are you having problems with? If you tell us the issue, we can probably give you a hint in the right direction.

Henry
Darryl Burke
Bartender

Joined: May 03, 2008
Posts: 4658
    
    5

Henry Wong wrote:
Matthew Fierro wrote:
Would you happen to have an RDP program that can handle the following grammar?

What have you done so far?
Henry

I can answer that.
http://www.java-forums.org/advanced-java/26859-recursive-descent-parser.html
http://www.javaprogrammingforums.com/algorithms-recursion/3777-recursive-descent-parser.html
http://www.codeguru.com/forum/showthread.php?p=1925894
http://www.cplusplus.com/forum/general/21208/
http://www.dreamincode.net/forums/index.php?showtopic=163179

Called me something nice on the Sun forums too, but the post was blocked ;)


luck, db
There are no new questions, but there may be new answers.
Matthew Fierro
Greenhorn

Joined: Mar 20, 2010
Posts: 16
Here is some pseudocode. I have very little Java experience and the assignment must be done in Java.








Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18994
    
  40


Well, that's pretty detailed pseudo code... certainly more detailed than I would have done it. So... what is the issue? It looks like you have everything designed out, and ready -- just need to actually code it in Java. And given the detail of pseudo code, it should be easy.

Henry
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18994
    
  40



Oh, I see the issue now... he didn't write the pseudo code (it came from one of the links). So, he doesn't know the design, or even probably how recursive decent works.

In that case, I recommend dumping the pseudo code and starting with pen and paper, or even going back to the text book and class notes. Recursion is not a topic that you want done for you. It is a very powerful tool. You will need it in the future. And you really need to learn it, instead of having homework done for you.

Henry
Matthew Fierro
Greenhorn

Joined: Mar 20, 2010
Posts: 16
no actually I did write the pseudocode. I was the one who posted it on those sites. The guy who posted those links just [DELETED].
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

In that case, please see BeForthrightWhenCrossPostingToOtherSites.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18994
    
  40

Matthew Fierro wrote:no actually I did write the pseudocode. I was the one who posted it on those sites.



Then you are more than 90% done... as the design, and pseudo code implemention is the bulk of the work. And as I mentioned in a previous post, I was impressed with the detail of the pseudo code. So, it should be very easy...

What issue are you running into?

Henry
Matthew Fierro
Greenhorn

Joined: Mar 20, 2010
Posts: 16
I know, but I am not a Java Programmer and I was hoping someone could give me a boost, maybe show me how to write a method or two.
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

What specifically are you having issues with? There are quite a large number of Java tutorials that cover everything you need to get started. We're more likely to provide assistance if you ShowSomeEffort.
Matthew Fierro
Greenhorn

Joined: Mar 20, 2010
Posts: 16
ok I gave a shot at converting the first procedure to java. Some parts that I had no clue I just left in pseudocode. I should mention that all of the variables must be kept global. In java are global variables the same as instance variables?

David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

Perhaps writing it in whatever language you're familiar with first would be beneficial--why must it be done in Java if you're not familiar with Java?
Matthew Fierro
Greenhorn

Joined: Mar 20, 2010
Posts: 16
Our professor only has solutions for Java and C++
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18994
    
  40

Matthew Fierro wrote: In java are global variables the same as instance variables?


In Java, an instance variable is tied to a specific instance of an class -- meaning there is one copy of the variable per instance. So... if you happen to have only one instance, and it is publically accessible, then it is just like a global variable.

Henry
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

I guess I'd still suggest writing it in a language you know (what do you know?) and then looking at either Java/C/C++ guides for conversion hints, or starting a *new* thread (rather than hijacking this one) with specific questions regarding the language conversion process.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursive Descent Parser Question