Re: GNU-NYU Ada project

[alex@MIMSY.CS.UMD.EDU (Alex Blakemore)]

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