---------------------------------------------------------------------------------------
                                   specRTL Grammar
                                   ---------------

            We  provide a  context  free grammar  in  yacc format.  This
            grammar accomodates some additional structures that have not
            been  described  in  the  paper.  In  particular,  we  allow
            multiple  RTL  templates  to  be  provided  for  both  input
            templates and output templates of a pattern. The name of the
            base pattern that is being refined gets associated with each
            template. This  subsumes the simpler structure  described in
            the paper.

            Terminal symbols  are in  capital letter.  The non-terminals
            may consist  of multiple names  separated by "_";  the first
            letter of each name is capitalized.

            The conventional  MD patterns  (invluding C  code fragments)
            which are enclosed  in a pair of "{:" and  ":}" are detected
            by the scanner as a  single token called CMD_SPEC_BODY. They
            may include  multiple patterns or multiple  C code fragments
            that should appear together.

----------------------------------------------------------------------------------------
Pattern_List 
        : Pattern_List Pattern 
        | Pattern
        ;

Pattern : Abstract_Pattern
        | Concrete_Pattern
	| CMD_SPEC_BODY
        ;

Abstract_Pattern    
        : ABSTRACT Derived_Name Abstract_Rtl_Spec
        ;

Concrete_Pattern    
        : CONCRETE Qualified_Derived_Name  Concrete_Rtl_Spec
        | CONCRETE '.' PEEPHOLE2 Concrete_Rtl_Spec_List_In Concrete_Rtl_Spec_List_Out
        | CONCRETE Qualified_Split_Name Concrete_Rtl_Spec_List_In Concrete_Rtl_Spec_List_Out
        ;

Abstract_Rtl_Spec
        : EXTENDS Base_Name '{' Abstract_Extend_Body '}'
        | OVERRIDES Base_Name '{' Abstract_Override_Body '}'
        ;

Concrete_Rtl_Spec
        : INSTANTIATES Named_Concrete_Instantiate_Body
        | OVERRIDES Named_Concrete_Override_Body
        ;

Concrete_Rtl_Spec_In
        : INSTANTIATES '.' IN Named_Concrete_Instantiate_Body 
        | OVERRIDES '.' IN Named_Concrete_Override_Body 
	| CMD_SPEC '.' IN CMD_SPEC_BODY
        ;

Concrete_Rtl_Spec_Out
        : INSTANTIATES '.' OUT Named_Concrete_Instantiate_Body 
        | OVERRIDES '.' OUT Named_Concrete_Override_Body 
	| CMD_SPEC '.' OUT CMD_SPEC_BODY
        ;

Concrete_Rtl_Spec_List_Out
        : Concrete_Rtl_Spec_List_Out Concrete_Rtl_Spec_Out
        | Concrete_Rtl_Spec_Out
        ;

Concrete_Rtl_Spec_List_In
        : Concrete_Rtl_Spec_List_In Concrete_Rtl_Spec_In
        | Concrete_Rtl_Spec_In
        ;

Named_Concrete_Instantiate_Body
        : Qualified_Base_Name '{' Concrete_Instantiate_Body '}'
        ;

Named_Concrete_Override_Body
        : Qualified_Base_Name '{' Concrete_Override_Body '}'
        ;

Derived_Name        
        : Derived_Name '<' ID '>'
        | Derived_Name '<' ID '>' ID  
        | Derived_Name '<' ID '>' NUMBER 
        | Derived_Name '<' ID '>' NUMBER ID
        | ID  
        ; 

Base_Name        
        : Derived_Name        
        | RTLOP
        ;

Qualified_Derived_Name 
        : Derived_Name 
        | Derived_Name '.' Qualifier
        ;

Qualified_Base_Name 
        : Base_Name
        | Base_Name '.' Qualifier
        ;

Qualifier
        : INSN
        | EXPAND
        ;

Qualified_Split_Name 
        : Derived_Name '.' INSN_AND_SPLIT        
        | '.' SPLIT
        ;

