From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on ip-172-31-74-118.ec2.internal X-Spam-Level: X-Spam-Status: No, score=-1.9 required=3.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.5-pre1 Date: 20 Nov 92 22:55:41 GMT From: alex@MIMSY.CS.UMD.EDU (Alex Blakemore) Subject: Re: GNU-NYU Ada project Message-ID: <62223@mimsy.umd.edu> List-Id: dpoole@hydrogen.oscs.montana.edu (David Poole) writes: [report about NYU GNU Ada Project] > the parser uses recursive descent. Why? I thought LALR was the best possibl e. Thoretical answer at the end but in short in choosing between a LALR(1) and recursive descent approach to a parser - there are tradeoffs on both sides. LALR(1) + appropriate for a wide class of languages + usually constructed automatically from a grammar + easy to handle synthesized attributes - harder to handle inherited attributes - difficult to get good error messages and recovery recursive descent (works for LL(1)) + often faster (though parsing is not usually the compilation bottleneck) + easier to get good error messages and recover from syntax errors gracefully + easy to handle inherited attributes - harder to handle synthesized attributes - usually requires construction by hand - some grammars are not LL(1) but are LALR(1) So we should be happy that the NYU GNAT team (really Robert Dewar in this case I think) were willing to put in the effort to build a parser by hand so GNU Ada would be faster and have very good error messages/recovery. The class of language accepted is not as critical as one would think because all practical compilers parse a language that includes strings (programs) that are not in the source language and then prune illegal programs via semantic checks (conceptually after parsing phase). LALR(1) is a very popular class of grammar because it includes a large class of languages and there are efficient techniques/tools for automatically constru cting parsers for LALR(1) grammars. It is not the _best possible_ assuming you mean can parse the largest class of grammars. I believe there exist languages for w hich there exist LR(1) grammars but not LALR(1) grammars for example. Recursive des cent works for the class LL(1) which is smaller than LALR(1). -- --------------------------------------------------- Alex Blakemore alex@cs.umd.edu NeXT mail accepted