Re: parsing tools, was Dragon Book - update necessary?

Randall Hyde <rhyde@cs.ucr.edu> wrote:
>> I think that writing a compiler of that size in recursive descent would
>> be a maintenance nightmare.
>
>So was writing a compiler of that size with Flex/Bison :-)
>I predict the C++ R.D. version would be half the size.


I actually find that ANTLR grammar specs and programs to be easier to
maintain and debug by a significant factor than LEX/YACC
combinations. There are a number of reasons for this but if often
comes down to the fact that the generated code most often looks like
something an unimaginative, but retentive programmer would create for
the same grammar.


Debugging is just a matter of walking through code with genearted names that
map cleanly to your grammar and so on.


>> ANTLR generates the recursive descent code
>> for you from a grammar specification. However, as you painfully
>> discovered, you will be married to the tool, for better or for worse.
>
>ANTLR is at the top of my list of tools to consider. I do have a couple
>of concerns I would like answers to though:
>
>(1) I would prefer to write my lexer in assembly language (gasp!).
> HLA spends the vast majority of its time in lexical analysis and
> due to the interpreter I've integrated into the compiler (producing
> what I call the "compile-time language") there is a very incestuous
> relationship between the parser and lexer (the parser calls the lexer
> which recursively calls the parser, which recursively calls the lexer,
> etc.). I'm using this bit of craziness to support on-the-fly expansion
> of HLA's macros and other features (a preprocessor will *not* work
> here). So how hard is it to ignore ANTLR's lexer generator capabilities
> and call one or more different lexers written in another language (e.g.,
> assembly)?


I have done equivalent things in replacing one of my lexers with a JNI wrapped
lexer written in C. It was pretty easy. The fact that you can switch in lexers
or parsers for a given part of the grammar helps.


>
>(2) Is it easy to create and merge multiple parsers into the same compiler?
> Remember, I need a compiler and an interpreter in the same package.
> Merging the two grammars together, as I had to do with Flex/Bison
> created a lot of problems for me (yes, I realize I could have created
> two parsers with Bison, but I was never able to get some simple test
> systems working to my satisfaction).
>
>(3) Being written in Java concerns me. What is the performance like?
> Granted, it's got to be better than running 100 KLOC through Bison
> (which generally takes about a minute on my machine), but I would
> really like better turn around on the compiles with the next version.


ANTLR has a solid (LTIL) C++ backend.
When speed has been an issue I have always been able to make basic changes to
the code after profiling that have given me the desired results.


>
>(4) How large a system can you compile with ANTLR? Although not using
> Bison will allow me to reduce my grammar considerably, it's still a
> large language. HLA has several hundred statements, each with it's
> own syntactical variations. The original versions of FLEX and Bison
> that I started with choked early on (first I ran out of table space,
> then the unsigned shorts used as indexes into the tables started
> large grammar I'd produced. Alas, I was left behind as newer versions
> of Flex and Bison arrived because I didn't want to have to go in and
> make all those changes to the newer versions of the tools. This was
> a real problem with FLEX (you should see the ugly algorithm, involving
> unget, I use to expand macros on the fly; a problem that was
> eliminated in later versions of Flex that I could not use).
>>
>> I would also point out that a recursive program tends to be much slower
>> than an iterative one. A few years back, I compared my table-driven C
>> recognizer to the one provided with ANTLR. Mine was about three times
>> faster when executed on the ANTLR source code itself.




Have fun,
        Jim JM

Return to the comp.compilers page.
Search the comp.compilers archives again.