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

Pascal Bourguignon wrote:


> Unless you're trapped on a planet light years away, with nothing else
> than a BASIC, I see no reason to use that to bootstrap a compiler.
>
> Even if you have to compile the compiler to BASIC for some strange
> reason, I see no reason why you shouldn't use more powerful tools to
> generate the BASIC code...


From what I've read, many compilers are grown and extended by using
their own language, I like that idea.


> So, here is a simple Recursive Descent Parser generator, written in
> Common Lisp, that can generate the parser in lisp, or in a
> pseudo-basic. You could modify it to generate the code you want, for
> your target basic system.
>
> http://www.informatimago.com/develop/lisp/small-cl-pgms/rdp/
>
> For the scanner, it uses a regexp library with a simplistic algorithm
> (trying the regexp for each token in turn.
>
> If speed was needed, a smarter algorithm using a fusionned DFA for the
> scanner would be in order, and of course, a table based parser too.


I will check it out.


> > 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.
>
> There's no specific algorith to build the AST. It's merely built by
> the actions associated to the grammar rules, and executed by the
> parser when the rule is used.


Oh darn, an algorithm would give a standard to work with and compare
to.


> The reason why it's interesting to build this AST as an intermediate
> data structure, is that apart from the most simple cases, some
> semantic analysis, and some optimizations are needed, for which we
> need a global view of the AST.
>
> For example to check that the declaredtype of the variables matches
> the type of the operators with which the variables are used, or to to
> type inference.
>
> The remaining phases can be implemented as progressive transformations
> of the AST into less and less abstract trees until what remains is a
> list of target processor instructions.
>
>
>
>
> Here is an example of the grammar written for my simple recursive
> descent parser.
>
I will glean from your example all that I can. I appreciate it.




Thank you,




W.

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