Tcl Library Source Code

Bounty program for improvements to Tcl and certain Tcl packages.

[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]


grammar::me::cpu::gasm - ME assembler

Table Of Contents


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! 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::Nop text
::grammar::me::cpu::gasm::Note text
::grammar::me::cpu::gasm::Jmp label
::grammar::me::cpu::gasm::Who label
::grammar::me::cpu::gasm::/Label name
::grammar::me::cpu::gasm::/At name


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 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 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.

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.

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 recall that instruction by its label.

  3. The condition code to use when creating arcs between instructions, 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.


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.

  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 instruction. 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 comments 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 assembler.

    • 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.

    • 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 condition 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 instruction 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.


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. 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 output 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.


assembler, grammar, graph, parsing, tree, virtual machine


Grammars and finite automata


Copyright © 2005 Andreas Kupries