On Mon, 02 Apr 2001  21:29:26 +0900, Robert Feldt wrote:
> On Mon, 2 Apr 2001, Christophe Broult wrote:
> 
> > I cannot work on that in the near future but I will keep the idea in the
> > back of my mind:-(
> > 
> Would be great if someone could briefly summarize the advantages and
> disadvantages of ANTLR-style parsing (LL?) compared to yacc/bison ditto
                                          ^
ANTLR does a linear approximation of LL(k) for k > 1.

> (LALR(1))? Short example showing the benefits?

ANTLR grammars are written in a kind of EBNF, which makes them very
readable:

rule
	:	TOKEN
	|	nonterminal
	|	(optional)?
	|	(zero_or_more)*
	|	(one_or_more)?
	;

syntactic_predicates			// finite lookahead, back-tracking
	:	(A A b) => A A b
	|	(A)* b
	;

semantic_predicates
	:	{ conditional_code; } => rule
	|	{ conditional_code; } => rule
	|	foo
	;

automatic Abstract Syntax Tree generation with grammar annotations (^):

mult_expr
	:	add_expr ((STAR^ | SLASH^) add_expr)
	;

add_expr
	:	atom ((PLUS^ | MINUS^) atom)
	;

so 1 + 2 * 3 gives (+ 1 (* 2 3)) (LISPy representations)

ANTLR
- generates parsers, lexers and AST-treeparsers, all with the same
  EBNF notation
- error handling with exceptions
- polymorphic token streams

See http://www.antlr.org/contributions.html for more detail.

> My (uninformed) impression is that LALR(1) is theoretically stronger but
> LL in practice is as strong but more human readable. Is this correct?

Correct. The biggest advantage I get from LL(k) parsers is the fact
that the generated code is -- unlike yacc code -- not write-only; and
thus far easier to debug.

> FYI, there are already a couple of solutions for generating LALR(1) Ruby
> parser:
> 
> * racc   (pure-ruby implementation of yacc, ie. with action code)
> * rbison (convert bison output to ruby, ie. with action code)
> * rockit (pure-ruby implementation that gives abstract syntax tree
>           directly from grammar)

Know'em, like'em  :)

	Michel