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:

incomplete.sdf.sg.gif

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.

See also

getsortgraphGT