From comp.compilers Thu Sep 14 23:10:02 1989 Path: jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!apple!sun-barr!decwrl!decvax!ima!esegue!compilers-sender From: rayan@cs.toronto.edu (Rayan Zachariassen) Newsgroups: comp.compilers Subject: S/SL (Was Re: Name that PD parser generator) Message-ID: <1989Sep14.142907.2085@esegue.segue.boston.ma.us> Date: 14 Sep 89 14:29:07 GMT 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> Sender: compilers-sender@esegue.segue.boston.ma.us Reply-To: rayan@cs.toronto.edu (Rayan Zachariassen) Organization: Compilers Central Lines: 56 Approved: compilers@esegue.segue.boston.ma.us 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)] -- Send compilers articles to compilers@ima.isc.com or, perhaps, Levine@YALE.EDU { decvax | harvard | yale | bbn }!ima. Meta-mail to ima!compilers-request. Please send responses to the author of the message, not the poster.