Concrete_Instantiate_Body        
        : ID '(' Operands ')' ';' Concrete_Stmt_List  
                                                          /* Check if the first ID is a predefined operator. Further 
                                                             this order is important. If there is an instantiation, 
                                                             it better be the very first statement. */
        | RTLOP '(' Operands ')' ';' Concrete_Stmt_List  
                                                           /* This order is important.  If there is an instantiation, 
                                                              it better be the very first statement. */
        | Concrete_Stmt_List
        ;

Concrete_Override_Body        
        : ID MODE_MODIFIER ID ';' Concrete_Stmt_List
        | Concrete_Stmt_List
        ;

Concrete_Stmt_List 
        : Concrete_Stmt_List  Concrete_Stmt
        | /* Empty concrete body allowed */        
        ;

Concrete_Stmt 
        : ROOT Operand_Access ASSIGN Operand ';'             /* Set the value of a leaf node as an operand */ 
        | ALLCONSTRAINTS ASSIGN '(' Constraint_List ')' ';'           
        | ALLPREDICATES ASSIGN '(' Predicate_List ')' ';'                   
        | Common_Stmt
        ;

Operand_Access         
        : Operand_Access '.' NUMBER 
        | '.' NUMBER         
        ;     

Operands        
        : Operands ',' Operand 
        | Operand 
        ;

Operand                
        : PREDICATE ':' ID ':' CONSTRAINT
                                                      /* Check if the first operand is a predefined predicate 
                                                         (including null), second ID is a mode  */
        | ID ':' ID ':' CONSTRAINT 
                                                      /* Check if the first operand is a userdefined predicate 
                                                         (including null), second ID is a mode  */
        | '<' PREDICATE '>' ':' ID  ':' CONSTRAINT    /* Satisfies match_operand variations */ 
        | '<' ID '>' ':' ID  ':' CONSTRAINT           /* Satisfies match_operand variations */ 
        | DUPLICATE NUMBER                            /* Corresponds to match_dup */
        | ID ':' CONSTRAINT                           /* Corresponds to match_scratch */
        | NUMBER
        | Fixed_Reg_or_Const                          /* For register,memory,constant etc operands */
        ;

Fixed_Reg_or_Const
        : ID '(' ID ':' ID ')'                        /* First ID should be reg. Corresponds to the register operand */
        | ID                                          /* Should be FLAGS_REG,scratch, cc0 or pc */
        | ID ':' NUMBER                               /* First ID should be constant specifier */ 
        | ID ':' NUMBER  ':' ID                       /* First ID should be constant specifier */
        ;

Abstract_Extend_Body 
        : Abstract_Extend_Body Abstract_Stmt
        | Abstract_Stmt
        ;

Abstract_Override_Body 
        : Abstract_Override_Body Common_Stmt
        | Common_Stmt
        ;

Abstract_Stmt 
        : ROOT Operand_Access ASSIGN RTLOP ';'        /* Access a node and extend using an operator */
        | ROOT Operand_Access ASSIGN ID ';'           /* Access a node and extend using an abstract 
                                                         pattern predefined */
        | Common_Stmt
        ;

Common_Stmt     
        : ROOT Attr_Access ASSIGN ID ';'              /* change the value of an attribute of a node */
        | ROOT Attr_Access ASSIGN PREDICATE ';'
        | ROOT Attr_Access ASSIGN CONSTRAINT ';'
        ;

Predicate_List  
        : Predicate_List ',' PREDICATE                /* Since predicates are predefined, they can be 
                                                         passed as tokens */
        | PREDICATE
        | Predicate_List ',' ID                       /* Since predicates are predefined, they can be 
                                                         passed as tokens */
        | ID
         ;

Constraint_List 
        : Constraint_List ',' CONSTRAINT 
        | CONSTRAINT
        ;

Attr_Access        
        : '.' ID                                       /* Change the attribute of a node */
        | Operand_Access '.' ID
        ;