This is for projects who use propagation graphs, like the
propagation graph highlighting project.

The objects described in *.trv files are sentences of class
Traversal_graph = "Traversal" "directive" ":" ...
and *.trn files are sentences of class
Transportation_graph = "Traversal" "directive" ":" ...

The complete definitions are below.

// The class dictionaries which define the inputs to our tools are
// available with the following copyright notice:

//  Copyright (C) 1985-1993 Northeastern University.

//  Permission is granted to any individual or institution to use, copy, modify,
//  and distribute this class dictionary, provided that this complete copyright
//  and permission notice is maintained, intact, in all copies and supporting
//  documentation.



/////////////////////////////////////////////////////////////////////////////////////
// $Log: cd.cd,v $
//  Revision 5.4.1.4  1994/02/25  21:39:02  demeter
//  restriction checking
//
//  Revision 5.4.1.3  1994/02/24  20:52:21  demeter
//   reimplement object transportation -- cun
//
//  Revision 5.4.1.2  1994/02/22  14:45:22  demeter
//  update according to the new semantics
//
/////////////////////////////////////////////////////////////////////////////////////
Traversal_graph = "Traversal" "directive" ":"
		<traversal_directive> Propagation_directive_exp

		  "Propagation graph" "for" "traversal" ":"
	        <traversal_graph> Propagation_schema.


Transportation_graph = "Traversal" "directive" ":"
		<traversal_directive> Propagation_directive_exp
			"Transportation" "directive" ":"
		<transportation_directive> Propagation_directive_exp
			"Propagation" "graph" "for" "transportation" ":"
	        <transportation_graph> Propagation_schema.


Propagation_schema = [ "*source*" <source_port> Vertex_selector *l ]
                     [ "*target*" <target_port> Vertex_selector *l ]
                      + "*paths*" *l +  <paths> Cd_graph  - - *l.

Cd_graph     =    <adjacencies> Nlist(Adjacency)
                [ + "*terminal_sets*" <terminal_sets> Commalist(Vertex) "." - *l ] .

Adjacency    = < source > Vertex                                                        
               ["(" < parameters> Commalist(Vertex) ")"]                               
               < ns > Neighbors *l
               "." .                                                                    
Neighbors    : Neighbors_wc |  Repetit_n  *common*. 
Neighbors_wc : Construct_ns |  Alternat_ns                          
                  *common* *l + + + < construct_ns > List(Any_vertex) - - - .    
Construct_ns = "=".                                                        
Alternat_ns  = ":" [ *l + + + <alternat_ns> Barlist(Term) - - - ] <common> Common .    
Common       = + + + "*common*" - - - .

Repetit_n    = "~" [ <sandwiched> Sandwich(Kernel) ].                             
Kernel       = [ <nonempty> Term ]  "{" <repeated> Sandwich(Term) "}".

Any_vertex   : Opt_labeled_term  | Optional_term  | Syntax_vertex  | Inherit_term 
     *common*
   .


Vertex       =  < vertex_name > DemIdent.

Syntax_vertex :  Regular_syntax | Print_command *common*. 
Print_command :  Print_indent | Print_unindent | Print_skip | Print_space *common*.
Print_indent   = "+" .
Print_unindent = "-" .
Print_skip     = "*l" .
Print_space    = "*s" .

Regular_syntax  = < string > DemString .                                      
Opt_labeled_term :  Labeled | Regular
      *common*  [StaticSpec] [AccessorSpec] <vertex> Term. 

StaticSpec = "*static*" .
AccessorSpec : ReadOnlyAcc | PrivateAcc *common* .
ReadOnlyAcc = "*read-only*" .
PrivateAcc = "*private*" .

Regular          = .                                                                
Labeled          = "<" < label_name > DemIdent ">" .                                   
Inherit_term     = "*inherit*" <inherited> Commalist(Term). 
Term : Normal | CppTerm 
	*common* <vertex> Vertex 
		 <moduleRef> TermRef.
