Re: Need starting tips for a new interpreter / parser

hunk@alpha1.csd.uwm.edu (Mark William Hopkins)
15 Jan 1999 01:09:32 -0500

          From comp.compilers

Related articles
[3 earlier articles]
Re: Need starting tips for a new interpreter / parser lio-daa@online.no (Harald Fjerdingstad) (1999-01-04)
Re: Need starting tips for a new interpreter / parser lio-daa@online.no (Harald Fjerdingstad) (1999-01-06)
Re: Need starting tips for a new interpreter / parser escargo@mirage.skypoint.com (1999-01-06)
Re: Need starting tips for a new interpreter / parser mslamm@mscc.huji.ac.il (Ehud Lamm) (1999-01-11)
Re: Need starting tips for a new interpreter / parser Immanuel.Litzroth@pandora.be (Immanuel Litzroth) (1999-01-11)
Re: Need starting tips for a new interpreter / parser mikee@cetasoft.cog (1999-01-15)
Re: Need starting tips for a new interpreter / parser hunk@alpha1.csd.uwm.edu (1999-01-15)
Re: Need starting tips for a new interpreter / parser lio-daa@online.no (Harald Fjerdingstad) (1999-01-17)
Re: Need starting tips for a new interpreter / parser mikee@cetasoft.cog (1999-01-19)
Re: Need starting tips for a new interpreter / parser ndc@alum.mit.edu (N. D. Culver) (1999-01-20)
| List of all articles for this month |
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.