Rigi RSFSpecification

Program-Transformation.Org: The Program Transformation Wiki
The original specification was posted in the Rigi mailing list (now defunct): http://www.rigi.csc.uvic.ca/list-archives/rigi-developer-archive/2000-02-10-15.26.16-19165

---------- Forwarded message ----------
Date: Thu, 19 Aug 1999 11:58:34 -0700 (PDT)
From: Johannes Martin <jmartin@csr.csc.uvic.ca>
To: cliffmcc@csr, edwardyu@csr, hausi@csr, ianmunro@csr, jpettit@csr, kenw@csr,
     mingdu@csr, mstorey@csr, mwang@csr, pingyu@csr, pkaminsk@gulf, shadian@csr,
     tracywen@csr, veronica@csr, wintb@csr, wjw@csr, tsysta@csr.csc.uvic.ca
Subject: RSF file format
Resent-Date: Thu, 10 Feb 2000 23:21:38 +0000 (GMT)
Resent-From: Johannes Martin <jmartin@csr.csc.uvic.ca>
Resent-To: rigi-developer-archive@rigi.uvic.ca
Resent-Subject: RSF file format

Hi folks,

while discussing the various RSF file formats with Jamie yesterday, we
noticed once again that RSF is not properly documented (in particular the
various structured formats).

Below is an attempt to write up a more or less formal definition of the
various RSF formats, as well as a proposal on how to fix some of the
deficiencies of unstructured RSF.

Also included is a list showing which tool supports which format.

I invite you to submit your comments and suggestions.


P.S.: I hereby call for volunteers to document the format of Rigi view


RSF format description:

In the productions:
- literals are in double quotes,
- regular expressions are unquoted,
- \n denotes newline character,
- whitespace can be either space or tab,
- <...> referes to a non-literal

1. Unstructured RSF:

rsf-file:      <rsf-tuples>

rsf-tuples:      <rsf-tuple>
          <rsf-tuple> \n <rsf-tuples>
          <comment> \n <rsf-tuples>
          \n <rsf-tuples>

comment:       ^#.*$

rsf-tuple:      <node-definition>

node-definition:   "type" <node-spec> <node-type>

arc-definition:      <arc-type> <node-spec> <node-spec>

attribute-definition:   <attribute-type> <node-spec> <attribute-value>

node-spec:      <identifier>
node-type:      <identifier>
arc-type:      <identifier>
attribute-type:      <identifier>
attribute-value:   <identifier>

identifier:      [^[[:space:]]]+

2. Partly structured RSF (differences from 1.):

node-spec:      <node-ID>!<identifier>

node-ID:      [1-9][0-9]*

Reserved node identifiers: "Root" (the root node of the graph)
Reserved arc types: "level" (connect parent to children nodes)

3. Stuctured RSF (differences from 2.):

node-definition:   n!type <node-spec> <node-type>

arc-definition:      a!<arc-type> <node-ID>!<arc-ID> <node-spec>

attributed-definition:  <node-attribute-def>

node-attribute-def:   n!<attribute-type> <node-spec> <attribute-value>

arc-attribute-def:   a!<attribute-type> <arc-ID> <attribute-value>

arc-ID:         [1-9][0-9]*

4. 4-tuple unstructured RSF (differences from 1.):

rsf-tuple:      <rsf-tuple2> <source-location>?

rsf-tuple2:      <node-definition>

source-location:   <file-name>";"<line-number>(";"<column-number>)?

file-name:      identifier
line-number:      [0-9]+
column-number:      [0-9]+

5. Proposal for a better unstructured RSF (differences from 4.):

RSF, and in particular unstructured RSF, has some deficiencies:
- there is no way to express arc attributes in unstructured RSF
- and RSF files does not contain domain information
- strings with embedded double quotes cause problems

Here is a working proposal on how to fix RSF without breaking existing

a) allow for arc attributes and the possibility to exactly identify nodes/arcs:

arc-definition:      <arc-type> <node-spec2> <node-spec2>

attribute-definition:   <attribute-type> <spec> <attribute-value>

spec:         <arc-spec>

node-spec2:      <node-spec>

arc-spec:      "("<arc-type>","<node-spec2>","<node-spec2>")"

identifier:      [^[[:space:]],()]+

b) include domain definition:

rsf-file:      <domain-definition>

domain-definition:   <nodetype-definition>

nodetype-definition:   "type" <node-type> "nodetype"
arctype-definition:   "type" <arc-type> "arctype"
attrtype-definition:   "type" <attribute-type> "attrtype"

Your comments and suggestions for this proposal are appreciated.

Appendix: Tool support
Here's a list showing which of our tools supports which of the above

                | Support for ... RSF:
Tool           | unstructured | partly structured | structured | 4-tuple
C parser       | write        |                   |            | write
Java parser    | write        |                   |            |
C++ parser     |              |                   |            | write
sortrsf        | read/write   |                   |            | read/write
htmlrsf        | read/write   |                   |            | read/write
rigiedit       | read         | read              | write      |