source: translator/Parser.old/cfa.y@ c8ffe20b

/*                               -*- Mode: C -*-
 *
 * CForall Grammar Version 1.0, Copyright (C) Peter A. Buhr 2001 -- Permission is granted to copy this
 *      grammar and to use it within software systems.  THIS GRAMMAR IS PROVIDED "AS IS" AND WITHOUT
 *      ANY EXPRESS OR IMPLIED WARRANTIES.
 *
 * cfa.y --
 *
 * Author           : Peter A. Buhr
 * Created On       : Sat Sep  1 20:22:55 2001
 * Last Modified By : Peter A. Buhr
 * Last Modified On : Tue Dec 17 08:47:30 2002
 * Update Count     : 795
 */

/* This grammar is based on the ANSI99 C grammar, specifically parts of EXPRESSION and STATEMENTS, and on the
   C grammar by James A. Roskind, specifically parts of DECLARATIONS and EXTERNAL DEFINITIONS.  While parts
   have been copied, important changes have been made in all sections; these changes are sufficient to
   constitute a new grammar.  In particular, this grammar attempts to be more syntactically precise, i.e., it
   parses less incorrect language syntax that must be subsequently rejected by semantic checks.  Nevertheless,
   there are still several semantic checks required and many are noted in the grammar. Finally, the grammar
   is extended with GCC and CFA language extensions. */

/* Acknowledgments to Richard Bilson, Glen Ditchfield, and Rodolfo Gabriel Esteves who all helped when I got
   stuck with the grammar. */

/* The root language for this grammar is ANSI99 C. All of ANSI99 is parsed, except for:

   1. designation with '=' (use ':' instead)

   Most of the syntactic extensions from ANSI90 to ANSI99 C are marked with the comment "ANSI99". This grammar
   also has two levels of extensions. The first extensions cover most of the GCC C extensions, except for:

   1. nested functions
   2. generalized lvalues
   3. designation with and without '=' (use ':' instead)
   4. attributes not allowed in parenthesis of declarator

   All of the syntactic extensions for GCC C are marked with the comment "GCC". The second extensions are for
   Cforall (CFA), which fixes several of C's outstanding problems and extends C with many modern language
   concepts. All of the syntactic extensions for CFA C are marked with the comment "CFA". As noted above,
   there is one unreconcileable parsing problem between ANSI99 and CFA with respect to designators; this is
   discussed in detail before the "designation" grammar rule. */

%{
#define YYDEBUG_LEXER_TEXT (yylval)                     /* lexer loads this up each time */
#define YYDEBUG 1                                       /* get the pretty debugging code to compile*/


#include <cstdio>
#include <stack>
#include "TypedefTable.h"
#include "lex.h"
#include "ParseNode.h"
#include "LinkageSpec.h"

DeclarationNode *theTree = 0;                           /* the resulting parse tree */
LinkageSpec::Type linkage = LinkageSpec::Cforall;
std::stack< LinkageSpec::Type > linkageStack;
TypedefTable typedefTable;
%}

/************************* TERMINAL TOKENS ********************************/

/* keywords */
%token TYPEDEF
%token AUTO EXTERN REGISTER STATIC
%token INLINE                                           /* ANSI99 */
%token FORTRAN                                          /* ANSI99, extension ISO/IEC 9899:1999 Section J.5.9(1) */
%token CONST VOLATILE
%token RESTRICT                                         /* ANSI99 */
%token FORALL LVALUE                                    /* CFA */
%token VOID CHAR SHORT INT LONG FLOAT DOUBLE SIGNED UNSIGNED
%token BOOL COMPLEX IMAGINARY                           /* ANSI99 */
%token TYPEOF LABEL                                     /* GCC */
%token ENUM STRUCT UNION
%token TYPE FTYPE DTYPE CONTEXT                         /* CFA */
%token SIZEOF
%token ALIGNOF ATTRIBUTE EXTENSION                      /* GCC */
%token IF ELSE SWITCH CASE DEFAULT DO WHILE FOR BREAK CONTINUE GOTO RETURN
%token CHOOSE FALLTHRU TRY CATCH THROW                  /* CFA */
%token ASM                                              /* ANSI99, extension ISO/IEC 9899:1999 Section J.5.10(1) */

/* names and constants: lexer differentiates between identifier and typedef names */
%token<tok> IDENTIFIER          TYPEDEFname             TYPEGENname
%token<tok> INTEGERconstant     FLOATINGconstant        CHARACTERconstant       STRINGliteral
%token<tok> ZERO                ONE                     /* CFA */

/* multi-character operators */
%token ARROW                    /* ->                           */
%token ICR DECR                 /* ++   --                      */
%token LS RS                    /* <<   >>                      */
%token LE GE EQ NE              /* <=   >=      ==      !=      */
%token ANDAND OROR              /* &&   ||                      */
%token ELLIPSIS                 /* ...                          */

%token MULTassign       DIVassign       MODassign       /* *=   /=      %=      */
%token PLUSassign       MINUSassign                     /* +=   -=              */
%token LSassign         RSassign                        /* <<=  >>=             */
%token ANDassign        ERassign        ORassign        /* &=   ^=      |=      */

/* Types declaration */
%union
{
  struct token tok;
  ParseNode *pn;
  ExpressionNode *en;
  DeclarationNode *decl;
  DeclarationNode::TyCon aggKey;
  DeclarationNode::TypeClass tclass;
  StatementNode *sn;
  ConstantNode *constant;
  InitializerNode *in;
}

%type<tok> zero_one  identifier  identifier_or_typedef_name
%type<constant> string_literal_list

/* expressions */
%type<constant> constant
%type<en> tuple                 tuple_expression_list
%type<en> unary_operator                assignment_operator
%type<en> primary_expression            attribute_expression            postfix_expression      unary_expression
%type<en> cast_expression               multiplicative_expression       additive_expression     shift_expression
%type<en> relational_expression         equality_expression             AND_expression          exclusive_OR_expression
%type<en> inclusive_OR_expression       logical_AND_expression          logical_OR_expression   conditional_expression
%type<en> constant_expression           assignment_expression           assignment_expression_opt
%type<en> comma_expression      comma_expression_opt
%type<en> argument_expression_list      argument_expression             for_control_expression  assignment_opt
%type<en> subrange

/* statements */
%type<sn> labeled_statement     compound_statement      expression_statement    selection_statement
%type<sn> iteration_statement   jump_statement          exception_statement     asm_statement
%type<sn> fall_through_opt fall_through
%type<sn> statement             statement_list
%type<sn> block_item_list       block_item
%type<sn> case_clause
%type<en> case_value    case_value_list
%type<sn> case_label    case_label_list
%type<sn> switch_clause_list_opt switch_clause_list choose_clause_list_opt choose_clause_list
%type<pn> handler_list  handlers

/* declarations */
%type<decl> abstract_array abstract_declarator abstract_function abstract_parameter_array
%type<decl> abstract_parameter_declaration abstract_parameter_declarator abstract_parameter_function
%type<decl> abstract_parameter_ptr abstract_ptr

%type<aggKey> aggregate_key
%type<decl>  aggregate_name

%type<decl> array_dimension array_parameter_1st_dimension array_parameter_dimension multi_array_dimension

%type<decl> assertion assertion_list_opt

%type<en>   bit_subrange_size_opt bit_subrange_size

%type<decl> basic_declaration_specifier basic_type_name basic_type_specifier

%type<decl> context_declaration context_declaration_list context_declaring_list context_specifier

%type<decl> declaration declaration_list declaration_list_opt declaration_qualifier_list
%type<decl> declaration_specifier declarator declaring_list

%type<decl> elaborated_type_name

%type<decl> enumerator_list enum_name
%type<en> enumerator_value_opt

%type<decl> exception_declaration external_definition external_definition_list external_definition_list_opt

%type<decl> field_declaration field_declaration_list field_declarator field_declaring_list
%type<en> field field_list

%type<decl> function_array function_declarator function_definition function_no_ptr function_ptr

%type<decl> identifier_parameter_array identifier_parameter_declarator identifier_parameter_function
%type<decl> identifier_parameter_ptr identifier_list

%type<decl> new_abstract_array new_abstract_declarator_no_tuple new_abstract_declarator_tuple
%type<decl> new_abstract_function new_abstract_parameter_declaration new_abstract_parameter_list
%type<decl> new_abstract_ptr new_abstract_tuple

%type<decl> new_array_parameter_1st_dimension

%type<decl> new_context_declaring_list new_declaration new_field_declaring_list
%type<decl> new_function_declaration new_function_return new_function_specifier

%type<decl> new_identifier_parameter_array new_identifier_parameter_declarator_no_tuple
%type<decl> new_identifier_parameter_declarator_tuple new_identifier_parameter_ptr

%type<decl> new_parameter_declaration new_parameter_list new_parameter_type_list new_parameter_type_list_opt

%type<decl> new_typedef_declaration new_variable_declaration new_variable_specifier

%type<decl> old_declaration old_declaration_list old_declaration_list_opt old_function_array
%type<decl> old_function_declarator old_function_no_ptr old_function_ptr

%type<decl> parameter_declaration parameter_list parameter_type_list
%type<decl> parameter_type_list_opt

%type<decl> paren_identifier paren_typedef

%type<decl> storage_class storage_class_name storage_class_list

%type<decl> sue_declaration_specifier sue_type_specifier

%type<tclass> type_class
%type<decl> type_declarator type_declarator_name type_declaring_list

%type<decl> typedef typedef_array typedef_declaration typedef_declaration_specifier typedef_expression
%type<decl> typedef_function typedef_parameter_array typedef_parameter_function typedef_parameter_ptr
%type<decl> typedef_parameter_redeclarator typedef_ptr typedef_redeclarator typedef_type_specifier
%type<decl> typegen_declaration_specifier typegen_type_specifier

%type<decl> type_name type_name_no_function
%type<decl> type_parameter type_parameter_list

%type<en> type_name_list

%type<decl> type_qualifier type_qualifier_name type_qualifier_list type_qualifier_list_opt type_specifier

%type<decl> variable_abstract_array variable_abstract_declarator variable_abstract_function
%type<decl> variable_abstract_ptr variable_array variable_declarator variable_function variable_ptr

/* initializers */
%type<in>  initializer initializer_list initializer_opt

/* designators */
%type<en>  designator designator_list designation


/* Handle single shift/reduce conflict for dangling else by shifting the ELSE token. For example, this string
   is ambiguous:
   .---------.                  matches IF '(' comma_expression ')' statement
   if ( C ) S1 else S2
   `-----------------'  matches IF '(' comma_expression ')' statement ELSE statement */

%nonassoc THEN  /* rule precedence for IF '(' comma_expression ')' statement */
%nonassoc ELSE  /* token precedence for start of else clause in IF statement */

%start translation_unit                                 /* parse-tree root */

%%
/************************* Namespace Management ********************************/

/* The grammar in the ANSI C standard is not strictly context-free, since it relies upon the distinct terminal
   symbols "identifier" and "TYPEDEFname" that are lexically identical.  While it is possible to write a
   purely context-free grammar, such a grammar would obscure the relationship between syntactic and semantic
   constructs.  Hence, this grammar uses the ANSI style.

   Cforall compounds this problem by introducing type names local to the scope of a declaration (for instance,
   those introduced through "forall" qualifiers), and by introducing "type generators" -- parametrized types.
   This latter type name creates a third class of identifiers that must be distinguished by the scanner.

   Since the scanner cannot distinguish among the different classes of identifiers without some context
   information, it accesses a data structure (the TypedefTable) to allow classification of an identifier that
   it has just read.  Semantic actions during the parser update this data structure when the class of
   identifiers change.

   Because the Cforall language is block-scoped, there is the possibility that an identifier can change its
   class in a local scope; it must revert to its original class at the end of the block.  Since type names can
   be local to a particular declaration, each declaration is itself a scope.  This requires distinguishing
   between type names that are local to the current declaration scope and those that persist past the end of
   the declaration (i.e., names defined in "typedef" or "type" declarations).

   The non-terminals "push" and "pop" derive the empty string; their only use is to denote the opening and
   closing of scopes.  Every push must have a matching pop, although it is regrettable the matching pairs do
   not always occur within the same rule.  These non-terminals may appear in more contexts than strictly
   necessary from a semantic point of view.  Unfortunately, these extra rules are necessary to prevent parsing
   conflicts -- the parser may not have enough context and look-ahead information to decide whether a new
   scope is necessary, so the effect of these extra rules is to open a new scope unconditionally.  As the
   grammar evolves, it may be neccesary to add or move around "push" and "pop" nonterminals to resolve
   conflicts of this sort.  */

push:
                {
                    typedefTable.enterScope();
                }
        ;

pop:
                {
                    typedefTable.leaveScope();
                }
        ;

/************************* CONSTANTS ********************************/

constant:
                /* ENUMERATIONconstant is not included here; it is treated as a variable with type
                   "enumeration constant". */
        INTEGERconstant         { $$ = new ConstantNode(ConstantNode::Integer,   $1); }
        | FLOATINGconstant      { $$ = new ConstantNode(ConstantNode::Float,     $1); }
        | CHARACTERconstant     { $$ = new ConstantNode(ConstantNode::Character, $1); }
        ;

identifier:
        IDENTIFIER
        | zero_one                                      /* CFA */
        ;

zero_one:                                               /* CFA */
        ZERO
        | ONE
        ;

string_literal_list:                                    /* juxtaposed strings are concatenated */
        STRINGliteral                           { $$ = new ConstantNode(ConstantNode::String, $1); }
        | string_literal_list STRINGliteral     { $$ = $1->append( $2.str ); }
        ;

/************************* EXPRESSIONS ********************************/

