MyCasabaDoc.tioga
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Bill Jackson (bj) May 27, 1987 0:05:09 am PDT
James Rauen, June 10, 1988 11:43:17 am PDT
Last edited by: James Rauen July 10, 1988 11:24:59 am PDT
ThreeCasabaFour
CEDAR 7.0 — FOR INTERNAL XEROX USE ONLY
ThreeCasabaFour
A recursive fcn based compiler-compiler
Howard Sturgis
© Copyright 1988 Xerox Corporation. All rights reserved.
Abstract: ThreeC4 is a component of the more general Casaba package.
Created by: Howard Sturgis, John Field, Victor Shoup
Maintained by: Bill Jackson <BJackson.pa>
Keywords: compiler-compiler, Casaba, parsing, recurive functions
XEROX   Xerox Corporation
    Palo Alto Research Center
    3333 Coyote Hill Road
    Palo Alto, California 94304

For Internal Xerox Use Only
The Casaba Language:
Keywords:
AbstractProduction
AbstractType
BaseFunction
BaseType
Begin
Build
Builds
CedarEnumType
CedarFunction
CedarType
Control
DamagedReps
else
End
EnumeratedBaseType
for
From
GenericToken
if
in
Include
let
Module
NonTerminal
Returns
SharedReps
SimpleTokens
SourceLength
SourcePosition
then
TreeRecursiveFunction
where
2. Structure of a Casaba program
Concrete Grammar
The concrete grammar is a context free grammar which describes the syntax of the source language. It describes how to build the abstract parse tree while a source program is being parsed.
The terminal grammar symbols are divided into two categories: simple and generic. Simple terminals (such as keywords and operators) are collectively declared as SimpleTokens. Generic terminals (such as numbers and strings) are declared individually, each as a GenericToken.
Each nonterminal grammar symbol is declared as a NonTerminal. This declaration is followed by a Builds clause which indicates what abstract type (a node in the abstract parse tree) is created to represent the nonterminal. This clause is followed by a list of for <production> Build <bar> clauses, one for each of the nonterminal's productions.
Abstract Grammar
The abstract grammar describes the structure of abstract parse trees.
The terminal symbols are the same as those in the concrete grammar.
Each nonterminal in the abstract grammar describes a type of node in the abstract parse tree. It is declared with an AbstractType declaration. This declaration also indicates which tree-recursive functions can be applied to nodes of this type. The productions for each abstract type are defined with AbstractProduction declarations.
Recursive Functions
These are functions which can operate on certain kinds of nodes in the abstract parse tree.
Each function is declared as a TreeRecursiveFunction. The declaration indicates what types of arguments the function takes, what types of values it returns, and which of its arguments it damages. If a particular type is used more than once among the arguments and return values, then the different occurrences are distinguished by appending identifiers to each occurrence.
Each function is implemented with a set of methods. One method is defined for each kind of node in the abstract parse tree (i.e., each abstract production) that the function can act on.
Here is an example for the abstract production ModuleP.def, which has two methods declared for it. One method is for the MakeEnvironment function; the other is for the Explore function.
for ModuleP.def: AbstractProduction [ Directory, IdentList, Cedar, DefHead, DefBody ]
let MakeEnvironment [tree, fileName, env] ← <env2, interface>
where env2 ← AddInterfaceToEnvironment [env1, fileName, interface]
where interface ← CreateInterfaceFromContextTree [contextTree, nameSequence]
where contextTree ← MakeContextTree [DefBody, contextRib, paintRecords]
where contextRib ← FreezeLocalContext [localContext]
where paintRecords ← True []
where nameSequence ← MakeNameSequence [IdentList]
where <localContext, env1> ← ProcessDirectoryClause [Directory, rootContext, env]
where rootContext ← CreateEmptyContext [RootContextRib []]
let Explore [tree, fileName, env] ← <env2, interface>
where env2 ← AddInterfaceToEnvironment [env1, fileName, interface]
where interface ← CreateInterfaceFromContextTree [ct, EmptyNameSequence[]]
where ct ← EmptyContextTree [ RootContextRib []]
where env1 ← ExploreDirectoryClause [Directory, env]
;
Primitive Functions
Each primitive function is declared as a BaseFunction. It must be implemented separately.
Primitive Types
Each primitive type is declared as a BaseType. It must be implemented separately.
3. Primitives
Implementing a BaseType
Consider a base type named Bar, declared within a module named Foo. The declaration has the following form:
Foo: Module = Begin
...
Bar: BaseType;
...
End.
Casaba translates this into a Cedar opaque type declaration in the file FooDef.Mesa. It looks like this:
BarNode: TYPE = REF BarNodeBody;
BarNodeBody: TYPE;
Implement the type in a program module which exports the definitions file FooDef.
DIRECTORY
FooDef USING [BarNode];
Baz: CEDAR PROGRAM EXPORTS FooDef = BEGIN
...
BarNode: TYPE = FooDef.BarNode;
BarNodeBody: PUBLIC TYPE = whatever;
...
END.