As I understand your message, you are asking about issues:
(1) how to type-check the expressions and function calls
(including arity)
(2) how to represent functions in the interpreter
(both builtin and user-defined)
(3) how to architect the interpreter overall.
Below are some general overview thoughts.
1. type-checking
Type-checking cannot usually be done in a single pass by the parser
because there may be forward references (e.g., mutually recursive
functions). (Also, often it is clearer to keep the pass separate
rather than mixing it in with tree construction code.)
Generally the approach is to add another pass after parsing that
traverses a parse tree checking the types of each expression and
function call.
A type checking pass may be required for language with overloaded
functions, methods, or operators, since the types of the operand
determines what version of the function, method, or operator is called
(e.g., equals method in Java, or "+" operator in Java).
2. functions
For FUNCTION CALLS, most languages use the same syntax for calls to a
language-defined library and to a user-defined library, so the same
parse tree representation is used for both.
For PRIMITIVE FUNCTION DEFINITIONS, primitive ('native') functions may
be predefined in the symbol table using objects that implement the
function in Java.
For USER-DEFINED FUNCTION DEFINITIONS, functions are defined using a
parse tree (or a tree of interpreter objects derived from a parse
tree).
When a function is defined, the definition is stored in the symbol
environment.
When the function is called, the symbol ENVIRONMENT is
extended with a new environment frame, binding the symbols to
passed values. When symbols are looked up while interpreting the
function body, the local environment frame is searched for the symbol
before looking in the next outer frame.
Most languages are defined to use LEXICAL SCOPE, which means the next
outer environment frame corresponds to the nesting of the text in the
program. For example, if a function is defined in a top level
('global') scope, then the next outer environment is the global scope,
no matter from where the function was called. Some languages permit
definitions in nested scopes, such as a package, class, or locally
inside a function or method. Lexically scoped function
representations store a pointer to the environment where they were
defined.
(Some languages are defined to use DYNAMIC SCOPE, which means the next
outer environment frame is the frame used by the caller. This has the
disadvantage that local names used in the caller may unintentionally
override free names the callee expects to find in a library.
Languages which use dynamic scope may depend on unenforced conventions
to keep such names separate, such as using full words for library
names and abbreviations for local names.)
(Some languages use separate environments for functions and data and
types. Sometimes such languages cannot pass a function or a type as a
parameter.)
3. visitors, interpreter objects, ...
Some interpreters are implemented with a general parser that creates
general parse tree nodes (abstract syntax tree, AST), and then use
'visitors' to implement p***** that walk over parts of this parse tree
to type check and interpret it.
Some interpreters are implemented with a specialized parser that
creates special parse tree nodes (abstract syntax tree, AST) which are
specifically for the interpreter. Each node implements an interface
which sup****ts the operations needed by the interpreter for the
type-checking pass and for interpretation.
Tradeoffs:
* A general AST parser can be used for multiple purposes, since the
parse tree nodes are not specialized for the interpreter.
(For example, to build reformatting or javadoc-like tools.)
* A specialized AST parser for complex or experimental languages may
be more easily maintained, since adding or changing a single
language feature may be confined to a single node, rather than
spread out across every visitor, and unlike visitors, no file other
than the (JavaCC) parser has to know about every kind of node.
Some interpreters transform the parse tree into a more efficient
representation, for example to eliminate some environment lookups by
replacing a reference to a symbol with a direct pointer to the cell
holding the value, or code that can find it quickly (e.g., 'z' is the
3rd argument of the call frame).
So, the architecture often depends on what kinds of additions and
changes the implementor expects for maintaining the code in the
future.
Hope some of this helps.
|
