1grammar::me::cpu::gasm(n)Grammar operations and usagegrammar::me::cpu::gasm(n)
2
3
4
5______________________________________________________________________________
6

NAME

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

SYNOPSIS

11       package require grammar::me::cpu::gasm  ?0.1?
12
13       ::grammar::me::cpu::gasm::begin g n ?mode? ?note?
14
15       ::grammar::me::cpu::gasm::done --> t
16
17       ::grammar::me::cpu::gasm::state
18
19       ::grammar::me::cpu::gasm::state! s
20
21       ::grammar::me::cpu::gasm::lift t dst = src
22
23       ::grammar::me::cpu::gasm::Inline t node label
24
25       ::grammar::me::cpu::gasm::Cmd cmd ?arg...?
26
27       ::grammar::me::cpu::gasm::Bra
28
29       ::grammar::me::cpu::gasm::Nop text
30
31       ::grammar::me::cpu::gasm::Note text
32
33       ::grammar::me::cpu::gasm::Jmp label
34
35       ::grammar::me::cpu::gasm::Exit
36
37       ::grammar::me::cpu::gasm::Who label
38
39       ::grammar::me::cpu::gasm::/Label name
40
41       ::grammar::me::cpu::gasm::/Clear
42
43       ::grammar::me::cpu::gasm::/Ok
44
45       ::grammar::me::cpu::gasm::/Fail
46
47       ::grammar::me::cpu::gasm::/At name
48
49       ::grammar::me::cpu::gasm::/CloseLoop
50
51______________________________________________________________________________
52

DESCRIPTION

54       This  package provides a simple in-memory assembler. Its origin is that
55       of a support package for use by packages converting PEG and other gram‐
56       mars into a corresponding matcher based on the ME virtual machine, like
57       page::compiler::peg::mecpu. Despite that it is actually mostly agnostic
58       regarding  the  instructions, users can choose any instruction set they
59       like.
60
61       The program under construction is held in a graph structure (See  pack‐
62       age  struct::graph)  during  assembly and subsequent manipulation, with
63       instructions represented by nodes, and the flow  of  execution  between
64       instructions explicitly encoded in the arcs between them.
65
66       In  this  model  jumps are not encoded explicitly, they are implicit in
67       the arcs. The generation of explicit jumps is left to any code convert‐
68       ing  the  graph  structure into a more conventional representation. The
69       same goes for branches. They are implicitly encoded by all instructions
70       which  have two outgoing arcs, whereas all other instructions have only
71       one outgoing arc. Their conditonality is handled by tagging their  out‐
72       going  arcs  with information about the conditions under which they are
73       taken.
74
75       While the graph the assembler operates on is supplied from the outside,
76       i.e. external, it does manage some internal state, namely:
77
78       [1]    The handle of the graph node most assembler operations will work
79              on, the anchor.
80
81       [2]    A mapping from arbitrary strings to  instructions.  I.e.  it  is
82              possible  to  label  an  instruction  during assembly, and later
83              recall that instruction by its label.
84
85       [3]    The condition code to use when creating  arcs  between  instruc‐
86              tions, which is one of always, ok, and fail.
87
88       [4]    The current operation mode, one of halt, okfail, and !okfail.
89
90       [5]    The name of a node in a tree. This, and the operation mode above
91              are the parts most heavily influenced by the needs of a  grammar
92              compiler, as they assume some basic program structures (selected
93              through the operation mode), and intertwine  the  graph  with  a
94              tree, like the AST for the grammar to be compiled.
95

DEFINITIONS

97       As  the  graph the assembler is operating on, and the tree it is inter‐
98       twined with, are supplied to the assembler from the outside it is  nec‐
99       essary  to  specify  the  API  expected  from them, and to describe the
100       structures expected and/or generated by the assembler in either.
101
102       [1]    Any graph object command used by the assembler  has  to  provide
103              the  API  as  specified  in  the  documentation  for the package
104              struct::graph.
105
106       [2]    Any tree object command used by the assembler has to provide the
107              API   as   specified   in  the  documentation  for  the  package
108              struct::tree.
109
110       [3]    Any instruction (node) generated by the  assembler  in  a  graph
111              will have at least two, and at most three attributes:
112
113              instruction
114                     The  value  of this attribute is the name of the instruc‐
115                     tion. The only names currently defined by  the  assembler
116                     are the three pseudo-instructions
117
118                     NOP    This  instruction  does  nothing. Useful for fixed
119                            framework nodes, unchanging jump destinations, and
120                            the like. No arguments.
121
122                     C      A  .NOP  to  allow the insertion of arbitrary com‐
123                            ments into the instruction stream, i.e. a  comment
124                            node. One argument, the text of the comment.
125
126                     BRA    A  .NOP  serving  as  explicitly coded conditional
127                            branch. No arguments.
128
129                     However we reserve the space of  all  instructions  whose
130                     names begin with a "." (dot) for future use by the assem‐
131                     bler.
132
133              arguments
134                     The value of this attribute is a  list  of  strings,  the
135                     arguments  of the instruction. The contents are dependent
136                     on the actual instruction and the assembler doesn't  know
137                     or care about them. This means for example that it has no
138                     builtin knowledge about what instruction need which argu‐
139                     ments and thus doesn't perform any type of checking.
140
141              expr   This  attribute is optional. When it is present its value
142                     is the name of a node in the tree  intertwined  with  the
143                     graph.
144
145       [4]    Any arc between two instructions will have one attribute:
146
147              condition
148                     The value of this attribute determines under which condi‐
149                     tion execution will take this arc. It is one  of  always,
150                     ok,  and  fail.  The first condition is used for all arcs
151                     which are the single outgoing arc of an instruction.  The
152                     other  two  are  used  for  the  two  outgoing arcs of an
153                     instruction which implicitly encode a branch.
154
155       [5]    A tree node given to the assembler for cross-referencing will be
156              written  to and given the following attributes, some fixed, some
157              dependent on the operation mode. All values will  be  references
158              to  nodes in the instruction graph. Some of the instruction will
159              expect some or specific sets of these attributes.
160
161              gas::entry
162                     Always written.
163
164              gas::exit
165                     Written for all modes but okfail.
166
167              gas::exit::ok
168                     Written for mode okfail.
169
170              gas::exit::fail
171                     Written for mode okfail.
172

