S/SL (Was Re: Name that PD parser generator)

rayan@cs.toronto.edu (Rayan Zachariassen)
Thu, 14 Sep 89 00:10:41 EDT

          From comp.compilers

Related articles
S/SL (Was Re: Name that PD parser generator) rayan@cs.toronto.edu (1989-09-14)
Re: S/SL (Was Re: Name that PD parser generator) rayan@cs.toronto.edu (Rayan Zachariassen) (1989-09-25)
| List of all articles for this month |

From: rayan@cs.toronto.edu (Rayan Zachariassen)
References: <1989Sep6.152554.318@esegue.segue.boston.ma.us> <1989Sep11.015824.1006@esegue.segue.boston.ma.us> <1989Sep12.013014.1720@esegue.segue.boston.ma.us> <1989Sep13.145308.247@esegue.segue.boston.ma.us>
Date: Thu, 14 Sep 89 00:10:41 EDT

A usually more handy reference is:

            "An Introduction to S/SL: Syntax/Semantic Language"
            by R.C. Holt, J.R. Cordy, and D.B. Wortman,
            in ACM Transactions on Programming Languages and Systems (TOPLAS),
            Vol 4, No. 2, April 1982, Pages 149-178.

S/SL used to be a ``product'' but since only 4 or so places actually paid for
tapes I believe the authors consider it freely available (though
implementations are still copyrighted). At least, when I needed it for my
mailer and wrote a version in C, they agreed that it could be freely
redistributed subject to proper attribution when S/SL technology is used.

The proper address for CSRI is:

CSRI, University of Toronto
Sandford Fleming Building,
10 King's College Road,
Toronto, Ontario
Canada M5S 1A4

S/SL, in a nutshell, is compilable pseudo-code. A small language that defines
input/output/error token names (& values), semantic operations (which are
really escapes to a programming language but allow good abstration in the
pseudo-code), and a pseudo-code program that defines a grammar by the token
stream the program accepts. Alternation, control flow, and 1-symbol lookahead
constructs are part of the language. What I call an S/SL "implementation", is
a program that compiles this S/SL pseudo-code into a table (think byte-codes)
that is interpreted by the S/SL table-walker (interpreter). The S/SL compiler
is written using S/SL in case you need a real example. You supply the
table-walker, possibly based on a sample skeleton walker provided. I think
the pseudo-code language is LR(1), and that the semantic mechanisms turn it
into LR(N) relatively easily. It reminds me most of an abstract recursive-
descent approach.

You wouldn't use S/SL for off-the-cuff parsing needs, because the investment
in the table walker is much higher than what is needed to throw a yacc program
together. However for large or complicated jobs, anything based on yacc is
likely to be contorted and unmanageable. I used to have a hand-crafted RFC822
(that's a mail protocol) parser and a lex/yacc-based /bin/sh clone
implementation and got so disgusted with both that they are now implemented
using S/SL. S/SL has been used to build several quite large compilers
systems (Concurrent Euclid, Turing, Turing+ and variations, are those I know

If you've read this far, you deserve a cookie... my C implementation of the
S/SL compiler is now available by anonymous FTP to neat.cs.toronto.edu in

[From rayan@cs.toronto.edu (Rayan Zachariassen)]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.