Transforming a RTG into a LTG or a STTG
How to use our software

  1. Install ASF+SDF meta-environment on your computer (the stable realease).
    A binary distribution for Linux 32 bits is given, otherwise you should compile the source distribution.

    ASF+SDF web site:

    Follow the instructions mentioned on the web page to install ASF+SDF.

    Then, to run ASF+SDF, execute the shell script (when using the binary distribution 32 bits):

  2. Download, and unzipped it. The directory under which you have unzipped is called 'RTG-directory' in the following.

  3. To run our algorithm, type in a shell terminal:

    cd RTG-directory/RTGalgorithms

    Then click on Module/Open and choose RTGrProperties.sdf

    In the window on the right, a graph shows the links between modules. Richt-click on RTGrProperties, and click on "Edit/Term". Choose the regular grammar you want to transform into a LTG or a STTG (for example, click on example5.trm).

  4. The syntax contains (see the sub-window example5.trm):

    - the main function:
    regTGtoLTG to transform into a LTG
    regTGtoSTTG to transform into a STTG

    - plus 4 arguments (separated by commas):
    the list of non-terminals,
    the list of terminals,
    the start symbol(s),
    the production rules (separated by colons)

    To obtain the result grammar (given in the same syntax in the sub-window reduc.out), click on Term/Reduce.

    SxA is a new non-terminal introduced by the algorithm to replace both S and A.

    In the case of regTGtoSTTG, it is a bit more complicated. A non-terminal of the result grammar (denoted by Set1 or Set2,...) is a set of non-terminals of the initial grammar.
    The correspondance between Set1, Set2,... and the initial non-terminals, is mentionned at the end of the sub-window reduct.out. In the example opposite (Example 6 of the paper), Set2.Frame2.Frame1 means that the new non-terminal Set2 is the set {Frame2,Frame1}.

    Note that in the result grammar, some regular expressions could be simplified (the algorithm does not simplified them yet).

    You can also run the example of Section 4 (example-section4.trm). Of course, you may write your own examples.