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.
Because that sort of thing can get screwed up easily and cause all sorts of problems. I'm thinking of how Borland's precompiled headers sometimes goofed up, or my horrible experiences with Sun's cached templates on their C++ compiler. I'd rather explicitly tell the compiler exactly what I want done in terms of precompilation than to let it guess and screw up on its own.
If tits were wings it'd be flying around.
Microsoft Visual C++ had precompiled headers at least ten years ago. Y'know... when DOS was all the rage. :)
Is this simply something that nobody cared about and finally got around to doing it - or was it a tricky feature to implement given that GCC already worked quite well enough without it?
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.
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.)
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 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)
You can resolve the ambiguity using the same rules that decide which version you'll be calling (which you have to work out anyway, of course) and take the return type of that version. As long as you've got context -- which you have in the example case -- it's not a problem. In general, you'd need to specify which overload you wanted. It's kind of like explicit template instantiation (and equally horrible if you have to do it).
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
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).