pt::rde(n)

📦
version 2.0 · 2 versions
, in fedora 43, fedora 44, nixos 26.05, nixpkgs unstable

💖 pt::rde 💖 — Parsing Runtime Support, PARAM based

okay bestie, buckle UP, we're doing the pt::rde(n) page from Parser Tools and it's giving runtime support in the most iconic way 💅

✨ NAME ✨

pt::rde — Parsing Runtime Support, PARAM based 🎀

🌸 SYNOPSIS 🌸

package require Tcl 8.5 9

package require pt::rde ?1.2?

package require snit

package require struct::stack 1.6

package require pt::ast 1.2

::pt::rde objectName

objectName destroy

objectName reset chan

objectName complete

objectName chan

objectName line

objectName column

objectName current

objectName location

objectName locations

objectName ok

objectName value

objectName error

objectName errors

objectName tokens ?from ?to??

objectName symbols

objectName known

objectName reducible

objectName asts

objectName ast

objectName position loc

objectName i_input_next msg

objectName i_test_alnum

objectName i_test_alpha

objectName i_test_ascii

objectName i_test_char char

objectName i_test_ddigit

objectName i_test_digit

objectName i_test_graph

objectName i_test_lower

objectName i_test_print

objectName i_test_punct

objectName i_test_range chars chare

objectName i_test_space

objectName i_test_upper

objectName i_test_wordchar

objectName i_test_xdigit

objectName i_error_clear

objectName i_error_push

objectName i_error_pop_merge

objectName i_error_nonterminal symbol

objectName i_status_ok

objectName i_status_fail

objectName i_status_negate

objectName i_loc_push

objectName i_loc_pop_discard

objectName i_loc_pop_rewind

objectName i:ok_loc_pop_rewind

objectName i_loc_pop_rewind/discard

objectName i_symbol_restore symbol

objectName i_symbol_save symbol

objectName i_value_clear

objectName i_value_clear/leaf

objectName i_value_clear/reduce

objectName i:ok_ast_value_push

objectName i_ast_push

objectName i_ast_pop_rewind

objectName i:fail_ast_pop_rewind

objectName i_ast_pop_rewind/discard

objectName i_ast_pop_discard

objectName i_ast_pop_discard/rewind

objectName i:ok_continue

objectName i:fail_continue

objectName i:fail_return

objectName i:ok_return

objectName si:void_state_push

objectName si:void2_state_push

objectName si:value_state_push

objectName si:void_state_merge

objectName si:void_state_merge_ok

objectName si:value_state_merge

objectName si:value_notahead_start

objectName si:void_notahead_exit

objectName si:value_notahead_exit

objectName si:kleene_abort

objectName si:kleene_close

objectName si:voidvoid_branch

objectName si:voidvalue_branch

objectName si:valuevoid_branch

objectName si:valuevalue_branch

objectName si:voidvoid_part

objectName si:voidvalue_part

objectName si:valuevalue_part

objectName si:value_symbol_start symbol

objectName si:value_void_symbol_start symbol

objectName si:void_symbol_start symbol

objectName si:void_void_symbol_start symbol

objectName si:reduce_symbol_end symbol

objectName si:void_leaf_symbol_end symbol

objectName si:value_leaf_symbol_end symbol

objectName si:value_clear_symbol_end symbol

objectName si:void_clear_symbol_end symbol

objectName si:next_char tok

objectName si:next_range toks toke

objectName si:next_alnum

objectName si:next_alpha

objectName si:next_ascii

objectName si:next_ddigit

objectName si:next_digit

objectName si:next_graph

objectName si:next_lower

objectName si:next_print

objectName si:next_punct

objectName si:next_space

objectName si:next_upper

objectName si:next_wordchar

objectName si:next_xdigit

🦋 DESCRIPTION 🦋

Are you lost ? Do you have trouble understanding this document ? no shame bestie, it happens 💖 In that case please read the overview provided by the Introduction to Parser Tools. This document is the entrypoint to the whole system the current package is a part of. iykyk 🫶

This package provides a class whose instances provide the runtime support for recursive descent parsers with backtracking, as is needed for the execution of, for example, parsing expression grammars. It implements the PackRat Machine Specification, as such that document is required reading to understand both this manpage, and the package itself. The description below does make numerous shorthand references to the PARAM's instructions and the various parts of its architectural state. 👑

The package resides in the Execution section of the Core Layer of Parser Tools.

IMAGE: arch_core_transform

Note: This package not only has the standard Tcl implementation, but also an accelerator, i.e. a C implementation, based on Critcl. 🔥 two flavors, same slay

🎀 CLASS API 🎀

