ee163ahp@sdccs7.UUCP (GALACTUS) (05/05/84)
Is there a C compiler out there that does not use the Z-80 card for the apple II? If so, where and how much. Also, does anyone know of any parsing techniques suitable for micro-computer implementation besides recursive descent, and operator precedence. Nick Flor
bbanerje@sjuvax.UUCP (B. Banerjee) (05/07/84)
>> Also, does anyone know of any parsing techniques suitable for >> micro-computer implementation besides recursive descent, and operator >> precedence. >> >> Nick Flor Why anyone would use recursive descent is beyond me. Try an LL(1) predictive parser. You might want to keep the operator precedence grammar for expressions. This is just as powerful as the recursive descent parser (recognises the same grammar(s) ) but avoids recursive overhead. This brings me to... has anyone written a parser generator for LL(1) grammars, sort of like YACC? I'm planning to do it myself when I find the time, but would be overjoyed if someone had beaten me to it (and was willing to make it available). Regards, -- Binayak Banerjee {allegra | astrovax | bpa | burdvax}!sjuvax!bbanerje
gwyn@brl-vgr.ARPA (Doug Gwyn ) (05/08/84)
The Aztec C compiler from Manx Software Systems (somewhere in NJ) is available for the Apple II and does not use the Z80 card. The price etc. are available from their ad in magazines such as Byte.
willc@iuvax.UUCP (05/09/84)
I assume you're worried about the size of the parser, since any parsing technique suitable for mainframes ought to work also on micros if the program will fit. If you have access to a parser generator such as yacc, use it and don't worry about what kind of parser it generates. Yacc happens to generate an LALR(1) parser. A book on my shelf claims that an LALR(1) parser table for Algol 60 occupies less than 3000 bytes. I would guess that an LL(1) parser table would be about the same size. A true recursive descent parser is just an LL(1) parser in which the parser table is encoded procedurally. I would expect table-driven LL(1) parsers to be more compact than recursive descent parsers. If you don't have access to a parser generator, use table-driven LL(1) or recursive descent. Just be careful as you transform the grammar into LL(1) form. Consult a good textbook on compiler construction such as Aho & Ullman or Hunter. William Clinger ...iuvax!willc
ech@spuxll.UUCP (05/15/84)
What possible reason would you have to USE an LL(k)-based parser generator? (given that you can use yacc, that is.) Yacc is based on LALR(1), see the paper by Aho and Johnson (Computing Surveys, 1974 -- happy 10th anniversary!), and is far and away the easiest tool for HUMANS to use to construct parsers; by contrast, LL(1) is much more restrictive, and operator precedence is a REAL bear. Sorry, didn't mean to come on so strong, there. IS there any good reason to use any top-down method? =Ned=
henry@utzoo.UUCP (Henry Spencer) (05/17/84)
spuxll!ech comments:
What possible reason would you have to USE an LL(k)-based parser generator?
(given that you can use yacc, that is.) Yacc is based on LALR(1), see
the paper by Aho and Johnson (Computing Surveys, 1974 -- happy 10th
anniversary!), and is far and away the easiest tool for HUMANS to use to
construct parsers; by contrast, LL(1) is much more restrictive, and
operator precedence is a REAL bear.
Sorry, didn't mean to come on so strong, there. IS there any good reason
to use any top-down method?
Yes. The *only* thing bottom-up has going for it (aside from being more
"fashionable") is that one can build bottom-up parser generators that
accept a very wide range of grammars and make it very easy to throw a
parser together quickly. This is important, particularly when the parser
is secondary to some other objective, but it isn't everything.
Top-down schemes, in general, can do better error handling/repair (see
my other followup for comments on this), are easier to fit semantics
into, cope better with situations where odd parsing methods are needed
for some special component of the language, and are easier to understand
and work with. Their one problem is that it's often harder to cast a
given language into a suitable form. Note that there are better ways
of specifying top-down parsers than LL(1) grammars: LL(1) grammars
are incredibly difficult to come up with, but tables for table-driven
analogs to recursive descent are very easy to write. Even so, it's not
quite as simple as throwing together a yacc grammar.
In short, top-down methods show up much better when the problem is to
write a "production" compiler/whatever and one is willing to expend
considerable effort on getting things just right. Bottom-up methods
work much better -- **IF** you have yacc or the equivalent already
written! -- for quick experimenting and throwing together a parser
for a user interface to some other tool.
It is unfortunate that top-down parsing methods are badly neglected
in current textbooks and courses.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henryrpw3@fortune.UUCP (05/25/84)
#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