primary_expression:
        identifier                                      /* typedef name cannot be used as a variable name */
                { $$ = new VarRefNode($1); }
        | constant
                { $$ = $1; }
        | string_literal_list
                { $$ = $1; }
        | '(' comma_expression ')'
                { $$ = $2; }
        | '(' compound_statement ')'                    /* GCC, lambda expression */
                { $$ = new ValofExprNode($2); }
        ;

attribute_expression:                                   /* CFA, attribute */
        primary_expression
        | attribute_expression '!' identifier_or_typedef_name
        | attribute_expression '!' type_qualifier
        | attribute_expression '!' storage_class
        | '<' type_name_no_function '>' '!' identifier_or_typedef_name  { $$ = 0; }
        | '<' type_name_no_function '>' '!' type_qualifier              { $$ = 0; }
        | '<' type_name_no_function '>' '!' storage_class               { $$ = 0; }
        ;

postfix_expression:
        attribute_expression
        | postfix_expression '[' push assignment_expression pop ']'
                 /* CFA, comma_expression disallowed in the context because it results in a commom user error:
                    subscripting a matrix with x[i,j] instead of x[i][j]. While this change is not backwards
                    compatible, there seems to be little advantage to this feature and many disadvantages. It
                    is possible to write x[(i,j)] in CFA, which is equivalent to the old x[i,j]. */
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Index, $2.filename, $2.lineno), $1, $4); }
        | postfix_expression '(' argument_expression_list ')'
                { $$ = new CompositeExprNode($1, $3); }
        | postfix_expression '.' identifier_or_typedef_name
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::FieldSel, $2.filename, $2.lineno), $1,
                                             new VarRefNode($3)); }
        | postfix_expression '.' '[' push field_list pop ']' /* CFA, tuple field selector */
        | postfix_expression ARROW identifier_or_typedef_name
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::PFieldSel, $2.filename, $2.lineno), $1,
                                             new VarRefNode($3)); }
        | postfix_expression ARROW '[' push field_list pop ']' /* CFA, tuple field selector */
        | postfix_expression ICR
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::IncrPost, $2.filename, $2.lineno), $1); }
        | postfix_expression DECR
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::DecrPost, $2.filename, $2.lineno), $1); }
                /* GCC has priority: cast_expression */
        | '(' type_name_no_function ')' '{' initializer_list comma_opt '}' /* ANSI99 */
                { $$ = 0; }
        ;

argument_expression_list:
        argument_expression
        | argument_expression_list ',' argument_expression
                                                { $$ = (ExpressionNode *)($1->set_link($3)); }
        ;

argument_expression:
        /* empty */                                     /* use default argument */
                { $$ = 0; }
        | assignment_expression
        | identifier_or_typedef_name ':' assignment_expression
                                                { $$ = $3->set_asArgName($1.str); }
                /* Only a list of identifier_or_typedef_names is allowed in this context. However, there is
                   insufficient look ahead to distinguish between this list of parameter names and a tuple, so
                   the tuple form must be used with an appropriate semantic check. */
        | '[' push assignment_expression pop ']' ':' assignment_expression
                                                { $$ = $7->set_asArgName($3.str); }
        | '[' push assignment_expression ',' tuple_expression_list pop ']' ':' assignment_expression
                                                { $$ = $9->set_asArgName(new CompositeExprNode( new OperatorNode( OperatorNode::TupleC, $1.filename, $1.lineno ), (ExpressionNode *)$3->set_link( flattenCommas( $5 )))); }
        ;

field_list:                                             /* CFA, tuple field selector */
        field
        | field_list ',' field                  { $$ = (ExpressionNode *)$1->set_link( $3 ); }
        ;

field:                                                  /* CFA, tuple field selector */
        identifier_or_typedef_name
                                                { $$ = new VarRefNode( $1 ); }
        | identifier_or_typedef_name '.' field
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::FieldSel, $2.filename, $2.lineno), new VarRefNode( $1 ), $3); }
        | identifier_or_typedef_name '.' '[' push field_list pop ']'
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::FieldSel, $2.filename, $2.lineno), new VarRefNode( $1 ), $5); }
        | identifier_or_typedef_name ARROW field
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::PFieldSel, $2.filename, $2.lineno), new VarRefNode( $1 ), $3); }
        | identifier_or_typedef_name ARROW '[' push field_list pop ']'
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::PFieldSel, $2.filename, $2.lineno), new VarRefNode( $1 ), $5); }
        ;

unary_expression:
        postfix_expression
        | ICR unary_expression
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Incr, $1.filename, $1.lineno), $2); }
        | DECR unary_expression
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Decr, $1.filename, $1.lineno), $2); }
        | EXTENSION cast_expression                     /* GCC */
                { $$ = $2; }
        | unary_operator cast_expression
                { $$ = new CompositeExprNode($1, $2); }
        | '!' cast_expression
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Neg, $1.filename, $1.lineno), $2); }
        | '*' cast_expression                           /* CFA */
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::PointTo, $1.filename, $1.lineno), $2); }
                /* '*' is is separated from unary_operator because of shift/reduce conflict in:
                        { * X; } // dereference X
                        { * int X; } // CFA declaration of pointer to int
                   '&' must be moved here if C++ reference variables are supported. */
        | SIZEOF unary_expression
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::SizeOf, $1.filename, $1.lineno), $2); }
        | SIZEOF '(' type_name_no_function ')'
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::SizeOf, $1.filename, $1.lineno), new TypeValueNode($3)); }
        | ALIGNOF unary_expression                      /* GCC, variable alignment */
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::AlignOf, $1.filename, $1.lineno), $2); }
        | ALIGNOF '(' type_name_no_function ')'         /* GCC, type alignment */
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::AlignOf, $1.filename, $1.lineno), new TypeValueNode($3)); }
        | ANDAND identifier_or_typedef_name             /* GCC, address of label */
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::LabelAddress, $1.filename, $1.lineno),
                                             new VarRefNode($2, true)); }
        ;

unary_operator:
        '&'                               { $$ = new OperatorNode(OperatorNode::AddressOf, $1.filename, $1.lineno); }
        | '+'                             { $$ = new OperatorNode(OperatorNode::UnPlus, $1.filename, $1.lineno); }
        | '-'                             { $$ = new OperatorNode(OperatorNode::UnMinus, $1.filename, $1.lineno); }
        | '~'                             { $$ = new OperatorNode(OperatorNode::BitNeg, $1.filename, $1.lineno); }
        ;

cast_expression:
        unary_expression
        | '(' type_name_no_function ')' cast_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Cast, $1.filename, $1.lineno),
                                                                       new TypeValueNode($2), $4); }
        | '(' type_name_no_function ')' tuple
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Cast, $1.filename, $1.lineno),
                                                                       new TypeValueNode($2), $4); }
        ;

multiplicative_expression:
        cast_expression
        | multiplicative_expression '*' cast_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Mul, $2.filename, $2.lineno),$1,$3); }
        | multiplicative_expression '/' cast_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Div, $2.filename, $2.lineno),$1,$3); }
        | multiplicative_expression '%' cast_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Mod, $2.filename, $2.lineno),$1,$3); }
        ;

additive_expression:
        multiplicative_expression
        | additive_expression '+' multiplicative_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Plus, $2.filename, $2.lineno),$1,$3); }
        | additive_expression '-' multiplicative_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Minus, $2.filename, $2.lineno),$1,$3); }
        ;

shift_expression:
        additive_expression
        | shift_expression LS additive_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::LShift, $2.filename, $2.lineno),$1,$3); }
        | shift_expression RS additive_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::RShift, $2.filename, $2.lineno),$1,$3); }
        ;

relational_expression:
        shift_expression
        | relational_expression '<' shift_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::LThan, $2.filename, $2.lineno),$1,$3); }
        | relational_expression '>' shift_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::GThan, $2.filename, $2.lineno),$1,$3); }
        | relational_expression LE shift_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::LEThan, $2.filename, $2.lineno),$1,$3); }
        | relational_expression GE shift_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::GEThan, $2.filename, $2.lineno),$1,$3); }
        ;

equality_expression:
        relational_expression
        | equality_expression EQ relational_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Eq, $2.filename, $2.lineno), $1, $3); }
        | equality_expression NE relational_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Neq, $2.filename, $2.lineno), $1, $3); }
        ;

AND_expression:
        equality_expression
        | AND_expression '&' equality_expression
                                                { $$ =new CompositeExprNode(new OperatorNode(OperatorNode::BitAnd, $2.filename, $2.lineno), $1, $3); }
        ;

exclusive_OR_expression:
        AND_expression
        | exclusive_OR_expression '^' AND_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Xor, $2.filename, $2.lineno), $1, $3); }
        ;

inclusive_OR_expression:
        exclusive_OR_expression
        | inclusive_OR_expression '|' exclusive_OR_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::BitOr, $2.filename, $2.lineno), $1, $3); }
        ;

logical_AND_expression:
        inclusive_OR_expression
        | logical_AND_expression ANDAND inclusive_OR_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::And, $2.filename, $2.lineno), $1, $3); }
        ;

logical_OR_expression:
        logical_AND_expression
        | logical_OR_expression OROR logical_AND_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Or, $2.filename, $2.lineno), $1, $3); }
        ;

conditional_expression:
        logical_OR_expression
        | logical_OR_expression '?' comma_expression ':' conditional_expression
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Cond, $2.filename, $2.lineno),
                                                                       (ExpressionNode *)mkList((*$1,*$3,*$5))); }
        | logical_OR_expression '?' /* empty */ ':' conditional_expression /* GCC, omitted first operand */
                                                { $$=new CompositeExprNode(new OperatorNode(OperatorNode::NCond, $2.filename, $2.lineno),$1,$4); }
        | logical_OR_expression '?' comma_expression ':' tuple /* CFA, tuple expression */
                                                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Cond, $2.filename, $2.lineno),
                                                                       (ExpressionNode *)mkList(( *$1, *$3, *$5 ))); }
        ;

constant_expression:
        conditional_expression
        ;

assignment_expression:
                /* CFA, assignment is separated from assignment_operator to ensure no assignment operations
                   for tuples */
        conditional_expression
        | unary_expression '=' assignment_expression
                                                { $$ =new CompositeExprNode(new OperatorNode(OperatorNode::Assign, $2.filename, $2.lineno), $1, $3); }
        | unary_expression assignment_operator assignment_expression
                                                { $$ =new CompositeExprNode($2, $1, $3); }
        | tuple assignment_opt                          /* CFA, tuple expression */
                {
                  if( $2 == 0 ) {
                    $$ = $1;
                  } else {
                    $$ = new CompositeExprNode( new OperatorNode( OperatorNode::Assign, $2.filename, $2.lineno ), $1, $2 );
                  }
                }
        ;

assignment_expression_opt:
        /* empty */
                { $$ = new NullExprNode; }
        | assignment_expression
        ;

tuple:                                                  /* CFA, tuple */
                /* CFA, one assignment_expression is factored out of comma_expression to eliminate a
                   shift/reduce conflict with comma_expression in new_identifier_parameter_array and
                   new_abstract_array */
        '[' push pop ']'
                { $$ = new CompositeExprNode( new OperatorNode( OperatorNode::TupleC, $1.filename, $1.lineno ) ); }
        | '[' push assignment_expression pop ']'
                { $$ = new CompositeExprNode( new OperatorNode( OperatorNode::TupleC, $1.filename, $1.lineno ), $3 ); }
        | '[' push ',' tuple_expression_list pop ']'
                { $$ = new CompositeExprNode( new OperatorNode( OperatorNode::TupleC, $1.filename, $1.lineno ), (ExpressionNode *)(new NullExprNode)->set_link( $4 ) ); }
        | '[' push assignment_expression ',' tuple_expression_list pop ']'
                { $$ = new CompositeExprNode( new OperatorNode( OperatorNode::TupleC, $1.filename, $1.lineno ), (ExpressionNode *)$3->set_link( flattenCommas( $5 ) ) ); }
        ;

tuple_expression_list:
        assignment_expression_opt
        | tuple_expression_list ',' assignment_expression_opt
                { $$ = (ExpressionNode *)$1->set_link( $3 ); }
        ;

assignment_operator:
        MULTassign                                      { $$ = new OperatorNode(OperatorNode::MulAssn, $1.filename, $1.lineno);   }
        | DIVassign                                     { $$ = new OperatorNode(OperatorNode::DivAssn, $1.filename, $1.lineno);   }
        | MODassign                                     { $$ = new OperatorNode(OperatorNode::ModAssn, $1.filename, $1.lineno);   }
        | PLUSassign                                    { $$ = new OperatorNode(OperatorNode::PlusAssn, $1.filename, $1.lineno);  }
        | MINUSassign                                   { $$ = new OperatorNode(OperatorNode::MinusAssn, $1.filename, $1.lineno); }
        | LSassign                                      { $$ = new OperatorNode(OperatorNode::LSAssn, $1.filename, $1.lineno);    }
        | RSassign                                      { $$ = new OperatorNode(OperatorNode::RSAssn, $1.filename, $1.lineno);    }
        | ANDassign                                     { $$ = new OperatorNode(OperatorNode::AndAssn, $1.filename, $1.lineno);   }
        | ERassign                                      { $$ = new OperatorNode(OperatorNode::ERAssn, $1.filename, $1.lineno);    }
        | ORassign                                      { $$ = new OperatorNode(OperatorNode::OrAssn, $1.filename, $1.lineno);    }
        ;

comma_expression:
        assignment_expression
        | comma_expression ',' assignment_expression    /* { $$ = (ExpressionNode *)$1->add_to_list($3); } */
                               { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Comma, $2.filename, $2.lineno),$1,$3); }
        ;

comma_expression_opt:
        /* empty */                                     { $$ = 0; }
        | comma_expression
        ;

/*************************** STATEMENTS *******************************/

statement:
        labeled_statement
        | compound_statement
        | expression_statement                          { $$ = $1; }
        | selection_statement
        | iteration_statement
        | jump_statement
        | exception_statement
        | asm_statement
        ;