API

174       ::grammar::me::cpu::gasm::begin g n ?mode? ?note?
175              This command starts the assembly of an instruction sequence, and
176              (re)initializes  the state of the assembler. After completion of
177              the instruction sequence use  ::grammar::me::cpu::gasm::done  to
178              finalize the assembler.
179
180              It will operate on the graph g in the specified mode (Default is
181              okfail). As part of the initialization it will always  create  a
182              standard  .NOP instruction and label it "entry". The creation of
183              the remaining standard instructions is mode-dependent:
184
185              halt   An "icf_halt" instruction labeled "exit/return".
186
187              !okfail
188                     An "icf_ntreturn" instruction labeled "exit/return".
189
190              okfail Two .NOP instructions labeled "exit/ok"  and  "exit/fail"
191                     respectively.
192
193              The note, if specified (default is not), is given to the "entry"
194              .NOP instruction.
195
196              The node reference  n  is  simply  stored  for  use  by  ::gram‐
197              mar::me::cpu::gasm::done.  It has to refer to a node in the tree
198              t argument of that command.
199
200              After the initialization is done the "entry" instruction will be
201              the anchor, and the condition code will be set to always.
202
203              The command returns the empy string as its result.
204
205       ::grammar::me::cpu::gasm::done --> t
206              This  command  finalizes the creation of an instruction sequence
207              and then clears the state of the assembler.  NOTE that this does
208              not  delete  any  of  the created instructions. They can be made
209              available to future begin/done cycles.  Further assembly will be
210              possible  only  after reinitialization of the system via ::gram‐
211              mar::me::cpu::gasm::begin.
212
213              Before the state is  cleared  selected  references  to  selected
214              instructions  will be written to attributes of the node n in the
215              tree t.  Which instructions are saved  is  mode-dependent.  Both
216              mode and the destination node n were specified during invokation
217              of ::grammar::me::cpu::gasm::begin.
218
219              Independent of the mode a reference to the  instruction  labeled
220              "entry" will be saved to the attribute gas::entry of n. The ref‐
221              erence to the node n will further be saved  into  the  attribute
222              "expr" of the "entry" instruction. Beyond that
223
224              halt   A reference to the instruction labeled "exit/return" will
225                     be saved to the attribute gas::exit of n.
226
227              okfail See halt.
228
229              !okfail
230                     Reference to the two instructions labeled  "exit/ok"  and
231                     "exit/fail" will be saved to the attributes gas::exit::ok
232                     and gas::exit::fail of n respectively.
233
234       The command returns the empy string as its result.
235
236       ::grammar::me::cpu::gasm::state
237              This command returns the current state  of  the  assembler.  Its
238              format  is  not  documented and considered to be internal to the
239              package.
240
241       ::grammar::me::cpu::gasm::state! s
242              This command takes a serialized assembler state s as returned by
243              ::grammar::me::cpu::gasm::state  and  makes it the current state
244              of the assembler.
245
246              Note that this may overwrite label definitions, however all non-
247              conflicting  label  definitions  in  the  state  before  are not
248              touched and merged with s.
249
250              The command returns the empty string as its result.
251
252       ::grammar::me::cpu::gasm::lift t dst = src
253              This command operates on the tree t. It copies the  contents  of
254              the  attributes  gas::entry,  gas::exit::ok  and gas::exit::fail
255              from the node src to the node dst.  It returns the empty  string
256              as its result.
257
258       ::grammar::me::cpu::gasm::Inline t node label
259              This command links an instruction sequence created by an earlier
260              begin/done pair into the current instruction sequence.
261
262              To this end it
263
264              [1]    reads the  instruction  references  from  the  attributes
265                     gas::entry,  gas::exit::ok,  and gas::exit::fail from the
266                     node n of the tree t and makes them available  to  assem‐
267                     bler  und  the  labels  label/entry,  label/exit::ok, and
268                     label/exit::fail respectively.
269
270              [2]    Creates an arc  from  the  anchor  to  the  node  labeled
271                     label/entry, and tags it with the current condition code.
272
273              [3]    Makes the node labeled label/exit/ok the new anchor.
274
275              The command returns the empty string as its result.
276
277       ::grammar::me::cpu::gasm::Cmd cmd ?arg...?
278              This  is the basic command to add instructions to the graph.  It
279              creates a new instruction of type cmd with the  given  arguments
280              arg...   If  the  anchor  was defined it will also create an arc
281              from the anchor to the new instruction using the current  condi‐
282              tion  code.   After  the  call  the  new instruction will be the
283              anchor and the current condition code will be set to always.
284
285              The command returns the empty string as its result.
286
287       ::grammar::me::cpu::gasm::Bra
288              This is a convenience command to create a  .BRA  pseudo-instruc‐
289              tion.  It  uses ::grammar::me::cpu::gasm::Cmd to actually create
290              the instruction and inherits its behaviour.
291
292       ::grammar::me::cpu::gasm::Nop text
293              This is a convenience command to create a  .NOP  pseudo-instruc‐
294              tion.  It  uses ::grammar::me::cpu::gasm::Cmd to actually create
295              the instruction and inherits its behaviour.  The  text  will  be
296              saved as the first and only argument of the new instruction.
297
298       ::grammar::me::cpu::gasm::Note text
299              This is a convenience command to create a .C pseudo-instruction,
300              i.e. a comment. It uses ::grammar::me::cpu::gasm::Cmd  to  actu‐
301              ally  create  the  instruction  and inherits its behaviour.  The
302              text will be saved as the first and only  argument  of  the  new
303              instruction.
304
305       ::grammar::me::cpu::gasm::Jmp label
306              This  command  creates an arc from the anchor to the instruction
307              labeled with label, and tags  with  the  the  current  condition
308              code.
309
310              The command returns the empty string as its result.
311
312       ::grammar::me::cpu::gasm::Exit
313              This  command  creates an arc from the anchor to one of the exit
314              instructions,  based  on  the  operation   mode   (see   ::gram‐
315              mar::me::cpu::gasm::begin),  and  tags it with current condition
316              code.
317
318              For mode okfail it  links  to  the  instruction  labeled  either
319              "exit/ok"  or  "exit/fail",  depending  on the current condition
320              code, and tagging it with the current  condition  code  For  the
321              other   two   modes   it   links   to  the  instruction  labeled
322              "exit/return", tagging it condition code always, independent the
323              current condition code.
324
325              The command returns the empty string as its result.
326
327       ::grammar::me::cpu::gasm::Who label
328              This command returns a reference to the instruction labeled with
329              label.
330
331       ::grammar::me::cpu::gasm::/Label name
332              This command labels the anchor with name.  Note that an instruc‐
333              tion can have more than one label.
334
335              The command returns the empty string as its result.
336
337       ::grammar::me::cpu::gasm::/Clear
338              This  command  clears the anchor, leaving it undefined, and fur‐
339              ther resets the current condition code to always.
340
341              The command returns the empty string as its result.
342
343       ::grammar::me::cpu::gasm::/Ok
344              This command sets the current condition code to ok.
345
346              The command returns the empty string as its result.
347
348       ::grammar::me::cpu::gasm::/Fail
349              This command sets the current condition code to fail.
350
351              The command returns the empty string as its result.
352
353       ::grammar::me::cpu::gasm::/At name
354              This command sets the anchor to  the  instruction  labeled  with
355              name, and further resets the current condition code to always.
356
357              The command returns the empty string as its result.
358
359       ::grammar::me::cpu::gasm::/CloseLoop
360              This  command marks the anchor as the last instruction in a loop
361              body, by creating the attribute LOOP.
362
363              The command returns the empty string as its result.
364

BUGS, IDEAS, FEEDBACK

366       This document, and the package it describes, will  undoubtedly  contain
367       bugs and other problems.  Please report such in the category grammar_me
368       of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].   Please
369       also  report any ideas for enhancements you may have for either package
370       and/or documentation.
371
372       When proposing code changes, please provide unified diffs, i.e the out‐
373       put of diff -u.
374
375       Note  further  that  attachments  are  strongly  preferred over inlined
376       patches. Attachments can be made by going  to  the  Edit  form  of  the
377       ticket  immediately  after  its  creation, and then using the left-most
378       button in the secondary navigation bar.
379

KEYWORDS

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

CATEGORY

384       Grammars and finite automata
385
387       Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>
388
389
390
391
392tcllib                                0.1            grammar::me::cpu::gasm(n)
Impressum