1grammar::me::cpu::gasm(n)Grammar operations and usagegrammar::me::cpu::gasm(n)
2______________________________________________________________________________
6
8 grammar::me::cpu::gasm - ME assembler
9
11 package require grammar::me::cpu::gasm ?0.1?
12 ::grammar::me::cpu::gasm::begin g n ?mode? ?note?
14 ::grammar::me::cpu::gasm::done --> t
16 ::grammar::me::cpu::gasm::state
18 ::grammar::me::cpu::gasm::state! s
20 ::grammar::me::cpu::gasm::lift t dst = src
22 ::grammar::me::cpu::gasm::Inline t node label
24 ::grammar::me::cpu::gasm::Cmd cmd ?arg...?
26 ::grammar::me::cpu::gasm::Bra
28 ::grammar::me::cpu::gasm::Nop text
30 ::grammar::me::cpu::gasm::Note text
32 ::grammar::me::cpu::gasm::Jmp label
34 ::grammar::me::cpu::gasm::Exit
36 ::grammar::me::cpu::gasm::Who label
38 ::grammar::me::cpu::gasm::/Label name
40 ::grammar::me::cpu::gasm::/Clear
42 ::grammar::me::cpu::gasm::/Ok
44 ::grammar::me::cpu::gasm::/Fail
46 ::grammar::me::cpu::gasm::/At name
48 ::grammar::me::cpu::gasm::/CloseLoop
50______________________________________________________________________________
52
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 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 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 While the graph the assembler operates on is supplied from the outside,
76 i.e. external, it does manage some internal state, namely:
77 [1] The handle of the graph node most assembler operations will work
79 on, the anchor.
80 [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 [3] The condition code to use when creating arcs between instruc‐
86 tions, which is one of always, ok, and fail.
87 [4] The current operation mode, one of halt, okfail, and !okfail.
89 [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
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 [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 [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 [3] Any instruction (node) generated by the assembler in a graph
111 will have at least two, and at most three attributes:
112 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 NOP This instruction does nothing. Useful for fixed
119 framework nodes, unchanging jump destinations, and
120 the like. No arguments.
121 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 BRA A .NOP serving as explicitly coded conditional
127 branch. No arguments.
128 However we reserve the space of all instructions whose
130 names begin with a "." (dot) for future use by the assem‐
131 bler.
132 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 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 [4] Any arc between two instructions will have one attribute:
146 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 [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 gas::entry
162 Always written.
163 gas::exit
165 Written for all modes but okfail.
166 gas::exit::ok
168 Written for mode okfail.
169 gas::exit::fail
171 Written for mode okfail.
172
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 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 halt An "icf_halt" instruction labeled "exit/return".
186 !okfail
188 An "icf_ntreturn" instruction labeled "exit/return".
189 okfail Two .NOP instructions labeled "exit/ok" and "exit/fail"
191 respectively.
192 The note, if specified (default is not), is given to the "entry"
194 .NOP instruction.
195 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 After the initialization is done the "entry" instruction will be
201 the anchor, and the condition code will be set to always.
202 The command returns the empy string as its result.
204 ::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 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 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 halt A reference to the instruction labeled "exit/return" will
225 be saved to the attribute gas::exit of n.
226 okfail See halt.
228 !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 The command returns the empy string as its result.
235 ::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 ::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 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 The command returns the empty string as its result.
251 ::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 ::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 To this end it
263 [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 [2] Creates an arc from the anchor to the node labeled
271 label/entry, and tags it with the current condition code.
272 [3] Makes the node labeled label/exit/ok the new anchor.
274 The command returns the empty string as its result.
276 ::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 The command returns the empty string as its result.
286 ::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 ::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 ::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 ::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 The command returns the empty string as its result.
311 ::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 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 The command returns the empty string as its result.
326 ::grammar::me::cpu::gasm::Who label
328 This command returns a reference to the instruction labeled with
329 label.
330 ::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 The command returns the empty string as its result.
336 ::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 The command returns the empty string as its result.
342 ::grammar::me::cpu::gasm::/Ok
344 This command sets the current condition code to ok.
345 The command returns the empty string as its result.
347 ::grammar::me::cpu::gasm::/Fail
349 This command sets the current condition code to fail.
350 The command returns the empty string as its result.
352 ::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 The command returns the empty string as its result.
358 ::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 The command returns the empty string as its result.
364
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 When proposing code changes, please provide unified diffs, i.e the out‐
373 put of diff -u.
374 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
381 assembler, grammar, graph, parsing, tree, virtual machine
382
384 Grammars and finite automata
385
387 Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>
388tcllib 0.1 grammar::me::cpu::gasm(n)