Re: C++ Template implementation

Jerry Leichter <>
27 Apr 1998 23:30:33 -0400

          From comp.compilers

Related articles
C++ Template implementation (Bill Fahle) (1998-04-21)
Re: C++ Template implementation (Jerry Leichter) (1998-04-27)
Re: C++ Template implementation (John Williams) (1998-04-27)
| List of all articles for this month |

From: Jerry Leichter <>
Newsgroups: comp.compilers
Date: 27 Apr 1998 23:30:33 -0400
Organization: System Management ARTS
References: 98-04-086
Keywords: C++

| I have a working C parser that I am currently turning into a C++
| parser. I use the Roskind grammar for C, and have an old Roskind C++
| grammar that doesn't include templates or namespaces. What I'm
| wondering is how to implement templates in the grammar without causing
| too many conflicts. Something I've seen in several C++ grammars is
| the following:
| template_class_name::= template_name "<" List(template_arg) ">".
| template_arg::= expression | type_name.
| What I'm wondering is
| a) Why is template_class_name never used anywhere else in the grammar?

You'd have to ask the author of the grammar. C++ has a grammar that
walks the edge of parseability, and written grammars for it don't
convey good information, even to human beings, in the edge cases.
(Many grammars, BTW, follow the convention that there's a *real*
syntactic non-terminal called "name", and a bunch of ancilliary
pseudo-non- terminals with names like "typedef_name". The grammar
can't distinguish all the "foo_names" from each other - they're all
just plain "name"'s; but humans may be able to get something useful
out of the extended name. This could be the case here: It could be
that "template_class_name" is really just another production for a

| b) Why are expressions necessary to the template_arg? I've never seen
| this in practice, and I'm not sure of the semantics.

A template parameter can be either a type, or a (constant) integer
value. The classic use of this is something like the following:

template <int n>
class intarray
{ int len;
int val[n];

: len(n);

Add an appropriate definition for operator[] and you have an array
that "knows its own size". If you wanted, you could have more than
one parameter, and have upper and lower bounds. Since each instances
of an intarray is statically bound to a particular value of 'len',
inlining and constant elimination could, in theory, make uses of
intarray safe (i.e., array bounds would be checked) without
significant overhead. (In practice ... inlining has become C++'s
answer to every question about "efficiency". We accept compilation
costs - including real compiler run-times, on high-end machines - that
a few years ago lead us to laugh at functional programming as neat,
but way too expensive to ever be practical.)

| These seem to
| cause a lot of the conflicts I experience, because of the >
| ambiguity. A general expression would indeed be ambiguous:
| SpecificList<Specific *, a>b > m_specificList;

You betcha'. The re-use of '<>' for template parameters was one of the
stupider bits of syntactic design in C++. The way the grammar is
defined, the *first* possible '>' closes the template parameter list.
So your example would be parsed "incorrectly". You have to use
parentheses to hide the ">" hidden in the expression. (Note, BTW, that
at the *lexical* level, we always take the *longest* string of
characters that can form a token - so 'List<Array<x>>' won't work, since
the trailing '>>' is taken as a single token; you have to write
'List<Array<x> >'. On the other hand, at the *syntactic* level, we
always take the *shortest* string that can be reduced - so you have to
use parentheses in the above example. Consistency? Nah....)

-- Jerry

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.