Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site ndsuvax.UUCP Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!stolaf!mmm!dicomed!ndsuvax!nckary From: nckary@ndsuvax.UUCP (nckary) Newsgroups: net.micro.amiga Subject: Re: Amiga OS (really recursive descent compilers) Message-ID: <174@ndsuvax.UUCP> Date: Tue, 4-Feb-86 22:19:48 EST Article-I.D.: ndsuvax.174 Posted: Tue Feb 4 22:19:48 1986 Date-Received: Sun, 9-Feb-86 07:36:15 EST Distribution: net Lines: 55 In message <1133@caip.RUTGERS.EDU> Mike (I'll be mellow when I'm dead) Meyer writes: > I've been told that Lattice C is a recursive descent compiler. > Anybody silly enough to write a recursive descent compiler for > something like the Amiga (or most anything else....) is silly enough Please explain yourself. I have written compilers that parse top down and compilers that parse bottom up and I don't see a reason to call either technique silly. YACC has made LALR parsing very popular and I almost always use YACC because it is so convenient, but LL parsing is just as viable and in the absence of YACC it may be easier to implement. I suppose the reason that LL (recursive descent) parsing has a bad name is that in it's simplest form the parser selects productions in a pre- determined order and backtracks when a dead end is encountered. Recursive descent can be refined by adding a selection set for each production. The selection set permits the parser to select the correct production in any situation, so backtracking is eliminated. This sort of parser is sometimes called a Deterministic Recursive Descent Parser. The execution time for this type of parser is Big Oh of n (where n is the length of the input sentence), which is as good as it gets! Another possible drawback to LL parsing is that LL grammars can not contain left recursive rules (direct or indirect). Many programming languages are specified with grammars that are left recursive because it is both convenient and intuitive. While algorithms exist to transform left recursive grammars to non left recursive grammars the result can be considerably less intuitive. There are advantages to LL parsing if you are up to the task of writing the grammar. I personally think that error detection is easier in an LL parser. Once an LL grammar is written, the parser is trivial. I would not want to write an LALR parser without the aid of something like YACC. Maybe I'm making a mountain out of a mole hill but LALR parsers seem complex to me. A good text on this subject is "Compiler Design and Construction" by Arthur B. Pyster published by PWS Publishers (Prindle, Weber & Schmidt). The text is intended for undergraduates, it is easy to read and includes an example compiler for a PASCAL like language using a recursive descent parser. The example is coded in "structured English". The only point here is that the use of recursive descent is not automatically a reason to sneer at a compiler and may well be a reason to admire it. Since I do wish Mike a long and fruitful live, I will not ask him to become mellow :-). Dan Kary North Dakota State University Computer Science Department 300 Minard Hall P.O. Box 5075 Fargo, ND 58105 (701) 237-8171 ihnp4!dicomed!ndsuvax!nckary