1pt::param(n) Parser Tools pt::param(n)
2______________________________________________________________________________
6
8 pt::param - PackRat Machine Specification
9
11 package require Tcl 8.5
12______________________________________________________________________________
14
16 Are you lost ? Do you have trouble understanding this document ? In
17 that case please read the overview provided by the Introduction to
18 Parser Tools. This document is the entrypoint to the whole system the
19 current package is a part of.
20 Welcome to the PackRat Machine (short: PARAM), a virtual machine geared
22 towards the support of recursive descent parsers, especially packrat
23 parsers. Towards this end it has features like the caching and reuse of
24 partial results, the caching of the encountered input, and the ability
25 to backtrack in both input and AST creation.
26 This document specifies the machine in terms of its architectural state
28 and instruction set.
29
31 Any PARAM implementation has to manage at least the following state:
32 Input (IN)
34 This is the channel the characters to process are read from.
35 This part of the machine's state is used and modified by the
37 instructions defined in the section Input Handling.
38 Current Character (CC)
40 The character from the input currently tested against its possi‐
41 ble alternatives.
42 This part of the machine's state is used and modified by the
44 instructions defined in the section Character Processing.
45 Current Location (CL)
47 The location of the current character in the input, as offset
48 relative to the beginning of the input. Character offsets are
49 counted from 0.
50 This part of the machine's state is used and modified by the
52 instructions defined in the sections Character Processing, Loca‐
53 tion Handling, and Nonterminal Execution.
54 Location Stack (LS)
56 A stack of locations in the input, saved for possible backtrack‐
57 ing.
58 This part of the machine's state is used and modified by the
60 instructions defined in the sections Character Processing, Loca‐
61 tion Handling, and Nonterminal Execution.
62 Status (ST)
64 The status of the last attempt of testing the input, indicating
65 either success or failure.
66 This part of the machine's state is used and modified by the
68 instructions defined in the sections Status Control, Character
69 Processing, and Nonterminal Execution.
70 Semantic Value (SV)
72 The current semantic value, either empty, or a node for AST con‐
73 structed from the input.
74 This part of the machine's state is used and modified by the
76 instructions defined in the sections Value Construction, and AST
77 Construction.
78 AST Reduction Stack (ARS)
80 The stack of partial ASTs constructed during the processing of
81 nonterminal symbols.
82 This part of the machine's state is used and modified by the
84 instructions defined in the sections Value Construction, and AST
85 Construction.
86 AST Stack (AS)
88 The stack of reduction stacks, saved for possible backtracking.
89 This part of the machine's state is used and modified by the
91 instructions defined in the sections Value Construction, and AST
92 Construction.
93 Error Status (ER)
95 The machine's current knowledge of errors. This is either empty,
96 or set to a pair of location in the input and the set of mes‐
97 sages for that location.
98 Note that this part of the machine's state can be set even if
100 the last test of the current character was successful. For exam‐
101 ple, the *-operator (matching a sub-expression zero or more
102 times) in a PEG is always successful, even if it encounters a
103 problem further in the input and has to backtrack. Such problems
104 must not be forgotten when continuing the parsing.
105 This part of the machine's state is used and modified by the
107 instructions defined in the sections Error Handling, Character
108 Processing, and Nonterminal Execution.
109 Error Stack (ES)
111 The stack of error stati, saved for backtracking. This enables
112 the machine to merge current and older error stati when perform‐
113 ing backtracking in choices after an failed match.
114 This part of the machine's state is used and modified by the
116 instructions defined in the sections Error Handling, Character
117 Processing, and Nonterminal Execution.
118 Nonterminal Cache (NC)
120 A cache of machine states keyed by pairs name of nonterminal
121 symbol and location in the input. Each pair (N, L) is associated
122 with a 4-tuple holding the values to use for CL, ST, SV, and ER
123 after the nonterminal N was parsed starting from the location L.
124 It is a performance aid for backtracking parsers, allowing them
125 to avoid an expensive reparsing of complex nonterminal symbols
126 if they have been encountered before at a given location.
127 The key location is where machine started the attempt to match
129 the named nonterminal symbol, and the location in the saved
130 4-tuple is where machine ended up after the attempt completed,
131 independent of the success of the attempt.
132 This part of the machine's state is used and modified by the
134 instructions defined in the section Nonterminal Execution.
135 Terminal Cache (TC)
137 A cache of characters read from IN, with their location in IN as
138 pair of line and column, keyed by the location in IN, this time
139 as character offset from the beginning of IN. It is a perfor‐
140 mance aid for backtracking parsers, allowing them to avoid a
141 possibly expensive rereading of characters from IN, or even
142 enabling backtracking at, i.e. in the case of IN not randomly
143 seekable.
144 This part of the machine's state is used and modified by the
146 instructions defined in the section Input Handling.
147
149 With the machine's architectural state specified it is now possible to
150 specify the instruction set operating on that state and to be imple‐
151 mented by any realization of the PARAM. The 37 instructions are grouped
152 roughly by the state they influence and/or query during their execu‐
153 tion.
154 INPUT HANDLING
156 The instructions in this section mainly access IN, pulling the charac‐
157 ters to process into the machine.
158 input_next msg
160 This method reads the next character, i.e. the character after
161 CL, from IN. If successful this character becomes CC, CL is
162 advanced by one, ES is cleared, and the operation is recorded as
163 a success in ST.
164 The operation may read the character from IN if the next charac‐
166 ter is not yet known to TC. If successful the new character is
167 stored in TC, with its location (line, column), and the opera‐
168 tion otherwise behaves as specified above. Future reads from the
169 same location, possible due to backtracking, will then be satis‐
170 fied from TC instead of IN.
171 If, on the other hand, the end of IN was reached, the operation
173 is recorded as failed in ST, CL is left unchanged, and the pair
174 of CL and msg becomes the new ES.
175 CHARACTER PROCESSING
177 The instructions in this section mainly access CC, testing it against
178 character classes, ranges, and individual characters.
179 test_alnum
181 This instruction implements the special PE operator "alnum",
182 which checks if CC falls into the character class of the same
183 name, or not.
184 Success and failure of the test are both recorded directly in
186 ST. Success further clears ES, wheras failure sets the pair of
187 CL and expected input (encoded as a leaf parsing expression) as
188 the new ES and then rewinds CL by one character, preparing the
189 machine for another parse attempt by a possible alternative.
190 test_alpha
192 This instruction implements the special PE operator "alpha",
193 which checks if CC falls into the character class of the same
194 name, or not.
195 Success and failure of the test are both recorded directly in
197 ST. Success further clears ES, wheras failure sets the pair of
198 CL and expected input (encoded as a leaf parsing expression) as
199 the new ES and then rewinds CL by one character, preparing the
200 machine for another parse attempt by a possible alternative.
201 test_ascii
203 This instruction implements the special PE operator "ascii",
204 which checks if CC falls into the character class of the same
205 name, or not.
206 Success and failure of the test are both recorded directly in
208 ST. Success further clears ES, wheras failure sets the pair of
209 CL and expected input (encoded as a leaf parsing expression) as
210 the new ES and then rewinds CL by one character, preparing the
211 machine for another parse attempt by a possible alternative.
212 test_char char
214 This instruction implements the character matching operator,
215 i.e. it checks if CC is char.
216 Success and failure of the test are both recorded directly in
218 ST. Success further clears ES, wheras failure sets the pair of
219 CL and expected input (encoded as a leaf parsing expression) as
220 the new ES and then rewinds CL by one character, preparing the
221 machine for another parse attempt by a possible alternative.
222 test_ddigit
224 This instruction implements the special PE operator "ddigit",
225 which checks if CC falls into the character class of the same
226 name, or not.
227 Success and failure of the test are both recorded directly in
229 ST. Success further clears ES, wheras failure sets the pair of
230 CL and expected input (encoded as a leaf parsing expression) as
231 the new ES and then rewinds CL by one character, preparing the
232 machine for another parse attempt by a possible alternative.
233 test_digit
235 This instruction implements the special PE operator "digit",
236 which checks if CC falls into the character class of the same
237 name, or not.
238 Success and failure of the test are both recorded directly in
240 ST. Success further clears ES, wheras failure sets the pair of
241 CL and expected input (encoded as a leaf parsing expression) as
242 the new ES and then rewinds CL by one character, preparing the
243 machine for another parse attempt by a possible alternative.
244 test_graph
246 This instruction implements the special PE operator "graph",
247 which checks if CC falls into the character class of the same
248 name, or not.
249 Success and failure of the test are both recorded directly in
251 ST. Success further clears ES, wheras failure sets the pair of
252 CL and expected input (encoded as a leaf parsing expression) as
253 the new ES and then rewinds CL by one character, preparing the
254 machine for another parse attempt by a possible alternative.
255 test_lower
257 This instruction implements the special PE operator "lower",
258 which checks if CC falls into the character class of the same
259 name, or not.
260 Success and failure of the test are both recorded directly in
262 ST. Success further clears ES, wheras failure sets the pair of
263 CL and expected input (encoded as a leaf parsing expression) as
264 the new ES and then rewinds CL by one character, preparing the
265 machine for another parse attempt by a possible alternative.
266 test_print
268 This instruction implements the special PE operator "print",
269 which checks if CC falls into the character class of the same
270 name, or not.
271 Success and failure of the test are both recorded directly in
273 ST. Success further clears ES, wheras failure sets the pair of
274 CL and expected input (encoded as a leaf parsing expression) as
275 the new ES and then rewinds CL by one character, preparing the
276 machine for another parse attempt by a possible alternative.
277 test_punct
279 This instruction implements the special PE operator "punct",
280 which checks if CC falls into the character class of the same
281 name, or not.
282 Success and failure of the test are both recorded directly in
284 ST. Success further clears ES, wheras failure sets the pair of
285 CL and expected input (encoded as a leaf parsing expression) as
286 the new ES and then rewinds CL by one character, preparing the
287 machine for another parse attempt by a possible alternative.
288 test_range chars chare
290 This instruction implements the range matching operator, i.e. it
291 checks if CC falls into the interval of characters spanned up by
292 the two characters from chars to chare, both inclusive.
293 Success and failure of the test are both recorded directly in
295 ST. Success further clears ES, wheras failure sets the pair of
296 CL and expected input (encoded as a leaf parsing expression) as
297 the new ES and then rewinds CL by one character, preparing the
298 machine for another parse attempt by a possible alternative.
299 test_space
301 This instruction implements the special PE operator "space",
302 which checks if CC falls into the character class of the same
303 name, or not.
304 Success and failure of the test are both recorded directly in
306 ST. Success further clears ES, wheras failure sets the pair of
307 CL and expected input (encoded as a leaf parsing expression) as
308 the new ES and then rewinds CL by one character, preparing the
309 machine for another parse attempt by a possible alternative.
310 test_upper
312 This instruction implements the special PE operator "upper",
313 which checks if CC falls into the character class of the same
314 name, or not.
315 Success and failure of the test are both recorded directly in
317 ST. Success further clears ES, wheras failure sets the pair of
318 CL and expected input (encoded as a leaf parsing expression) as
319 the new ES and then rewinds CL by one character, preparing the
320 machine for another parse attempt by a possible alternative.
321 test_wordchar
323 This instruction implements the special PE operator "wordchar",
324 which checks if CC falls into the character class of the same
325 name, or not.
326 Success and failure of the test are both recorded directly in
328 ST. Success further clears ES, wheras failure sets the pair of
329 CL and expected input (encoded as a leaf parsing expression) as
330 the new ES and then rewinds CL by one character, preparing the
331 machine for another parse attempt by a possible alternative.
332 test_xdigit
334 This instruction implements the special PE operator "xdigit",
335 which checks if CC falls into the character class of the same
336 name, or not.
337 Success and failure of the test are both recorded directly in
339 ST. Success further clears ES, wheras failure sets the pair of
340 CL and expected input (encoded as a leaf parsing expression) as
341 the new ES and then rewinds CL by one character, preparing the
342 machine for another parse attempt by a possible alternative.
343 ERROR HANDLING
345 The instructions in this section mainly access ER and ES.
346 error_clear
348 This instruction clears ER.
349 error_push
351 This instruction makes a copy of ER and pushes it on ES.
352 error_pop_merge
354 This instruction takes the topmost entry of ES and merges the
355 error status it contains with ES, making the result the new ES.
356 The merge is governed by four rules, with the merge result
358 [1] Empty if both states are empty.
360 [2] The non-empty state if only one of the two states is non-
362 empty.
363 [3] The state with the larger location, if the two states
365 specify different locations.
366 [4] The pair of the location shared by the two states, and
368 the set-union of their messages for states at the same
369 location.
370 error_nonterminal symbol
372 This is a guarded instruction. It does nothing if either ES is
373 empty, or if the location in ES is not just past the last loca‐
374 tion saved in LS. Otherwise it sets the pair of that location
375 and the nonterminal symbol as the new ES.
376 Note: In the above "just past" means "that location plus one",
378 or also "the location of the next character after that loca‐
379 tion".
380 STATUS CONTROL
382 The instructions in this section directly manipulate ST.
383 status_ok
385 This instruction sets ST to true, recording a success.
386 status_fail
388 This instruction sets ST to false, recording a failure.
389 status_negate
391 This instruction negates ST, turning a failure into a success
392 and vice versa.
393 LOCATION HANDLING
395 The instructions in this section access CL and LS.
396 loc_push
398 This instruction makes a copy of CL and pushes it on LS.
399 loc_pop_discard
401 This instructions pops the last saved location from LS.
402 loc_pop_rewind
404 This instruction pops the last saved location from LS and
405 restores it as CL.
406 NONTERMINAL EXECUTION
408 The instructions in this section access and manipulate NC.
409 symbol_restore symbol
411 This instruction checks if NC contains data for the nonterminal
412 symbol at CL, or not. The result of the instruction is a boolean
413 flag, with True indicating that data was found in the cache. In
414 that case the instruction has further updated the architectural
415 state of the machine with the cached information, namely CL, ST,
416 ER, and SV.
417 The method with which the instruction's result is transformed
419 into control flow is left undefined and the responsibility of
420 the implementation.
421 symbol_save symbol
423 This instructions saves the current settings of CL, ST, ER, and
424 SV in NC, using the pair of nonterminal symbol and the last
425 location saved in LS as key.
426 VALUE CONSTRUCTION
428 The instructions in this section manipulate SV.
429 value_clear
431 This instruction clears SV.
432 value_leaf symbol
434 This instruction constructs an AST node for symbol covering the
435 range of IN from one character after the last location saved on
436 LS to CL and stores it in SV. ...
437 value_reduce symbol
439 This instruction generally behaves like value_nonterminal_leaf,
440 except that it takes all AST nodes on ARS, if any, and makes
441 them the children of the new node, with the last node saved on
442 ARS becoming the right-most / last child. Note that ARS is not
443 modfied by this operation.
444 AST CONSTRUCTION
446 The instructions in this section manipulate ARS and AS.
447 ast_value_push
449 This instruction makes a copy of SV and pushes it on ARS.
450 ast_push
452 This instruction pushes the current state of ARS on AS and then
453 clears ARS.
454 ast_pop_rewind
456 This instruction pops the last entry saved on AS and restores it
457 as the new state of ARS.
458 ast_pop_discard
460 This instruction pops the last entry saved on AS.
461 CONTROL FLOW
463 Normally this section would contain the specifications of the control
464 flow instructions of the PARAM, i.e. (un)conditional jumps and the
465 like. However, this part of the PARAM is intentionally left unspeci‐
466 fied. This allows the implementations to freely choose how to implement
467 control flow.
468 The implementation of this machine in Parser Tools, i.e the package
470 pt::rde, is not only coded in Tcl, but also relies on Tcl commands to
471 provide it with control flow (instructions).
472
474 InstructionInputsOutputs
475 ======================= ===========================================
476 ast_pop_discardAS->AS
477 ast_pop_rewindAS->AS, ARS
478 ast_push ARS, AS->AS
479 ast_value_pushSV, ARS->ARS
480 ======================= ===========================================
481 error_clear-->ER
482 error_nonterminal symER, LS->ER
483 error_pop_merge ES, ER->ER
484 error_pushES, ER->ES
485 ======================= ===========================================
486 input_next msgIN->TC, CL, CC, ST, ER
487 ======================= ===========================================
488 loc_pop_discardLS->LS
489 loc_pop_rewindLS->LS, CL
490 loc_push CL, LS->LS
491 ======================= ===========================================
492 status_fail-->ST
493 status_negateST->ST
494 status_ok -->ST
495 ======================= ===========================================
496 symbol_restore symNC->CL, ST, ER, SV
497 symbol_save symCL, ST, ER, SV LS->NC
498 ======================= ===========================================
499 test_alnum CC->ST, ER
500 test_alphaCC->ST, ER
501 test_asciiCC->ST, ER
502 test_char charCC->ST, ER
503 test_ddigitCC->ST, ER
504 test_digitCC->ST, ER
505 test_graphCC->ST, ER
506 test_lowerCC->ST, ER
507 test_printCC->ST, ER
508 test_punctCC->ST, ER
509 test_range chars chareCC->ST, ER
510 test_spaceCC->ST, ER
511 test_upperCC->ST, ER
512 test_wordcharCC->ST, ER
513 test_xdigitCC->ST, ER
514 ======================= ===========================================
515 value_clear-->SV
516 value_leaf symbolLS, CL->SV
517 value_reduce symbolARS, LS, CL->SV
518 ======================= ===========================================
519
522 This document, and the package it describes, will undoubtedly contain
523 bugs and other problems. Please report such in the category pt of the
524 Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please also
525 report any ideas for enhancements you may have for either package
526 and/or documentation.
527 When proposing code changes, please provide unified diffs, i.e the out‐
529 put of diff -u.
530 Note further that attachments are strongly preferred over inlined
532 patches. Attachments can be made by going to the Edit form of the
533 ticket immediately after its creation, and then using the left-most
534 button in the secondary navigation bar.
535
537 EBNF, LL(k), PEG, TDPL, context-free languages, expression, grammar,
538 matching, parser, parsing expression, parsing expression grammar, push
539 down automaton, recursive descent, state, top-down parsing languages,
540 transducer, virtual machine
541
543 Parsing and Grammars
544
546 Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>
547tcllib 1 pt::param(n)