labeled_statement:
        identifier_or_typedef_name ':' attribute_list_opt statement
                { $$ = $4->add_label($1);}
        ;

compound_statement:
        '{' '}'
                { $$ = new CompoundStmtNode( (StatementNode *)0 ) }
        | '{'
                /* Two scopes are necessary because the block itself has a scope, but every declaration within
                   the block also requires its own scope */
          push push
          label_declaration_opt                         /* GCC, local labels */
          block_item_list pop '}'                       /* ANSI99, intermix declarations and statements */
                { $$ = new CompoundStmtNode( $5 ); }
        ;

block_item_list:                                        /* ANSI99 */
        block_item
        | block_item_list push block_item
                { if($1 != 0) { $1->set_link($3); $$ = $1; } }
        ;

block_item:
        declaration                                     /* CFA, new & old style declarations */
                { $$ = new StatementNode( $1 ); }
        | EXTENSION declaration                         /* GCC */
                { $$ = new StatementNode( $2 ); }
        | statement pop
        ;

statement_list:
        statement
        | statement_list statement
                { if($1 != 0) { $1->set_link($2); $$ = $1; } }
        ;

expression_statement:
        comma_expression_opt ';'
                { $$ = new StatementNode(StatementNode::Exp, $1, 0); }
        ;

selection_statement:
        IF '(' comma_expression ')' statement           %prec THEN
                /* explicitly deal with the shift/reduce conflict on if/else */
                { $$ = new StatementNode(StatementNode::If, $1.filename, $1.lineno, $3, $5); }
        | IF '(' comma_expression ')' statement ELSE statement
                { $$ = new StatementNode(StatementNode::If, $1.filename, $1.lineno, $3, (StatementNode *)mkList((*$5, *$7)) ); }
        | SWITCH '(' comma_expression ')' case_clause   /* CFA */
                { $$ = new StatementNode(StatementNode::Switch, $1.filename, $1.lineno, $3, $5); }
        | SWITCH '(' comma_expression ')' '{' push declaration_list_opt switch_clause_list_opt '}' /* CFA */
                { $$ = new StatementNode(StatementNode::Switch, $1.filename, $1.lineno, $3, $8); /* xxx */ }
                /* The semantics of the declaration list is changed to include any associated initialization,
                   which is performed *before* the transfer to the appropriate case clause.  Statements after
                   the initial declaration list can never be executed, and therefore, are removed from the
                   grammar even though C allows it. */
        | CHOOSE '(' comma_expression ')' case_clause   /* CFA */
                { $$ = new StatementNode(StatementNode::Choose, $1.filename, $1.lineno, $3, $5); }
        | CHOOSE '(' comma_expression ')' '{' push declaration_list_opt choose_clause_list_opt '}' /* CFA */
                { $$ = new StatementNode(StatementNode::Choose, $1.filename, $1.lineno, $3, $8); }
        ;

/* CASE and DEFAULT clauses are only allowed in the SWITCH statement, precluding Duff's device. In addition, a
   case clause allows a list of values and subranges. */

case_value:                                             /* CFA */
        constant_expression                     { $$ = $1; }
        | constant_expression ELLIPSIS constant_expression /* GCC, subrange */
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Range),$1,$3); }
        | subrange                                      /* CFA, subrange */
        ;

case_value_list:                                        /* CFA */
        case_value
        | case_value_list ',' case_value        {  $$ = (ExpressionNode *)($1->set_link($3)); }
        ;

case_label:                                             /* CFA */
        CASE case_value_list ':'                {  $$ = new StatementNode(StatementNode::Case, $1.filename, $1.lineno, $2, 0); }
        | DEFAULT ':'                           {  $$ = new StatementNode(StatementNode::Default, $1.filename, $1.lineno);     }
                /* A semantic check is required to ensure only one default clause per switch/choose
                   statement. */
        ;

case_label_list:                                        /* CFA */
        case_label
        | case_label_list case_label            { $$ = (StatementNode *)($1->set_link($2)); }
        ;

case_clause:                                            /* CFA */
        case_label_list statement               {  $$ = $1->append_last_case($2); }
        ;

switch_clause_list_opt:                                 /* CFA */
        /* empty */                             { $$ = 0; }
        | switch_clause_list
        ;

switch_clause_list:                                     /* CFA */
        case_label_list statement_list
                                                { $$ = $1->append_last_case($2); }
        | switch_clause_list case_label_list statement_list
                                                { $$ = (StatementNode *)($1->set_link($2->append_last_case($3))); }
        ;

choose_clause_list_opt:                                 /* CFA */
        /* empty */                             { $$ = 0; }
        | choose_clause_list
        ;

choose_clause_list:                                     /* CFA */
        case_label_list fall_through
                  { $$ = $1->append_last_case($2); }
        | case_label_list statement_list fall_through_opt
                  { $$ = $1->append_last_case((StatementNode *)mkList((*$2,*$3))); }
        | choose_clause_list case_label_list fall_through
                  { $$ = (StatementNode *)($1->set_link($2->append_last_case($3))); }
        | choose_clause_list case_label_list statement_list fall_through_opt
                  { $$ = (StatementNode *)($1->set_link($2->append_last_case((StatementNode *)mkList((*$3,*$4))))); }
        ;

fall_through_opt:                                       /* CFA */
        /* empty */                             { $$ = 0; }
        | fall_through
        ;

fall_through:                                           /* CFA */
        FALLTHRU                                { $$ = new StatementNode(StatementNode::Fallthru, $1.filename, $1.lineno, 0, 0); }
        | FALLTHRU ';'                          { $$ = new StatementNode(StatementNode::Fallthru, $1.filename, $1.lineno, 0, 0); }
        ;

iteration_statement:
        WHILE '(' comma_expression ')' statement
                                                { $$ = new StatementNode(StatementNode::While, $1.filename, $1.lineno, $3, $5); }
        | DO statement WHILE '(' comma_expression ')' ';'
                                                { $$ = new StatementNode(StatementNode::Do, $1.filename, $1.lineno, $5, $2); }
        | FOR '(' push for_control_expression ')' statement
                                                { $$ = new StatementNode(StatementNode::For, $1.filename, $1.lineno, $4, $6); }
        ;

for_control_expression:
        comma_expression_opt pop ';' comma_expression_opt ';' comma_expression_opt
                                                { $$ = new ForCtlExprNode($1, $4, $6); }
        | declaration comma_expression_opt ';' comma_expression_opt /* ANSI99 */
                /* Like C++, the loop index can be declared local to the loop. */
                                                { $$ = new ForCtlExprNode($1, $2, $4); }
        ;

jump_statement:
        GOTO identifier_or_typedef_name ';'
                                                { $$ = new StatementNode(StatementNode::Goto, $1.filename, $1.lineno, $2); }
        | GOTO '*' comma_expression ';'         /* GCC, computed goto */
                /* The syntax for the GCC computed goto violates normal expression precedence, e.g.,
                   goto *i+3; => goto *(i+3); whereas normal operator precedence yields goto (*i)+3; */
                                                { $$ = new StatementNode(StatementNode::Goto, $1.filename, $1.lineno, $3); }
        | CONTINUE ';'
                /* A semantic check is required to ensure this statement appears only in the body of an
                   iteration statement. */
                                                { $$ = new StatementNode(StatementNode::Continue, $1.filename, $1.lineno, 0, 0); }
        | CONTINUE identifier_or_typedef_name ';'       /* CFA, multi-level continue */
                /* A semantic check is required to ensure this statement appears only in the body of an
                   iteration statement, and the target of the transfer appears only at the start of an
                   iteration statement. */
                                                { $$ = new StatementNode(StatementNode::Continue, $1.filename, $1.lineno, $2); }
        | BREAK ';'
                /* A semantic check is required to ensure this statement appears only in the body of an
                   iteration statement. */
                                                { $$ = new StatementNode(StatementNode::Break, $1.filename, $1.lineno, 0, 0); }
        | BREAK identifier_or_typedef_name ';'          /* CFA, multi-level exit */
                /* A semantic check is required to ensure this statement appears only in the body of an
                   iteration statement, and the target of the transfer appears only at the start of an
                   iteration statement. */
                                                { $$ = new StatementNode(StatementNode::Break, $1.filename, $1.lineno, $2 ); }
        | RETURN comma_expression_opt ';'
                                                { $$ = new StatementNode(StatementNode::Return, $1.filename, $1.lineno, $2, 0); }
        | THROW assignment_expression ';'
                                                { $$ = new StatementNode(StatementNode::Throw, $1.filename, $1.lineno, $2, 0); }
        | THROW ';'
                                                { $$ = new StatementNode(StatementNode::Throw, $1.filename, $1.lineno, 0, 0); }
        ;

exception_statement:
        TRY compound_statement handler_list
                             { $$ = new StatementNode(StatementNode::Try, $1.filename, $1.lineno, 0,(StatementNode *)(mkList((*$2,*$3)))); }
        ;

handler_list:
                /* There must be at least one catch clause */
        handlers
        | CATCH '(' ELLIPSIS ')' compound_statement
                                                { $$ = StatementNode::newCatchStmt( $1.filename, $1.lineno, 0, $5, true ); }
        | handlers CATCH '(' ELLIPSIS ')' compound_statement
                /* ISO/IEC 9899:1999 Section 15.3(6) If present, a "..." handler shall be the last handler for
                   its try block. */
                                                { $$ = $1->set_link( StatementNode::newCatchStmt( $2.filename, $2.lineno, 0, $6, true ) ); }
        ;

handlers:
        CATCH '(' push push exception_declaration pop ')' compound_statement pop
                                                { $$ = StatementNode::newCatchStmt($1.filename, $1.lineno, $5, $8); }
        | handlers CATCH '(' push push exception_declaration pop ')' compound_statement pop
                                                { $$ = $1->set_link( StatementNode::newCatchStmt($2.filename, $2.lineno, $6, $9) );   }
        ;

exception_declaration:
                /* A semantic check is required to ensure type_specifier does not create a new type, e.g.:

                        catch ( struct { int i; } x ) ...

                   This new type cannot catch any thrown type because of name equivalence among types. */
        type_specifier
        | type_specifier declarator
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    $$ = $2->addType( $1 );
                }
        | type_specifier variable_abstract_declarator
                {   $$ = $2->addType( $1 ); }
        | new_abstract_declarator_tuple identifier_or_typedef_name /* CFA */
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    $$ = $1->addName( $2 );
                }
        | new_abstract_declarator_tuple                 /* CFA */
        ;

asm_statement:
        ASM type_qualifier_list_opt '(' constant_expression ')' ';'
                                                { $$ = new StatementNode(StatementNode::Asm, $1.filename, $1.lineno, 0, 0); }
        | ASM type_qualifier_list_opt '(' constant_expression ':' asm_operands_opt ')' ';' /* remaining GCC */
                                                { $$ = new StatementNode(StatementNode::Asm, $1.filename, $1.lineno, 0, 0); }
        | ASM type_qualifier_list_opt '(' constant_expression ':' asm_operands_opt ':' asm_operands_opt ')' ';'
                                                { $$ = new StatementNode(StatementNode::Asm, $1.filename, $1.lineno, 0, 0); }
        | ASM type_qualifier_list_opt '(' constant_expression ':' asm_operands_opt ':' asm_operands_opt ':'
                        asm_clobbers_list ')' ';'
                                                { $$ = new StatementNode(StatementNode::Asm, $1.filename, $1.lineno, 0, 0); }
        ;

asm_operands_opt:                                       /* GCC */
        /* empty */
        | asm_operands_list
        ;

asm_operands_list:                                      /* GCC */
        asm_operand
        | asm_operands_list ',' asm_operand
        ;

asm_operand:                                            /* GCC */
        STRINGliteral '(' constant_expression ')'       {}
        ;

asm_clobbers_list:                                      /* GCC */
        STRINGliteral                           {}
        | asm_clobbers_list ',' STRINGliteral
        ;

/******************************* DECLARATIONS *********************************/

declaration_list_opt:                                   /* used at beginning of switch statement */
        pop
                { $$ = 0; }
        | declaration_list
        ;

declaration_list:
        declaration
        | declaration_list push declaration
                { $$ = $1->appendList( $3 ); }
        ;

old_declaration_list_opt:                               /* used to declare parameter types in K&R style functions */
        pop
                { $$ = 0; }
        | old_declaration_list
        ;

old_declaration_list:
        old_declaration
        | old_declaration_list push old_declaration
                { $$ = $1->appendList( $3 ); }
        ;

label_declaration_opt:                                  /* GCC, local label */
        /* empty */
        | label_declaration_list
        ;

label_declaration_list:                                 /* GCC, local label */
        LABEL label_list ';'
        | label_declaration_list LABEL label_list ';'
        ;

label_list:                                             /* GCC, local label */
        identifier_or_typedef_name              {}
        | label_list ',' identifier_or_typedef_name {}
        ;

declaration:                                            /* CFA, new & old style declarations */
        new_declaration
        | old_declaration
        ;

/* C declaration syntax is notoriously confusing and error prone. Cforall provides its own type, variable and
   function declarations. CFA declarations use the same declaration tokens as in C; however, CFA places
   declaration modifiers to the left of the base type, while C declarations place modifiers to the right of
   the base type. CFA declaration modifiers are interpreted from left to right and the entire type
   specification is distributed across all variables in the declaration list (as in Pascal).  ANSI C and the
   new CFA declarations may appear together in the same program block, but cannot be mixed within a specific
   declaration.

            CFA             C
        [10] int x;     int x[10];      // array of 10 integers
        [10] * char y;  char *y[10];    // array of 10 pointers to char
   */

new_declaration:                                        /* CFA */
        new_variable_declaration pop ';'
        | new_typedef_declaration pop ';'
        | new_function_declaration pop ';'
        | type_declaring_list pop ';'
        | context_specifier pop ';'
        ;

