Slashdot Mirror
GCC Gets PCH Support And New Parser
Screaming Lunatic writes "GCC will finally get precompiled header support which should help with faster compile times. GCC will also be fitted with a new recursive descent parser that fixes more than 100 bugs in GCC. I'm not sure how they decomposed C++ into a context free grammar so that it could be parsed using recursive descent."
since the link for the parser is dated 2000 it's a bit confusing as to why this is news. However the 3.4 changelog (yes, 2 versions away for both features) meantions both.
http://gcc.gnu.org/gcc-3.4/changes.html
Terrence Parr, the author of the antlr compiler construction tool says that most languages can be parsed with LL-k grammars provided you have a deep enough look ahead (that means 'k' is big enough).
... however this is a guess(stemming from java parsers which are often LL-1)
Basicly: you aer NOT context free but context sensitive, of course.
Terrence showed that in practice the hughe drawbacks of a look ahead of k does not appear often.
I would think the typical look ahead for C++ is 1 in over 85% of the cases and 2 for the rest and in rare cases 4
angel'o'sphere
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
One of things sorely missing in C++ is an easy way to analyze source code. Would that new parser simplify this? Can I use it outside of gcc to implement a refactoring tool (for example).
Anyway, the links provide little to no information. Perhaps someone knows more.
Why, why, why, why? Why can't the header file simply be compiled at the first inclusion and cached somewhere? I know I am bitching about a single step here, but can anyone explain to me the rationale behind this?
context free grammar
This is good for slashdot, which is a grammar-free context!
(OT) Just wait until you see C++0x. It will (probably) support variable definitions like
and figure out a type for iter by looking at the result type from map<>::begin().From the gcc.gnu.org homepage news:
January 10, 2003
Geoffrey Keating of Apple Computer, Inc., with support from Red Hat, Inc., has contributed a precompiled header implementation that can dramatically speed up compilation of some projects.
December 27, 2002
Mark Mitchell of CodeSourcery has contributed a new, hand-crafted recursive-descent C++ parser sponsored by the Los Alamos National Laboratory. The new parser is more standard conforming and fixes many bugs (about 100 in our bug database alone) from the old YACC-derived parser.
... in my experience, good use of forward declarations (to avoid unrequired chains of #include), combined with simply putting less in each .c file is a lot more effective than adding the complication of precompiled headers into your build process.
Great... that will make using C++ templates and stuff a bit nicer...
(Of course, SML and O'Caml (and related languages) have had much more sophisticated type inference for 30 years!)
Just to clarify: A language does not need to be context-free in order to be parsed by a recursive descent parser, because you can augment the recursive functions with extra arguments that provide, well, context. For instance:
::= x | let [dec] in [exp] end | n | print [exp]
::= val x = [exp]
[exp]
[dec]
(where x is the set of variables and n is the set of integer constants)
This language is context-free, but the following restriction isn't: We say that strings are only in this language if variables aren't used before being declared. Legal:
let
val x = 3
in
print x
end
Illegal:
let
val x = 3
in
print y
end
This language isn't context-free (in the usual sense) but can be parsed easily by a recursive function. That function simply takes with it a list of all the declared variables. (In fact, you can pull this same sort of hack with lex/yac by having the lexer make a call into your code, which keeps a symbol table of variables it has seen as it runs.)
(If I understand the problem with C and C++ correctly, the difficulty parsing has to do with recognizing a token as a type name or an identifier, so I think this is relevant.)
A predictive bottom-up LR parser is more powerful than top-down LL. It's in the dragon book. Additionally, a top-down, recursive descent parser (using a stack or recursive calls) has huge, huge memory requirements (non-deterministic). SLR(1)/LALR(1)/LALR(k) parsers are usually table driven, and are essentially finite state machines (FSMs). Shift-Reduce parsers (such as those generated by lex/yacc/flex/bison) use a symbol stack that doesn't grow huge with one-or-more or zero-or-more conditionals, because it reduces. Bottom up parsers tend to push all the previous crap on to the stack, all the way up to the root node. Index operations are several orders of magnitude faster than procedure calls. Sounds like GCC is having a case of feature creep. I'll stick to 2.95 TYVM.
The biggest trick the devil pulled was letting lawyers become politicians so they can write the laws.
In terms of grammars alone, I believe that is somewhat correct but we're talking about a compiler here. LL parsing is often helpful because it can create and use inherited attributes. A top-down parser can perform some of the semantic work that an LR bottom-up parser cannot.
I also don't think that the recursive call stack should be of much concern because GCC will probably do something like that anyway (though maybe not as fine grained) in the next compiler pass. As said before, it might actually reduce the amount of work.
What do you mean by 'huge memory requirements (non-deterministic)'? Yes, an LL parser will maintain a deeper stack but the memory usage is by no means unbounded.
I don't know how you can classify changing GCC's internal structure as 'feature-creep'. LL grammars are usually considered easier to read/understand and despite what some wannabe-macho programmers may think, readability/clarity is good. It is also easier to write meaningful error messages because an LL parser kind of models the way we naturally think.
Now I'm not saying that LL parsers are better. The workings of LR grammars are extremely interesting (Knuth is a god). However, don't knock it for no reason at all (stick to 2.95? gimme a break). I'm sure the GCC guys know more than both of us about compiler design and have good reasons for their design decisions.
You don't need GCC to implement it, nor do you need to wait on C++0x. Every container declares appropriate nested typedefs. Using your example:
The "figure out a type for you" was done when some_map was declared.
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
You don't really want that kind of thing done in the parser, because your refactorer (or whatever) would then have to handle the possibility of incorrect code. The parser is handling syntax (mostly), remember; semantic correctness is checked later.
You want GCC to parse the code, check the code, and then do something other than generate assembly. To some extent that's being done already (there are command-line options to dump various representations of the source, e.g., -fdump-translation-unit).
Also, the back-end (code generation) is seperate from the front end (language handling), so if you were to implement a back-end whose "assembly language" output was actually, say, XML, then you would have a C-to-XML, C++-to-XML, Java-to-XML, FORTRAN-to-XML, ObjectiveC-to-XML, and whatever-else-I'm-missing-to-XML converter. Dunno why you'd want such a thing, but you could probably build some kind of program database out of it (which is what IDEs use to do things like function name completion when typing code).
All of which is independent of the front-end parser.
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
The version of GCC that ships with OS X has been heavily hacked on to make it work better for that operating system. One of the things Apple added was a simple implementation of PCH.
Other companies have done the same thing, many times. One of the customized versions of GCC that Cygnus did for a customer had a (simple) PCH in it, too.
The version being checked in to GCC is the result of all these different implementations coming together.
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
Index operations are several orders of magnitude faster than procedure calls.
Actually a table based solution like bison is slower than implementing the parser directly in code (like recursive descent).
But giving up on LALR parsing is not necessary. You can use recursive ascent. See this article that claims a speedup of 2.5 to 6.5 compared to table based LALR(1).