CppTerm = "$" .
Normal = .
TermRef : LocalRef | ModuleRef.
ModuleRef : CompRef | LibRef *common* <moduleName> DemIdent.
LocalRef = .
CompRef = "@".
LibRef  = "@@".
Optional_term = "[" <opt> Sandwich(Opt_labeled_term) "]".                  

////////////////////////////////////////////////////////////////////////
// propagation directive expressions
////////////////////////////////////////////////////////////////////////

Propagation_directive_exp : Pde | Dir_name_with_exp.

Dir_name_with_exp = <inst> DemIdent.

Pde                       =  "*from*" <source_port> Vertex_selector
                             [ <constraint> Path_constraint_exp ]
                             <via> List(Segment).

Segment                    =  <targets> Targets
                              [  <constraint> Path_constraint_exp ].

Targets                    =  <to_or_via> To_or_via
                              <targets> Vertex_selector .

To_or_via                 : To | Via | Tostop.

Via                       = "*via*".
To                        =  "*to*".
Tostop                    =  "*to-stop*".

Path_constraint_exp        : Require_through | Require_bypassing.
Require_through            =    <through>   Through_path_constraint 
                              [ <bypassing> Bypassing_path_constraint ].
Require_bypassing          =   <bypassing>  Bypassing_path_constraint 
                             [ <through>   Through_path_constraint ].
Through_path_constraint    = "*through*"   <through>   Commalist(Meta_edge).
Bypassing_path_constraint  = "*bypassing*" <bypassing> Commalist(Meta_edge).

Vertices_edges             :  Require_vertex_selector | Require_meta_edges.

Require_vertex_selector    = <vertices> Vertex_selector
                             [ <edges>  Meta_edges ].

Require_meta_edges         = <edges>  Meta_edges
                             [ <vertices> Vertex_selector ].

Meta_edges                 =  <edges> Commalist(Meta_edge).

Meta_edge                  : Meta_construction_edge | Meta_alternation_edge |
                             Meta_repetition_edge | Meta_inheritance_edge. 


Meta_construction_edge       = "->" <from>  Vertex_selector ","
                                    <edge_label> Label_selector ","
                                    <to> Vertex_selector .
Meta_alternation_edge        = "=>" <from> Vertex_selector ","
                                    <to> Vertex_selector  .
Meta_inheritance_edge        = ":>" <from> Vertex_selector ","
                                    <to> Vertex_selector .
Meta_repetition_edge         = "~>" <from> Vertex_selector ","
                                    <to> Vertex_selector .

Macro_exp                    = "*expand*" .


Vertex_selector            : Any_term | Fixed_term | Vertex_set.

Any_term                   =   "*".
Fixed_term                 = <vertex> Term.

Vertex_set                 : Vertex_set_sim | Vertex_set_comp | Class_set_inst | Late_selected_terms.

Vertex_set_sim             =  "{" <terms> Commalist(Fixed_term) "}" .

Vertex_set_comp            = <op> Vertex_set_op <arg1> Vertex_set <arg2> Vertex_set ")".

Vertex_set_op              : Union | Intersect.

Union                      = "(*union*".
Intersect                  = "(*intersect*".

Class_set_inst             = <name> Class_set_name.

Class_set_name     = "*class-set*" <name> DemIdent .


Late_selected_terms        = "(*class-set*" <pde> Propagation_directive_exp ")".

Label_selector             : Any_edge_label | Relation_meta_var | Label_set.
Label_set                  = "{" <labels> Commalist(Relation_meta_var) "}".
Any_edge_label             =   "*".
Relation_meta_var          = <name> DemIdent.

/////////////////////////////////////////////////////////////////////////////////
// parameterized classes
/////////////////////////////////////////////////////////////////////////////////
List(S) ~ {S}.                                                             
Nlist(S) ~ S { *l S} *l .                                                          
Barlist(S) ~ S {"|" *l  S}.                                                   
Commalist(S) ~ S {"," S}.
Amplist(S) ~ S { *l  S } .                                                 
Sandwich(S) =                                                              
  <first> List(Syntax_vertex) <inner> S                                    
  <second> List(Syntax_vertex)                                             
  .