Sort Graph
Program-Transformation.Org: The Program Transformation Wiki
Description
Sort graphs are graphs that represent the dependencies between sorts in a grammar.
Visual clues
The following example sort graph provides a legend for the interpretation of sort graphs:
It was generated from http://www.cwi.nl/~jvisser/incomplete.sdf.
In other words:
Bottom sorts: Dotted outline
Nondeclared top sorts: Dashed outline
Declared sorts: Box shape
Declared top sorts: Bold outline, box shape
Nondeclared sorts: Eliptic shape
Terminology
- _Sort_
- In SDF grammars, non-terminals are called sorts. Used sort: A sort that occurs in the left-hand side of an SDF production. Defined sort: A sort that occurs in the right-hand side of and SDF production. Declared sort: A sort that occurs in a sorts section. Bottom sort: A sort that has been used but not defined. Top sort: A sort that has been defined, but not used.