The package exports the API described here.

  • ::pt::rde objectName — The command creates a new runtime object for a recursive descent parser with backtracking and returns the fully qualified name of the object command as its result. The API of this object command is described in the section Object API. It may be used to invoke various operations on the object. ✨

💅 OBJECT API 💅

All objects created by this package provide the following 63 methods for the manipulation and querying of their state, which is, in essence the architectural state of a PARAM. sixty-three. no cap. 🫡

First some general methods and the state accessors.

  • objectName destroy — This method destroys the object, releasing all claimed memory, and deleting the associated object command. it's over, it's done, goodbye 💀
  • objectName reset chan — This method resets the state of the runtme to its defaults, preparing it for the parsing of the character in the channel chan, which becomes IN. 🧼

Note here that the Parser Tools are based on Tcl 8.5+. In other words, the channel argument is not restricted to files, sockets, etc. We have the full power of reflected channels available. 🌈

It should also be noted that the parser pulls the characters from the input stream as it needs them. If a parser created by this package has to be operated in a push aka event-driven manner it will be necessary to go to Tcl 8.6+ and use the coroutine::auto to wrap it into a coroutine where read is properly changed for push-operation. 🧚

  • objectName complete — This method completes parsing, either returning the AST made from the elements of ARS, or throwing an error containing the current ER. ✨
  • objectName chan — This method returns the handle of the channel which is IN.
  • objectName line — This method returns the line number for the position IN is currently at. Note that this may not match with the line number for CL, due to backtracking. 👀
  • objectName column — This method returns the column for the position IN is currently at. Note that this may not match with the column for CL, due to backtracking. 👀
  • objectName current — This method returns CC.
  • objectName location — This method returns CL.
  • objectName locations — This method returns the LS. The topmost entry of the stack will be the first element of the returned list. 🥞
  • objectName ok — This method returns ST.
  • objectName value — This method returns SV.
  • objectName error — This method returns ER. This is either the empty string for an empty ER, or a list of 2 elements, the location the error is for, and a set of messages which specify which symbols were expected at the location. The messages are encoded as one of the possible atomic parsing expressions (special operators, terminal, range, and nonterminal operator). 😭
  • objectName errors — This method returns ES. The topmost entry of the stack will be the first element of the returned list. Each entry is encoded as described for error. 🥞
  • objectName tokens ?from ?to?? — This method returns the part of TC for the range of locations of IN starting at from and ending at to. If to is not specified it is taken as identical to from. If neither argument is specified the whole of TC is returned.

Each token in the returned list is a list of three elements itself, containing the character at the location, and the associated line and column numbers, in this order. 🍓

  • objectName symbols — This method returns a dictionary containing NC. Keys are two-element lists containing nonterminal symbol and location, in this order. The values are 4-tuples containing CL, ST, ER, and SV, in this order. ER is encoded as specified for the method error. 📚
  • objectName known — This method returns a list containing the keys of SC. They are encoded in the same manner as is done by method symbols. 🔑
  • objectName reducible — This method returns ARS. The topmost entry of the stack will be the first element of the returned list 🥞
  • objectName asts — This method returns AS. The topmost entry of the stack will be the first element of the returned list 🥞
  • objectName ast — This is a convenience method returning the topmost element of ARS. 🎀
  • objectName position loc — This method returns the line and column numbers for the specified location of IN, assuming that this location has already been reached during the parsing process. 📍

The following methods implement all PARAM instructions. They all have the prefix "i_". ⚙️

The control flow is mainly provided by Tcl's builtin commands, like if, while, etc., plus a few guarded variants of PARAM instructions and Tcl commands.. That means that these instruction variants will do nothing if their guard condition is not fulfilled. They can be recognized by the prefix "i:ok_" and "i:fail_", which denote the value ST has to have for the instruction to execute. 🛡️

