Simple Imperative symbol table is used for imperative languages. It is usually implemented as a stack. Such a table should support the following:
1) empty table for the operation to begin with
2) binding : for each new name object pair that is pushed on to the stack
3) lookup : the stack is searched from top to bottom for a match.
4) enter : the top of the stack is noted
5) exit : the previous top of stack marker is recalled and becomes current
A common efficiency issues to all of the mentioned symbol table implementations is that the lookup requires linear search. A common solution to this problem is hashing where the names are hashed to integers. However that complicates the enter and exit functions mentioned above because the hash table has to be updated for all array elements at every entry and exit. Instead a single stack is maintained to record all updates to the table such that they can be undone in time proportional to the number of updates in the local scope.
Separate name spaces : Functions and variables have separate name spaces, which means defining a name in one space doesn't affect the other. Name spaces can also be shared and sharing can exist between any subsets of namespaces. Separate name spaces are easily implemented using a symbol table per namespace. Shared namespaces share a single table. Separate name spaces can also share a single symbol table if there are namespace indicators added to the names. A namespace indicator is a textual prefix to the name. A name-space indicator can be a textual prefix to the name or a tag paired with the name. In both cases, a lookup matches both the name space indicator and the names.
If we look at the objects in a program, some of them share namespaces. Types, functions and procedures, and variables share the same namespace. Labels, data constructors and modules don't share name spaces.
Type checking is enforced either in a separate phase or immediately after the syntax checking or it could be interleaved with it. Actual translation often occurs based on type checking so this is combined with the translation. The checking phase involves several passes over the abstract syntax tree and each pass is a recursive walk. Each walk gathers information in earlier passes or uses it. Such information is called attributes . There are two kinds of attributes of the syntax tree - synthesized attributes are passed upwards in the syntax tree from the leaves upto the root. Inherited attributes are conversely passed downwards in the syntax tree. Attributes synthesized in one subtree may be inherited in another subtree or by the same subtree in a different pass. When the declarations are recursive, the scope may be the same syntax tree as the declaration itself. For example the symbol table synthesizes by declaration and inherits by the scope of the declaration. ( text from Mogensen )
1) empty table for the operation to begin with
2) binding : for each new name object pair that is pushed on to the stack
3) lookup : the stack is searched from top to bottom for a match.
4) enter : the top of the stack is noted
5) exit : the previous top of stack marker is recalled and becomes current
A common efficiency issues to all of the mentioned symbol table implementations is that the lookup requires linear search. A common solution to this problem is hashing where the names are hashed to integers. However that complicates the enter and exit functions mentioned above because the hash table has to be updated for all array elements at every entry and exit. Instead a single stack is maintained to record all updates to the table such that they can be undone in time proportional to the number of updates in the local scope.
Separate name spaces : Functions and variables have separate name spaces, which means defining a name in one space doesn't affect the other. Name spaces can also be shared and sharing can exist between any subsets of namespaces. Separate name spaces are easily implemented using a symbol table per namespace. Shared namespaces share a single table. Separate name spaces can also share a single symbol table if there are namespace indicators added to the names. A namespace indicator is a textual prefix to the name. A name-space indicator can be a textual prefix to the name or a tag paired with the name. In both cases, a lookup matches both the name space indicator and the names.
If we look at the objects in a program, some of them share namespaces. Types, functions and procedures, and variables share the same namespace. Labels, data constructors and modules don't share name spaces.
Type checking is enforced either in a separate phase or immediately after the syntax checking or it could be interleaved with it. Actual translation often occurs based on type checking so this is combined with the translation. The checking phase involves several passes over the abstract syntax tree and each pass is a recursive walk. Each walk gathers information in earlier passes or uses it. Such information is called attributes . There are two kinds of attributes of the syntax tree - synthesized attributes are passed upwards in the syntax tree from the leaves upto the root. Inherited attributes are conversely passed downwards in the syntax tree. Attributes synthesized in one subtree may be inherited in another subtree or by the same subtree in a different pass. When the declarations are recursive, the scope may be the same syntax tree as the declaration itself. For example the symbol table synthesizes by declaration and inherits by the scope of the declaration. ( text from Mogensen )
No comments:
Post a Comment