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 re‐
247 quired reading to understand both this manpage, and the package itself.
248 The description below does make numerous shorthand references to the
249 PARAM's instructions and the various parts of its architectural state.
250 The package resides in the Execution section of the Core Layer of
252 Parser Tools.
253 IMAGE: arch_core_transform
255 Note: This package not only has the standard Tcl implementation, but
257 also an accelerator, i.e. a C implementation, based on Critcl.
258 CLASS API
260 The package exports the API described here.
261 ::pt::rde objectName
263 The command creates a new runtime object for a recursive descent
264 parser with backtracking and returns the fully qualified name of
265 the object command as its result. The API of this object command
266 is described in the section Object API. It may be used to invoke
267 various operations on the object.
268 OBJECT API
270 All objects created by this package provide the following 63 methods
271 for the manipulation and querying of their state, which is, in essence
272 the architectural state of a PARAM.
273 First some general methods and the state accessors.
275 objectName destroy
277 This method destroys the object, releasing all claimed memory,
278 and deleting the associated object command.
279 objectName reset chan
281 This method resets the state of the runtme to its defaults, pre‐
282 paring it for the parsing of the character in the channel chan,
283 which becomes IN.
284 Note here that the Parser Tools are based on Tcl 8.5+. In other
286 words, the channel argument is not restricted to files, sockets,
287 etc. We have the full power of reflected channels available.
288 It should also be noted that the parser pulls the characters
290 from the input stream as it needs them. If a parser created by
291 this package has to be operated in a push aka event-driven man‐
292 ner it will be necessary to go to Tcl 8.6+ and use the corou‐
293 tine::auto to wrap it into a coroutine where read is properly
294 changed for push-operation.
295 objectName complete
297 This method completes parsing, either returning the AST made
298 from the elements of ARS, or throwing an error containing the
299 current ER.
300 objectName chan
302 This method returns the handle of the channel which is IN.
303 objectName line
305 This method returns the line number for the position IN is cur‐
306 rently at. Note that this may not match with the line number for
307 CL, due to backtracking.
308 objectName column
310 This method returns the column for the position IN is currently
311 at. Note that this may not match with the column for CL, due to
312 backtracking.
313 objectName current
315 This method returns CC.
316 objectName location
318 This method returns CL.
319 objectName locations
321 This method returns the LS. The topmost entry of the stack will
322 be the first element of the returned list.
323 objectName ok
325 This method returns ST.
326 objectName value
328 This method returns SV.
329 objectName error
331 This method returns ER. This is either the empty string for an
332 empty ER, or a list of 2 elements, the location the error is
333 for, and a set of messages which specify which symbols were ex‐
334 pected at the location. The messages are encoded as one of the
335 possible atomic parsing expressions (special operators, termi‐
336 nal, range, and nonterminal operator).
337 objectName errors
339 This method returns ES. The topmost entry of the stack will be
340 the first element of the returned list. Each entry is encoded as
341 described for error.
342 objectName tokens ?from ?to??
344 This method returns the part of TC for the range of locations of
345 IN starting at from and ending at to. If to is not specified it
346 is taken as identical to from. If neither argument is specified
347 the whole of TC is returned.
348 Each token in the returned list is a list of three elements it‐
350 self, containing the character at the location, and the associ‐
351 ated line and column numbers, in this order.
352 objectName symbols
354 This method returns a dictionary containing NC. Keys are two-el‐
355 ement lists containing nonterminal symbol and location, in this
356 order. The values are 4-tuples containing CL, ST, ER, and SV, in
357 this order. ER is encoded as specified for the method error.
358 objectName known
360 This method returns a list containing the keys of SC. They are
361 encoded in the same manner as is done by method symbols.
362 objectName reducible
364 This method returns ARS. The topmost entry of the stack will be
365 the first element of the returned list
366 objectName asts
368 This method returns AS. The topmost entry of the stack will be
369 the first element of the returned list
370 objectName ast
372 This is a convenience method returning the topmost element of
373 ARS.
374 objectName position loc
376 This method returns the line and column numbers for the speci‐
377 fied location of IN, assuming that this location has already
378 been reached during the parsing process.
379 The following methods implement all PARAM instructions. They all have
381 the prefix "i_".
382 The control flow is mainly provided by Tcl's builtin commands, like if,
384 while, etc., plus a few guarded variants of PARAM instructions and Tcl
385 commands.. That means that these instruction variants will do nothing
386 if their guard condition is not fulfilled. They can be recognized by
387 the prefix "i:ok_" and "i:fail_", which denote the value ST has to have
388 for the instruction to execute.
389 The instructions are listed in the same order they occur in the PackRat
391 Machine Specification, with the guard variants listed after their regu‐
392 lar implementation, if any, or in their place.
393 objectName i_input_next msg
395 This method implements the PARAM instruction input_next.
396 objectName i_test_alnum
398 This method implements the PARAM instruction test_alnum.
399 objectName i_test_alpha
401 This method implements the PARAM instruction test_alpha.
402 objectName i_test_ascii
404 This method implements the PARAM instruction test_ascii.
405 objectName i_test_char char
407 This method implements the PARAM instruction test_char.
408 objectName i_test_ddigit
410 This method implements the PARAM instruction test_ddigit.
411 objectName i_test_digit
413 This method implements the PARAM instruction test_digit.
414 objectName i_test_graph
416 This method implements the PARAM instruction test_graph.
417 objectName i_test_lower
419 This method implements the PARAM instruction test_lower.
420 objectName i_test_print
422 This method implements the PARAM instruction test_print.
423 objectName i_test_punct
425 This method implements the PARAM instruction test_punct.
426 objectName i_test_range chars chare
428 This method implements the PARAM instruction test_range.
429 objectName i_test_space
431 This method implements the PARAM instruction test_space.
432 objectName i_test_upper
434 This method implements the PARAM instruction test_upper.
435 objectName i_test_wordchar
437 This method implements the PARAM instruction test_wordchar.
438 objectName i_test_xdigit
440 This method implements the PARAM instruction test_xdigit.
441 objectName i_error_clear
443 This method implements the PARAM instruction error_clear.
444 objectName i_error_push
446 This method implements the PARAM instruction error_push.
447 objectName i_error_pop_merge
449 This method implements the PARAM instruction error_pop_merge.
450 objectName i_error_nonterminal symbol
452 This method implements the PARAM instruction error_nonterminal.
453 objectName i_status_ok
455 This method implements the PARAM instruction status_ok.
456 objectName i_status_fail
458 This method implements the PARAM instruction status_fail.
459 objectName i_status_negate
461 This method implements the PARAM instruction status_negate.
462 objectName i_loc_push
464 This method implements the PARAM instruction loc_push.
465 objectName i_loc_pop_discard
467 This method implements the PARAM instruction loc_pop_discard.
468 objectName i_loc_pop_rewind
470 This method implements the PARAM instruction loc_pop_rewind.
471 objectName i:ok_loc_pop_rewind
473 This guarded method, a variant of i_loc_pop_rewind, executes
474 only for "ST == ok".
475 objectName i_loc_pop_rewind/discard
477 This method is a convenient combination of control flow and the
478 two PARAM instructions loc_pop_rewind and loc_pop_discard. The
479 former is executed for "ST == fail", the latter for "ST == ok".
480 objectName i_symbol_restore symbol
482 This method implements the PARAM instruction symbol_restore.
483 The boolean result of the check is returned as the result of the
485 method and can be used with standard Tcl control flow commands.
486 objectName i_symbol_save symbol
488 This method implements the PARAM instruction symbol_save.
489 objectName i_value_clear
491 This method implements the PARAM instruction value_clear.
492 objectName i_value_clear/leaf
494 This method is a convenient combination of control flow and the
495 two PARAM instructions value_clear and value_leaf. The former is
496 executed for "ST == fail", the latter for "ST == ok".
497 objectName i_value_clear/reduce
499 This method is a convenient combination of control flow and the
500 two PARAM instructions value_clear and value_reduce. The former
501 is executed for "ST == fail", the latter for "ST == ok".
502 objectName i:ok_ast_value_push
504 This method implements a guarded variant of the the PARAM in‐
505 struction ast_value_push, which executes only for "ST == ok".
506 objectName i_ast_push
508 This method implements the PARAM instruction ast_push.
509 objectName i_ast_pop_rewind
511 This method implements the PARAM instruction ast_pop_rewind.
512 objectName i:fail_ast_pop_rewind
514 This guarded method, a variant of i_ast_pop_rewind, executes
515 only for "ST == fail".
516 objectName i_ast_pop_rewind/discard
518 This method is a convenient combination of control flow and the
519 two PARAM instructions ast_pop_rewind and ast_pop_discard. The
520 former is executed for "ST == fail", the latter for "ST == ok".
521 objectName i_ast_pop_discard
523 This method implements the PARAM instruction ast_pop_discard.
524 objectName i_ast_pop_discard/rewind
526 This method is a convenient combination of control flow and the
527 two PARAM instructions ast_pop_discard and ast_pop_rewind. The
528 former is executed for "ST == fail", the latter for "ST == ok".
529 objectName i:ok_continue
531 This guarded method executes only for "ST == ok". Then it aborts
532 the current iteration of the innermost loop in the calling Tcl
533 procedure.
534 objectName i:fail_continue
536 This guarded method executes only for "ST == fail". Then it
537 aborts the current iteration of the innermost loop in the call‐
538 ing Tcl procedure.
539 objectName i:fail_return
541 This guarded method executes only for "ST == fail". Then it
542 aborts the calling Tcl procedure.
543 objectName i:ok_return
545 This guarded method executes only for "ST == ok". Then it aborts
546 the calling Tcl procedure.
547 The next set of methods are super instructions, meaning that each im‐
549 plements a longer sequence of instructions commonly used in parsers.
550 The combinated instructions of the previous set, i.e. those with names
551 matching the pattern "i_*/*", are actually super instructions as well,
552 albeit with limited scope, handling 2 instructions with their control
553 flow. The upcoming set is much broader in scope, folding as much as six
554 or more PARAM instructions into a single method call.
555 In this we can see the reasoning behind their use well:
557 [1] By using less instructions the generated parsers become smaller,
559 as the common parts are now truly part of the common runtime,
560 and not explicitly written in the parser's code over and over
561 again.
562 [2] Using less instructions additionally reduces the overhead asso‐
564 ciated with calls into the runtime, i.e. the cost of method dis‐
565 patch and of setting up the variable context.
566 [3] Another effect of the super instructions is that their internals
568 can be optimized as well, especially regarding control flow, and
569 stack use, as the runtime internals are accessible to all in‐
570 structions folded into the sequence.
571 objectName si:void_state_push
573 This method combines
574 i_loc_push
577 i_error_clear
578 i_error_push
579 Parsers use it at the beginning of void sequences and choices
582 with a void initial branch.
583 objectName si:void2_state_push
585 This method combines
586 i_loc_push
589 i_error_clear
590 i_error_push
591 Parsers use it at the beginning of optional and repeated expres‐
594 sions.
595 objectName si:value_state_push
597 This method combines
598 i_ast_push
601 i_loc_push
602 i_error_clear
603 i_error_push
604 Parsers use it at the beginning of sequences generating an AST
607 and choices with an initial branch generating an AST.
608 objectName si:void_state_merge
610 This method combines
611 i_error_pop_merge
614 i_loc_pop_rewind/discard
615 Parsers use it at the end of void sequences and choices whose
618 last branch is void.
619 objectName si:void_state_merge_ok
621 This method combines
622 i_error_pop_merge
625 i_loc_pop_rewind/discard
626 i_status_ok
627 Parsers use it at the end of optional expressions
630 objectName si:value_state_merge
632 This method combines
633 i_error_pop_merge
636 i_ast_pop_rewind/discard
637 i_loc_pop_rewind/discard
638 Parsers use it at the end of sequences generating ASTs and
641 choices whose last branch generates an AST
642 objectName si:value_notahead_start
644 This method combines
645 i_loc_push
648 i_ast_push
649 Parsers use it at the beginning of negative lookahead predicates
652 which generate ASTs.
653 objectName si:void_notahead_exit
655 This method combines
656 i_loc_pop_rewind
659 i_status_negate
660 Parsers use it at the end of void negative lookahead predicates.
663 objectName si:value_notahead_exit
665 This method combines
666 i_ast_pop_discard/rewind
669 i_loc_pop_rewind
670 i_status_negate
671 Parsers use it at the end of negative lookahead predicates which
674 generate ASTs.
675 objectName si:kleene_abort
677 This method combines
678 i_loc_pop_rewind/discard
681 i:fail_return
682 Parsers use it to stop a positive repetition when its first, re‐
685 quired, expression fails.
686 objectName si:kleene_close
688 This method combines
689 i_error_pop_merge
692 i_loc_pop_rewind/discard
693 i:fail_status_ok
694 i:fail_return
695 Parsers use it at the end of repetitions.
698 objectName si:voidvoid_branch
700 This method combines
701 i_error_pop_merge
704 i:ok_loc_pop_discard
705 i:ok_return
706 i_loc_rewind
707 i_error_push
708 Parsers use it when transiting between branches of a choice when
711 both are void.
712 objectName si:voidvalue_branch
714 This method combines
715 i_error_pop_merge
718 i:ok_loc_pop_discard
719 i:ok_return
720 i_ast_push
721 i_loc_rewind
722 i_error_push
723 Parsers use it when transiting between branches of a choice when
726 the failing branch is void, and the next to test generates an
727 AST.
728 objectName si:valuevoid_branch
730 This method combines
731 i_error_pop_merge
734 i_ast_pop_rewind/discard
735 i:ok_loc_pop_discard
736 i:ok_return
737 i_loc_rewind
738 i_error_push
739 Parsers use it when transiting between branches of a choice when
742 the failing branch generates an AST, and the next to test is
743 void.
744 objectName si:valuevalue_branch
746 This method combines
747 i_error_pop_merge
750 i_ast_pop_discard
751 i:ok_loc_pop_discard
752 i:ok_return
753 i_ast_rewind
754 i_loc_rewind
755 i_error_push
756 Parsers use it when transiting between branches of a choice when
759 both generate ASTs.
760 objectName si:voidvoid_part
762 This method combines
763 i_error_pop_merge
766 i:fail_loc_pop_rewind
767 i:fail_return
768 i_error_push
769 Parsers use it when transiting between parts of a sequence and
772 both are void.
773 objectName si:voidvalue_part
775 This method combines
776 i_error_pop_merge
779 i:fail_loc_pop_rewind
780 i:fail_return
781 i_ast_push
782 i_error_push
783 Parsers use it when transiting between parts of a sequence and
786 the sucessfully matched part is void, and after it an AST is
787 generated.
788 objectName si:valuevalue_part
790 This method combines
791 i_error_pop_merge
794 i:fail_ast_pop_rewind
795 i:fail_loc_pop_rewind
796 i:fail_return
797 i_error_push
798 Parsers use it when transiting between parts of a sequence and
801 both parts generate ASTs.
802 objectName si:value_symbol_start symbol
804 This method combines
805 if/found? i_symbol_restore $symbol
808 i:found:ok_ast_value_push
809 i:found_return
810 i_loc_push
811 i_ast_push
812 Parsers use it at the beginning of a nonterminal symbol generat‐
815 ing an AST, whose right-hand side may have generated an AST as
816 well.
817 objectName si:value_void_symbol_start symbol
819 This method combines
820 if/found? i_symbol_restore $symbol
823 i:found:ok_ast_value_push
824 i:found_return
825 i_loc_push
826 i_ast_push
827 Parsers use it at the beginning of a void nonterminal symbol
830 whose right-hand side may generate an AST.
831 objectName si:void_symbol_start symbol
833 This method combines
834 if/found? i_symbol_restore $symbol
837 i:found_return
838 i_loc_push
839 i_ast_push
840 Parsers use it at the beginning of a nonterminal symbol generat‐
843 ing an AST whose right-hand side is void.
844 objectName si:void_void_symbol_start symbol
846 This method combines
847 if/found? i_symbol_restore $symbol
850 i:found_return
851 i_loc_push
852 Parsers use it at the beginning of a void nonterminal symbol
855 whose right-hand side is void as well.
856 objectName si:reduce_symbol_end symbol
858 This method combines
859 i_value_clear/reduce $symbol
862 i_symbol_save $symbol
863 i_error_nonterminal $symbol
864 i_ast_pop_rewind
865 i_loc_pop_discard
866 i:ok_ast_value_push
867 Parsers use it at the end of a non-terminal symbol generating an
870 AST using the AST generated by the right-hand side as child.
871 objectName si:void_leaf_symbol_end symbol
873 This method combines
874 i_value_clear/leaf $symbol
877 i_symbol_save $symbol
878 i_error_nonterminal $symbol
879 i_loc_pop_discard
880 i:ok_ast_value_push
881 Parsers use it at the end of a non-terminal symbol generating an
884 AST whose right-hand side is void.
885 objectName si:value_leaf_symbol_end symbol
887 This method combines
888 i_value_clear/leaf $symbol
891 i_symbol_save $symbol
892 i_error_nonterminal $symbol
893 i_loc_pop_discard
894 i_ast_pop_rewind
895 i:ok_ast_value_push
896 Parsers use it at the end of a non-terminal symbol generating an
899 AST discarding the AST generated by the right-hand side.
900 objectName si:value_clear_symbol_end symbol
902 This method combines
903 i_value_clear
906 i_symbol_save $symbol
907 i_error_nonterminal $symbol
908 i_loc_pop_discard
909 i_ast_pop_rewind
910 Parsers use it at the end of a void non-terminal symbol, dis‐
913 carding the AST generated by the right-hand side.
914 objectName si:void_clear_symbol_end symbol
916 This method combines
917 i_value_clear
920 i_symbol_save $symbol
921 i_error_nonterminal $symbol
922 i_loc_pop_discard
923 Parsers use it at the end of a void non-terminal symbol with a
926 void right-hand side.
927 objectName si:next_char tok
929 objectName si:next_range toks toke
931 objectName si:next_alnum
933 objectName si:next_alpha
935 objectName si:next_ascii
937 objectName si:next_ddigit
939 objectName si:next_digit
941 objectName si:next_graph
943 objectName si:next_lower
945 objectName si:next_print
947 objectName si:next_punct
949 objectName si:next_space
951 objectName si:next_upper
953 objectName si:next_wordchar
955 objectName si:next_xdigit
957 These methods all combine
958 i_input_next $msg
961 i:fail_return
962 with the appropriate i_test_xxx instruction. Parsers use them
965 for handling atomic expressions.
966
968 This document, and the package it describes, will undoubtedly contain
969 bugs and other problems. Please report such in the category pt of the
970 Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please also
971 report any ideas for enhancements you may have for either package
972 and/or documentation.
973 When proposing code changes, please provide unified diffs, i.e the out‐
975 put of diff -u.
976 Note further that attachments are strongly preferred over inlined
978 patches. Attachments can be made by going to the Edit form of the
979 ticket immediately after its creation, and then using the left-most
980 button in the secondary navigation bar.
981
983 EBNF, LL(k), PEG, TDPL, context-free languages, expression, grammar,
984 matching, parser, parsing expression, parsing expression grammar, push
985 down automaton, recursive descent, state, top-down parsing languages,
986 transducer
987
989 Parsing and Grammars
990
992 Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>
993tcllib 1.1 pt::rde(n)