new_variable_declaration:                               /* CFA */
        new_variable_specifier initializer_opt
                {
                        typedefTable.addToEnclosingScope( TypedefTable::ID);
                        $$ = $1;
                }
        | declaration_qualifier_list new_variable_specifier initializer_opt
                /* declaration_qualifier_list also includes type_qualifier_list, so a semantic check is
                   necessary to preclude them as a type_qualifier cannot appear in that context. */
                {
                        typedefTable.addToEnclosingScope( TypedefTable::ID);
                        $$ = $2->addQualifiers( $1 );
                }
        | new_variable_declaration pop ',' push identifier_or_typedef_name initializer_opt
                {
                        typedefTable.addToEnclosingScope( *$5.str, TypedefTable::ID);
                        $$ = $1->appendList( $1->cloneType( $5 ) );
                }
        ;

new_variable_specifier:                                 /* CFA */
                /* A semantic check is required to ensure asm_name only appears on declarations with implicit
                   or explicit static storage-class */
        new_abstract_declarator_no_tuple identifier_or_typedef_name asm_name_opt
                {
                        typedefTable.setNextIdentifier( *$2.str );
                        $$ = $1->addName( $2 );
                }
        | new_abstract_tuple identifier_or_typedef_name asm_name_opt
                {
                        typedefTable.setNextIdentifier( *$2.str );
                        $$ = $1->addName( $2 );
                }
        | type_qualifier_list new_abstract_tuple identifier_or_typedef_name asm_name_opt
                {
                        typedefTable.setNextIdentifier( *$3.str );
                        $$ = $2->addQualifiers( $1 )->addName( $3 );
                }
        ;

new_function_declaration:                               /* CFA */
        new_function_specifier
                {
                        typedefTable.addToEnclosingScope( TypedefTable::ID);
                        $$ = $1;
                }
        | declaration_qualifier_list new_function_specifier
                /* declaration_qualifier_list also includes type_qualifier_list, so a semantic check is
                   necessary to preclude them as a type_qualifier cannot appear in this context. */
                {
                        typedefTable.addToEnclosingScope( TypedefTable::ID);
                        $$ = $2->addQualifiers( $1 );
                }
        | new_function_declaration pop ',' push identifier_or_typedef_name
                {
                        typedefTable.addToEnclosingScope( *$5.str, TypedefTable::ID);
                        $$ = $1->appendList( $1->cloneType( $5 ) );
                }
        ;

new_function_specifier:                                 /* CFA */
        '[' push pop ']' identifier '(' push new_parameter_type_list_opt pop ')'
                {
                        typedefTable.setNextIdentifier( *($5.str) );
                        $$ = DeclarationNode::newFunction( $5, DeclarationNode::newTuple( 0, $1.filename, $1.lineno ), $8, 0 );
                }
        | '[' push pop ']' TYPEDEFname '(' push new_parameter_type_list_opt pop ')'
                {
                        typedefTable.setNextIdentifier( *($5.str) );
                        $$ = DeclarationNode::newFunction( $5, DeclarationNode::newTuple( 0, $1.filename, $1.lineno ), $8, 0 );
                }
                /* identifier_or_typedef_name must be broken apart because of the sequence:

                   '[' ']' identifier_or_typedef_name '(' new_parameter_type_list_opt ')'
                   '[' ']' type_specifier

                   type_specifier can resolve to just TYPEDEFname (e.g. typedef int T; int f( T );). Therefore
                   this must be flattened to allow lookahead to the '(' without having to reduce
                   identifier_or_typedef_name. */
        | new_abstract_tuple identifier_or_typedef_name '(' push new_parameter_type_list_opt pop ')'
                /* To obtain LR(1), this rule must be factored out from function return type (see
                   new_abstract_declarator). */
                {
                        $$ = DeclarationNode::newFunction( $2, $1, $5, 0 );
                }
        | new_function_return identifier_or_typedef_name '(' push new_parameter_type_list_opt pop ')'
                {
                        $$ = DeclarationNode::newFunction( $2, $1, $5, 0 );
                }
        ;

new_function_return:                                    /* CFA */
        '[' push new_parameter_list pop ']'
                { $$ = DeclarationNode::newTuple( $3, $1.filename, $1.lineno ); }
        | '[' push new_parameter_list pop ',' push new_abstract_parameter_list pop ']'
                /* To obtain LR(1), the last new_abstract_parameter_list is added into this flattened rule to
                   lookahead to the ']'. */
                { $$ = DeclarationNode::newTuple( $3->appendList( $7 ), $1.filename, $1.lineno ); }
        ;

new_typedef_declaration:                                /* CFA */
        TYPEDEF new_variable_specifier
                {
                        typedefTable.addToEnclosingScope( TypedefTable::TD);
                        $$ = $2->addTypedef();
                }
        | TYPEDEF new_function_specifier
                {
                        typedefTable.addToEnclosingScope( TypedefTable::TD);
                        $$ = $2->addTypedef();
                }
        | new_typedef_declaration pop ',' push identifier_or_typedef_name
                {
                        typedefTable.addToEnclosingScope( *$5.str, TypedefTable::TD);
                        $$ = $1->appendList( $1->cloneType( $5 ) );
                }
        ;

/* Traditionally typedef is part of storage-class specifier for syntactic convenience only. Here, it is
   factored out as a separate form of declaration, which syntactically precludes storage-class specifiers and
   initialization. */

typedef_declaration:
        TYPEDEF type_specifier declarator
                {
                        typedefTable.addToEnclosingScope( TypedefTable::TD);
                        $$ = $3->addType( $2 )->addTypedef();
                }
        | typedef_declaration pop ',' push declarator
                {
                        typedefTable.addToEnclosingScope( TypedefTable::TD);
                        $$ = $1->appendList( $1->cloneBaseType( $5 )->addTypedef() );
                }
        | type_qualifier_list TYPEDEF type_specifier declarator /* remaining OBSOLESCENT (see 2) */
                {
                        typedefTable.addToEnclosingScope( TypedefTable::TD);
                        $$ = $4->addType( $3 )->addQualifiers( $1 )->addTypedef();
                }
        | type_specifier TYPEDEF declarator
                {
                        typedefTable.addToEnclosingScope( TypedefTable::TD);
                        $$ = $3->addType( $1 )->addTypedef();
                }
        | type_specifier TYPEDEF type_qualifier_list declarator
                {
                        typedefTable.addToEnclosingScope( TypedefTable::TD);
                        $$ = $4->addQualifiers($1)->addTypedef()->addType($1);
                }
        ;

typedef_expression:                                     /* GCC, naming expression type */
        TYPEDEF identifier '=' assignment_expression
                {
                        typedefTable.addToEnclosingScope(*($2.str), TypedefTable::TD);
                        $$ = DeclarationNode::newName( $2 ); // XXX
                }
        | typedef_expression pop ',' push identifier '=' assignment_expression
                {
                        typedefTable.addToEnclosingScope(*($5.str), TypedefTable::TD);
                        $$ = DeclarationNode::newName( $5 ); // XXX
                }
        ;

old_declaration:
        declaring_list pop ';'
        | typedef_declaration pop ';'
        | typedef_expression pop ';'                    /* GCC, naming expression type */
        | sue_declaration_specifier pop ';'
        ;

declaring_list:
                /* A semantic check is required to ensure asm_name only appears on declarations with implicit
                   or explicit static storage-class */
        declaration_specifier declarator asm_name_opt initializer_opt
                {
                        typedefTable.addToEnclosingScope( TypedefTable::ID);
                        $$ = ($2->addType( $1 ))->addInitializer($4);
                }
        | declaring_list ',' attribute_list_opt declarator asm_name_opt initializer_opt
                {
                        typedefTable.addToEnclosingScope( TypedefTable::ID);
                        $$ = $1->appendList( $1->cloneBaseType( $4->addInitializer($6) ) );
                }
        ;

declaration_specifier:                                  /* type specifier + storage class */
        basic_declaration_specifier
        | sue_declaration_specifier
        | typedef_declaration_specifier
        | typegen_declaration_specifier
        ;

type_specifier:                                         /* declaration specifier - storage class */
        basic_type_specifier
        | sue_type_specifier
        | typedef_type_specifier
        | typegen_type_specifier
        ;

type_qualifier_list_opt:                                /* GCC, used in asm_statement */
        /* empty */
                { $$ = 0; }
        | type_qualifier_list
        ;

type_qualifier_list:
                /* A semantic check is necessary to ensure a type qualifier is appropriate for the kind of
                   declaration.

                   ISO/IEC 9899:1999 Section 6.7.3(4) : If the same qualifier appears more than once in the
                   same specifier-qualifier-list, either directly or via one or more typedefs, the behavior is
                   the same as if it appeared only once. */
        type_qualifier
        | type_qualifier_list type_qualifier
                { $$ = $1->addQualifiers( $2 ); }
        ;

type_qualifier:
        type_qualifier_name
        | attribute
                { $$ = DeclarationNode::newQualifier( DeclarationNode::Const, $1.filename, $1.lineno ); }
        ;

type_qualifier_name:
        CONST
                { $$ = DeclarationNode::newQualifier( DeclarationNode::Const, $1.filename, $1.lineno ); }
        | RESTRICT
                { $$ = DeclarationNode::newQualifier( DeclarationNode::Restrict, $1.filename, $1.lineno ); }
        | VOLATILE
                { $$ = DeclarationNode::newQualifier( DeclarationNode::Volatile, $1.filename, $1.lineno ); }
        | LVALUE                                        /* CFA */
                { $$ = DeclarationNode::newQualifier( DeclarationNode::Lvalue, $1.filename, $1.lineno ); }
        | FORALL '(' 
                {
                        typedefTable.enterScope();
                }
          type_parameter_list ')'               /* CFA */
                {
                        typedefTable.leaveScope();
                        $$ = DeclarationNode::newForall( $4, $1.filename, $1.lineno );
                }
        ;

declaration_qualifier_list:
        storage_class_list
        | type_qualifier_list storage_class_list        /* remaining OBSOLESCENT (see 2) */
                { $$ = $1->addQualifiers( $2 ); }
        | declaration_qualifier_list type_qualifier_list storage_class_list
                { $$ = $1->addQualifiers( $2 )->addQualifiers( $3 ); }
        ;

storage_class_list:
                /* A semantic check is necessary to ensure a storage class is appropriate for the kind of
                   declaration and that only one of each is specified, except for inline, which can appear
                   with the others.

                   ISO/IEC 9899:1999 Section 6.7.1(2) : At most, one storage-class specifier may be given in
                   the declaration specifiers in a declaration. */
        storage_class
        | storage_class_list storage_class
                { $$ = $1->addQualifiers( $2 ); }
        ;

storage_class:
        storage_class_name
        ;

storage_class_name:
        AUTO
                { $$ = DeclarationNode::newStorageClass( DeclarationNode::Auto, $1.filename, $1.lineno ); }
        | EXTERN
                { $$ = DeclarationNode::newStorageClass( DeclarationNode::Extern, $1.filename, $1.lineno ); }
        | REGISTER
                { $$ = DeclarationNode::newStorageClass( DeclarationNode::Register, $1.filename, $1.lineno ); }
        | STATIC
                { $$ = DeclarationNode::newStorageClass( DeclarationNode::Static, $1.filename, $1.lineno ); }
        | INLINE                                        /* ANSI99 */
                /* INLINE is essentially a storage class specifier for functions, and hence, belongs here. */
                { $$ = DeclarationNode::newStorageClass( DeclarationNode::Inline, $1.filename, $1.lineno ); }
        | FORTRAN                                       /* ANSI99 */
                { $$ = DeclarationNode::newStorageClass( DeclarationNode::Fortran, $1.filename, $1.lineno ); }
        ;

basic_type_name:
        CHAR
                { $$ = DeclarationNode::newBasicType( DeclarationNode::Char, $1.filename, $1.lineno ); }
        | DOUBLE
                { $$ = DeclarationNode::newBasicType( DeclarationNode::Double, $1.filename, $1.lineno ); }
        | FLOAT
                { $$ = DeclarationNode::newBasicType( DeclarationNode::Float, $1.filename, $1.lineno ); }
        | INT
                { $$ = DeclarationNode::newBasicType( DeclarationNode::Int, $1.filename, $1.lineno ); }
        | LONG
                { $$ = DeclarationNode::newModifier( DeclarationNode::Long, $1.filename, $1.lineno ); }
        | SHORT
                { $$ = DeclarationNode::newModifier( DeclarationNode::Short, $1.filename, $1.lineno ); }
        | SIGNED
                { $$ = DeclarationNode::newModifier( DeclarationNode::Signed, $1.filename, $1.lineno ); }
        | UNSIGNED
                { $$ = DeclarationNode::newModifier( DeclarationNode::Unsigned, $1.filename, $1.lineno ); }
        | VOID
                { $$ = DeclarationNode::newBasicType( DeclarationNode::Void, $1.filename, $1.lineno ); }
        | BOOL                                          /* ANSI99 */
                { $$ = DeclarationNode::newBasicType( DeclarationNode::Bool, $1.filename, $1.lineno ); }
        | COMPLEX                                       /* ANSI99 */
                { $$ = DeclarationNode::newBasicType( DeclarationNode::Complex, $1.filename, $1.lineno ); }
        | IMAGINARY                                     /* ANSI99 */
                { $$ = DeclarationNode::newBasicType( DeclarationNode::Imaginary, $1.filename, $1.lineno ); }
        | TYPEOF '(' type_name ')'                      /* GCC: typeof(x) y; */
                { $$ = $3; }
        | TYPEOF '(' comma_expression ')'               /* GCC: typeof(a+b) y; */
                { $$ = DeclarationNode::newTypeof( $3, $1.filename, $1.lineno ); }
        | '<' identifier '>'                            /* CFA: <x> y; */
                { $$ = DeclarationNode::newName( $2 ); /* XXX */ }
        | '<' '(' comma_expression ')' '>'              /* CFA: <(a+b)> y */
                { $$ = DeclarationNode::newName( $3 ); /* XXX */ }
        ;

