Search code examples
language-agnosticprogramming-languageslogicgrammarproof

Proving syntactic ambiguity of type declaration grammar


Given a grammar to achieve C-style type declarations:

Declaration ::= Type Declarator ;

       Type ::= int | char

 Declarator ::= * Declarator

              | Declarator [ num ]

              | Declarator ( Type )

              | ( Declarator )

              | name

I must prove syntactic ambiguity. I am having difficulty identifying cases it which it is ambiguous. Here are all of the following cases I have come up with that satisfy the grammar:

  • int * Declarator;
  • char * Declarator;
  • int Declarator[num];
  • char Declarator[num];
  • int Declarator(type);
  • char Declarator(type);
  • int Declarator;
  • char Declarator;
  • int name;
  • char name;

What am I not seeing here?


Solution

  • Is int *something[3] an array of three pointers or a pointer to an array of three ints? How about int **something[3]?

    A simplified C grammar from the C standard's Appendix A includes:

    (Many productions omitted)
    declarator: pointeropt direct-declarator
    pointer: '*'
           | '*' pointer
    direct-declarator: identifier
                       '(' declarator ')'
                       direct-declarator '[' assignment-expressionopt ']'
    

    How does that resolve the above ambiguity?

    Also, consider the expression *a[3] and the declaration int *a[3]. In the expression, the postfix qualifier [3] takes precedence over the prefix qualifier *, which is the normal pattern for expressions. How does that compare with the syntax of the declaration? Why was that decision taken?