Re: c-exp.y

Re: c-exp.y

[Paul Hilfinger]

 > Basically, I want to revamp the way that GDB handles qualified names
 > in C++: these are names like C::x or C::D::y or whatever, where C
 > and/or D might be classes or namespaces.

A noble goal, but rather difficult, to say the least.

 > Unfortunately, some sort of distinction between types and
 > non-types seems to be hard-wired into the parser at a deep level: it
 > seems to be the parser's job to actually evaluate expressions
 > corresponding to types, whereas other expressions get evaluated by
 > somebody else.

Yes. This is a well-known issue with C++ parsing.  Consider

     (T) *x

We must know whether T is a type to know whether this is a cast.

Of course, the most infamous characteristic of C++ syntax is even
worse.  Even if you know that T is a type name, 

	T(x);

may be parsed either as a declaration of x or as an invocation of the
constructor for T on argument x (yielding a value of type T that is
voided).  The rule is that this is a declaration.  

 > Question 2: What should I do about it?

I hesitate to bring this up, but the newest versions of Bison support
GLR parsing, which can handle the infamous case.  In principle, one
could use GLR parsing to push off the distinction between types and
non-types to a later stage of the compiler, but this is probably not a
wise way to use it.  Still, I suspect that GLR parsing could clean up
at least some things in the C++ grammar.  Unfortunately, the feature
is new and experimental, and will need shaking down.  It is also not
in yacc or (at least for now) byacc, which may or may not be a problem.
On the other hand, I know for a fact that, starting next month, GLR's
contributer would be willing to work on getting the kinks out (;->).  

Paul Hilfinger

Re: c-exp.y

[David Carlton]

On Tue, 17 Dec 2002 13:43:22 -0800, Paul Hilfinger <hilfingr@CS.Berkeley.EDU> said:

>> Unfortunately, some sort of distinction between types and non-types
>> seems to be hard-wired into the parser at a deep level: it seems to
>> be the parser's job to actually evaluate expressions corresponding
>> to types, whereas other expressions get evaluated by somebody else.

> Yes. This is a well-known issue with C++ parsing.

I have heard that C++ parsing is a royal pain, but I'm not sure that's
the issue here: I suspect that GDB's problems are at a more basic
level.  I suspect that the division of labor between what the
parse_expression does and what eval_expression does is a bit funny,
and I'm pretty sure that the rule

  start   :     exp1
          |     type_exp
          ;

in the parser leads to some conceptual incoherence.  Basically, what
the parser is trying to parse isn't a C++ expression (which, as you
point out, is ridiculously difficult if you really want to do it
correctly) but is instead either an expression or a type, so that the
same parser can be used unmodified for either GDB's 'print' command or
its 'ptype' command.

I could be wrong, though.

David Carlton
carlton@math.stanford.edu

Re: c-exp.y

[Paul Hilfinger]

> I have heard that C++ parsing is a royal pain, but I'm not sure that's
> the issue here: I suspect that GDB's problems are at a more basic
> level.  I suspect that the division of labor between what the
> parse_expression does and what eval_expression does is a bit funny,
> and I'm pretty sure that the rule
> 
>   start   :     exp1
>           |     type_exp
>           ;
> 
> in the parser leads to some conceptual incoherence.  

It does, but it is not alone, which I guess was my point.  Look
further down in the grammar, and you find

    exp	:	'(' type ')' exp  %prec UNARY
			     ...
	    ;

    exp	:	'(' exp1 ')'
		{ }

which is essentially the same thing all over again.

The point is that there are instances in the C/C++ grammar that require
knowing whether a given identifier or qualified name is or is not a
type, which is why this sort of stuff tends to migrate into lexical
analysis.  

Paul Hilfinger

Re: c-exp.y

[David Carlton]

On Wed, 18 Dec 2002 19:36:22 -0800, Paul Hilfinger <hilfingr@CS.Berkeley.EDU> said:

