Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site fortune.UUCP
Path: utzoo!linus!vaxine!wjh12!genrad!grkermit!masscomp!clyde!burl!ulysses!mhuxl!ihnp4!fortune!rpw3
From: rpw3@fortune.UUCP
Newsgroups: net.micro.apple
Subject: Re: C compiler - (nf)
Message-ID: <3428@fortune.UUCP>
Date: Fri, 25-May-84 04:04:03 EDT
Article-I.D.: fortune.3428
Posted: Fri May 25 04:04:03 1984
Date-Received: Mon, 28-May-84 05:38:23 EDT
Sender: notes@fortune.UUCP
Organization: Fortune Systems, Redwood City, CA
Lines: 47

#R:sdccs7:-120700:fortune:22000004:000:2140
fortune!rpw3    May 24 20:49:00 1984

Incidentally, easy-to-use compiler-compilers for top-down languages HAVE
been written in the past. The "META" class of compiler-copilers got some
attention for a while. I once got a copy of an Algol-W compiler that had
been written with "META-II", and the distribution (from DECUS for the PDP-10)
included the full "META-II" package, so I played with it a bit. I was able
to write a compiler for a toy version of BLISS (took most of the language
but the generated code was *AWFUL*) in a weekend.

In META-II, you write the grammar with imbedded output rules. Once you match
a rule to the point of outputting something, backup is forbidden, so you need
to do a bit of munging to force (nearly) LL(1) prefix structure. Sample rules
(productions):

	expr:	"(" expr ")" | addop ;

	addop:	mulop "+" OUTPUT("push AC") addop OUTPUT("add @sp+");

	mulop:	mulop "*" OUTPUT("push AC") primary OUTPUT("mul @sp+");

	primary: integer OUTPUT("load ac,[%1]") | name OUTPUT("load ac,%1");

Each rule (production) was compiled into a recursive procedure, which
was called by the stack/backup control routine. Each literal string
was compiled into a call to 'match("string")'. The %1 notation was the
top of stack #1 (of 4), which contained the LEXICAL string most recently
matched (note the use in the rule 'primary'). (The stacks were actually
local stack-variables, in that there was a fresh set available on each
new rule invocation.) You could do ^2 to push onto stack #2, etc. Having
the four stacks around let you re-order the code generation for things like
'if' and 'case' statements. The 'OUTPUT' command was no more than a 'printf'
equivalant, so META-II-generated compilers output assembler source (like
C does).

However, once I had seen how they did it, I quit using META-II, and
started crafting my own recognizer procedures directly, using a small
library of things like 'match'. Given that "bag of tricks", small
top-down parsers are easy to whip up when needed.

Rob Warnock

UUCP:	{ihnp4,ucbvax!amd70,hpda,harpo,sri-unix,allegra}!fortune!rpw3
DDD:	(415)595-8444
USPS:	Fortune Systems Corp, 101 Twin Dolphin Drive, Redwood City, CA 94065