Why pointer symbol and multiplication sign are same in C/C++?

Question

I am writing a limited C/C++ code parser. Now, multiplication and pointer signs give me really a tough time, as both are same. For example,

int main ()
{
  int foo(X * p); // forward declaration
  bar(x * y);  // function call
}

I need to apply special rules to sort out if * is indeed a pointer. In above code, I have to find out if foo() is a forward declaration and bar() is a function call. Real world code can be lot more complex. Had there been different symbol like @ for pointers, then it would have been straight forward.

The pointers were introduced in C, then why some different symbol was not chosen for the same ? Was keyboard so limited ?

[It will be an add-on if someone can throw light on how modern day parser deal with this ? Keep in mind that, in one scope X can be typename and another scope it can be a variable name, at the same time.]

Answer 1

Yes, the same symbols are being reused, because there were no UTF32 back there. So you have * as a pointer type, * as a dereference operator, * as a multiplication operator, and that's just in C. You also have a similar problem with "&" for example ("&" as address-off, "&" as bitwise-end and "&" as part of "&&" - logical and), and others.

The lexical parsers differentiate between them based on the context.

in your example, you have two different paths in your parser: one that starts with a type (a variable/forward declaration) and one that doesn't (function call). If there's an ambiguity - you get a compilation error.

If you're using a subset of C - you need to make sure you get the right subset of the grammar that handles this issue.

Answer 2

There are two rules in the C BNF that make writing a parser difficult:

if-statement: "if" expression statement |
              "if" expression statement "else" statement

leads to the dangling else problem, where

if a if b c else d

can be parsed as either of

(if-statement (a) (if-statement (b) (c) (d)))
(if-statement (a) (if-statement (b) (c)) (d))

The typical resolution for this conflict is to prefer shift over reduce, attaching the "else" branch to the inner if-statement.

The other, more difficult problem is

typedef-name: identifier

which makes the language context sensitive. This conflict is resolved by omitting the rule in the parser and creating a separate token for typedef-names; for this to work, the scanner must have a table of names that have been declared as typedef.

For C++, the rules are a lot more complex, and it is usually simpler to write an integrated scanner/parser that resolves all identifiers.

Answer 3

They're resolved by using symbol tables. This symbol table keeps track of the declarations you've seen to sort out whether or not you're calling a function that's already been declared. When the parser encounters an identifier, it makes a lookup to the symbol table to see what it is. You will find similar situations for type names- especially since C has multiple namespaces and you can start shadowing them. These rules are non-trivial.

typedef int MahInt;
MahInt * p; // declaration or multiplication?

It is not possible to parse C without symbol tables.

As for why it is that way, because keyboards at the time were very limited- for example digraphs and trigraphs, which produce symbols that were unusual at the time. For example, witness the "WTF" operator:

int x, y;
x ??!??! y;

which is really

x || y

Answer 4

The typedef was a relatively late addition to the C language.

In earlier versions of C, the grammar defined what is or is not a type name fairly straightforwardly. Many type names: int, char, double, etc. were (and still are) single keywords. Other type names included keywords or symbols: struct foo, char *, int[42]. A non-keyword identifier could never be a type name.

When the typedef construct was added to the existing language, it wasn't possible to change the grammar to be able to treat a non-keyword identifier as a type name without either creating ambiguities or breaking existing code. For example, in:

int foo() {
    x*y;
}

x*y could be either an expression statement that multiplies x by y and discards the result, or a declaration of y as a pointer to type x.

One way of looking at it is that a typedef creates a new keyword, one that exists only until the end of the scope in which it's defined. That means that the parser has to look at the symbol table to know how to interpret things (something that's not true for a lot of other languages; for example, in Pascal an identifier can be a type name, and this doesn't introduce an ambiguity).

For example:

int x, y;
int foo() {
     x * y; /* x isn't type name, so this is an expression statement */
     {
         typedef int x;
         x *y; /* Now x is a type name (effectively a keyword),
                  so this is a declaration */
     }
     x * y; /* The type name x is now out of scope,
               so it's an expression statement again */
}

(Treating typedef names as keywords is just one way to look at it; I don't mean to suggest that compilers actually do that internally.)

Answer 5

Consider using a GLR parsing, it allows you to postpone the choice between the ambiguous syntax interpretations till you've got type information. That is how parsers like Elsa work.

Another alternative is to collect and expand the types while parsing - e.g., it works well with an ad hoc recursive descent parsing implementation. This approach is used in both gcc and Clang.

There are more possibilities available: you can still use a high level generator producing a Packrat parser out of PEG specifications - this way you can stuff more side effect logic into a parsing without having to implement the whole thing manually, as with an ad hoc approach.