From: Robert Feldt Date: 2003-07-31T06:33:33+09:00 Subject: Re: Parser generator gabriele renzi skrev den Wed, 30 Jul 2003 11:28:55 +0900: > il Tue, 29 Jul 2003 10:00:03 +0900, "Rodrigo B. de Oliveira" > ha scritto:: > >> I'm evaluating language/frameworks for creating a toy language compiler >> and I'd love to use ruby. Unfortunately I couldn't find a mature parser >> generator for ruby (automatic AST generation is a plus). Advices? > Rockit builds your AST and has EBNF constructs. but see below for recommendation. > dunno what you mean for 'mature' but look on RAA for RACC and rockit. > the first is yacc/bison like, rockit is, I think, antlr-like. > Rockit is GLR which is Generalized LR which is LR(infinity). It is very nice since you can parse any context-free language with it and grammars look very nice and are easy to understand. I think antlr is LL(k) for varying and controllable k (I guess sort of LL(infinity) in practice...). Its powerful if you know what you are doing but you generally need to "direct it" more than a GLR parser, ie. write more. Upside is performance *can* be better. Recently some new algorithms and ideas for GLR has made C implementations approach bison (LALR) in performance (I think the best are within 3-10% of bison) when the grammar is unambigous (which they are the majority of the time in practice). This is the best of worlds since you only take the performance hit when there is no way to decide early which parse tree is the correct one. Rockit 0.3.8 is too immature (bugs and poor performance) to use for parsing large grammars/inputs unfortunately since I haven't had enough time to work on it. There is a later version that uses one of the new C-implemented GLR backend's for nice speed but I never get enough time to tighten/pack it up. Hopefully it will happen some day but for now you can consider it vaporware... ;) So a safe summary is to go for racc for time-tested algorithms and a really good implementation. If you want to stay on the bleeding edge you might wanna watch out for rockit or other glr (or maybe an antlr in ruby port?) ruby offerings. Regards, Robert Feldt