Re: A Compiler for a Functional language ?

On 31 Mar 2002 23:21:32 -0500, Peter Hansen <ztig@mail.tele.dk> wrote:
>
>I am currently trying to create a compiler / interpreter for a Functionel
>language. However i seem to be getting stuck right after having created the
>abstract / concrete syntax of my little language. Can anyone tell me what
>the next step is going to be, because i can't seem to figure out where to go
>next.


Best place to go would be your to your Teaching Assistant for help
with your homework. ;-)


The question's vague, but here are a few pointers. I'm assuming you
wrote out the language syntax, but haven't implemented anything yet.


First thing you need to do is write a program that recognizes the
language's individual tokens (identifiers, math symbols, strings,
numeric constants, keywords, etc.). Depending on the complexity of
the language, you can write this by hand or use a suitable string
processing language. Lex (or flex, the gnu version) is a lexical
analyzer generator, designed for this kind of thing.


Get that working, then write another program that recognizes the
syntax of the language. The output should do little more than tell
you whether the input is syntactically correct according to the
concrete syntax. There are a couple of basic techniques. Easiest to
use a parser generator tool like yacc (or bison, the gnu version).


Where to go from here depends on a variety of implementation decisions,
the complexity of your language, and the target. Decide whether you
want to produce a translated version of your program, or just
interpret the code on the fly.


Usually, you modify the language recognizer to produce a tree
structure matching the language syntax, as it processes the language
productions. This is called a syntax tree. Of course, you don't need
things like semicolons in your tree that add nothing to the semantics
(they're just in there to make it possible to parse the language), so
you take them out of the tree. The result is called an Abstract
Syntax Tree (AST).


So, you have a tree structure for an expression like (2 * a + 3 / b):


                                                [expr: root]
                                                  |
                                                [expr: + ]
                                              / \
                                        [expr: *] [expr: / ]
                                        / \ / \
                                    [num: 2] [sym: a] [num: 3] [sym: b]


You need to do a recursive postorder traversal of your AST. Eg. for
the above example, you evaluate the [expr: +] node by evaluating the
lefthand side, the right-hands side, and then adding the two results
together.


Good luck,




Morris

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