1pt::rde(n) Parser Tools pt::rde(n)
2______________________________________________________________________________
6
8 pt::rde - Parsing Runtime Support, PARAM based
9
11 package require Tcl 8.5
12 package require pt::rde ?1.1?
14 package require snit
16 package require struct::stack 1.5
18 package require pt::ast 1.1
20 ::pt::rde objectName
22 objectName destroy
24 objectName reset chan
26 objectName complete
28 objectName chan
30 objectName line
32 objectName column
34 objectName current
36 objectName location
38 objectName locations
40 objectName ok
42 objectName value
44 objectName error
46 objectName errors
48 objectName tokens ?from ?to??
50 objectName symbols
52 objectName known
54 objectName reducible
56 objectName asts
58 objectName ast
60 objectName position loc
62 objectName i_input_next msg
64 objectName i_test_alnum
66 objectName i_test_alpha
68 objectName i_test_ascii
70 objectName i_test_char char
72 objectName i_test_ddigit
74 objectName i_test_digit
76 objectName i_test_graph
78 objectName i_test_lower
80 objectName i_test_print
82 objectName i_test_punct
84 objectName i_test_range chars chare
86 objectName i_test_space
88 objectName i_test_upper
90 objectName i_test_wordchar
92 objectName i_test_xdigit
94 objectName i_error_clear
96 objectName i_error_push
98 objectName i_error_pop_merge
100 objectName i_error_nonterminal symbol
102 objectName i_status_ok
104 objectName i_status_fail
106 objectName i_status_negate
108 objectName i_loc_push
110 objectName i_loc_pop_discard
112 objectName i_loc_pop_rewind
114 objectName i:ok_loc_pop_rewind
116 objectName i_loc_pop_rewind/discard
118 objectName i_symbol_restore symbol
120 objectName i_symbol_save symbol
122 objectName i_value_clear
124 objectName i_value_clear/leaf
126 objectName i_value_clear/reduce
128 objectName i:ok_ast_value_push
130 objectName i_ast_push
132 objectName i_ast_pop_rewind
134 objectName i:fail_ast_pop_rewind
136 objectName i_ast_pop_rewind/discard
138 objectName i_ast_pop_discard
140 objectName i_ast_pop_discard/rewind
142 objectName i:ok_continue
144 objectName i:fail_continue
146 objectName i:fail_return
148 objectName i:ok_return
150 objectName si:void_state_push
152 objectName si:void2_state_push
154 objectName si:value_state_push
156 objectName si:void_state_merge
158 objectName si:void_state_merge_ok
160 objectName si:value_state_merge
162 objectName si:value_notahead_start
164 objectName si:void_notahead_exit
166 objectName si:value_notahead_exit
168 objectName si:kleene_abort
170 objectName si:kleene_close
172 objectName si:voidvoid_branch
174 objectName si:voidvalue_branch
176 objectName si:valuevoid_branch
178 objectName si:valuevalue_branch
180 objectName si:voidvoid_part
182 objectName si:voidvalue_part
184 objectName si:valuevalue_part
186 objectName si:value_symbol_start symbol
188 objectName si:value_void_symbol_start symbol
190 objectName si:void_symbol_start symbol
192 objectName si:void_void_symbol_start symbol
194 objectName si:reduce_symbol_end symbol
196 objectName si:void_leaf_symbol_end symbol
198 objectName si:value_leaf_symbol_end symbol
200 objectName si:value_clear_symbol_end symbol
202 objectName si:void_clear_symbol_end symbol
204 objectName si:next_char tok
206 objectName si:next_range toks toke
208 objectName si:next_alnum
210 objectName si:next_alpha
212 objectName si:next_ascii
214 objectName si:next_ddigit
216 objectName si:next_digit
218 objectName si:next_graph
220 objectName si:next_lower
222 objectName si:next_print
224 objectName si:next_punct
226 objectName si:next_space
228 objectName si:next_upper
230 objectName si:next_wordchar
232 objectName si:next_xdigit
234______________________________________________________________________________
236
238 Are you lost ? Do you have trouble understanding this document ? In
239 that case please read the overview provided by the Introduction to
240 Parser Tools. This document is the entrypoint to the whole system the
241 current package is a part of.
242 This package provides a class whose instances provide the runtime sup‐
244 port for recursive descent parsers with backtracking, as is needed for
245 the execution of, for example, parsing expression grammars. It imple‐
246 ments the PackRat Machine Specification, as such that document is
247 required reading to understand both this manpage, and the package
248 itself. The description below does make numerous shorthand references
249 to the PARAM's instructions and the various parts of its architectural
250 state.
251 The package resides in the Execution section of the Core Layer of
253 Parser Tools.
254 IMAGE: arch_core_transform
256 Note: This package not only has the standard Tcl implementation, but
258 also an accelerator, i.e. a C implementation, based on Critcl.
259 CLASS API
261 The package exports the API described here.
262 ::pt::rde objectName
264 The command creates a new runtime object for a recursive descent
265 parser with backtracking and returns the fully qualified name of
266 the object command as its result. The API of this object command
267 is described in the section Object API. It may be used to invoke
268 various operations on the object.
269 OBJECT API
271 All objects created by this package provide the following 63 methods
272 for the manipulation and querying of their state, which is, in essence
273 the architectural state of a PARAM.
274 First some general methods and the state accessors.
276 objectName destroy
278 This method destroys the object, releasing all claimed memory,
279 and deleting the associated object command.
280 objectName reset chan
282 This method resets the state of the runtme to its defaults, pre‐
283 paring it for the parsing of the character in the channel chan,
284 which becomes IN.
285 Note here that the Parser Tools are based on Tcl 8.5+. In other
287 words, the channel argument is not restricted to files, sockets,
288 etc. We have the full power of reflected channels available.
289 It should also be noted that the parser pulls the characters
291 from the input stream as it needs them. If a parser created by
292 this package has to be operated in a push aka event-driven man‐
293 ner it will be necessary to go to Tcl 8.6+ and use the corou‐
294 tine::auto to wrap it into a coroutine where read is properly
295 changed for push-operation.
296 objectName complete
298 This method completes parsing, either returning the AST made
299 from the elements of ARS, or throwing an error containing the
300 current ER.
301 objectName chan
303 This method returns the handle of the channel which is IN.
304 objectName line
306 This method returns the line number for the position IN is cur‐
307 rently at. Note that this may not match with the line number for
308 CL, due to backtracking.
309 objectName column
311 This method returns the column for the position IN is currently
312 at. Note that this may not match with the column for CL, due to
313 backtracking.
314 objectName current
316 This method returns CC.
317 objectName location
319 This method returns CL.
320 objectName locations
322 This method returns the LS. The topmost entry of the stack will
323 be the first element of the returned list.
324 objectName ok
326 This method returns ST.
327 objectName value
329 This method returns SV.
330 objectName error
332 This method returns ER. This is either the empty string for an
333 empty ER, or a list of 2 elements, the location the error is
334 for, and a set of messages which specify which symbols were
335 expected at the location. The messages are encoded as one of the
336 possible atomic parsing expressions (special operators, termi‐
337 nal, range, and nonterminal operator).
338 objectName errors
340 This method returns ES. The topmost entry of the stack will be
341 the first element of the returned list. Each entry is encoded as
342 described for error.
343 objectName tokens ?from ?to??
345 This method returns the part of TC for the range of locations of
346 IN starting at from and ending at to. If to is not specified it
347 is taken as identical to from. If neither argument is specified
348 the whole of TC is returned.
349 Each token in the returned list is a list of three elements
351 itself, containing the character at the location, and the asso‐
352 ciated line and column numbers, in this order.
353 objectName symbols
355 This method returns a dictionary containing NC. Keys are two-
356 element lists containing nonterminal symbol and location, in
357 this order. The values are 4-tuples containing CL, ST, ER, and
358 SV, in this order. ER is encoded as specified for the method
359 error.
360 objectName known
362 This method returns a list containing the keys of SC. They are
363 encoded in the same manner as is done by method symbols.
364 objectName reducible
366 This method returns ARS. The topmost entry of the stack will be
367 the first element of the returned list
368 objectName asts
370 This method returns AS. The topmost entry of the stack will be
371 the first element of the returned list
372 objectName ast
374 This is a convenience method returning the topmost element of
375 ARS.
376 objectName position loc
378 This method returns the line and column numbers for the speci‐
379 fied location of IN, assuming that this location has already
380 been reached during the parsing process.
381 The following methods implement all PARAM instructions. They all have
383 the prefix "i_".
384 The control flow is mainly provided by Tcl's builtin commands, like if,
386 while, etc., plus a few guarded variants of PARAM instructions and Tcl
387 commands.. That means that these instruction variants will do nothing
388 if their guard condition is not fulfilled. They can be recognized by
389 the prefix "i:ok_" and "i:fail_", which denote the value ST has to have
390 for the instruction to execute.
391 The instructions are listed in the same order they occur in the PackRat
393 Machine Specification, with the guard variants listed after their regu‐
394 lar implementation, if any, or in their place.
395 objectName i_input_next msg
397 This method implements the PARAM instruction input_next.
398 objectName i_test_alnum
400 This method implements the PARAM instruction test_alnum.
401 objectName i_test_alpha
403 This method implements the PARAM instruction test_alpha.
404 objectName i_test_ascii
406 This method implements the PARAM instruction test_ascii.
407 objectName i_test_char char
409 This method implements the PARAM instruction test_char.
410 objectName i_test_ddigit
412 This method implements the PARAM instruction test_ddigit.
413 objectName i_test_digit
415 This method implements the PARAM instruction test_digit.
416 objectName i_test_graph
418 This method implements the PARAM instruction test_graph.
419 objectName i_test_lower
421 This method implements the PARAM instruction test_lower.
422 objectName i_test_print
424 This method implements the PARAM instruction test_print.
425 objectName i_test_punct
427 This method implements the PARAM instruction test_punct.
428 objectName i_test_range chars chare
430 This method implements the PARAM instruction test_range.
431 objectName i_test_space
433 This method implements the PARAM instruction test_space.
434 objectName i_test_upper
436 This method implements the PARAM instruction test_upper.
437 objectName i_test_wordchar
439 This method implements the PARAM instruction test_wordchar.
440 objectName i_test_xdigit
442 This method implements the PARAM instruction test_xdigit.
443 objectName i_error_clear
445 This method implements the PARAM instruction error_clear.
446 objectName i_error_push
448 This method implements the PARAM instruction error_push.
449 objectName i_error_pop_merge
451 This method implements the PARAM instruction error_pop_merge.
452 objectName i_error_nonterminal symbol
454 This method implements the PARAM instruction error_nonterminal.
455 objectName i_status_ok
457 This method implements the PARAM instruction status_ok.
458 objectName i_status_fail
460 This method implements the PARAM instruction status_fail.
461 objectName i_status_negate
463 This method implements the PARAM instruction status_negate.
464 objectName i_loc_push
466 This method implements the PARAM instruction loc_push.
467 objectName i_loc_pop_discard
469 This method implements the PARAM instruction loc_pop_discard.
470 objectName i_loc_pop_rewind
472 This method implements the PARAM instruction loc_pop_rewind.
473 objectName i:ok_loc_pop_rewind
475 This guarded method, a variant of i_loc_pop_rewind, executes
476 only for "ST == ok".
477 objectName i_loc_pop_rewind/discard
479 This method is a convenient combination of control flow and the
480 two PARAM instructions loc_pop_rewind and loc_pop_discard. The
481 former is executed for "ST == fail", the latter for "ST == ok".
482 objectName i_symbol_restore symbol
484 This method implements the PARAM instruction symbol_restore.
485 The boolean result of the check is returned as the result of the
487 method and can be used with standard Tcl control flow commands.
488 objectName i_symbol_save symbol
490 This method implements the PARAM instruction symbol_save.
491 objectName i_value_clear
493 This method implements the PARAM instruction value_clear.
494 objectName i_value_clear/leaf
496 This method is a convenient combination of control flow and the
497 two PARAM instructions value_clear and value_leaf. The former is
498 executed for "ST == fail", the latter for "ST == ok".
499 objectName i_value_clear/reduce
501 This method is a convenient combination of control flow and the
502 two PARAM instructions value_clear and value_reduce. The former
503 is executed for "ST == fail", the latter for "ST == ok".
504 objectName i:ok_ast_value_push
506 This method implements a guarded variant of the the PARAM
507 instruction ast_value_push, which executes only for "ST == ok".
508 objectName i_ast_push
510 This method implements the PARAM instruction ast_push.
511 objectName i_ast_pop_rewind
513 This method implements the PARAM instruction ast_pop_rewind.
514 objectName i:fail_ast_pop_rewind
516 This guarded method, a variant of i_ast_pop_rewind, executes
517 only for "ST == fail".
518 objectName i_ast_pop_rewind/discard
520 This method is a convenient combination of control flow and the
521 two PARAM instructions ast_pop_rewind and ast_pop_discard. The
522 former is executed for "ST == fail", the latter for "ST == ok".
523 objectName i_ast_pop_discard
525 This method implements the PARAM instruction ast_pop_discard.
526 objectName i_ast_pop_discard/rewind
528 This method is a convenient combination of control flow and the
529 two PARAM instructions ast_pop_discard and ast_pop_rewind. The
530 former is executed for "ST == fail", the latter for "ST == ok".
531 objectName i:ok_continue
533 This guarded method executes only for "ST == ok". Then it aborts
534 the current iteration of the innermost loop in the calling Tcl
535 procedure.
536 objectName i:fail_continue
538 This guarded method executes only for "ST == fail". Then it
539 aborts the current iteration of the innermost loop in the call‐
540 ing Tcl procedure.
541 objectName i:fail_return
543 This guarded method executes only for "ST == fail". Then it
544 aborts the calling Tcl procedure.
545 objectName i:ok_return
547 This guarded method executes only for "ST == ok". Then it aborts
548 the calling Tcl procedure.
549 The next set of methods are super instructions, meaning that each
551 implements a longer sequence of instructions commonly used in parsers.
552 The combinated instructions of the previous set, i.e. those with names
553 matching the pattern "i_*/*", are actually super instructions as well,
554 albeit with limited scope, handling 2 instructions with their control
555 flow. The upcoming set is much broader in scope, folding as much as six
556 or more PARAM instructions into a single method call.
557 In this we can see the reasoning behind their use well:
559 [1] By using less instructions the generated parsers become smaller,
561 as the common parts are now truly part of the common runtime,
562 and not explicitly written in the parser's code over and over
563 again.
564 [2] Using less instructions additionally reduces the overhead asso‐
566 ciated with calls into the runtime, i.e. the cost of method dis‐
567 patch and of setting up the variable context.
568 [3] Another effect of the super instructions is that their internals
570 can be optimized as well, especially regarding control flow, and
571 stack use, as the runtime internals are accessible to all
572 instructions folded into the sequence.
573 objectName si:void_state_push
575 This method combines
576 i_loc_push
579 i_error_clear
580 i_error_push
581 Parsers use it at the beginning of void sequences and choices
584 with a void initial branch.
585 objectName si:void2_state_push
587 This method combines
588 i_loc_push
591 i_error_clear
592 i_error_push
593 Parsers use it at the beginning of optional and repeated expres‐
596 sions.
597 objectName si:value_state_push
599 This method combines
600 i_ast_push
603 i_loc_push
604 i_error_clear
605 i_error_push
606 Parsers use it at the beginning of sequences generating an AST
609 and choices with an initial branch generating an AST.
610 objectName si:void_state_merge
612 This method combines
613 i_error_pop_merge
616 i_loc_pop_rewind/discard
617 Parsers use it at the end of void sequences and choices whose
620 last branch is void.
621 objectName si:void_state_merge_ok
623 This method combines
624 i_error_pop_merge
627 i_loc_pop_rewind/discard
628 i_status_ok
629 Parsers use it at the end of optional expressions
632 objectName si:value_state_merge
634 This method combines
635 i_error_pop_merge
638 i_ast_pop_rewind/discard
639 i_loc_pop_rewind/discard
640 Parsers use it at the end of sequences generating ASTs and
643 choices whose last branch generates an AST
644 objectName si:value_notahead_start
646 This method combines
647 i_loc_push
650 i_ast_push
651 Parsers use it at the beginning of negative lookahead predicates
654 which generate ASTs.
655 objectName si:void_notahead_exit
657 This method combines
658 i_loc_pop_rewind
661 i_status_negate
662 Parsers use it at the end of void negative lookahead predicates.
665 objectName si:value_notahead_exit
667 This method combines
668 i_ast_pop_discard/rewind
671 i_loc_pop_rewind
672 i_status_negate
673 Parsers use it at the end of negative lookahead predicates which
676 generate ASTs.
677 objectName si:kleene_abort
679 This method combines
680 i_loc_pop_rewind/discard
683 i:fail_return
684 Parsers use it to stop a positive repetition when its first,
687 required, expression fails.
688 objectName si:kleene_close
690 This method combines
691 i_error_pop_merge
694 i_loc_pop_rewind/discard
695 i:fail_status_ok
696 i:fail_return
697 Parsers use it at the end of repetitions.
700 objectName si:voidvoid_branch
702 This method combines
703 i_error_pop_merge
706 i:ok_loc_pop_discard
707 i:ok_return
708 i_loc_rewind
709 i_error_push
710 Parsers use it when transiting between branches of a choice when
713 both are void.
714 objectName si:voidvalue_branch
716 This method combines
717 i_error_pop_merge
720 i:ok_loc_pop_discard
721 i:ok_return
722 i_ast_push
723 i_loc_rewind
724 i_error_push
725 Parsers use it when transiting between branches of a choice when
728 the failing branch is void, and the next to test generates an
729 AST.
730 objectName si:valuevoid_branch
732 This method combines
733 i_error_pop_merge
736 i_ast_pop_rewind/discard
737 i:ok_loc_pop_discard
738 i:ok_return
739 i_loc_rewind
740 i_error_push
741 Parsers use it when transiting between branches of a choice when
744 the failing branch generates an AST, and the next to test is
745 void.
746 objectName si:valuevalue_branch
748 This method combines
749 i_error_pop_merge
752 i_ast_pop_discard
753 i:ok_loc_pop_discard
754 i:ok_return
755 i_ast_rewind
756 i_loc_rewind
757 i_error_push
758 Parsers use it when transiting between branches of a choice when
761 both generate ASTs.
762 objectName si:voidvoid_part
764 This method combines
765 i_error_pop_merge
768 i:fail_loc_pop_rewind
769 i:fail_return
770 i_error_push
771 Parsers use it when transiting between parts of a sequence and
774 both are void.
775 objectName si:voidvalue_part
777 This method combines
778 i_error_pop_merge
781 i:fail_loc_pop_rewind
782 i:fail_return
783 i_ast_push
784 i_error_push
785 Parsers use it when transiting between parts of a sequence and
788 the sucessfully matched part is void, and after it an AST is
789 generated.
790 objectName si:valuevalue_part
792 This method combines
793 i_error_pop_merge
796 i:fail_ast_pop_rewind
797 i:fail_loc_pop_rewind
798 i:fail_return
799 i_error_push
800 Parsers use it when transiting between parts of a sequence and
803 both parts generate ASTs.
804 objectName si:value_symbol_start symbol
806 This method combines
807 if/found? i_symbol_restore $symbol
810 i:found:ok_ast_value_push
811 i:found_return
812 i_loc_push
813 i_ast_push
814 Parsers use it at the beginning of a nonterminal symbol generat‐
817 ing an AST, whose right-hand side may have generated an AST as
818 well.
819 objectName si:value_void_symbol_start symbol
821 This method combines
822 if/found? i_symbol_restore $symbol
825 i:found:ok_ast_value_push
826 i:found_return
827 i_loc_push
828 i_ast_push
829 Parsers use it at the beginning of a void nonterminal symbol
832 whose right-hand side may generate an AST.
833 objectName si:void_symbol_start symbol
835 This method combines
836 if/found? i_symbol_restore $symbol
839 i:found_return
840 i_loc_push
841 i_ast_push
842 Parsers use it at the beginning of a nonterminal symbol generat‐
845 ing an AST whose right-hand side is void.
846 objectName si:void_void_symbol_start symbol
848 This method combines
849 if/found? i_symbol_restore $symbol
852 i:found_return
853 i_loc_push
854 Parsers use it at the beginning of a void nonterminal symbol
857 whose right-hand side is void as well.
858 objectName si:reduce_symbol_end symbol
860 This method combines
861 i_value_clear/reduce $symbol
864 i_symbol_save $symbol
865 i_error_nonterminal $symbol
866 i_ast_pop_rewind
867 i_loc_pop_discard
868 i:ok_ast_value_push
869 Parsers use it at the end of a non-terminal symbol generating an
872 AST using the AST generated by the right-hand side as child.
873 objectName si:void_leaf_symbol_end symbol
875 This method combines
876 i_value_clear/leaf $symbol
879 i_symbol_save $symbol
880 i_error_nonterminal $symbol
881 i_loc_pop_discard
882 i:ok_ast_value_push
883 Parsers use it at the end of a non-terminal symbol generating an
886 AST whose right-hand side is void.
887 objectName si:value_leaf_symbol_end symbol
889 This method combines
890 i_value_clear/leaf $symbol
893 i_symbol_save $symbol
894 i_error_nonterminal $symbol
895 i_loc_pop_discard
896 i_ast_pop_rewind
897 i:ok_ast_value_push
898 Parsers use it at the end of a non-terminal symbol generating an
901 AST discarding the AST generated by the right-hand side.
902 objectName si:value_clear_symbol_end symbol
904 This method combines
905 i_value_clear
908 i_symbol_save $symbol
909 i_error_nonterminal $symbol
910 i_loc_pop_discard
911 i_ast_pop_rewind
912 Parsers use it at the end of a void non-terminal symbol, dis‐
915 carding the AST generated by the right-hand side.
916 objectName si:void_clear_symbol_end symbol
918 This method combines
919 i_value_clear
922 i_symbol_save $symbol
923 i_error_nonterminal $symbol
924 i_loc_pop_discard
925 Parsers use it at the end of a void non-terminal symbol with a
928 void right-hand side.
929 objectName si:next_char tok
931 objectName si:next_range toks toke
933 objectName si:next_alnum
935 objectName si:next_alpha
937 objectName si:next_ascii
939 objectName si:next_ddigit
941 objectName si:next_digit
943 objectName si:next_graph
945 objectName si:next_lower
947 objectName si:next_print
949 objectName si:next_punct
951 objectName si:next_space
953 objectName si:next_upper
955 objectName si:next_wordchar
957 objectName si:next_xdigit
959 These methods all combine
960 i_input_next $msg
963 i:fail_return
964 with the appropriate i_test_xxx instruction. Parsers use them
967 for handling atomic expressions.
968
970 This document, and the package it describes, will undoubtedly contain
971 bugs and other problems. Please report such in the category pt of the
972 Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please also
973 report any ideas for enhancements you may have for either package
974 and/or documentation.
975 When proposing code changes, please provide unified diffs, i.e the out‐
977 put of diff -u.
978 Note further that attachments are strongly preferred over inlined
980 patches. Attachments can be made by going to the Edit form of the
981 ticket immediately after its creation, and then using the left-most
982 button in the secondary navigation bar.
983
985 EBNF, LL(k), PEG, TDPL, context-free languages, expression, grammar,
986 matching, parser, parsing expression, parsing expression grammar, push
987 down automaton, recursive descent, state, top-down parsing languages,
988 transducer
989
991 Parsing and Grammars
992
994 Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>
995tcllib 1.1 pt::rde(n)