basic_declaration_specifier:
                /* A semantic check is necessary for conflicting storage classes. */
        basic_type_specifier
        | declaration_qualifier_list basic_type_specifier
                { $$ = $2->addQualifiers( $1 ); }
        | basic_declaration_specifier storage_class     /* remaining OBSOLESCENT (see 2) */
                { $$ = $1->addQualifiers( $2 ); }
        | basic_declaration_specifier storage_class type_qualifier_list
                { $$ = $1->addQualifiers( $2 )->addQualifiers( $3 ); }
        | basic_declaration_specifier storage_class basic_type_specifier
                { $$ = $3->addQualifiers( $2 )->addType( $1 ); }
        ;

basic_type_specifier:
                /* A semantic check is necessary for conflicting type qualifiers. */
        basic_type_name
        | type_qualifier_list basic_type_name
                { $$ = $2->addQualifiers( $1 ); }
        | basic_type_specifier type_qualifier
                { $$ = $1->addQualifiers( $2 ); }
        | basic_type_specifier basic_type_name
                { $$ = $1->addType( $2 ); }
        ;

sue_declaration_specifier:
        sue_type_specifier
        | declaration_qualifier_list sue_type_specifier
                { $$ = $2->addQualifiers( $1 ); }
        | sue_declaration_specifier storage_class       /* remaining OBSOLESCENT (see 2) */
                { $$ = $1->addQualifiers( $2 ); }
        | sue_declaration_specifier storage_class type_qualifier_list
                { $$ = $1->addQualifiers( $2 )->addQualifiers( $3 ); }
        ;

sue_type_specifier:
        elaborated_type_name                            /* struct, union, enum */
        | type_qualifier_list elaborated_type_name
                { $$ = $2->addQualifiers( $1 ); }
        | sue_type_specifier type_qualifier
                { $$ = $1->addQualifiers( $2 ); }
        ;

typedef_declaration_specifier:
        typedef_type_specifier
        | declaration_qualifier_list typedef_type_specifier
                { $$ = $2->addQualifiers( $1 ); }
        | typedef_declaration_specifier storage_class   /* remaining OBSOLESCENT (see 2) */
                { $$ = $1->addQualifiers( $2 ); }
        | typedef_declaration_specifier storage_class type_qualifier_list
                { $$ = $1->addQualifiers( $2 )->addQualifiers( $3 ); }
        ;

typedef_type_specifier:                                 /* typedef types */
        TYPEDEFname
                { $$ = DeclarationNode::newFromTypedef( $1 ); }
        | type_qualifier_list TYPEDEFname
                { $$ = DeclarationNode::newFromTypedef( $2 )->addQualifiers( $1 ); }
        | typedef_type_specifier type_qualifier
                { $$ = $1->addQualifiers( $2 ); }
        ;

elaborated_type_name:
        aggregate_name
        | enum_name
        ;

aggregate_name:
        aggregate_key '{' field_declaration_list '}'
                { $$ = DeclarationNode::newAggregate( $1, $2.filename, $2.lineno, 0, 0, $3 ); }
        | aggregate_key identifier_or_typedef_name
                { $$ = DeclarationNode::newAggregate( $1, $2, 0, 0, 0 ); }
        | aggregate_key identifier_or_typedef_name '{' field_declaration_list '}'
                { $$ = DeclarationNode::newAggregate( $1, $2, 0, 0, $4 ); }
        | aggregate_key '(' push type_parameter_list pop ')' '{' field_declaration_list '}' /* CFA */
                { $$ = DeclarationNode::newAggregate( $1, $2.filename, $2.lineno, $4, 0, $8 ); }
        | aggregate_key '(' push type_parameter_list pop ')' identifier_or_typedef_name /* CFA */
                { $$ = DeclarationNode::newAggregate( $1, $7, $4, 0, 0 ); }
        | aggregate_key '(' push type_parameter_list pop ')' identifier_or_typedef_name '{' field_declaration_list '}' /* CFA */
                { $$ = DeclarationNode::newAggregate( $1, $7, $4, 0, $9 ); }
        | aggregate_key '(' push type_parameter_list pop ')' '(' type_name_list ')' '{' field_declaration_list '}' /* CFA */
                { $$ = DeclarationNode::newAggregate( $1, $2.filename, $2.lineno, $4, $8, $11 ); }
        | aggregate_key '(' push type_name_list pop ')' identifier_or_typedef_name /* CFA */
                /* push and pop are only to prevent S/R conflicts */
                { $$ = DeclarationNode::newAggregate( $1, $7, 0, $4, 0 ); }
        | aggregate_key '(' push type_parameter_list pop ')' '(' type_name_list ')' identifier_or_typedef_name '{' field_declaration_list '}' /* CFA */
                { $$ = DeclarationNode::newAggregate( $1, $10, $4, $8, $12 ); }
        ;

aggregate_key:
        STRUCT attribute_list_opt
                { $$ = DeclarationNode::Struct; }
        | UNION attribute_list_opt
                { $$ = DeclarationNode::Union; }
        ;

field_declaration_list:
        field_declaration
                { $$ = $1; }
        | field_declaration_list field_declaration
                { $$ = $1->appendList( $2 ); }
        ;

field_declaration:
        new_field_declaring_list ';'                    /* CFA, new style field declaration */
        | EXTENSION new_field_declaring_list ';'        /* GCC */
                { $$ = $2; }
        | field_declaring_list ';'
        | EXTENSION field_declaring_list ';'            /* GCC */
                { $$ = $2; }
        ;

new_field_declaring_list:                               /* CFA, new style field declaration */
        new_abstract_declarator_tuple                   /* CFA, no field name */
        | new_abstract_declarator_tuple identifier_or_typedef_name
                { $$ = $1->addName( $2 ); }
        | new_field_declaring_list ',' identifier_or_typedef_name
                { $$ = $1->appendList( $1->cloneType( $3 ) ); }
        | new_field_declaring_list ','                  /* CFA, no field name */
                { $$ = $1->appendList( $1->cloneType( 0 ) ); }
        ;

field_declaring_list:
        type_specifier field_declarator
                { $$ = $2->addType( $1 ); }
        | field_declaring_list ',' attribute_list_opt field_declarator
                { $$ = $1->appendList( $1->cloneBaseType( $4 ) ); }
        ;

field_declarator:
        /* empty */                                     /* CFA, no field name */
                { $$ = 0; /* XXX */ }
        | bit_subrange_size                             /* no field name */
                { $$ = DeclarationNode::newBitfield( $1 ); }
        | variable_declarator bit_subrange_size_opt
                /* A semantic check is required to ensure bit_subrange only appears on base type int. */
                { $$ = $1->addBitfield( $2 ); }
        | typedef_redeclarator bit_subrange_size_opt
                /* A semantic check is required to ensure bit_subrange only appears on base type int. */
                { $$ = $1->addBitfield( $2 ); }
        | variable_abstract_declarator                  /* CFA, no field name */
        ;

bit_subrange_size_opt:
        /* empty */
                { $$ = 0; }
        | bit_subrange_size
                { $$ = $1; }
        ;

bit_subrange_size:
        ':' constant_expression
                { $$ = $2; }
        ;

enum_key:
        ENUM attribute_list_opt
        ;

enum_name:
        enum_key '{' enumerator_list comma_opt '}'
                { $$ = DeclarationNode::newEnum( $2.filename, $2.lineno, $3 ); }
        | enum_key identifier_or_typedef_name '{' enumerator_list comma_opt '}'
                { $$ = DeclarationNode::newEnum( $2, $4 ); }
        | enum_key identifier_or_typedef_name
                { $$ = DeclarationNode::newEnum( $2, 0 ); }
        ;

enumerator_list:
        identifier_or_typedef_name enumerator_value_opt
                { $$ = DeclarationNode::newEnumConstant( $1, $2 ); }
        | enumerator_list ',' identifier_or_typedef_name enumerator_value_opt
                { $$ = $1->appendList( DeclarationNode::newEnumConstant( $3, $4 ) ); }
        ;

enumerator_value_opt:
        /* empty */
                { $$ = 0; }
        | '=' constant_expression
                { $$ = $2; }
        ;

/* Minimum of one parameter after which ellipsis is allowed only at the end. */

new_parameter_type_list_opt:                            /* CFA */
        /* empty */
                { $$ = 0; }
        | new_parameter_type_list
        ;

new_parameter_type_list:                                /* CFA, abstract + real */
        new_abstract_parameter_list
        | new_parameter_list
        | new_parameter_list pop ',' push new_abstract_parameter_list
                { $$ = $1->appendList( $5 ); }
        | new_abstract_parameter_list pop ',' push ELLIPSIS
                { $$ = $1->addVarArgs(); }
        | new_parameter_list pop ',' push ELLIPSIS
                { $$ = $1->addVarArgs(); }
        ;

new_parameter_list:                                     /* CFA */
                /* To obtain LR(1) between new_parameter_list and new_abstract_tuple, the last
                   new_abstract_parameter_list is factored out from new_parameter_list, flattening the rules
                   to get lookahead to the ']'. */
        new_parameter_declaration
        | new_abstract_parameter_list pop ',' push new_parameter_declaration
                { $$ = $1->appendList( $5 ); }
        | new_parameter_list pop ',' push new_parameter_declaration
                { $$ = $1->appendList( $5 ); }
        | new_parameter_list pop ',' push new_abstract_parameter_list pop ',' push new_parameter_declaration
                { $$ = $1->appendList( $5 )->appendList( $9 ); }
        ;

new_abstract_parameter_list:                            /* CFA, new & old style abstract */
        new_abstract_parameter_declaration
        | new_abstract_parameter_list pop ',' push new_abstract_parameter_declaration
                { $$ = $1->appendList( $5 ); }
        ;

parameter_type_list_opt:
        /* empty */
                { $$ = 0; }
        | parameter_type_list
        ;

parameter_type_list:
        parameter_list
        | parameter_list pop ',' push ELLIPSIS
                { $$ = $1->addVarArgs(); }
        ;

parameter_list:                                         /* abstract + real */
        abstract_parameter_declaration
        | parameter_declaration
        | parameter_list pop ',' push abstract_parameter_declaration
                { $$ = $1->appendList( $5 ); }
        | parameter_list pop ',' push parameter_declaration
                { $$ = $1->appendList( $5 ); }
        ;

/* Provides optional identifier names (abstract_declarator/variable_declarator), no initialization, different
   semantics for typedef name by using typedef_parameter_redeclarator instead of typedef_redeclarator, and
   function prototypes. */

new_parameter_declaration:                              /* CFA, new & old style parameter declaration */
        parameter_declaration
        | new_identifier_parameter_declarator_no_tuple identifier_or_typedef_name assignment_opt
                { $$ = $1->addName( $2 ); }
        | new_abstract_tuple identifier_or_typedef_name assignment_opt
                /* To obtain LR(1), these rules must be duplicated here (see new_abstract_declarator). */
                { $$ = $1->addName( $2 ); }
        | type_qualifier_list new_abstract_tuple identifier_or_typedef_name assignment_opt
                { $$ = $2->addName( $3 )->addQualifiers( $1 ); }
        | new_function_specifier
        ;

new_abstract_parameter_declaration:                     /* CFA, new & old style parameter declaration */
        abstract_parameter_declaration
        | new_identifier_parameter_declarator_no_tuple
        | new_abstract_tuple
                /* To obtain LR(1), these rules must be duplicated here (see new_abstract_declarator). */
        | type_qualifier_list new_abstract_tuple
                { $$ = $2->addQualifiers( $1 ); }
        | new_abstract_function
        ;

parameter_declaration:
        declaration_specifier identifier_parameter_declarator assignment_opt
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID);
                    $$ = $2->addType( $1 );
                }
        | declaration_specifier typedef_parameter_redeclarator assignment_opt
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID);
                    $$ = $2->addType( $1 );
                }
        ;

abstract_parameter_declaration:
        declaration_specifier
        | declaration_specifier abstract_parameter_declarator
                { $$ = $2->addType( $1 ); }
        ;

/* ISO/IEC 9899:1999 Section 6.9.1(6) : "An identifier declared as a typedef name shall not be redeclared as a
   parameter." Because the scope of the K&R-style parameter-list sees the typedef first, the following is
   based only on identifiers.  The ANSI-style parameter-list can redefine a typedef name. */

identifier_list:                                        /* K&R-style parameter list => no types */
        identifier
                { $$ = DeclarationNode::newName( $1 ); }
        | identifier_list ',' identifier
                { $$ = $1->appendList( DeclarationNode::newName( $3 ) ); }
        ;

identifier_or_typedef_name:
        identifier
        | TYPEDEFname
        | TYPEGENname
        ;

type_name_no_function:                                  /* sizeof, alignof, cast (constructor) */
        new_abstract_declarator_tuple                   /* CFA */
        | type_specifier
        | type_specifier variable_abstract_declarator
                { $$ = $2->addType( $1 ); }
        ;

type_name:                                              /* typeof, assertion */
        new_abstract_declarator_tuple                   /* CFA */
        | new_abstract_function                         /* CFA */
        | type_specifier
        | type_specifier abstract_declarator
                { $$ = $2->addType( $1 ); }
        ;

initializer_opt:
        /* empty */                             { $$ = 0; }
        | '=' initializer                       { $$ = $2; }
        ;

initializer:
        assignment_expression                   { $$ = new InitializerNode($1); }
        | '{' initializer_list comma_opt '}'    { $$ = new InitializerNode($2, true); }
        ;

