[comment {-*- tcl -*- doctools manpage}] [manpage_begin grammar::me::cpu::gasm n 0.1] [copyright {2005 Andreas Kupries }] [moddesc {Grammar operations and usage}] [titledesc {ME assembler}] [category {Grammars and finite automata}] [require grammar::me::cpu::gasm [opt 0.1]] [description] [keywords {virtual machine}] [keywords parsing grammar assembler graph tree] This package provides a simple in-memory assembler. Its origin is that of a support package for use by packages converting PEG and other grammars into a corresponding matcher based on the ME virtual machine, like [package page::compiler::peg::mecpu]. Despite that it is actually mostly agnostic regarding the instructions, users can choose any instruction set they like. [para] The program under construction is held in a graph structure (See package [package 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. [para] In this model jumps are not encoded explicitly, they are implicit in the arcs. The generation of explicit jumps is left to any code converting 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 outgoing arcs with information about the conditions under which they are taken. [para] While the graph the assembler operates on is supplied from the outside, i.e. external, it does manage some internal state, namely: [list_begin enumerated] [enum] The handle of the graph node most assembler operations will work on, the [term anchor]. [enum] A mapping from arbitrary strings to instructions. I.e. it is possible to [term label] an instruction during assembly, and later recall that instruction by its label. [enum] The condition code to use when creating arcs between instructions, which is one of [const always], [const ok], and [const fail]. [enum] The current operation mode, one of [const halt], [const okfail], and [const !okfail]. [enum] 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. [list_end] [section DEFINITIONS] As the graph the assembler is operating on, and the tree it is intertwined with, are supplied to the assembler from the outside it is necessary to specify the API expected from them, and to describe the structures expected and/or generated by the assembler in either. [para] [list_begin enumerated] [enum] Any graph object command used by the assembler has to provide the API as specified in the documentation for the package [package struct::graph]. [enum] Any tree object command used by the assembler has to provide the API as specified in the documentation for the package [package struct::tree]. [enum] Any instruction (node) generated by the assembler in a graph will have at least two, and at most three attributes: [list_begin definitions] [def [const instruction]] The value of this attribute is the name of the instruction. The only names currently defined by the assembler are the three pseudo-instructions [comment {Fix nroff backend so that the put the proper . on the command name}] [list_begin definitions] [def [const NOP]] This instruction does nothing. Useful for fixed framework nodes, unchanging jump destinations, and the like. No arguments. [def [const C]] A .NOP to allow the insertion of arbitrary comments into the instruction stream, i.e. a comment node. One argument, the text of the comment. [def [const BRA]] A .NOP serving as explicitly coded conditional branch. No arguments. [list_end] However we reserve the space of all instructions whose names begin with a "." (dot) for future use by the assembler. [def [const arguments]] The value of this attribute is a list of strings, the arguments 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 arguments and thus doesn't perform any type of checking. [def [const expr]] This attribute is optional. When it is present its value is the name of a node in the tree intertwined with the graph. [list_end] [enum] Any arc between two instructions will have one attribute: [list_begin definitions] [def [const condition]] The value of this attribute determines under which condition execution will take this arc. It is one of [const always], [const ok], and [const 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 instruction which implicitly encode a branch. [list_end] [enum] 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. [list_begin definitions] [def [const gas::entry]] Always written. [def [const gas::exit]] Written for all modes but [const okfail]. [def [const gas::exit::ok]] Written for mode [const okfail]. [def [const gas::exit::fail]] Written for mode [const okfail]. [list_end] [list_end] [section API] [list_begin definitions] [call [cmd ::grammar::me::cpu::gasm::begin] [arg g] [arg n] [opt [arg mode]] [opt [arg 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 [cmd ::grammar::me::cpu::gasm::done] to finalize the assembler. [para] It will operate on the graph [arg g] in the specified [arg mode] (Default is [const 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 [arg mode]-dependent: [list_begin definitions] [def [const halt]] An "icf_halt" instruction labeled "exit/return". [def [const !okfail]] An "icf_ntreturn" instruction labeled "exit/return". [def [const okfail]] Two .NOP instructions labeled "exit/ok" and "exit/fail" respectively. [list_end] The [arg note], if specified (default is not), is given to the "entry" .NOP instruction. [para] The node reference [arg n] is simply stored for use by [cmd ::grammar::me::cpu::gasm::done]. It has to refer to a node in the tree [arg t] argument of that command. [para] After the initialization is done the "entry" instruction will be the [term anchor], and the condition code will be set to [const always]. [para] The command returns the empy string as its result. [call [cmd ::grammar::me::cpu::gasm::done] [const -->] [arg t]] This command finalizes the creation of an instruction sequence and then clears the state of the assembler. [emph NOTE] that this [emph {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 [cmd ::grammar::me::cpu::gasm::begin]. [para] Before the state is cleared selected references to selected instructions will be written to attributes of the node [arg n] in the tree [arg t]. Which instructions are saved is [arg mode]-dependent. Both [arg mode] and the destination node [arg n] were specified during invokation of [cmd ::grammar::me::cpu::gasm::begin]. [para] Independent of the mode a reference to the instruction labeled "entry" will be saved to the attribute [const gas::entry] of [arg n]. The reference to the node [arg n] will further be saved into the attribute "expr" of the "entry" instruction. Beyond that [list_begin definitions] [def [const halt]] A reference to the instruction labeled "exit/return" will be saved to the attribute [const gas::exit] of [arg n]. [def [const okfail]] See [const halt]. [def [const !okfail]] Reference to the two instructions labeled "exit/ok" and "exit/fail" will be saved to the attributes [const gas::exit::ok] and [const gas::exit::fail] of [arg n] respectively. [list_end] [para] The command returns the empy string as its result. [call [cmd ::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. [call [cmd ::grammar::me::cpu::gasm::state!] [arg s]] This command takes a serialized assembler state [arg s] as returned by [cmd ::grammar::me::cpu::gasm::state] and makes it the current state of the assembler. [para] [emph Note] that this may overwrite label definitions, however all non-conflicting label definitions in the state before are not touched and merged with [arg s]. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::lift] [arg t] [arg dst] [const =] [arg src]] This command operates on the tree [arg t]. It copies the contents of the attributes [const gas::entry], [const gas::exit::ok] and [const gas::exit::fail] from the node [arg src] to the node [arg dst]. It returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::Inline] [arg t] [arg node] [arg label]] This command links an instruction sequence created by an earlier begin/done pair into the current instruction sequence. [para] To this end it [list_begin enumerated] [enum] reads the instruction references from the attributes [const gas::entry], [const gas::exit::ok], and [const gas::exit::fail] from the node [arg n] of the tree [arg t] and makes them available to assembler und the labels [arg label]/entry, [arg label]/exit::ok, and [arg label]/exit::fail respectively. [enum] Creates an arc from the [term anchor] to the node labeled [arg label]/entry, and tags it with the current condition code. [enum] Makes the node labeled [arg label]/exit/ok the new [term anchor]. [list_end] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::Cmd] [arg cmd] [opt [arg arg]...]] This is the basic command to add instructions to the graph. It creates a new instruction of type [arg cmd] with the given arguments [arg arg]... If the [term anchor] was defined it will also create an arc from the [term anchor] to the new instruction using the current condition code. After the call the new instruction will be the [term anchor] and the current condition code will be set to [const always]. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::Bra]] This is a convenience command to create a .BRA pseudo-instruction. It uses [cmd ::grammar::me::cpu::gasm::Cmd] to actually create the instruction and inherits its behaviour. [call [cmd ::grammar::me::cpu::gasm::Nop] [arg text]] This is a convenience command to create a .NOP pseudo-instruction. It uses [cmd ::grammar::me::cpu::gasm::Cmd] to actually create the instruction and inherits its behaviour. The [arg text] will be saved as the first and only argument of the new instruction. [call [cmd ::grammar::me::cpu::gasm::Note] [arg text]] This is a convenience command to create a .C pseudo-instruction, i.e. a comment. It uses [cmd ::grammar::me::cpu::gasm::Cmd] to actually create the instruction and inherits its behaviour. The [arg text] will be saved as the first and only argument of the new instruction. [call [cmd ::grammar::me::cpu::gasm::Jmp] [arg label]] This command creates an arc from the [term anchor] to the instruction labeled with [arg label], and tags with the the current condition code. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::Exit]] This command creates an arc from the [term anchor] to one of the exit instructions, based on the operation mode (see [cmd ::grammar::me::cpu::gasm::begin]), and tags it with current condition code. [para] For mode [const 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/return", tagging it condition code [const always], independent the current condition code. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::Who] [arg label]] This command returns a reference to the instruction labeled with [arg label]. [call [cmd ::grammar::me::cpu::gasm::/Label] [arg name]] This command labels the [term anchor] with [arg name]. [emph Note] that an instruction can have more than one label. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::/Clear]] This command clears the [term anchor], leaving it undefined, and further resets the current condition code to [const always]. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::/Ok]] This command sets the current condition code to [const ok]. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::/Fail]] This command sets the current condition code to [const fail]. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::/At] [arg name]] This command sets the [term anchor] to the instruction labeled with [arg name], and further resets the current condition code to [const always]. [para] The command returns the empty string as its result. [call [cmd ::grammar::me::cpu::gasm::/CloseLoop]] This command marks the [term anchor] as the last instruction in a loop body, by creating the attribute [const LOOP]. [para] The command returns the empty string as its result. [list_end] [section {BUGS, IDEAS, FEEDBACK}] This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category [emph grammar_me] of the [uri {http://sourceforge.net/tracker/?group_id=12883} {Tcllib SF Trackers}]. Please also report any ideas for enhancements you may have for either package and/or documentation. [manpage_end]