symbol_table

Description:

symbol table

symbol_table #


A generic symbol table implementation in Dart, with support for scopes and constants.
The symbol tables produced by this package are hierarchical (in this case, tree-shaped),
and utilize basic memoization to speed up repeated lookups.
Variables #
To represent a symbol, use Variable. I opted for the name
Variable to avoid conflict with the Dart primitive Symbol.
var foo = new Variable<String>('foo');
var bar = new Variable<String>('bar', value: 'baz');

// Call `lock` to mark a symbol as immutable.
var shelley = new Variable<String>('foo', value: 'bar')..lock();

foo.value = 'bar';
shelley.value = 'Mary'; // Throws a StateError - constants cannot be overwritten.

foo.lock();
foo.value = 'baz'; // Also throws a StateError - Once a variable is locked, it cannot be overwritten.
copied to clipboard
Visibility #
Variables are public by default, but can also be marked as private or protected. This can be helpful if you are trying
to determine which symbols should be exported from a library or class.
myVariable.visibility = Visibility.protected;
myVariable.visibility = Visibility.private;
copied to clipboard
Symbol Tables #
It's easy to create a basic symbol table:
var mySymbolTable = new SymbolTable<int>();
var doubles = new SymbolTable<double>(values: {
'hydrogen': 1.0,
'avogadro': 6.022e23
});

// Create a new variable within the scope.
doubles.create('one');
doubles.create('one', value: 1.0);
doubles.create('one', value: 1.0, constant: true);

// Set a variable within an ancestor, OR create a new variable if none exists.
doubles.assign('two', value: 2.0);

// Completely remove a variable.
doubles.remove('two');

// Find a symbol, either in this symbol table or an ancestor.
var symbol = doubles.resolve('one');

// Find OR create a symbol.
var symbol = doubles.resolveOrCreate('one');
var symbol = doubles.resolveOrCreate('one', value: 1.0);
var symbol = doubles.resolveOrCreate('one', value: 1.0, constant: true);
copied to clipboard
Exporting Symbols #
Due to the tree structure of symbol tables, it is extremely easy to
extract a linear list of distinct variables, with variables lower in the hierarchy superseding their parents
(effectively accomplishing variable shadowing).
var allSymbols = mySymbolTable.allVariables;
copied to clipboard
We can also extract symbols which are not private. This helps us export symbols from libraries
or classes.
var exportedSymbols = mySymbolTable.allPublicVariables;
copied to clipboard
It's easy to extract symbols of a given visibility:
var exportedSymbols = mySymbolTable.allVariablesWithVisibility(Visibility.protected);
copied to clipboard
Child Scopes #
There are three ways to create a new symbol table:
Regular Children #
This is what most interpreters need; it simply creates a symbol table with the current symbol table
as its parent. The new scope can define its own symbols, which will only shadow the ancestors within the
correct scope.
var child = mySymbolTable.createChild();
var child = mySymbolTable.createChild(values: {...});
copied to clipboard
Depth #
Every symbol table has an associated depth attached to it, with the depth at the root
being 0. When createChild is called, the resulting child has an incremented depth.
Clones #
This creates a scope at the same level as the current one, with all the same variables.
var clone = mySymbolTable.clone();
copied to clipboard
Forked Scopes #
If you are implementing a language with closure functions, you might consider looking into this.
A forked scope is a scope identical to the current one, but instead of merely copying references
to variables, the values of variables are copied into new ones.
The new scope is essentially a "frozen" version of the current one.
It is also effectively orphaned - though it is aware of its parent, the parent scope is unaware
that the forked scope is a child. Thus, calls to resolve may return old variables, if a parent
has called remove on a symbol.
var forked = mySymbolTable.fork();
var forked = mySymbolTable.fork(values: {...});
copied to clipboard
Creating Names #
In languages with block scope, oftentimes, identifiers will collide within a global scope.
To avoid this, symbol tables expose a uniqueName() method that simply attaches a numerical suffix to
an input name. The name is guaranteed to never be repeated within a specific scope.
var name0 = mySymbolTable.uniqueName('foo'); // foo0
var name1 = mySymbolTable.uniqueName('foo'); // foo1
var name2 = mySymbolTable.uniqueName('foo'); // foo2
copied to clipboard
this Context #
Many languages handle a sort of this context that values within a scope may
optionally be resolved against. Symbol tables can easily set their context
as follows:
void foo() {
mySymbolTable.context = thisContext;
}
copied to clipboard
Resolution of the context getter functions just like a symbol; if none is
set locally, then it will refer to the parent.
void bar() {
mySymbolTable.context = thisContext;
expect(mySymbolTable.createChild().createChild().context, thisContext);
}
copied to clipboard