initializer_list:
        initializer
        | designation initializer                            { $$ = $2->set_designators( $1 ); }
        | initializer_list ',' initializer                   { $$ = (InitializerNode *)( $1->set_link($3) ); }
        | initializer_list ',' designation initializer
                                           { $$ = (InitializerNode *)( $1->set_link( $4->set_designators($3) ) ); }
        ;

/* There is an unreconcileable parsing problem between ANSI99 and CFA with respect to designators. The problem
   is use of '=' to separator the designator from the initializer value, as in:

        int x[10] = { [1] = 3 };

   The string "[1] = 3" can be parsed as a designator assignment or a tuple assignment.  To disambiguate this
   case, CFA changes the syntax from "=" to ":" as the separator between the designator and initializer. GCC
   does uses ":" for field selection. The optional use of the "=" in GCC, or in this case ":", cannot be
   supported either due to shift/reduce conflicts */

designation:
        designator_list ':'                             /* ANSI99, CFA uses ":" instead of "=" */
        | identifier_or_typedef_name ':'                /* GCC, field name */
                                                       { $$ = new VarRefNode( $1 ); }
        ;

designator_list:                                        /* ANSI99 */
        designator
        | designator_list designator                   { $$ = (ExpressionNode *)($1->set_link( $2 )); }
        ;

designator:
        '.' identifier_or_typedef_name                  /* ANSI99, field name */
                                                       { $$ = new VarRefNode( $2 ); }
        | '[' push assignment_expression pop ']'        /* ANSI99, single array element */
                /* assignment_expression used instead of constant_expression because of shift/reduce conflicts
                   with tuple. */
                                                       { $$ = $3; }
        | '[' push subrange pop ']'                     /* CFA, multiple array elements */
                                                       { $$ = $3; }
        | '[' push constant_expression ELLIPSIS constant_expression pop ']' /* GCC, multiple array elements */
                                                       { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Range, $1.filename, $1.lineno), $3, $5); }
        | '.' '[' push field_list pop ']'               /* CFA, tuple field selector */
                                                       { $$ = $4; }
        ;

/* The CFA type system is based on parametric polymorphism, the ability to declare functions with type
   parameters, rather than an object-oriented type system. This required four groups of extensions:

   Overloading: function, data, and operator identifiers may be overloaded.

   Type declarations: "type" is used to generate new types for declaring objects. Similarly, "dtype" is used
       for object and incomplete types, and "ftype" is used for function types. Type declarations with
       initializers provide definitions of new types. Type declarations with storage class "extern" provide
       opaque types.

   Polymorphic functions: A forall clause declares a type parameter. The corresponding argument is inferred at
       the call site. A polymorphic function is not a template; it is a function, with an address and a type.

   Specifications and Assertions: Specifications are collections of declarations parameterized by one or more
       types. They serve many of the purposes of abstract classes, and specification hierarchies resemble
       subclass hierarchies. Unlike classes, they can define relationships between types.  Assertions declare
       that a type or types provide the operations declared by a specification.  Assertions are normally used
       to declare requirements on type arguments of polymorphic functions.  */

typegen_declaration_specifier:                          /* CFA */
        typegen_type_specifier
        | declaration_qualifier_list typegen_type_specifier
                { $$ = $2->addQualifiers( $1 ); }
        | typegen_declaration_specifier storage_class   /* remaining OBSOLESCENT (see 2) */
                { $$ = $1->addQualifiers( $2 ); }
        | typegen_declaration_specifier storage_class type_qualifier_list
                { $$ = $1->addQualifiers( $2 )->addQualifiers( $3 ); }
        ;

typegen_type_specifier:                                 /* CFA */
        TYPEGENname '(' type_name_list ')'
                { $$ = DeclarationNode::newFromTypeGen( $1, $3 ); }
        | type_qualifier_list TYPEGENname '(' type_name_list ')'
                { $$ = DeclarationNode::newFromTypeGen( $2, $4 )->addQualifiers( $1 ); }
        | typegen_type_specifier type_qualifier
                { $$ = $1->addQualifiers( $2 ); }
        ;

type_parameter_list:                                    /* CFA */
        type_parameter assignment_opt
        | type_parameter_list ',' type_parameter assignment_opt
                { $$ = $1->appendList( $3 ); }
        ;

type_parameter:                                         /* CFA */
        type_class identifier_or_typedef_name
                { typedefTable.addToEnclosingScope(*($2.str), TypedefTable::TD); }
          assertion_list_opt
                { $$ = DeclarationNode::newTypeParam( $1, $2.str )->addAssertions( $4 ); }
        | type_specifier identifier_parameter_declarator
        ;

type_class:                                             /* CFA */
        TYPE
                { $$ = DeclarationNode::Type; }
        | DTYPE
                { $$ = DeclarationNode::Ftype; }
        | FTYPE
                { $$ = DeclarationNode::Dtype; }
        ;

assertion_list_opt:                                     /* CFA */
        /* empty */
                { $$ = 0; }
        | assertion_list_opt assertion
                { $$ = $1 == 0 ? $2 : $1->appendList( $2 ); }
        ;

assertion:                                              /* CFA */
        '|' identifier_or_typedef_name '(' type_name_list ')'
                {
                    typedefTable.openContext( *($2.str) );
                    $$ = DeclarationNode::newContextUse( $2, $4 );
                }
        | '|' '{' push context_declaration_list '}'
                { $$ = $4; }
        | '|' '(' push type_parameter_list pop ')' '{' push context_declaration_list '}' '(' type_name_list ')'
                { $$ = 0; }
        ;

type_name_list:                                         /* CFA */
        type_name
                { $$ = new TypeValueNode( $1 ); }
        | assignment_expression
        | type_name_list ',' type_name
                { $$ = (ExpressionNode *)($1->set_link(new TypeValueNode( $3 ))); }
        | type_name_list ',' assignment_expression
                { $$ = (ExpressionNode *)($1->set_link($3)); }
        ;

type_declaring_list:                                    /* CFA */
        TYPE type_declarator
                { $$ = $2; }
        | storage_class_list TYPE type_declarator
                { $$ = $3->addQualifiers( $1 ); }
        | type_declaring_list ',' type_declarator
                { $$ = $1->appendList( $3->copyStorageClasses( $1 ) ); }
        ;

type_declarator:                                        /* CFA */
        type_declarator_name assertion_list_opt
                { $$ = $1->addAssertions( $2 ); }
        | type_declarator_name assertion_list_opt '=' type_name
                { $$ = $1->addAssertions( $2 )->addType( $4 ); }
        ;

type_declarator_name:                                   /* CFA */
        identifier_or_typedef_name
                {
                    typedefTable.addToEnclosingScope(*($1.str), TypedefTable::TD);
                    $$ = DeclarationNode::newTypeDecl( $1, 0 );
                }
        | identifier_or_typedef_name '(' push type_parameter_list pop ')'
                {
                    typedefTable.addToEnclosingScope(*($1.str), TypedefTable::TG);
                    $$ = DeclarationNode::newTypeDecl( $1, $4 );
                }
        ;

context_specifier:                                      /* CFA */
        CONTEXT identifier_or_typedef_name '(' push type_parameter_list pop ')' '{' '}'
                {
                    typedefTable.addToEnclosingScope(*($2.str), TypedefTable::ID);
                    $$ = DeclarationNode::newContext( $2, $5, 0 );
                }
        | CONTEXT identifier_or_typedef_name '(' push type_parameter_list pop ')' '{'
                {
                    typedefTable.enterContext( *($2.str) );
                    typedefTable.enterScope();
                }
          context_declaration_list '}'
                {
                    typedefTable.leaveContext();
                    typedefTable.addToEnclosingScope(*($2.str), TypedefTable::ID);
                    $$ = DeclarationNode::newContext( $2, $5, $10 );
                }
        ;

context_declaration_list:                               /* CFA */
        context_declaration
        | context_declaration_list push context_declaration
                { $$ = $1->appendList( $3 ); }
        ;

context_declaration:                                    /* CFA */
        new_context_declaring_list pop ';'
        | context_declaring_list pop ';'
        ;

new_context_declaring_list:                             /* CFA */
        new_variable_specifier
                {
                    typedefTable.addToEnclosingScope2( TypedefTable::ID );
                    $$ = $1;
                }
        | new_function_specifier
                {
                    typedefTable.addToEnclosingScope2( TypedefTable::ID );
                    $$ = $1;
                }
        | new_context_declaring_list pop ',' push identifier_or_typedef_name
                {
                    typedefTable.addToEnclosingScope2( *($5.str), TypedefTable::ID );
                    $$ = $1->appendList( $1->cloneType( $5 ) );
                }
        ;

context_declaring_list:                                 /* CFA */
        type_specifier declarator
                {
                    typedefTable.addToEnclosingScope2( TypedefTable::ID);
                    $$ = $2->addType( $1 );
                }
        | context_declaring_list pop ',' push declarator
                {
                    typedefTable.addToEnclosingScope2( TypedefTable::ID);
                    $$ = $1->appendList( $1->cloneBaseType( $5 ) );
                }
        ;

/***************************** EXTERNAL DEFINITIONS *****************************/

translation_unit:
        /* empty */                                     /* empty input file */
                {}
        | external_definition_list
                {
                  if( theTree ) {
                    theTree->appendList( $1 );
                  } else {
                    theTree = $1;
                  }
                }
        ;

external_definition_list:
        external_definition
        | external_definition_list push external_definition
                {
                  if( $1 ) {
                    $$ = $1->appendList( $3 );
                  } else {
                    $$ = $3;
                  }
                }
        ;

external_definition_list_opt:
        /* empty */
                {
                  $$ = 0;
                }
        | external_definition_list
        ;

external_definition:
        declaration
        | function_definition
        | asm_statement                                 /* GCC, global assembler statement */
                {}
        | EXTERN STRINGliteral
                {
                  linkageStack.push( linkage );
                  linkage = LinkageSpec::fromString( *$2.str );
                }
          '{' external_definition_list_opt '}'          /* C++-style linkage specifier */
                {
                  linkage = linkageStack.top();
                  linkageStack.pop();
                  $$ = $5;
                }
        | EXTENSION external_definition
                { $$ = $2; }
        ;

function_definition:
        new_function_specifier compound_statement       /* CFA */
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $1->addFunctionBody( $2 );
                }
        | declaration_qualifier_list new_function_specifier compound_statement /* CFA */
                /* declaration_qualifier_list also includes type_qualifier_list, so a semantic check is
                   necessary to preclude them as a type_qualifier cannot appear in this context. */
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $2->addFunctionBody( $3 )->addQualifiers( $1 );
                }

        | declaration_specifier function_declarator compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $2->addFunctionBody( $3 )->addType( $1 );
                }

                /* These rules are a concession to the "implicit int" type_specifier because there is a
                   significant amount of code with functions missing a type-specifier on the return type.
                   Parsing is possible because function_definition does not appear in the context of an
                   expression (nested functions would preclude this concession). A function prototype
                   declaration must still have a type_specifier. OBSOLESCENT (see 1) */
        | function_declarator compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $1->addFunctionBody( $2 );
                }
        | type_qualifier_list function_declarator compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $2->addFunctionBody( $3 )->addQualifiers( $1 );
                }
        | declaration_qualifier_list function_declarator compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $2->addFunctionBody( $3 )->addQualifiers( $1 );
                }
        | declaration_qualifier_list type_qualifier_list function_declarator compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $3->addFunctionBody( $4 )->addQualifiers( $2 )->addQualifiers( $1 );
                }

                /* Old-style K&R function definition, OBSOLESCENT (see 4) */
        | declaration_specifier old_function_declarator push old_declaration_list_opt compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $2->addOldDeclList( $4 )->addFunctionBody( $5 )->addType( $1 );
                }
        | old_function_declarator push old_declaration_list_opt compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $1->addOldDeclList( $3 )->addFunctionBody( $4 );
                }
        | type_qualifier_list old_function_declarator push old_declaration_list_opt compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $2->addOldDeclList( $4 )->addFunctionBody( $5 )->addQualifiers( $1 );
                }

                /* Old-style K&R function definition with "implicit int" type_specifier, OBSOLESCENT (see 4) */
        | declaration_qualifier_list old_function_declarator push old_declaration_list_opt compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $2->addOldDeclList( $4 )->addFunctionBody( $5 )->addQualifiers( $1 );
                }
        | declaration_qualifier_list type_qualifier_list old_function_declarator push old_declaration_list_opt
                        compound_statement
                {
                    typedefTable.addToEnclosingScope( TypedefTable::ID );
                    typedefTable.leaveScope();
                    $$ = $3->addOldDeclList( $5 )->addFunctionBody( $6 )->addQualifiers( $2 )->addQualifiers( $1 );
                }
        ;

declarator:
        variable_declarator
        | function_declarator
        | typedef_redeclarator
        ;

subrange:
        constant_expression '~' constant_expression     /* CFA, integer subrange */
                { $$ = new CompositeExprNode(new OperatorNode(OperatorNode::Range, $2.filename, $2.lineno), $1, $3); }
        ;

asm_name_opt:                                           /* GCC */
        /* empty */
        | ASM '(' string_literal_list ')' attribute_list_opt
        ;

attribute_list_opt:                                     /* GCC */
        /* empty */
        | attribute_list
        ;

attribute_list:                                         /* GCC */
        attribute
        | attribute_list attribute
        ;

attribute:                                              /* GCC */
        ATTRIBUTE '(' '(' attribute_parameter_list ')' ')'
        ;

attribute_parameter_list:                               /* GCC */
        attrib
        | attribute_parameter_list ',' attrib
        ;

attrib:                                                 /* GCC */
        /* empty */
        | any_word
        | any_word '(' comma_expression_opt ')'
        ;

any_word:                                               /* GCC */
        identifier_or_typedef_name {}
        | storage_class_name {}
        | basic_type_name {}
        | type_qualifier {}
        ;

