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."
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.
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.)