Skip to main content
GameDev.net gamedev.net
🔒 Locked

C++ parser for visual assist -- suggestions?

Unity
Started by TDragon Oct 3, 2005 at 4:59 PM 11 replies 4.8k views
Original Post
TDragon
TDragon
Given the current state of the code-completion/class-browsing (what I call Visual Assist) plugin for Code::Blocks -- very buggy -- and the author's lack of time available to update it, I decided to look into what it would take for me to either fix it up or create my own. I started getting acquainted with the current codebase for the plugin, and found that it's basically a homebrewn parser sewn into the plugin interface. Not the prettiest code, either -- meaning it's not the easiest to familiarize myself with. All of a sudden it's looking, if not easier, at least a lot more fun to go ahead and write my own -- especially for the learning experience. This, of course, led me down a fascinating path into the land of lexing and parsing and whatnot, which I haven't had much previous experience with. I went ahead and read up on Boost::Spirit and have spent most of the day happily messing around creating some sort of EBNF grammar for C and C++ (and I could probably end up spending weeks getting a working prototype of it, let alone filling in the gaps -- and then there's handling the output). My questions to the GameDev community, then, are these: How would you go about parsing C++ code with the end result of full-featured visual assist functionality in mind (think Visual Assist X from Whole Tomato) -- what tools would you use? Have you done anything like this before? Is there already a standard(-ish) library out there that will extract all the information I need for me? I looked at exuberant ctags and it was very promising, but didn't seem to extract all the scoping information I'd need. What other thoughts and suggestions would you have in the general area of providing visual assist functionality? Thanks, Twilight Dragon
TDragon
TDragon
If there is, I can't find it...and if you do know where to find it, or where another good grammar for C++ resides, that'd be great.

One consideration to be taken eventually is that of speed. Hearsay on mailing lists is that Spirit isn't the fastest camel in the pack, and for something like I need, parsing needs to happen fairly often (every time the file is saved, at a minimum; more often would be preferable) but without long pauses while it happens. Obviously I don't have any firsthand data to prove or disprove Spirit's speed, but if there are other options out there designed with this in mind, I'd definitely like to know.
TDragon
TDragon
Ah, I see. Unfortunately, that appears a very simple and limited lexer that only recognizes basic attributes of the language, without respect to placement, relation to other entities, scoping, and such. Not exactly the complexity I need -- it would take a heck of a lot of extension. I may have to end up writing my own, or giving that one some major extension to turn it into a full-fledged parser. Which is an option.

All suggestions welcome.

- Twilight Dragon
risingdragon3
risingdragon3
visual assist is NOT just parsing and such. There is far more complex work to be done to make it as "good" as eclipse or VS.NET or whole tomato. You need to do some semantic analysis as well. However, one problem is speed. Your parser and analysis needs to be superfast speedy stuff. Further, you can't just stick in a C++ EBNF and be done. Consider that your assist must work even when the file cannot be compiled, i.e, is not parseable! This means you must be quite clever and make sure your parser can recover from errors, and still go on parsing - fast. Then you have to do semantic analysis and so on.

For example, in eclipse they have an modified version of the parser so that it can handle errors properly, and an extremely fast (well, fast-ish?) handwritten semantic analysis for just the parts that they want to deal with.

VS is somewhat similar internally.

You will have to basically take an parser from, say, GCC or something, and then add significant error handling code, and then do some analysis on top. this is nontrivial - if you want a relaly good visual assist. But for some thing less complicated you can get away with just parsing ... maybe.
Promit
Promit
Probably the only functional open source code bases for this sort of thing are embedded deep within KDevelop or Anjuta...or worse yet, are in Emacs using LISP.

risingdragon3 summed a lot of the really big problems. There's a reason WholeTomato can charge a hundred bucks a pop for their things. It's a damn hard problem, particularly with a language like C++. Compare the quality of Intellisense in VC++ to VC# or VB.NET. The newer languages, VB in particular, have far better Intellisense. Not only is Intellisense hard in general, it's damn near impossible to do well in C++. Even VC breaks down oftentimes.
SlimDX | Ventspace Blog | Twitter | Diverse teams make better games. I am currently hiring capable C++ engine developers in Baltimore, MD.
TDragon
TDragon
risingdragon3, I was under the impression that parsing was implicitly involved in semantics, as opposed to lexing which is merely dividing the input into its basic grammatic components. Speaking of which, I'm not so sure that working from an entire C++ grammar would be desirable. Specifically, there are a lot of constructs that I don't need to handle -- if/else, switch, function calls (except when activating auto-complete, of course), etc. In fact I only really need to recognize variable declarations, type definitions (struct, class, typedef, enum), namespaces, function declarations, and using declarations.

Error recovery, though, will be a hard one. I can visualize recovering from inter-statement errors, but missing brackets I have yet to figure out.

I had thought along the lines of storing a "scope tree" from the input, with the global namespace being the root and variables being the leaves; namespaces, class defs, function defs, etc. in between. Does this sound viable?

Thanks,
Twilight Dragon
risingdragon3
risingdragon3
Quote:
Original post by TDragon
risingdragon3, I was under the impression that parsing was implicitly involved in semantics, as opposed to lexing which is merely dividing the input into its basic grammatic components. Speaking of which, I'm not so sure that working from an entire C++ grammar would be desirable. Specifically, there are a lot of constructs that I don't need to handle -- if/else, switch, function calls (except when activating auto-complete, of course), etc. In fact I only really need to recognize variable declarations, type definitions (struct, class, typedef, enum), namespaces, function declarations, and using declarations.

Error recovery, though, will be a hard one. I can visualize recovering from inter-statement errors, but missing brackets I have yet to figure out.

I had thought along the lines of storing a "scope tree" from the input, with the global namespace being the root and variables being the leaves; namespaces, class defs, function defs, etc. in between. Does this sound viable?

Thanks,
Twilight Dragon


ALthough technically parsing includes analysis, analysis is such a big part that a lot of compiler writers like to put that as a seperate stage along with optimization.
As for part of the grammar only, it's a good idea, since that will also speed up analysis. But you need a lot of things. Consider:

int a() {int b;if(c == 4) {int q;}else {float q;}}

How is q defined? what's it's type? etc. etc.

Further, consider .h files, and stuff. macros - how will you handle them? I dont' really know how VC does it.

About your idea for scoping: you are stumbling onto stuff that people have researched well and have worked out well 30 years ago. Check out compiler classes, read lecture notess - all of this will help you. Please don't be reinventing the wheel badly.
Troll
Troll
Boost.Spirit does not contain a C++ parser. C++ is not a context-free language; therefore, you cannot necessarily properly parse a file without doing a semantic analysis of the text. C++ is much more difficult to parse than C, Pascal, LISP, etc.
TDragon
TDragon
Awesome...I may well have stumbled upon a project to keep me occupied for the next 5 years or so. I guess it makes sense that parsing the language with respect to visual assist is tied up in compiler design. That's what I'll research next; I may even be able to fit a class involving compiler design in next semester as an elective.

Any other thoughts and suggestions are as always welcome.

- Twilight Dragon
WillC
WillC
You could also check out ANTLR, although it may be a bit OTT for your needs.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.