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

Hans-Peter Diettrich wrote:
> 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?


FutureBasic - Its a dialect of BASIC for the Macintosh.




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


Maybe because it is my first compiler is just seems complicated.
I don't know how many books I've read on the subject and at the time
they made sense. Once I decided that I would write my own it started
to become a whole lot more challenging than the compilers I've read
about.


> 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.


This is the approach I am taking. The more I sketched how I want want
to accomplish what I want to do, the more problems I found because the
language appears to be really complex at the parsing level. The user
gets an easy to use language while I pull out small chunks of hair
thinking of how to do all the work under the hood.




> > 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.


To add more information, it will be a cross-compiler PPC and Intel on
Mac. I plan to keep the front end separated from the back-end with an
AST. Keeping the front and back separated should allow for


easier cross compiling
easier inclusion of a built in debugger
register usage analysis
code optimization


> 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.


The language is a fully procedual language; local functions, local &
global variables




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


I've never done anything like this before. I've been gleaning
from a number of books on compilers and finally felt I might
be ready to take the plunge into actually writing one.
Theory is one thing, actually writing one is a something
completely different.


Thank you for the life preserver. Trust me, I will take it.




W.

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