Re: LL(1) BNF validator wanted

> Is there a tool out there that can take a BNF (or BNF-like)
> description of a language and indicate all parts of the grammar that
> are not LL(1)?


I have recently finished writing a compact LL(1) compiler generator called
RDP for use in my undergraduate compiler class. It includes a hash-coded
symbol table module, an unusual scanner (which might turn out to be a big
mistake!) and a set manipulation module. It takes a grammar written in
standard EBNF and spits out an ANSI C parser, after having checked that
the language is LL(1). You could use this to check your grammar since it
does give full diagnostics when it finds non-LL(1)-isms. RDP uses
synthesized attributes to describe the semantics and in addition allows
arbitrary chunks of C to be included in the output. The source EBNF
supports an unusual construct for compactly specifying lists.


RDP is written in about 3000 lines of ANSI C, and compiles and runs
happily under Borland C on a PC and GNU C on Unix. There is a description
of RDP in the RDP source langauge, i.e. RDP can generate itself, a useful
test of a compiler generator! RDP has been used to generate several
assemblers, compilers for two small internal languages and a Pascal parser
which is presently being worked up into a pretty printer. The technical
reports dscribing its use and implementation are still being written, but
I'm very happy to send out copies of the sourse and pre-compiled MS-DOS
executables to anybody who wants them.


There are of course many compiler generators out there, and I make no
claims for my own except that it is small and that students can therefore
get to grips with how it is implemented (as well as how to use it) within
a single semester course.


Incidentally, I've always found Chapter Five of Algorithms + Data
Structures = Programs (Wirth, Prentice Hall) to be about the most
student-friendly introduction to compiler writing available, although the
Pascal domination might repel C programmers.


Adrian Johnstone, Computer Science Dept, Royal Holloway, University of London
adrian@dcs.rhbnc.ac.uk




--

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