ELAN - Compiler
A first ELAN compiler was designed and presented in [11].
Experimentations made clear that a higher-level of programming is achieved
when some functions may be declared as AC. However rewriting in
such theories is computationally difficult and providing an efficient compiler
for the language becomes a real challenge. The compilation techniques used
in the design of the new ELAN compiler are the following:
-
Many-to-one matching is implemented using deterministic automata.
-
AC symbols are handled. In order to get a good efficiency of the
compiled programs, the effort concentrated on most used patterns with at
most two layers of AC symbols. Other patterns are transformed during
a preprocessing step which introduces new where local assignments,
and that also linearises the left-hand sides of rules. A Compact Bipartite
Graph data structure is used to design an efficient many-to-one AC
matching algorithm described in [16].
-
Due to non-deterministic strategies, particular choice point management
is needed. For implementation of backtracking, two functions are usually
required: the first one, to create a choice point and save the execution
environment; the second one, to backtrack to the last created choice point
and restore the saved environment. Two flow control functions, set-choice-point
and fail, have been implemented in assembly language. set-choice-point
sets a choice point, and the computation goes on. The fail function
performs a jump into the last call of set-choice-point. Their implementation
is described in [18].
-
More efficiency is also achieved thanks to determinism analysis. The determinism
analysis phase of the ELAN compiler annotates every rule and strategy in
the program with its determinism mode for use in later phases of the compiler:
matching phase, various optimisations on the generated code and detection
of non termination. This work is developped in [19].