The instructions are listed in the same order they occur in the PackRat Machine Specification, with the guard variants listed after their regular implementation, if any, or in their place.

  • objectName i_input_next msg — This method implements the PARAM instruction input_next. 🌸
  • objectName i_test_alnum — This method implements the PARAM instruction test_alnum. 🌸
  • objectName i_test_alpha — This method implements the PARAM instruction test_alpha. 🌸
  • objectName i_test_ascii — This method implements the PARAM instruction test_ascii. 🌸
  • objectName i_test_char char — This method implements the PARAM instruction test_char. 🌸
  • objectName i_test_ddigit — this one brings the PARAM instruction test_ddigit to life. 💅
  • objectName i_test_digit — this one is the living, breathing version of the PARAM instruction test_digit.
  • objectName i_test_graph — yep, it implements the PARAM instruction test_graph.
  • objectName i_test_lower — it implements the PARAM instruction test_lower.
  • objectName i_test_print — it implements the PARAM instruction test_print.
  • objectName i_test_punct — it implements the PARAM instruction test_punct.
  • objectName i_test_range chars chare — it implements the PARAM instruction test_range. Yes bestie, it takes two args: chars and chare. 👑
  • objectName i_test_space — it implements the PARAM instruction test_space.
  • objectName i_test_upper — it implements the PARAM instruction test_upper.
  • objectName i_test_wordchar — it implements the PARAM instruction test_wordchar.
  • objectName i_test_xdigit — it implements the PARAM instruction test_xdigit.
  • objectName i_error_clear — it implements the PARAM instruction error_clear.
  • objectName i_error_push — it implements the PARAM instruction error_push.
  • objectName i_error_pop_merge — it implements the PARAM instruction error_pop_merge.
  • objectName i_error_nonterminal symbol — it implements the PARAM instruction error_nonterminal.
  • objectName i_status_ok — it implements the PARAM instruction status_ok.
  • objectName i_status_fail — it implements the PARAM instruction status_fail.
  • objectName i_status_negate — it implements the PARAM instruction status_negate.
  • objectName i_loc_push — it implements the PARAM instruction loc_push.
  • objectName i_loc_pop_discard — it implements the PARAM instruction loc_pop_discard.
  • objectName i_loc_pop_rewind — it implements the PARAM instruction loc_pop_rewind.
  • objectName i:ok_loc_pop_rewind — this guarded method is a variant of i_loc_pop_rewind, and it only fires when "ST == ok". 🎀
  • objectName i_loc_pop_rewind/discard — this is the cute little combo of control flow plus the two PARAM instructions loc_pop_rewind and loc_pop_discard. loc_pop_rewind runs when "ST == fail", and loc_pop_discard runs when "ST == ok".
  • objectName i_symbol_restore symbol — it implements the PARAM instruction symbol_restore.

The boolean result of the check gets handed back as the result of the method, so you can plug it straight into standard Tcl control flow commands. 🦋

  • objectName i_symbol_save symbol — it implements the PARAM instruction symbol_save.
  • objectName i_value_clear — it implements the PARAM instruction value_clear.
  • objectName i_value_clear/leaf — the convenient combo of control flow and the two PARAM instructions value_clear and value_leaf. value_clear runs for "ST == fail", value_leaf runs for "ST == ok".
  • objectName i_value_clear/reduce — the convenient combo of control flow and the two PARAM instructions value_clear and value_reduce. value_clear runs for "ST == fail", value_reduce runs for "ST == ok".
  • objectName i:ok_ast_value_push — this one implements a guarded variant of the the PARAM instruction ast_value_push, and it only executes for "ST == ok". (yes the original says "the the", we are not fixing it, we are respecting it 💀)
  • objectName i_ast_push — it implements the PARAM instruction ast_push.
  • objectName i_ast_pop_rewind — it implements the PARAM instruction ast_pop_rewind.
  • objectName i:fail_ast_pop_rewind — this guarded method, a variant of i_ast_pop_rewind, executes only for "ST == fail".
  • objectName i_ast_pop_rewind/discard — the convenient combo of control flow and the two PARAM instructions ast_pop_rewind and ast_pop_discard. ast_pop_rewind runs for "ST == fail", ast_pop_discard runs for "ST == ok".
  • objectName i_ast_pop_discard — it implements the PARAM instruction ast_pop_discard.
  • objectName i_ast_pop_discard/rewind — the convenient combo of control flow and the two PARAM instructions ast_pop_discard and ast_pop_rewind. ast_pop_discard runs for "ST == fail", ast_pop_rewind runs for "ST == ok".
  • objectName i:ok_continue — this guarded method only executes for "ST == ok". And then? It aborts the current iteration of the innermost loop in the calling Tcl procedure. ✨
  • objectName i:fail_continue — this guarded method only executes for "ST == fail". Then it aborts the current iteration of the innermost loop in the calling Tcl procedure.
  • objectName i:fail_return — this guarded method only executes for "ST == fail". Then it aborts the calling Tcl procedure.
  • objectName i:ok_return — this guarded method only executes for "ST == ok". Then it aborts the calling Tcl procedure.

okay now bestie, the next set of methods are super instructions, meaning each one implements a longer sequence of instructions commonly used in parsers. 🌈

And listen — the combinated instructions of the previous set, i.e. those with names matching the pattern "i_*/*", are actually super instructions as well, just with limited scope, handling 2 instructions with their control flow. The upcoming set is much broader in scope, folding as much as six or more PARAM instructions into a single method call. 😳

