Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] handling forward references in a compiler
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-05-26 (11:31)
From: Marcin 'Qrczak' Kowalczyk <qrczak@k...>
Subject: Re: [Caml-list] handling forward references in a compiler
W li¶cie z wto, 25-05-2004, godz. 17:52 +0800, napisa³:

> I'm writing a compiler for a language that allows undeclared forward
> references in OCaml, and I'm just wondering how one is supposed to
> handle these sorts of things without resorting to imperative features or
> multiple passes.

These are indeed two most obvious choices. I prefer the second one.

In the first pass we scan only "heads" of definitions, creating an
environment which maps strings to some unique ids. In the second pass
we know the meaning of each identifier, so we can process code normally
no matter which identifiers have their definitions before or after.

> Another option is to make a second pass through the
> generated intermediate representation, and fixing up the forward
> references after all of the declarations have been processed, but this
> seems like a second traversal that can be avoided.

There is no need to have a separate pass which only patches references.
You just lookup references in the previously constructed environment
as necessary, when processing the code tree in the next pass which also
does whatever it was supposed to do anyway.

In a compiler I implemented it was not that easy to scan heads of
definitions, because some syntactic sugar was not yet resolved, so it
would have to be resolved twice. To avoid this, the pass which gathers
defined names also produces a modified list of definitions, with
resolved toplevel syntactic sugar, with bound names represented by
unique ids, but with everything else - in particular all embedded
expressions - left unprocessed. They are processed in the next pass,
which resolves used identifiers and expression-level syntactic sugar,
and produces a new code representation for further processing.

   __("<         Marcin Kowalczyk

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: