pt::pe(3tcl)

📦
version 2.0 · 2 versions
, in debian trixie, ubuntu questing, ubuntu resolute, ubuntu stonking

💖 pt::pe — Parsing Expression Serialization 💖

okay bestie, welcome to pt::pe, a manual page from the Parser Tools collection, sitting pretty in the 3tcl section. this one's about serialization of parsing expressions, and honestly? it's giving foundational. 🎀

✨ NAME ✨

pt::pe — Parsing Expression Serialization. that's the whole name, that's the whole vibe. 💅

🌸 SYNOPSIS 🌸

package require Tcl 8.5 9

package require pt::pe ?1.0.2?

package require char

::pt::pe verify serial ?canonvar?

::pt::pe verify-as-canonical serial

::pt::pe canonicalize serial

::pt::pe print serial

::pt::pe bottomup cmdprefix pe

cmdprefix pe op arguments

::pt::pe topdown cmdprefix pe

::pt::pe equal seriala serialb

::pt::pe epsilon

::pt::pe dot

::pt::pe alnum

::pt::pe alpha

::pt::pe ascii

::pt::pe control

::pt::pe digit

::pt::pe graph

::pt::pe lower

::pt::pe print

::pt::pe punct

::pt::pe space

::pt::pe upper

::pt::pe wordchar

::pt::pe xdigit

::pt::pe ddigit

::pt::pe terminal t

::pt::pe range ta tb

::pt::pe nonterminal nt

::pt::pe choice pe...

::pt::pe sequence pe...

::pt::pe repeat0 pe

::pt::pe repeat1 pe

::pt::pe optional pe

::pt::pe ahead pe

::pt::pe notahead pe

🦋 DESCRIPTION 🦋

are you lost?? 😭 like, genuinely confused by this document? no worries babe, go read the overview in the Introduction to Parser Tools. that's the entrypoint to the entire system this package is a part of, and it'll catch you up. 🫶

so. this package hands you the commands to work with the serializations of parsing expressions as managed by the Parser Tools — all specified over in the section PE serialization format. ✨

this is a supporting package in the Core Layer of Parser Tools, so it's lowkey the glue holding things together. 💜

IMAGE: arch_core_support

👑 API 👑

🍓 ::pt::pe verify serial ?canonvar?

this one checks that whatever's inside serial is actually a valid serialization of a parsing expression. if it's not? boom, it throws an error. 💀 if it is valid, the command just returns the empty string. no drama.

if you pass the argument canonvar, it gets interpreted as the name of a variable in the calling context. that variable gets written to if and only if serial is a valid regular serialization. its value will be a boolean, and here's the tea:

  • True — the serialization isn't just valid, it's also canonical. slay.
  • False — valid, but non-canonical. still valid tho, don't be rude.

for the full spec on serializations, go check the section PE serialization format. 📖

🧚 ::pt::pe verify-as-canonical serial

this one is stricter — it verifies that serial is a valid canonical serialization of a parsing expression, and throws an error if it isn't. 💅 result of the command is the empty string.

same deal: spec lives in the PE serialization format section. ✨

🌈 ::pt::pe canonicalize serial

this command assumes the content of serial is a valid regular serialization of a parsing expression, and will throw an error if that's not the case. no cap.

assuming it's fine, it converts the input into the canonical serialization of that parsing expression and returns it as the result. and if the input was already canonical? it comes right back at you unchanged. iconic. 👑

again, for the spec on regular and canonical serializations, see PE serialization format. 🎀

🦄 ::pt::pe print serial

this one assumes the argument serial holds a valid serialization of a parsing expression, and it returns a string containing that PE in a human readable form. so pretty. 🌸

heads up bestie: the exact format of that human-readable form is not specified and you cannot rely on it for parsing or any other machine-based activities. it's for your eyeballs only, not your parser's. 🙈

for the serialization spec, see PE serialization format. 📚

💜 ::pt::pe bottomup cmdprefix pe

this walks the parsing expression pe from the bottom up to the root, invoking the command prefix cmdprefix for each partial expression. what that means in practice: the children of a parsing expression PE get handled before PE itself. so it's leaves first, then upward. 🌱➡️🌳

the command prefix has this signature:

cmdprefix pe op arguments

so basically it gets called with:

  • the parsing expression pe that the walk is currently sitting at,
  • the operator in that pe,
  • and the operator's arguments.

here's the fun part: the result returned by the command prefix replaces pe in the parsing expression it was a child of. so yes, you can transform the expression tree. 💅

which also means that for all inner parsing expressions, the contents of arguments are the results of the command prefix invoked for the children of that inner parsing expression. nesting, but make it cute. 🎀

🌟 ::pt::pe topdown cmdprefix pe

this one walks pe from the root down to the leaves, invoking cmdprefix for each partial expression. so here the children of a parsing expression PE are handled after PE. top first, then down. ⬇️

the command prefix has the same signature as for bottomup (scroll up, bestie ☝️).

and the result returned by the command prefix is ignored. noted. 🫡

🫶 ::pt::pe equal seriala serialb

tests the two parsing expressions seriala and serialb for structural equality. result is a boolean: true if the expressions are identical, false otherwise. simple as that. ✨

one caveat tho: string equality is usable only if we can assume the two parsing expressions are pure Tcl lists. don't forget it. 💀

💅 atomic parsing expressions — the little building blocks 💅

each of these constructs the atomic parsing expression for the thing named. one-liners, but they're all main characters in their own right. 👑

  • ::pt::pe epsilon — constructs the atomic parsing expression for epsilon.
  • ::pt::pe dot — constructs the atomic parsing expression for dot.
  • ::pt::pe alnum — constructs the atomic parsing expression for alnum.
  • ::pt::pe alpha — constructs the atomic parsing expression for alpha.
  • ::pt::pe ascii — constructs the atomic parsing expression for ascii.
  • ::pt::pe control — constructs the atomic parsing expression for control.
  • ::pt::pe digit — constructs the atomic parsing expression for digit.
  • ::pt::pe graph — constructs the atomic parsing expression for graph.
  • ::pt::pe lower — constructs the atomic parsing expression for lower.
  • ::pt::pe print — constructs the atomic parsing expression for print.
  • ::pt::pe punct — constructs the atomic parsing expression for punct.
  • ::pt::pe space — constructs the atomic parsing expression for space.
  • ::pt::pe upper — constructs the atomic parsing expression for upper.
  • ::pt::pe wordchar — constructs the atomic parsing expression for wordchar.
  • ::pt::pe xdigit — constructs the atomic parsing expression for xdigit.
  • ::pt::pe ddigit — constructs the atomic parsing expression for ddigit.

🎀 ::pt::pe terminal t

constructs the atomic parsing expression for the terminal symbol t. 🌸

🍓 ::pt::pe range ta tb

constructs the atomic parsing expression for the range of terminal symbols ta ... tb. inclusive vibes. ✨

🧚 ::pt::pe nonterminal nt

constructs the atomic parsing expression for the nonterminal symbol nt. 💜

👑 ::pt::pe choice pe...

constructs the parsing expression representing the ordered (or prioritized) choice between the argument parsing expressions. and important detail: the first argument has the highest priority. so order matters, bestie. 🥇

🌈 ::pt::pe sequence pe...

constructs the parsing expression representing the sequence of the argument parsing expressions. the first argument is the first element of the sequence. left to right, no notes. 💅

⭐ ::pt::pe repeat0 pe

constructs the parsing expression representing the zero or more repetition of the argument parsing expression pe — also known as the kleene closure. zero is allowed. we love an inclusive queen. 👑

🔥 ::pt::pe repeat1 pe

constructs the parsing expression representing the one or more repetition of the argument parsing expression pe — also known as the positive kleene closure. at least one, no skipping. 💪

🦋 ::pt::pe optional pe

constructs the parsing expression representing the optionality of the argument parsing expression pe. take it or leave it, literally. 🙈

🌟 ::pt::pe ahead pe

constructs the parsing expression representing the positive lookahead of the argument parsing expression pe. peeking respectfully. 👀

💀 ::pt::pe notahead pe

constructs the parsing expression representing the negative lookahead of the argument parsing expression pe. peeking, but with an agenda. 🚫

that's it for part 1, bestie — more is coming, so don't go anywhere. 💖

✨ PE SERIALIZATION FORMAT ✨

okay bestie, gather round, because this is the whole spec for how the Parser Tools serialize Parsing Expressions — as immutable values, so you can ship them around for transport, comparison, all of that. 🎀

And there's a plot twist: we split this into regular and canonical serializations. A parsing expression can have more than one regular serialization, but exactly one of them is canonical. only one. periodt. 💅

💅 Regular serialization 💅