>> I suspect that the division of labor between what the
>> parse_expression does and what eval_expression does is a bit funny,
>> and I'm pretty sure that the rule
>> 
>> start   :     exp1
>> |     type_exp
>> ;
>> 
>> in the parser leads to some conceptual incoherence.  

> It does, but it is not alone, which I guess was my point.  Look
> further down in the grammar, and you find

>     exp	:	'(' type ')' exp  %prec UNARY
> 			     ...
> 	    ;

>     exp	:	'(' exp1 ')'
> 		{ }

> which is essentially the same thing all over again.

Ah, gotcha.  Good point.  I'll have to think about what to do with
this, then.  It seems like the two obvious options would be either to
have the lexer handle all double-colons, or else to have the lexer
handle none of them but to add a rule in the grammer converting a
possibly qualified name to a type.

And the former option doesn't work because the lexer doesn't have
enough smarts to let GDB do something useful with expressions of the
form C::x where x is a non-type member of C.  And the latter option
probably won't work for the reasons you are bringing up.

Sigh.  Certainly the short-term "fix" of extending the current hack in
yylex is looking more and more necessary.

David Carlton
carlton@math.stanford.edu

c-exp.y

[David Carlton]

Is anybody out there an expert on c-exp.y?  I'm playing around with it
right now, I've run into a bit of a mess, and I could use some
hand-holding.  (It doesn't help that it's been almost a decade since I
last dealt with YACC.)

Basically, I want to revamp the way that GDB handles qualified names
in C++: these are names like C::x or C::D::y or whatever, where C
and/or D might be classes or namespaces.

Currently, if I understand it correctly (which may well not be the
case), that support is handled within c-exp.y in two different ways:

1) The #if 1 section of yylex handles the case of nested types.  So if
   the lexer runs into C::D, it checks to see if C::D looks like a
   nested type, and if so it swallows the entire string C::D.  (Its
   way of calculating the nested type in question isn't too great, but
   never mind that.)  Otherwise, it just swallows the string C, and
   the next call to yylex will swallow the :: (returning a COLONCOLON
   token).

2) The 'qualified_name' symbol handles the case C::x where C is a
   class and x is a (non-type) member of that class.

This division of responsibilities seems like a mess.  (And I'm leaving
out the case of ::x or ::C::x, which I still haven't tried to figure
out.)  Unfortunately, some sort of distinction between types and
non-types seems to be hard-wired into the parser at a deep level: it
seems to be the parser's job to actually evaluate expressions
corresponding to types, whereas other expressions get evaluated by
somebody else.


Question 1: Is what I say above correct?

Question 2: What should I do about it?


Working on the assumption that we need to distinguish between types
and non-types, I added a 'qualified_type' symbol to parallel
'qualified_name'.  This gave me one more shift/reduce conflict and 8
more reduce/reduce conflicts; I wasn't sure whether or not that was a
big deal (like I said, it's been a while since I last used YACC), so I
pressed on with it.  After running it on some test data, I found that
it worked in most situations, but it broke ptype on qualified types.
What I think is going on is that we have the rule

  start : exp1
        | type_exp
        ;

and, if you have a qualified expression, then there are two possible
paths in the grammar to reach 'start' (with the last step being either
via 'qualified_name' or 'qualified_type'); Bison chose the former,
which shuts off the possibility of qualified expressions ever being
interpreted as types.  (So, given C::D::x, C::D is a type via
qualified_type, but C::D::x is never a type.)  This presumably is
reflected in the extra conflicts that I got.


Question 3: Is what I've said since my last questions correct?

Question 4: Again, what should I do about it?


For now, it seems to me that probably c-exp.y has some conceptual
problems that are too big for me to deal with; so I'm leaning towards
going back to the original solution of shoving nested types back into
the lexer.  I still feel that's the wrong place for that, but I should
be able to get it to work.  And I'm still nervous about the initial
double-colon case: I suspect that the lexer can't handle that, unless
it handles all situations involving double-colons.

Sigh.

David Carlton
carlton@math.stanford.edu