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

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
of).


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
pub/ssl.tar.Z.


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

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