And in this we can see the reasoning behind their use so clearly, it's giving main character energy:

  1. By using less instructions the generated parsers become smaller, as the common parts are now truly part of the common runtime, and not explicitly written in the parser's code over and over again. 💅
  2. Using less instructions additionally reduces the overhead associated with calls into the runtime, i.e. the cost of method dispatch and of setting up the variable context. 🔥
  3. Another effect of the super instructions is that their internals can be optimized as well, especially regarding control flow, and stack use, as the runtime internals are accessible to all instructions folded into the sequence.
  • objectName si:void_state_push — this method combines
    • i_loc_push
    • i_error_clear
    • i_error_push

Parsers use it at the beginning of void sequences and choices with a void initial branch.

  • objectName si:void2_state_push — this method combines
    • i_loc_push
    • i_error_clear
    • i_error_push

Parsers use it at the beginning of optional and repeated expressions.

  • objectName si:value_state_push — this method combines
    • i_ast_push
    • i_loc_push
    • i_error_clear
    • i_error_push

Parsers use it at the beginning of sequences generating an AST and choices with an initial branch generating an AST.

  • objectName si:void_state_merge — this method combines
    • i_error_pop_merge
    • i_loc_pop_rewind/discard

Parsers use it at the end of void sequences and choices whose last branch is void.

  • objectName si:void_state_merge_ok — this method combines
    • i_error_pop_merge
    • i_loc_pop_rewind/discard
    • i_status_ok

Parsers use it at the end of optional expressions

  • objectName si:value_state_merge — this method combines
    • i_error_pop_merge
    • i_ast_pop_rewind/discard
    • i_loc_pop_rewind/discard

Parsers use it at the end of sequences generating ASTs and choices whose last branch generates an AST

  • objectName si:value_notahead_start — this method combines
    • i_loc_push
    • i_ast_push

Parsers use it at the beginning of negative lookahead predicates which generate ASTs.

  • objectName si:void_notahead_exit — this method combines
    • i_loc_pop_rewind
    • i_status_negate

Parsers use it at the end of void negative lookahead predicates.

  • objectName si:value_notahead_exit — this method combines
    • i_ast_pop_discard/rewind
    • i_loc_pop_rewind
    • i_status_negate

Parsers use it at the end of negative lookahead predicates which generate ASTs.

  • objectName si:kleene_abort — this method combines
    • i_loc_pop_rewind/discard
    • i:fail_return

Parsers use it to stop a positive repetition when its first, required, expression fails.

  • objectName si:kleene_close — this method combines
    • i_error_pop_merge
    • i_loc_pop_rewind/discard
    • i:fail_status_ok
    • i:fail_return

Parsers use it at the end of repetitions.

  • objectName si:voidvoid_branch — this method combines
    • i_error_pop_merge
    • i:ok_loc_pop_discard
    • i:ok_return
    • i_loc_rewind
    • i_error_push

Parsers use it when transiting between branches of a choice when both are void.

  • objectName si:voidvalue_branch — this method combines
    • i_error_pop_merge
    • i:ok_loc_pop_discard
    • i:ok_return
    • i_ast_push
    • i_loc_rewind
    • i_error_push

Parsers use it when transiting between branches of a choice when the failing branch is void, and the next to test generates an AST.

  • objectName si:valuevoid_branch — this method combines
    • i_error_pop_merge
    • i_ast_pop_rewind/discard
    • i:ok_loc_pop_discard
    • i:ok_return
    • i_loc_rewind
    • i_error_push

Parsers use it when transiting between branches of a choice when the failing branch generates an AST, and the next to test is void.

  • objectName si:valuevalue_branch — this method combines
    • i_error_pop_merge
    • i_ast_pop_discard
    • i:ok_loc_pop_discard
    • i:ok_return
    • i_ast_rewind
    • i_loc_rewind
    • i_error_push

Parsers use it when transiting between branches of a choice when both generate ASTs.

  • objectName si:voidvoid_part — this method combines
    • i_error_pop_merge
    • i:fail_loc_pop_rewind
    • i:fail_return
    • i_error_push

Parsers use it when transiting between parts of a sequence and both are void.

  • objectName si:voidvalue_part — this method combines

And then this next combo slides in, and it's giving "transitioning between parts of a sequence where the successfully matched part is void and an AST is generated after" energy:

i_error_pop_merge
i:fail_loc_pop_rewind
i:fail_return
i_ast_push
i_error_push