/* ============================================================================
   The following sections are a series of grammar patterns used to parse declarators. Multiple patterns are
   necessary because the type of an identifier in wrapped around the identifier in the same form as its usage
   in an expression, as in:

        int (*f())[10] { ... };
        ... (*f())[3] += 1;     // definition mimics usage

   Because these patterns are highly recursive, changes at a lower level in the recursion require copying some
   or all of the pattern. Each of these patterns has some subtle variation to ensure correct syntax in a
   particular context.
   ============================================================================ */

/* ----------------------------------------------------------------------------
   The set of valid declarators before a compound statement for defining a function is less than the set of
   declarators to define a variable or function prototype, e.g.:

        valid declaration       invalid definition
        -----------------       ------------------
        int f;                  int f {}
        int *f;                 int *f {}
        int f[10];              int f[10] {}
        int (*f)(int);          int (*f)(int) {}

   To preclude this syntactic anomaly requires separating the grammar rules for variable and function
   declarators, hence variable_declarator and function_declarator.
   ---------------------------------------------------------------------------- */

/* This pattern parses a declaration of a variable that is not redefining a typedef name. The pattern
   precludes declaring an array of functions versus a pointer to an array of functions. */

variable_declarator:
        paren_identifier attribute_list_opt
        | variable_ptr
        | variable_array attribute_list_opt
        | variable_function attribute_list_opt
        ;

paren_identifier:
        identifier
                {
                    typedefTable.setNextIdentifier( *($1.str) );
                    $$ = DeclarationNode::newName( $1 );
                }
        | '(' paren_identifier ')'                      /* redundant parenthesis */
                { $$ = $2; }
        ;

variable_ptr:
        '*' variable_declarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0, $1.filename, $1.lineno ) ); }
        | '*' type_qualifier_list variable_declarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2, $1.filename, $1.lineno ) ); }
        | '(' variable_ptr ')'
                { $$ = $2 }
        ;

variable_array:
        paren_identifier array_dimension
                { $$ = $1->addArray( $2 ); }
        | '(' variable_ptr ')' array_dimension
                { $$ = $2->addArray( $4 ); }
        | '(' variable_array ')' multi_array_dimension  /* redundant parenthesis */
                { $$ = $2->addArray( $4 ); }
        | '(' variable_array ')'                        /* redundant parenthesis */
                { $$ = $2; }
        ;

variable_function:
        '(' variable_ptr ')' '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $2->addParamList( $6 ); }
        | '(' variable_function ')'                     /* redundant parenthesis */
                { $$ = $2; }
        ;

/* This pattern parses a function declarator that is not redefining a typedef name. Because functions cannot
   be nested, there is no context where a function definition can redefine a typedef name. To allow nested
   functions requires further separation of variable and function declarators in typedef_redeclarator.  The
   pattern precludes returning arrays and functions versus pointers to arrays and functions. */

function_declarator:
        function_no_ptr attribute_list_opt
        | function_ptr
        | function_array attribute_list_opt
        ;

function_no_ptr:
        paren_identifier '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $1->addParamList( $4 ); }
        | '(' function_ptr ')' '(' push parameter_type_list_opt pop ')'
                { $$ = $2->addParamList( $6 ); }
        | '(' function_no_ptr ')'                       /* redundant parenthesis */
                { $$ = $2; }
        ;

function_ptr:
        '*' function_declarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0, $1.filename, $1.lineno ) ); }
        | '*' type_qualifier_list function_declarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2, $1.filename, $1.lineno ) ); }
        | '(' function_ptr ')'
                { $$ = $2; }
        ;

function_array:
        '(' function_ptr ')' array_dimension
                { $$ = $2->addArray( $4 ); }
        | '(' function_array ')' multi_array_dimension  /* redundant parenthesis */
                { $$ = $2->addArray( $4 ); }
        | '(' function_array ')'                        /* redundant parenthesis */
                { $$ = $2; }
        ;

/* This pattern parses an old-style K&R function declarator (OBSOLESCENT, see 4) that is not redefining a
   typedef name (see function_declarator for additional comments). The pattern precludes returning arrays and
   functions versus pointers to arrays and functions. */

old_function_declarator:
        old_function_no_ptr
        | old_function_ptr
        | old_function_array
        ;

old_function_no_ptr:
        paren_identifier '(' identifier_list ')'        /* function_declarator handles empty parameter */
                { $$ = $1->addIdList( $3 ); }
        | '(' old_function_ptr ')' '(' identifier_list ')'
                { $$ = $2->addIdList( $5 ); }
        | '(' old_function_no_ptr ')'                   /* redundant parenthesis */
                { $$ = $2; }
        ;

old_function_ptr:
        '*' old_function_declarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0, $1.filename, $1.lineno ) ); }
        | '*' type_qualifier_list old_function_declarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2, $1.filename, $1.lineno ) ); }
        | '(' old_function_ptr ')'
                { $$ = $2; }
        ;

old_function_array:
        '(' old_function_ptr ')' array_dimension
                { $$ = $2->addArray( $4 ); }
        | '(' old_function_array ')' multi_array_dimension /* redundant parenthesis */
                { $$ = $2->addArray( $4 ); }
        | '(' old_function_array ')'                    /* redundant parenthesis */
                { $$ = $2; }
        ;

/* This pattern parses a declaration for a variable or function prototype that redefines a typedef name, e.g.:

        typedef int foo;
        {
           int foo; // redefine typedef name in new scope
        }

   The pattern precludes declaring an array of functions versus a pointer to an array of functions, and
   returning arrays and functions versus pointers to arrays and functions. */

typedef_redeclarator:
        paren_typedef attribute_list_opt
        | typedef_ptr
        | typedef_array attribute_list_opt
        | typedef_function attribute_list_opt
        ;

paren_typedef:
        TYPEDEFname
                {
                typedefTable.setNextIdentifier( *($1.str) );
                $$ = DeclarationNode::newName( $1 );
                }
        | '(' paren_typedef ')'
                { $$ = $2; }
        ;

typedef_ptr:
        '*' typedef_redeclarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0, $1.filename, $1.lineno ) ); }
        | '*' type_qualifier_list typedef_redeclarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2, $1.filename, $1.lineno ) ); }
        | '(' typedef_ptr ')'
                { $$ = $2; }
        ;

typedef_array:
        paren_typedef array_dimension
                { $$ = $1->addArray( $2 ); }
        | '(' typedef_ptr ')' array_dimension
                { $$ = $2->addArray( $4 ); }
        | '(' typedef_array ')' multi_array_dimension   /* redundant parenthesis */
                { $$ = $2->addArray( $4 ); }
        | '(' typedef_array ')'                         /* redundant parenthesis */
                { $$ = $2; }
        ;

typedef_function:
        paren_typedef '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $1->addParamList( $4 ); }
        | '(' typedef_ptr ')' '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $2->addParamList( $6 ); }
        | '(' typedef_function ')'                      /* redundant parenthesis */
                { $$ = $2; }
        ;

/* This pattern parses a declaration for a parameter variable or function prototype that is not redefining a
   typedef name and allows the ANSI99 array options, which can only appear in a parameter list.  The pattern
   precludes declaring an array of functions versus a pointer to an array of functions, and returning arrays
   and functions versus pointers to arrays and functions. */

identifier_parameter_declarator:
        paren_identifier attribute_list_opt
        | identifier_parameter_ptr
        | identifier_parameter_array attribute_list_opt
        | identifier_parameter_function attribute_list_opt
        ;

identifier_parameter_ptr:
        '*' identifier_parameter_declarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0, $1.filename, $1.lineno ) ); }
        | '*' type_qualifier_list identifier_parameter_declarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2, $1.filename, $1.lineno ) ); }
        | '(' identifier_parameter_ptr ')'
                { $$ = $2; }
        ;

identifier_parameter_array:
        paren_identifier array_parameter_dimension
                { $$ = $1->addArray( $2 ); }
        | '(' identifier_parameter_ptr ')' array_dimension
                { $$ = $2->addArray( $4 ); }
        | '(' identifier_parameter_array ')' multi_array_dimension /* redundant parenthesis */
                { $$ = $2->addArray( $4 ); }
        | '(' identifier_parameter_array ')'            /* redundant parenthesis */
                { $$ = $2; }
        ;

identifier_parameter_function:
        paren_identifier '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $1->addParamList( $4 ); }
        | '(' identifier_parameter_ptr ')' '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $2->addParamList( $6 ); }
        | '(' identifier_parameter_function ')'         /* redundant parenthesis */
                { $$ = $2; }
        ;

/* This pattern parses a declaration for a parameter variable or function prototype that is redefining a
   typedef name, e.g.:

        typedef int foo;
        int f( int foo ); // redefine typedef name in new scope

   and allows the ANSI99 array options, which can only appear in a parameter list.  In addition, the pattern
   handles the special meaning of parenthesis around a typedef name:

        ISO/IEC 9899:1999 Section 6.7.5.3(11) : "In a parameter declaration, a single typedef name in
        parentheses is taken to be an abstract declarator that specifies a function with a single parameter,
        not as redundant parentheses around the identifier."

   which precludes the following cases:

        typedef float T;
        int f( int ( T [5] ) );                 // see abstract_parameter_declarator
        int g( int ( T ( int ) ) );             // see abstract_parameter_declarator
        int f( int f1( T a[5] ) );              // see identifier_parameter_declarator
        int g( int g1( T g2( int p ) ) );       // see identifier_parameter_declarator

   In essence, a '(' immediately to the left of typedef name, T, is interpreted as starting a parameter type
   list, and not as redundant parentheses around a redeclaration of T. Finally, the pattern also precludes
   declaring an array of functions versus a pointer to an array of functions, and returning arrays and
   functions versus pointers to arrays and functions. */

typedef_parameter_redeclarator:
        typedef attribute_list_opt
        | typedef_parameter_ptr
        | typedef_parameter_array attribute_list_opt
        | typedef_parameter_function attribute_list_opt
        ;

typedef:
        TYPEDEFname
                {
                    typedefTable.setNextIdentifier( *($1.str) );
                    $$ = DeclarationNode::newName( $1 );
                }
        ;

typedef_parameter_ptr:
        '*' typedef_parameter_redeclarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0, $1.filename, $1.lineno ) ); }
        | '*' type_qualifier_list typedef_parameter_redeclarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2, $1.filename, $1.lineno ) ); }
        | '(' typedef_parameter_ptr ')'
                { $$ = $2; }
        ;

typedef_parameter_array:
        typedef array_parameter_dimension
                { $$ = $1->addArray( $2 ); }
        | '(' typedef_parameter_ptr ')' array_parameter_dimension
                { $$ = $2->addArray( $4 ); }
        ;

typedef_parameter_function:
        typedef '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $1->addParamList( $4 ); }
        | '(' typedef_parameter_ptr ')' '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $2->addParamList( $6 ); }
        ;

/* This pattern parses a declaration of an abstract variable or function prototype, i.e., there is no
   identifier to which the type applies, e.g.:

        sizeof( int );
        sizeof( int [10] );

   The pattern precludes declaring an array of functions versus a pointer to an array of functions, and
   returning arrays and functions versus pointers to arrays and functions. */

abstract_declarator:
        abstract_ptr
        | abstract_array attribute_list_opt
        | abstract_function attribute_list_opt
        ;

abstract_ptr:
        '*'
                { $$ = DeclarationNode::newPointer( 0, $1.filename, $1.lineno ); }
        | '*' type_qualifier_list
                { $$ = DeclarationNode::newPointer( $2, $1.filename, $1.lineno ); }
        | '*' abstract_declarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0, $1.filename, $1.lineno ) ); }
        | '*' type_qualifier_list abstract_declarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2, $1.filename, $1.lineno ) ); }
        | '(' abstract_ptr ')'
                { $$ = $2; }
        ;

abstract_array:
        array_dimension
        | '(' abstract_ptr ')' array_dimension
                { $$ = $2->addArray( $4 ); }
        | '(' abstract_array ')' multi_array_dimension  /* redundant parenthesis */
                { $$ = $2->addArray( $4 ); }
        | '(' abstract_array ')'                        /* redundant parenthesis */
                { $$ = $2; }
        ;

abstract_function:
        '(' push parameter_type_list_opt pop ')'        /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = DeclarationNode::newFunction( 0, 0, $3, 0 ); }
        | '(' abstract_ptr ')' '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $2->addParamList( $6 ); }
        | '(' abstract_function ')'                     /* redundant parenthesis */
                { $$ = $2; }
        ;

array_dimension:
                /* Only the first dimension can be empty. */
        '[' push pop ']'
                { $$ = DeclarationNode::newArray( 0, 0, false ); }
        | '[' push pop ']' multi_array_dimension
                { $$ = DeclarationNode::newArray( 0, 0, false )->addArray( $5 ); }
        | multi_array_dimension
        ;

multi_array_dimension:
        '[' push assignment_expression pop ']'
                { $$ = DeclarationNode::newArray( $3, 0, false ); }
        | '[' push '*' pop ']'                          /* ANSI99 */
                { $$ = DeclarationNode::newVarArray( 0 ); }
        | multi_array_dimension '[' push assignment_expression pop ']'
                { $$ = $1->addArray( DeclarationNode::newArray( $4, 0, false ) ); }
        | multi_array_dimension '[' push '*' pop ']'    /* ANSI99 */
                { $$ = $1->addArray( DeclarationNode::newVarArray( 0 ) ); }
        ;

/* This pattern parses a declaration of a parameter abstract variable or function prototype, i.e., there is no
   identifier to which the type applies, e.g.:

        int f( int );           // abstract variable parameter; no parameter name specified
        int f( int (int) );     // abstract function-prototype parameter; no parameter name specified

   The pattern precludes declaring an array of functions versus a pointer to an array of functions, and
   returning arrays and functions versus pointers to arrays and functions. */

