15 Jan 1999 01:09:32 -0500

From: | hunk@alpha1.csd.uwm.edu (Mark William Hopkins) |

Newsgroups: | comp.compilers |

Date: | 15 Jan 1999 01:09:32 -0500 |

Organization: | University of Wisconsin - Milwaukee, Computing Services Division |

References: | 99-01-016 99-01-020 99-01-023 |

Keywords: | interpreter, design |

The best way to approach this is to DEFINE the evaluation of elements of

the language operationally by a recursive definition and then

systematically derive the architecture of the interpreter from that

definition by eliminating the recursion.

The only example I can give you, off hand, is a language based on the

Lambda Calculus. So, suppose your language consisted of the expressions

E -> lambda x. E -- definition of the function which when applied to x

gives you E.

E(E) -- evaluation of function.

x = E; E -- substitution expression (1st E substituted for x in

second E).

E? E: E -- conditional expression.

x -- atomic value (variable or constant).

The evaluation of an expression can be rigorously defined as follows:

Let [E] denote the result of evaluating E.

[E] need not be defined for all expressions E, if the

evaluation is an unending process.

Define:

[lambda x. E] = \x.[E]

[lambda x. E1 (E2)] = [x = E2; E1]

[E1(E2)] = { [E1], [E2] }, if E1 is not a lambda term.

[x = E1; E2] = [x <- [E1], E2]

[E? E1: E2] = [E1] -- if [E] is not 0.

= [E2] -- if [E] is 0.

[x] = x.

where

{ lambda x.N2, N1 } = [x <- N2, N1]

{ f, N1 } = f(N1) -- built-in functions.

and where

x <- N, E denotes the result of substituting N for every x in E.

From this definition, an interpreter can be systematically derived.

For handling substitutions, it's actually easier to take an explicit

definition of substitution, and integrate it into the above definition

to define

[e, E]

where e denotes an arbitrary set of substitutions. When the recursion

is eliminated from the resulting definition the result will be an

architecture which contains 4 components

S -- a state

E -- an "environment", which is nothing more than the "e"

in [e, E].

C -- the "currently executing code", which is nothing but the

"E" in [e, E].

D -- the "dump", which is the stack of pending recursive

sub-evaluations.

To design an interpreter, a similar sequence of steps can be taken.

First, define the evaluator as a recursive subroutine, then eliminate

the recursion, replacing it by the run-time stack.

Every interpreter you design will have something like a definition for

[E], a definition for substitution, an extension of the definition of

[E] to one for [e, E]. Every interpreter will therefore have something

like an S (the execution state) in it, an E (such as the run-time symbol

table), a C (such as the program counter) and a D (the run-time stack).

As an exercise, if you have an interpreter on hand or previously

developed one, take the interpreter and see if you can identify which

parts correspond to which parts of the description above.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.