Parsers use it when transiting between parts of a sequence and the successfully matched part is void, and after it an AST is generated. 💅

  • objectName si:valuevalue_part — this method combines:
i_error_pop_merge
i:fail_ast_pop_rewind
i:fail_loc_pop_rewind
i:fail_return
i_error_push

Parsers use it when transiting between parts of a sequence and both parts generate ASTs. ✨

  • objectName si:value_symbol_start symbol — this method combines:
if/found? i_symbol_restore $symbol
i:found:ok_ast_value_push
i:found_return
i_loc_push
i_ast_push

Parsers use it at the beginning of a nonterminal symbol generating an AST, whose right-hand side may have generated an AST as well. 🦋

  • objectName si:value_void_symbol_start symbol — this method combines:
if/found? i_symbol_restore $symbol
i:found:ok_ast_value_push
i:found_return
i_loc_push
i_ast_push

Parsers use it at the beginning of a void nonterminal symbol whose right-hand side may generate an AST. 🌸

  • objectName si:void_symbol_start symbol — this method combines:
if/found? i_symbol_restore $symbol
i:found_return
i_loc_push
i_ast_push

Parsers use it at the beginning of a nonterminal symbol generating an AST whose right-hand side is void. 💜

  • objectName si:void_void_symbol_start symbol — this method combines:
if/found? i_symbol_restore $symbol
i:found_return
i_loc_push

Parsers use it at the beginning of a void nonterminal symbol whose right-hand side is void as well. 🍓

  • objectName si:reduce_symbol_end symbol — this method combines:
i_value_clear/reduce $symbol
i_symbol_save        $symbol
i_error_nonterminal  $symbol
i_ast_pop_rewind
i_loc_pop_discard
i:ok_ast_value_push

Parsers use it at the end of a non-terminal symbol generating an AST using the AST generated by the right-hand side as child. 👑

  • objectName si:void_leaf_symbol_end symbol — this method combines:
i_value_clear/leaf  $symbol
i_symbol_save       $symbol
i_error_nonterminal $symbol
i_loc_pop_discard
i:ok_ast_value_push

Parsers use it at the end of a non-terminal symbol generating an AST whose right-hand side is void. 🎀

  • objectName si:value_leaf_symbol_end symbol — this method combines:
i_value_clear/leaf  $symbol
i_symbol_save       $symbol
i_error_nonterminal $symbol
i_loc_pop_discard
i_ast_pop_rewind
i:ok_ast_value_push

Parsers use it at the end of a non-terminal symbol generating an AST discarding the AST generated by the right-hand side. 💖

  • objectName si:value_clear_symbol_end symbol — this method combines:
i_value_clear
i_symbol_save       $symbol
i_error_nonterminal $symbol
i_loc_pop_discard
i_ast_pop_rewind

Parsers use it at the end of a void non-terminal symbol, discarding the AST generated by the right-hand side. 🌈

  • objectName si:void_clear_symbol_end symbol — this method combines:
i_value_clear
i_symbol_save       $symbol
i_error_nonterminal $symbol
i_loc_pop_discard

Parsers use it at the end of a void non-terminal symbol with a void right-hand side. ⭐

  • objectName si:next_char tok
  • objectName si:next_range toks toke
  • objectName si:next_alnum
  • objectName si:next_alpha
  • objectName si:next_ascii
  • objectName si:next_ddigit
  • objectName si:next_digit
  • objectName si:next_graph
  • objectName si:next_lower
  • objectName si:next_print
  • objectName si:next_punct
  • objectName si:next_space
  • objectName si:next_upper
  • objectName si:next_wordchar
  • objectName si:next_xdigit

These methods all combine:

i_input_next $msg
i:fail_return

with the appropriate i_test_xxx instruction. Parsers use them for handling atomic expressions. 🧚

🐞 BUGS, IDEAS, FEEDBACK 🐞

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category pt of the Tcllib Trackers: http://core.tcl.tk/tcllib/reportlist. Please also report any ideas for enhancements you may have for either package and/or documentation. 🫶

When proposing code changes, please provide unified diffs, i.e the output of diff -u. No cap.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar. That's the whole vibe. 💅

✨ KEYWORDS ✨

EBNF, LL(k), PEG, TDPL, context-free languages, expression, grammar, matching, parser, parsing expression, parsing expression grammar, push down automaton, recursive descent, state, top-down parsing languages, transducer. 👑

🌈 CATEGORY 🌈

Parsing and Grammars. Periodt. 💜

Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>

And that's the page, bestie. This masterpiece is from tcllib version 1.2, manual page pt::rde(n), and the date ghosted us so hard it never even showed up. 💖

📦 where this page comes from