Re: Need starting tips for a new interpreter / parser

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.

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