Re: Generating a simple hand-coded like recursive descent parser

Mr.E wrote:


> I recently got my scanner working for my [first] compiler. My
> compiler is for an existing BASIC language.


Can you tell us which one?


> I am seeing the
> complexity of the language at the parsing level. There are
> approximately 600 keyword or keyword combinations which include
> compound words due to intrinsic functions.


Most BASICs are LL(1) and quite easy to parse, even if they have many
different statements/productions.




> Is there a parser generator that produces the equivalent of a
> hand-coded recursive descent parser? I'm looking for a generator that
> doesn't require an engine and doesn't use external libraries... just
> plain old C.


If your BASIC also can be interpreted, the parser can not be that
complicated.


I've written some compilers and decompilers in BASIC, many years ago,
and found it very convenient to use the special built-in functions of my
various BASICs. That's a bit incompatible with the use of parser
generators, in detail for parser code produced for/in C.


If you want to write your compiler in BASIC, you can use more parser
generators, not only for C. CoCo/R may do what you want, with output of
the recursive descent parser in plain old Pascal. But I think that only
expressions will deserve the assistance of an parser generator, until
you get a feeling for how things can be done, then you can proceed with
handcrafting the remaining parts for statements etc. yourself. You also
can start with a very small subset of the language, and extend it later
to the full language. Then you can play with various approaches to the
generation of code and internal data structures very soon, until you
found a well working model. If you start with the full language instead,
you'll have many places in your code, where every modification of your
model has to be reflected, worth nothing but a giant waste of time.




> I can watch and debug recursive descent code because I can understand
> that. I cant imagine trying to debug a table driven parser or having
> to rewrite it in BASIC.


I can't as well ;-)


>
> The reason for my request is that my compiler will be written in a
> BASIC dialect instead of C. I would generate the parser in ANSI C
> then rewrite it in BASIC. I'm using a BASIC compiler to bootstrap my
> own. It seems to be a good idea to write the compiler in the language
> its going to compileso that's what I'm doing.


IMO that's feasible, with your powerful BASIC.


>
> Also are there any algorithms for AST building. Everything I've
> understand tells me that I really want to build an AST and do code
> generation from it versus trying to generate code as I go along. I
> thought I understood the process but I'm not there yet.


In my recent C compiler project I didn't use any parser generator, and
built all data structures manually in the recursive descent parser. IMO
automatic construction of an AST will only defer the problem of
recognizing what has to be done with the parsed input. Since you want to
implement an recursive descent parser, you can collect all required
information during parsing, perhaps, but not necessarily, in a tree-like
structure, from which you can produce code almost immediately. Remember
that an interpreter also interprets the statements one by one, possibly
after translating (scanning) everything into byte code, while loading a
program.


Provided your BASIC allows for procedures, you'll have to think some
time about a decent framework for procedures and their local variables,
so that you can patch the entry code of procedures easily, after
outputting the code for an procedure body. Or you may use a table,
describing the required amount of local memory and other things (line
numbers for ONERROR etc.), that can be inspected at runtime. Most BASIC
dialects do not really compile very well into machine code, so you may
be better off with a virtual machine and an byte code emulator for the
procedure framework, with an escape to compiled machine code for the
evaluation of expressions etc., which really profit from such a compilation.


Feel free to contact me by e-mail, for a more concrete discussion of
your project.


DoDi

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