abstract_parameter_declarator:
        abstract_parameter_ptr
        | abstract_parameter_array attribute_list_opt
        | abstract_parameter_function attribute_list_opt
        ;

abstract_parameter_ptr:
        '*'
                { $$ = DeclarationNode::newPointer( 0 ); }
        | '*' type_qualifier_list
                { $$ = DeclarationNode::newPointer( $2 ); }
        | '*' abstract_parameter_declarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0 ) ); }
        | '*' type_qualifier_list abstract_parameter_declarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2 ) ); }
        | '(' abstract_parameter_ptr ')'
                { $$ = $2; }
        ;

abstract_parameter_array:
        array_parameter_dimension
        | '(' abstract_parameter_ptr ')' array_parameter_dimension
                { $$ = $2->addArray( $4 ); }
        | '(' abstract_parameter_array ')' multi_array_dimension /* redundant parenthesis */
                { $$ = $2->addArray( $4 ); }
        | '(' abstract_parameter_array ')'              /* redundant parenthesis */
                { $$ = $2; }
        ;

abstract_parameter_function:
        '(' push parameter_type_list_opt pop ')'        /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = DeclarationNode::newFunction( 0, 0, $3, 0 ); }
        | '(' abstract_parameter_ptr ')' '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $2->addParamList( $6 ); }
        | '(' abstract_parameter_function ')'           /* redundant parenthesis */
                { $$ = $2; }
        ;

array_parameter_dimension:
                /* Only the first dimension can be empty or have qualifiers. */
        array_parameter_1st_dimension
        | array_parameter_1st_dimension multi_array_dimension
                { $$ = $1->addArray( $2 ); }
        | multi_array_dimension
        ;

/* The declaration of an array parameter has additional syntax over arrays in normal variable declarations:

        ISO/IEC 9899:1999 Section 6.7.5.2(1) : "The optional type qualifiers and the keyword static shall
        appear only in a declaration of a function parameter with an array type, and then only in the
        outermost array type derivation."
   */

array_parameter_1st_dimension:
        '[' push pop ']'
                { $$ = DeclarationNode::newArray( 0, 0, false ); }
        | '[' push type_qualifier_list '*' pop ']'      /* remaining ANSI99 */
                { $$ = DeclarationNode::newVarArray( $3 ); }
        | '[' push type_qualifier_list assignment_expression pop ']'
                { $$ = DeclarationNode::newArray( $4, $3, false ); }
        | '[' push STATIC assignment_expression pop ']'
                { $$ = DeclarationNode::newArray( $4, 0, true ); }
        | '[' push STATIC type_qualifier_list assignment_expression pop ']'
                { $$ = DeclarationNode::newArray( $5, $4, true ); }
        ;

/* This pattern parses a declaration of an abstract variable, i.e., there is no identifier to which the type
   applies, e.g.:

        sizeof( int ); // abstract variable; no identifier name specified

   The pattern precludes declaring an array of functions versus a pointer to an array of functions, and
   returning arrays and functions versus pointers to arrays and functions. */

variable_abstract_declarator:
        variable_abstract_ptr
        | variable_abstract_array attribute_list_opt
        | variable_abstract_function attribute_list_opt
        ;

variable_abstract_ptr:
        '*'
                { $$ = DeclarationNode::newPointer( 0 ); }
        | '*' type_qualifier_list
                { $$ = DeclarationNode::newPointer( $2 ); }
        | '*' variable_abstract_declarator
                { $$ = $2->addPointer( DeclarationNode::newPointer( 0 ) ); }
        | '*' type_qualifier_list variable_abstract_declarator
                { $$ = $3->addPointer( DeclarationNode::newPointer( $2 ) ); }
        | '(' variable_abstract_ptr ')'
                { $$ = $2; }
        ;

variable_abstract_array:
        array_dimension
        | '(' variable_abstract_ptr ')' array_dimension
                { $$ = $2->addArray( $4 ); }
        | '(' variable_abstract_array ')' multi_array_dimension /* redundant parenthesis */
                { $$ = $2->addArray( $4 ); }
        | '(' variable_abstract_array ')'               /* redundant parenthesis */
                { $$ = $2; }
        ;

variable_abstract_function:
        '(' variable_abstract_ptr ')' '(' push parameter_type_list_opt pop ')' /* empty parameter list OBSOLESCENT (see 3) */
                { $$ = $2->addParamList( $6 ); }
        | '(' variable_abstract_function ')'            /* redundant parenthesis */
                { $$ = $2; }
        ;

/* This pattern parses a new-style declaration for a parameter variable or function prototype that is either
   an identifier or typedef name and allows the ANSI99 array options, which can only appear in a parameter
   list. */

new_identifier_parameter_declarator_tuple:              /* CFA */
        new_identifier_parameter_declarator_no_tuple
        | new_abstract_tuple
        | type_qualifier_list new_abstract_tuple
                { $$ = $2->addQualifiers( $1 ); }
        ;

new_identifier_parameter_declarator_no_tuple:           /* CFA */
        new_identifier_parameter_ptr
        | new_identifier_parameter_array
        ;

new_identifier_parameter_ptr:                           /* CFA */
        '*' type_specifier
                { $$ = $2->addNewPointer( DeclarationNode::newPointer( 0 ) ); }
        | type_qualifier_list '*' type_specifier
                { $$ = $3->addNewPointer( DeclarationNode::newPointer( $1 ) ); }
        | '*' new_abstract_function
                { $$ = $2->addNewPointer( DeclarationNode::newPointer( 0 ) ); }
        | type_qualifier_list '*' new_abstract_function
                { $$ = $3->addNewPointer( DeclarationNode::newPointer( $1 ) ); }
        | '*' new_identifier_parameter_declarator_tuple
                { $$ = $2->addNewPointer( DeclarationNode::newPointer( 0 ) ); }
        | type_qualifier_list '*' new_identifier_parameter_declarator_tuple
                { $$ = $3->addNewPointer( DeclarationNode::newPointer( $1 ) ); }
        ;

new_identifier_parameter_array:                         /* CFA */
                /* Only the first dimension can be empty or have qualifiers. Empty dimension must be factored
                   out due to shift/reduce conflict with new-style empty (void) function return type. */
        '[' push pop ']' type_specifier
                { $$ = $5->addNewArray( DeclarationNode::newArray( 0, 0, false ) ); }
        | new_array_parameter_1st_dimension type_specifier
                { $$ = $2->addNewArray( $1 ); }
        | '[' push pop ']' multi_array_dimension type_specifier
                { $$ = $6->addNewArray( $5 )->addNewArray( DeclarationNode::newArray( 0, 0, false ) ); }
        | new_array_parameter_1st_dimension multi_array_dimension type_specifier
                { $$ = $3->addNewArray( $2 )->addNewArray( $1 ); }
        | multi_array_dimension type_specifier
                { $$ = $2->addNewArray( $1 ); }
        | '[' push pop ']' new_identifier_parameter_ptr
                { $$ = $5->addNewArray( DeclarationNode::newArray( 0, 0, false ) ); }
        | new_array_parameter_1st_dimension new_identifier_parameter_ptr
                { $$ = $2->addNewArray( $1 ); }
        | '[' push pop ']' multi_array_dimension new_identifier_parameter_ptr
                { $$ = $6->addNewArray( $5 )->addNewArray( DeclarationNode::newArray( 0, 0, false ) ); }
        | new_array_parameter_1st_dimension multi_array_dimension new_identifier_parameter_ptr
                { $$ = $3->addNewArray( $2 )->addNewArray( $1 ); }
        | multi_array_dimension new_identifier_parameter_ptr
                { $$ = $2->addNewArray( $1 ); }
        ;

new_array_parameter_1st_dimension:
        '[' push type_qualifier_list '*' pop ']'        /* remaining ANSI99 */
                { $$ = DeclarationNode::newVarArray( $3 ); }
        | '[' push type_qualifier_list assignment_expression pop ']'
                { $$ = DeclarationNode::newArray( $4, $3, false ); }
        | '[' push declaration_qualifier_list assignment_expression pop ']'
                /* declaration_qualifier_list must be used because of shift/reduce conflict with
                   assignment_expression, so a semantic check is necessary to preclude them as a
                   type_qualifier cannot appear in this context. */
                { $$ = DeclarationNode::newArray( $4, $3, true ); }
        | '[' push declaration_qualifier_list type_qualifier_list assignment_expression pop ']'
                { $$ = DeclarationNode::newArray( $5, $4->addQualifiers( $3 ), true ); }
        ;

/* This pattern parses a new-style declaration of an abstract variable or function prototype, i.e., there is
   no identifier to which the type applies, e.g.:

        [int] f( int );         // abstract variable parameter; no parameter name specified
        [int] f( [int] (int) ); // abstract function-prototype parameter; no parameter name specified

   These rules need LR(3):

        new_abstract_tuple identifier_or_typedef_name
        '[' new_parameter_list ']' identifier_or_typedef_name '(' new_parameter_type_list_opt ')'

   since a function return type can be syntactically identical to a tuple type:

        [int, int] t;
        [int, int] f( int );

   Therefore, it is necessary to look at the token after identifier_or_typedef_name to know when to reduce
   new_abstract_tuple. To make this LR(1), several rules have to be flattened (lengthened) to allow
   the necessary lookahead. To accomplish this, new_abstract_declarator has an entry point without tuple, and
   tuple declarations are duplicated when appearing with new_function_specifier. */

new_abstract_declarator_tuple:                          /* CFA */
        new_abstract_tuple
        | type_qualifier_list new_abstract_tuple
                { $$ = $2->addQualifiers( $1 ); }
        | new_abstract_declarator_no_tuple
        ;

new_abstract_declarator_no_tuple:                       /* CFA */
        new_abstract_ptr
        | new_abstract_array
        ;

new_abstract_ptr:                                       /* CFA */
        '*' type_specifier
                { $$ = $2->addNewPointer( DeclarationNode::newPointer( 0 ) ); }
        | type_qualifier_list '*' type_specifier
                { $$ = $3->addNewPointer( DeclarationNode::newPointer( $1 ) ); }
        | '*' new_abstract_function
                { $$ = $2->addNewPointer( DeclarationNode::newPointer( 0 ) ); }
        | type_qualifier_list '*' new_abstract_function
                { $$ = $3->addNewPointer( DeclarationNode::newPointer( $1 ) ); }
        | '*' new_abstract_declarator_tuple
                { $$ = $2->addNewPointer( DeclarationNode::newPointer( 0 ) ); }
        | type_qualifier_list '*' new_abstract_declarator_tuple
                { $$ = $3->addNewPointer( DeclarationNode::newPointer( $1 ) ); }
        ;

new_abstract_array:                                     /* CFA */
                /* Only the first dimension can be empty. Empty dimension must be factored out due to
                   shift/reduce conflict with empty (void) function return type. */
        '[' push pop ']' type_specifier
                { $$ = $5->addNewArray( DeclarationNode::newArray( 0, 0, false ) ); }
        | '[' push pop ']' multi_array_dimension type_specifier
                { $$ = $6->addNewArray( $5 )->addNewArray( DeclarationNode::newArray( 0, 0, false ) ); }
        | multi_array_dimension type_specifier
                { $$ = $2->addNewArray( $1 ); }
        | '[' push pop ']' new_abstract_ptr
                { $$ = $5->addNewArray( DeclarationNode::newArray( 0, 0, false ) ) }
        | '[' push pop ']' multi_array_dimension new_abstract_ptr
                { $$ = $6->addNewArray( $5 )->addNewArray( DeclarationNode::newArray( 0, 0, false ) ); }
        | multi_array_dimension new_abstract_ptr
                { $$ = $2->addNewArray( $1 ); }
        ;

new_abstract_tuple:                                     /* CFA */
        '[' push new_abstract_parameter_list pop ']'
                { $$ = DeclarationNode::newTuple( $3 ); }
        ;

new_abstract_function:                                  /* CFA */
        '[' push pop ']' '(' new_parameter_type_list_opt ')'
                { $$ = DeclarationNode::newFunction( 0, DeclarationNode::newTuple( 0 ), $6, 0 ); }
        | new_abstract_tuple '(' push new_parameter_type_list_opt pop ')'
                { $$ = DeclarationNode::newFunction( 0, $1, $4, 0 ); }
        | new_function_return '(' push new_parameter_type_list_opt pop ')'
                { $$ = DeclarationNode::newFunction( 0, $1, $4, 0 ); }
        ;

/* 1) ISO/IEC 9899:1999 Section 6.7.2(2) : "At least one type specifier shall be given in the declaration
      specifiers in each declaration, and in the specifier-qualifier list in each structure declaration and
      type name."

   2) ISO/IEC 9899:1999 Section 6.11.5(1) : "The placement of a storage-class specifier other than at the
      beginning of the declaration specifiers in a declaration is an obsolescent feature."

   3) ISO/IEC 9899:1999 Section 6.11.6(1) : "The use of function declarators with empty parentheses (not
      prototype-format parameter type declarators) is an obsolescent feature."

   4) ISO/IEC 9899:1999 Section 6.11.7(1) : "The use of function definitions with separate parameter
      identifier and declaration lists (not prototype-format parameter type and identifier declarators) is
      an obsolescent feature."  */

/************************* MISCELLANEOUS ********************************/

comma_opt:                                              /* redundant comma */
        /* empty */
        | ','
        ;

assignment_opt:
        /* empty */
                { $$ = 0; }
        | '=' assignment_expression
                { $$ = $2; }
        ;

%%
/* ----end of grammar----*/

void yyerror(char *string) {
    using std::cout;
    using std::endl;
    if( yyfilename ) {
      cout << yyfilename << ":" << endl;
    }
    cout << yylineno << ": syntax error reading token " << *(yylval.str) << endl;
}

/* Local Variables: */
/* fill-column: 110 */
/* compile-command: "gmake" */
/* End: */