🌸 Atomic Parsing Expressions 🌸

  1. The string epsilon is an atomic parsing expression. It matches the empty string. ✨
  2. The string dot is an atomic parsing expression. It matches any character.
  3. The string alnum is an atomic parsing expression. It matches any Unicode alphabet or digit character. This is a custom extension of PEs based on Tcl's builtin command string is.
  4. The string alpha is an atomic parsing expression. It matches any Unicode alphabet character. This is a custom extension of PEs based on Tcl's builtin command string is.
  5. The string ascii is an atomic parsing expression. It matches any Unicode character below U0080. This is a custom extension of PEs based on Tcl's builtin command string is.
  6. The string control is an atomic parsing expression. It matches any Unicode control character. This is a custom extension of PEs based on Tcl's builtin command string is.
  7. The string digit is an atomic parsing expression. It matches any Unicode digit character. Note that this includes characters outside of the [0..9] range. This is a custom extension of PEs based on Tcl's builtin command string is.
  8. The string graph is an atomic parsing expression. It matches any Unicode printing character, except for space. This is a custom extension of PEs based on Tcl's builtin command string is.
  9. The string lower is an atomic parsing expression. It matches any Unicode lower-case alphabet character. This is a custom extension of PEs based on Tcl's builtin command string is.
  10. The string print is an atomic parsing expression. It matches any Unicode printing character, including space. This is a custom extension of PEs based on Tcl's builtin command string is.
  11. The string punct is an atomic parsing expression. It matches any Unicode punctuation character. This is a custom extension of PEs based on Tcl's builtin command string is.
  12. The string space is an atomic parsing expression. It matches any Unicode space character. This is a custom extension of PEs based on Tcl's builtin command string is.
  13. The string upper is an atomic parsing expression. It matches any Unicode upper-case alphabet character. This is a custom extension of PEs based on Tcl's builtin command string is.
  14. The string wordchar is an atomic parsing expression. It matches any Unicode word character. This is any alphanumeric character (see alnum), and any connector punctuation characters (e.g. underscore). This is a custom extension of PEs based on Tcl's builtin command string is.
  15. The string xdigit is an atomic parsing expression. It matches any hexadecimal digit character. This is a custom extension of PEs based on Tcl's builtin command string is.
  16. The string ddigit is an atomic parsing expression. It matches any decimal digit character. This is a custom extension of PEs based on Tcl's builtin command regexp.
  17. The expression [list t x] is an atomic parsing expression. It matches the terminal string x.
  18. The expression [list n A] is an atomic parsing expression. It matches the nonterminal A.

🔥 Combined Parsing Expressions 🔥

  1. For parsing expressions e1, e2, ... the result of [list / e1 e2 ... ] is a parsing expression as well. This is the ordered choice, aka prioritized choice.
  2. For parsing expressions e1, e2, ... the result of [list x e1 e2 ... ] is a parsing expression as well. This is the sequence.
  3. For a parsing expression e the result of [list * e] is a parsing expression as well. This is the kleene closure, describing zero or more repetitions.
  4. For a parsing expression e the result of [list + e] is a parsing expression as well. This is the positive kleene closure, describing one or more repetitions.
  5. For a parsing expression e the result of [list & e] is a parsing expression as well. This is the and lookahead predicate.
  6. For a parsing expression e the result of [list ! e] is a parsing expression as well. This is the not lookahead predicate.
  7. For a parsing expression e the result of [list ? e] is a parsing expression as well. This is the optional input.

🎀 Canonical serialization 🎀

The canonical serialization of a parsing expression has the format as specified in the previous item, and then additionally satisfies the constraints below — which is literally what makes it unique among all the possible serializations of this parsing expression. it's giving main character energy, fr fr. 👑

  1. The string representation of the value is the canonical representation of a pure Tcl list. I.e. it does not contain superfluous whitespace.
  2. Terminals are not encoded as ranges (where start and end of the range are identical).

🌈 EXAMPLE 🌈

Say the parsing expression is the one sitting on the right-hand side of this rule:

Expression <- Term (AddOp Term)*

then its canonical serialization (except for whitespace, bestie) is:

{x {n Term} {* {x {n AddOp} {n Term}}}}

slay. 🦋

🩷 BUGS, IDEAS, FEEDBACK 🩷

ngl, 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 at http://core.tcl.tk/tcllib/reportlist. And please also report any ideas for enhancements you may have for either the package and/or the documentation — we want them, truly. 🫶

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

Also note, and this is a real one: attachments are strongly preferred over inlined patches. You can make an attachment 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. iykyk. 💅

⭐ 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

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

and that's the whole page, bestie!! 🎀 this one shipped as tcllib version 1.0.2, and it's the pt::pe(3tcl) manual page (the date field on the footer is just vibing empty, so nothing to report there 🙈). go forth and serialize, you absolute icon. ✨💖🦋

📦 where this page comes from