grammar::me::cpu::gasm(3tGrammar operations and usgrammar::me::cpu::gasm(3tcl)
______________________________________________________________________________
NAME
grammar::me::cpu::gasm - ME assembler
SYNOPSIS
package require grammar::me::cpu::gasm ?0.1?
::grammar::me::cpu::gasm::begin g n ?mode? ?note?
::grammar::me::cpu::gasm::done --> t
::grammar::me::cpu::gasm::state
::grammar::me::cpu::gasm::state! s
::grammar::me::cpu::gasm::lift t dst = src
::grammar::me::cpu::gasm::Inline t node label
::grammar::me::cpu::gasm::Cmd cmd ?arg...?
::grammar::me::cpu::gasm::Bra
::grammar::me::cpu::gasm::Nop text
::grammar::me::cpu::gasm::Note text
::grammar::me::cpu::gasm::Jmp label
::grammar::me::cpu::gasm::Exit
::grammar::me::cpu::gasm::Who label
::grammar::me::cpu::gasm::/Label name
::grammar::me::cpu::gasm::/Clear
::grammar::me::cpu::gasm::/Ok
::grammar::me::cpu::gasm::/Fail
::grammar::me::cpu::gasm::/At name
::grammar::me::cpu::gasm::/CloseLoop
______________________________________________________________________________
DESCRIPTION
This package provides a simple in-memory assembler. Its origin is that
of a support package for use by packages converting PEG and other gram-
mars into a corresponding matcher based on the ME virtual machine, like
page::compiler::peg::mecpu. Despite that it is actually mostly agnostic
regarding the instructions, users can choose any instruction set they
like.
The program under construction is held in a graph structure (See pack-
age struct::graph) during assembly and subsequent manipulation, with
instructions represented by nodes, and the flow of execution between
instructions explicitly encoded in the arcs between them.
In this model jumps are not encoded explicitly, they are implicit in
the arcs. The generation of explicit jumps is left to any code convert-
ing the graph structure into a more conventional representation. The
same goes for branches. They are implicitly encoded by all instructions
which have two outgoing arcs, whereas all other instructions have only
one outgoing arc. Their conditonality is handled by tagging their out-
going arcs with information about the conditions under which they are
taken.
While the graph the assembler operates on is supplied from the outside,
i.e. external, it does manage some internal state, namely:
[1] The handle of the graph node most assembler operations will work
on, the anchor.
[2] A mapping from arbitrary strings to instructions. I.e. it is
possible to label an instruction during assembly, and later re-
call that instruction by its label.
[3] The condition code to use when creating arcs between instruc-
tions, which is one of always, ok, and fail.
[4] The current operation mode, one of halt, okfail, and !okfail.
[5] The name of a node in a tree. This, and the operation mode above
are the parts most heavily influenced by the needs of a grammar
compiler, as they assume some basic program structures (selected
through the operation mode), and intertwine the graph with a
tree, like the AST for the grammar to be compiled.
DEFINITIONS
As the graph the assembler is operating on, and the tree it is inter-
twined with, are supplied to the assembler from the outside it is nec-
essary to specify the API expected from them, and to describe the
structures expected and/or generated by the assembler in either.
[1] Any graph object command used by the assembler has to provide
the API as specified in the documentation for the package
struct::graph.
[2] Any tree object command used by the assembler has to provide the
API as specified in the documentation for the package
struct::tree.
[3] Any instruction (node) generated by the assembler in a graph
will have at least two, and at most three attributes:
instruction
The value of this attribute is the name of the instruc-
tion. The only names currently defined by the assembler
are the three pseudo-instructions
NOP This instruction does nothing. Useful for fixed
framework nodes, unchanging jump destinations, and
the like. No arguments.
C A .NOP to allow the insertion of arbitrary com-
ments into the instruction stream, i.e. a comment
node. One argument, the text of the comment.
BRA A .NOP serving as explicitly coded conditional
branch. No arguments.
However we reserve the space of all instructions whose
names begin with a "." (dot) for future use by the assem-
bler.
arguments
The value of this attribute is a list of strings, the ar-
guments of the instruction. The contents are dependent on
the actual instruction and the assembler doesn't know or
care about them. This means for example that it has no
builtin knowledge about what instruction need which argu-
ments and thus doesn't perform any type of checking.
expr This attribute is optional. When it is present its value
is the name of a node in the tree intertwined with the
graph.
[4] Any arc between two instructions will have one attribute:
condition
The value of this attribute determines under which condi-
tion execution will take this arc. It is one of always,
ok, and fail. The first condition is used for all arcs
which are the single outgoing arc of an instruction. The
other two are used for the two outgoing arcs of an in-
struction which implicitly encode a branch.
[5] A tree node given to the assembler for cross-referencing will be
written to and given the following attributes, some fixed, some
dependent on the operation mode. All values will be references
to nodes in the instruction graph. Some of the instruction will
expect some or specific sets of these attributes.
gas::entry
Always written.
gas::exit
Written for all modes but okfail.
gas::exit::ok
Written for mode okfail.
gas::exit::fail
Written for mode okfail.
API
::grammar::me::cpu::gasm::begin g n ?mode? ?note?
This command starts the assembly of an instruction sequence, and
(re)initializes the state of the assembler. After completion of
the instruction sequence use ::grammar::me::cpu::gasm::done to
finalize the assembler.
It will operate on the graph g in the specified mode (Default is
okfail). As part of the initialization it will always create a
standard .NOP instruction and label it "entry". The creation of
the remaining standard instructions is mode-dependent:
halt An "icf_halt" instruction labeled "exit/return".
!okfail
An "icf_ntreturn" instruction labeled "exit/return".
okfail Two .NOP instructions labeled "exit/ok" and "exit/fail"
respectively.
The note, if specified (default is not), is given to the "entry"
.NOP instruction.
The node reference n is simply stored for use by ::gram-
mar::me::cpu::gasm::done. It has to refer to a node in the tree
t argument of that command.
After the initialization is done the "entry" instruction will be
the anchor, and the condition code will be set to always.
The command returns the empy string as its result.
::grammar::me::cpu::gasm::done --> t
This command finalizes the creation of an instruction sequence
and then clears the state of the assembler. NOTE that this does
not delete any of the created instructions. They can be made
available to future begin/done cycles. Further assembly will be
possible only after reinitialization of the system via ::gram-
mar::me::cpu::gasm::begin.
Before the state is cleared selected references to selected in-
structions will be written to attributes of the node n in the
tree t. Which instructions are saved is mode-dependent. Both
mode and the destination node n were specified during invokation
of ::grammar::me::cpu::gasm::begin.
Independent of the mode a reference to the instruction labeled
"entry" will be saved to the attribute gas::entry of n. The ref-
erence to the node n will further be saved into the attribute
"expr" of the "entry" instruction. Beyond that
halt A reference to the instruction labeled "exit/return" will
be saved to the attribute gas::exit of n.
okfail See halt.
!okfail
Reference to the two instructions labeled "exit/ok" and
"exit/fail" will be saved to the attributes gas::exit::ok
and gas::exit::fail of n respectively.
The command returns the empy string as its result.
::grammar::me::cpu::gasm::state
This command returns the current state of the assembler. Its
format is not documented and considered to be internal to the
package.
::grammar::me::cpu::gasm::state! s
This command takes a serialized assembler state s as returned by
::grammar::me::cpu::gasm::state and makes it the current state
of the assembler.
Note that this may overwrite label definitions, however all non-
conflicting label definitions in the state before are not
touched and merged with s.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::lift t dst = src
This command operates on the tree t. It copies the contents of
the attributes gas::entry, gas::exit::ok and gas::exit::fail
from the node src to the node dst. It returns the empty string
as its result.
::grammar::me::cpu::gasm::Inline t node label
This command links an instruction sequence created by an earlier
begin/done pair into the current instruction sequence.
To this end it
[1] reads the instruction references from the attributes
gas::entry, gas::exit::ok, and gas::exit::fail from the
node n of the tree t and makes them available to assem-
bler und the labels label/entry, label/exit::ok, and la-
bel/exit::fail respectively.
[2] Creates an arc from the anchor to the node labeled la-
bel/entry, and tags it with the current condition code.
[3] Makes the node labeled label/exit/ok the new anchor.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::Cmd cmd ?arg...?
This is the basic command to add instructions to the graph. It
creates a new instruction of type cmd with the given arguments
arg... If the anchor was defined it will also create an arc
from the anchor to the new instruction using the current condi-
tion code. After the call the new instruction will be the an-
chor and the current condition code will be set to always.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::Bra
This is a convenience command to create a .BRA pseudo-instruc-
tion. It uses ::grammar::me::cpu::gasm::Cmd to actually create
the instruction and inherits its behaviour.
::grammar::me::cpu::gasm::Nop text
This is a convenience command to create a .NOP pseudo-instruc-
tion. It uses ::grammar::me::cpu::gasm::Cmd to actually create
the instruction and inherits its behaviour. The text will be
saved as the first and only argument of the new instruction.
::grammar::me::cpu::gasm::Note text
This is a convenience command to create a .C pseudo-instruction,
i.e. a comment. It uses ::grammar::me::cpu::gasm::Cmd to actu-
ally create the instruction and inherits its behaviour. The
text will be saved as the first and only argument of the new in-
struction.
::grammar::me::cpu::gasm::Jmp label
This command creates an arc from the anchor to the instruction
labeled with label, and tags with the the current condition
code.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::Exit
This command creates an arc from the anchor to one of the exit
instructions, based on the operation mode (see ::gram-
mar::me::cpu::gasm::begin), and tags it with current condition
code.
For mode okfail it links to the instruction labeled either
"exit/ok" or "exit/fail", depending on the current condition
code, and tagging it with the current condition code For the
other two modes it links to the instruction labeled "exit/re-
turn", tagging it condition code always, independent the current
condition code.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::Who label
This command returns a reference to the instruction labeled with
label.
::grammar::me::cpu::gasm::/Label name
This command labels the anchor with name. Note that an instruc-
tion can have more than one label.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::/Clear
This command clears the anchor, leaving it undefined, and fur-
ther resets the current condition code to always.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::/Ok
This command sets the current condition code to ok.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::/Fail
This command sets the current condition code to fail.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::/At name
This command sets the anchor to the instruction labeled with
name, and further resets the current condition code to always.
The command returns the empty string as its result.
::grammar::me::cpu::gasm::/CloseLoop
This command marks the anchor as the last instruction in a loop
body, by creating the attribute LOOP.
The command returns the empty string as its result.
BUGS, IDEAS, FEEDBACK
This document, and the package it describes, will undoubtedly contain
bugs and other problems. Please report such in the category grammar_me
of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please
also report any ideas for enhancements you may have for either package
and/or documentation.
When proposing code changes, please provide unified diffs, i.e the out-
put of diff -u.
Note further that attachments are strongly preferred over inlined
patches. Attachments can be made by going to the Edit form of the
ticket immediately after its creation, and then using the left-most
button in the secondary navigation bar.
KEYWORDS
assembler, grammar, graph, parsing, tree, virtual machine
CATEGORY
Grammars and finite automata
COPYRIGHT
Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>
tcllib 0.1 grammar::me::cpu::gasm(3tcl)