Related articles 

Internal code representation. markg@athens.emi.net (19951014) 
Re: Internal code representation. sgt20@cam.ac.uk (19951023) 
Re: Internal code representation. ganswijk@xs4all.nl (Jaap van Ganswijk) (19951023) 
Newsgroups:  comp.compilers,comp.programming,comp.lang.misc 
From:  sgt20@cam.ac.uk (Simon Tatham) 
Keywords:  interpreter 
Organization:  Trinity College, Cambridge 
References:  9510082 
Date:  Mon, 23 Oct 1995 08:22:29 GMT 
Mark Grosberg <markg@athens.emi.net> wrote:
>I am currently coding yet another (experimental) language interpreter.
>In all of my previous intepreters I used a RPNbased stack representation
>once code was absorbed and a stack to do evaluation.
>Any help or hints towards a good internal code representation would be
>appriciated, preferrably one that is both efficient and supports lazy and
>iterated parameter evaluation.
Have you tried a syntax tree? Each node in the tree may have many
children, and in the simplest case it corresponds exactly to the
grammar given in the parser description. For example
expr: term  expr '+' term ;
term: factor  term '*' factor ;
factor: NUMBER  '(' expr ')' ;
might give some kind of a syntax tree like
expr

term
/  \
term '*' factor
/ /  \
factor '(' expr ')'
/ /  \
NUMBER=2 expr '+' term
/ \
term factor
/ \
factor NUMBER=4
/
NUMBER=3
to denote the expression 2*(3+4). However, this tree can be collapsed
a long way, since "expr", "term", "factor" and "NUMBER" all have the
same basic data type, and so you can collapse the tree for the
productions "expr>term", "term>factor", "factor>'('expr')'" and
"factor>NUMBER", giving the reduced tree
expr
/  \
NUMBER=2 '+' expr
/  \
NUMBER=3 '*' NUMBER=4
which will allow a simple recursive evaluator to quickly execute the
"code". The same principle can equally well apply to statementtype
code rather than expressions.
Also, you can (presumably) try to spot if large branches of the tree
are equal to other large branches, and fiddle the internal
representation so that that code is not evaluated twice. (As long as
it has no side effects, of course, but that's obvious.)
Anyone catch me in a silly mistake?

Simon Tatham Email to: sgt20@cam.ac.uk
http://callisto.girton.cam.ac.uk/users/sgt20
Trinity College, Cambridge, CB2 1TQ, England
[Recursively running the tree is equivalent to interpreting the equivalent
RPN, except that the data stack is implicit in the call stack. John]

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