pt::pe(n)

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

💖 pt::pe — Parsing Expression Serialization 💖

okay bestie, welcome to the manual page for pt::pe, the Tcl package that lives in the Parser Tools family and handles Parsing Expression Serialization. she's a whole vibe, she's giving core-layer support energy, and yes we are going to read the entire thing together. grab a snack. 🍓

✨ NAME ✨

pt::pe — Parsing Expression Serialization. that's it, that's the name, short and iconic. 👑

🌸 SYNOPSIS 🌸

first things first, the requirements, because nothing works without the prerequisites bestie:

package require Tcl 8.5 9

package require pt::pe ?1.0.2?

package require char

see that ?1.0.2? — that's the version, optional-ish notation, and honestly slay. 💅

now here's the full roster of commands, all of them, no cap:

::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

look at that list. thirty-something commands and every single one is doing her little job. obsessed. 🌈

🦋 DESCRIPTION 🦋

okay so, real talk first:

Are you lost ? Do you have trouble understanding this document ? 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.

that's not me being shady, that's literally what the docs say, and honestly if you're confused the Introduction to Parser Tools is your girl. go read her first. 🫶

so what does this package actually do? it provides commands to work with the serializations of parsing expressions as managed by the Parser Tools, and specified in the section PE serialization format. (that section is coming, bestie, this page is long, we're in part 1.)

she's a supporting package in the Core Layer of Parser Tools. supporting role but main character energy, truly.

IMAGE: arch_core_support

💜 API 💜

here's where it gets juicy. every command, every argument, every single detail, let's go. ✨

🎀 ::pt::pe verify serial ?canonvar?

this one verifies that the content of serial is a valid serialization of a parsing expression, and she will throw an error if that's not the case. no chill, no mercy. 😭 the result of the command is the empty string.

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

  • True — the serialization is not only valid, but also canonical 👑
  • False — valid, but non-canonical (still valid tho, we don't judge)

for the specification of serializations, see the section PE serialization format.

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

same energy, stricter standards. this command verifies that the content of serial is a valid canonical serialization of a parsing expression, and will throw an error if that's not the case. the result of the command is the empty string.

for the specification of canonical serializations, see the section PE serialization format.

🎀 ::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, because assumptions have consequences bestie. 💀

then she converts the input into the canonical serialization of this parsing expression and returns it as her result. if the input is already canonical, it gets returned unchanged. glow-up not needed, she was already that girl.

for the specification of regular and canonical serializations, see the section PE serialization format.

🎀 ::pt::pe print serial

this command assumes the argument serial contains a valid serialization of a parsing expression, and returns a string containing that PE in a human readable form.

the exact format of this form is not specified and cannot be relied on for parsing or other machine-based activities.

so like, pretty for your eyes, not for your parser. do not build on it. fr fr.

for the specification of serializations, see the section PE serialization format.

🎀 ::pt::pe bottomup cmdprefix pe

this command walks the parsing expression pe from the bottom up to the root, invoking the command prefix cmdprefix for each partial expression. which implies that the children of a parsing expression PE are handled before PE. bottom-up, little ones first, then mama. 🧚

the command prefix has the signature:

cmdprefix pe op arguments

i.e. it's invoked with the parsing expression pe the walk is currently at, the operator in the pe, and the operator's arguments.

the result returned by the command prefix replaces pe in the parsing expression it was a child of, which allows transformations of the expression tree. 🌈

this also means that for all inner parsing expressions, the contents of arguments are the results of the command prefix invoked for the children of this inner parsing expression. yes, it's turtles all the way down, but make it ✨recursive✨.

🎀 ::pt::pe topdown cmdprefix pe

this command walks the parsing expression pe from the root down to the leaves, invoking the command prefix cmdprefix for each partial expression. which implies that the children of a parsing expression PE are handled after PE. so, opposite direction, same energy.

the command prefix has the same signature as for bottomup, see above. 👆

the result returned by the command prefix is ignored.

so don't get cute with return values here, she's not listening. 🙈

🎀 ::pt::pe equal seriala serialb

this command tests the two parsing expressions seriala and serialb for structural equality. the result of the command is a boolean value:

  • true — the expressions are identical 💖
  • false — otherwise 💔
string equality is usable only if we can assume that the two parsing expressions are pure Tcl lists.

keep that in mind, it matters.

🎀 the atomic parsing expression constructors

okay so these next ones are a whole squad, all doing the same genre of thing: each one constructs the atomic parsing expression for its lil thing. atomic baddies. ⭐

  • ::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.

every one of them, in order, exactly as written. no skips. periodt. 💅

🎀 ::pt::pe terminal t

this command constructs the atomic parsing expression for the terminal symbol t.

🎀 ::pt::pe range ta tb

this command constructs the atomic parsing expression for the range of terminal symbols ta ... tb.

🎀 ::pt::pe nonterminal nt

this command constructs the atomic parsing expression for the nonterminal symbol nt.

🎀 ::pt::pe choice pe...

this command constructs the parsing expression representing the ordered or prioritized choice between the argument parsing expressions. the first argument has the highest priority. so like, line order matters, bestie, she's picking favorites and it's the first one. 👑

🎀 ::pt::pe sequence pe...

this command constructs the parsing expression representing the sequence of the argument parsing expressions. the first argument is the first element of the sequence. in order, no shuffling. 🦋

🎀 ::pt::pe repeat0 pe

this command constructs the parsing expression representing the zero or more repetition of the argument parsing expression pe, also known as the kleene closure. zero or more, she's flexible like that. ✨

🎀 ::pt::pe repeat1 pe

this command constructs the parsing expression representing the one or more repetition of the argument parsing expression pe, also known as the positive kleene closure. one or more, she needs at least one, no crumbs accepted. 💖

🎀 ::pt::pe optional pe

this command constructs the parsing expression representing the optionality of the argument parsing expression pe. take it or leave it, she's chill. 🧚

🎀 ::pt::pe ahead pe

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

🎀 ::pt::pe notahead pe

this command constructs the parsing expression representing the negative lookahead of the argument parsing expression pe. peeking, but hoping she's not there. 🙈

more of this page is coming bestie, we are absolutely not done. 💜

🌈 PE SERIALIZATION FORMAT 🌈

okay bestie so this is where we talk about the format — like, the actual wire format the Parser Tools use to serialize Parsing Expressions as immutable values so they can be transported, compared, whatever. fr fr it's the glow-up your grammar gets before it goes out.

And here's the tea: there are two kinds of serialization, and they are not the same:

  • regular serialization
  • canonical serialization

A parsing expression can have more than one regular serialization, but exactly one of them is canonical. One. Singular. The main character. 👑

Regular serialization

Atomic Parsing Expressions

  1. The string epsilon is an atomic parsing expression. It matches the empty string. 💀 (yes, matching nothing is a whole personality)
  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 make it unique among all the possible serializations of this parsing expression. Like, it's the one true form. 🫶

  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 🌸

Assuming the parsing expression shown on the right-hand side of the rule

Expression <- Term (AddOp Term)*

then its canonical serialization (except for whitespace) is

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

😭 BUGS, IDEAS, FEEDBACK 😭

ngl this document, and the package it describes, will undoubtedly contain bugs and other problems. It's giving humble. 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. we love feedback bestie 💖

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

Also note: 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. 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, you ate it 🍓 this was pt::pe(n) from tcllib, version 1.0.2 — go forth and serialize your parsing expressions canonically, no cap 💅✨

📦 where this page comes from