C++ Template implementation

[Bill Fahle]

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?
Is it just coerced by the parser into a typedefname when the
template_class_name is reduced, something like the lexer hack? If so,
what state does the parser enter at that point, and what happens to
the state stack? (This is different from the lexer hack because it is
a complete nonterminal tree being turned into a typedefname, not just
a token).

b) Why are expressions necessary to the template_arg? I've never seen
this in practice, and I'm not sure of the semantics. 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;

TIA.

--
Send compilers articles to comp...@iecc.com, meta-mail to
compiler...@iecc.com. Archives at http://www.iecc.com/compilers

[Jerry Leichter]

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

| 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];

intarray()
: 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

[John Williams]

Bill Fahle wrote in message <98-0...@comp.compilers>...

>template_class_name::= template_name "<" List(template_arg) ">".
>
>template_arg::= expression | type_name.
>

>b) Why are expressions necessary to the template_arg? I've never seen

>this in practice, and I'm not sure of the semantics. 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;

An expression argument can be any compile-time constant. The problem with
ambiguity is solved by adding parentheses:

SpecificList<Specific *, (a>b) > m_specificList;

A case where you might see this in practice would be a fixed-size template
data structure:

template<class T, int M, int N>
class Matrix { private: T data[M*N]; ... };

Matrix<int, 3, 2> x; // x is a 3x2 matrix of integers

This is just the tip of the iceberg, though. To see some uses of templates
that will make your head spin, look at Blitz++:

http://seurat.uwaterloo.ca/blitz/

jw