Saffron
August 31, 1988
Saffron
An Experimental Cedar Compiler
James Rauen
August 31, 1988
Why another Cedar compiler?
· Demonstrate the viability of Casaba
· Principled implementation
Easy to maintain
Easy to verify
· Experiments
What is Cedar?
· CLRM
· Mesa manual
· The implementation
· Religion
Saffron
· Front end of a compiler
· Implements Cedar/Mesa ± Religion
· Implemented in Casaba
Parser
· Concrete Grammar
154 nonterminals
475 productions
· Abstract Grammar
120 nonterminals
364 productions
Recursive Functions
· Applied to the abstract parse tree
· Build:
Context Tree
Type Graph
Program Graph
· Example
CompileFrameBlock:
TreeRecursiveFunction [Tree, TypeGraphNode.transferType, ContextTree.parent, ProgramGraph.arg, CompilerState]
Returns [ContextTree, ProgramFragment, ProgramGraph.res]
DamagedReps [ContextTree.parent, ProgramGraph.arg];
Context Tree
Mimics the block structure of a program
One node for each block/scope:
· Opened names
· Enabled signals
· Field List
· Exit List
· Dependency graph
· Parent context pointer
Type Graph
· Predefined types
· Constructed types
Pair: TYPE = RECORD [x: INT, y: INT];
u: LIST OF REAL;
DIRECTORY Foo: TYPE Bar USING [Baz];
· Runtime state
Program Graph
· Intermediate language
· Retains all type information
· Type checking
Environment
[Artwork node; type 'Artwork on' to command tool]
Into the Abyss
Tree: TYPE = REF TreeBody;
TreeBody: TYPE = RECORD [
nodeData: REF ANY,
children: LIST OF Tree
];
a: INT = b;
b: INT = 3;
Deeper and Deeper
Foo: TYPE = INT[k..k+FIRST[Bar] ];
Bar: TYPE = INT[FIRST[Foo]..10];
k: INT = LAST[Bar]
The Problem
· Sequential processing of declarations
EXCEPT FOR
· Named constants with compile-time values (but not runtime constants)
AND
· Constant properties of types
The Solution
Dependency Graph
Nodes for:
· Values of named constants
· Bodies of inline procedures
· Initialization expressions of types
· SIZE, FIRST, LAST properties of types
· Runtime state
Evaluate nodes in topological order
Reject if:
· Cyclic, or
· A supposedly constant type property depends on runtime state
Example
Foo: TYPE = INT[k..k+FIRST[Bar] ];
Bar: TYPE = INT[FIRST[Foo]..10];
k: INT = LAST[Bar]
[Artwork node; type 'Artwork on' to command tool]
Saffron Now
· Builds type graphs and context trees
· Dependency analysis
· Generates some intermediate code:
Initialization (declarations)
Expressions
Assignments
A few simple statements
Blocks
Transfer type values (procedures, ...)
Wrapping Up
· Cedar
· Casaba
· Acknowledgements
Howard Sturgis
Bill Jackson
Carl Hauser
Russ Atkinson
Peter Kessler