grammar::me_ast(n)

💖 NAME 💖

grammar::me_ast — literally all the different representations of ASTs, bestie ✨

---

🦋 DESCRIPTION 🦋

Okay so this document specifies the various representations you can get for the abstract syntax trees (short: AST) that instances of ME virtual machines generate. And the whole thing is independent of variant — every variant, same tea. 🫶

Not me assuming you know what a ME virtual machine is 💀 — if you don't, go read grammar::me_intro first, fr fr. No skips.

ASTs, and every single representation we're about to specify, distinguish between two types of nodes, namely:

• Terminal — terminal nodes refer to the terminal symbols found in the token stream. They are always leaf nodes. I.e. terminal nodes never have children. Never ever. Periodt.
• Nonterminal — nonterminal nodes represent a nonterminal symbol of the grammar used during parsing. They can show up as leaf and inner nodes of the tree. Main character energy, honestly. 👑

Both types of nodes carry basic range information that tells a user which parts of the input are covered by the node, by providing the location of the first and last tokens found within the range. Locations are provided as non-negative integer offsets from the beginning of the token stream, and the first token found in the stream is located at offset 0 (zero). Yes, we're zero-indexed girlies. 💅

The root of an AST can be either a terminal or nonterminal node. Both are valid, both are iconic. 🌈

---

⭐ AST VALUES ⭐

This representation of ASTs is a Tcl list. The main list represents the root node of the tree, with the representations of the children nested within. It's giving... nesting dolls, but make it syntax trees. 🎀

Each node is represented by a single Tcl list containing three or more elements:

1. The first element is either the empty string or the name of a nonterminal symbol (which is never the empty string).
2. The second and third elements are then the locations of the first and last tokens.
3. Any additional elements after the third are then the representations of the children, with the leftmost child first — i.e. as the fourth element of the list representing the node.

---

🧚 AST OBJECTS 🧚

In this representation an AST is represented by a Tcl object command whose API is compatible to the tree objects provided by the package struct::tree. I.e. it has to support at least all of the methods described by that package, and may support more. Overachiever behavior, we love to see it. 💜

Because of this, the remainder of the specifications is written using the terms of struct::tree. So like, keep that in mind.

Each node of the AST directly maps to a node in the tree object. All data beyond the child nodes — i.e. node type and input locations — are stored in attributes of the node in the tree object. They are:

• type — the type of the AST node. The recognized values are terminal and nonterminal.
• range — the locations of the first and last token of the terminal data in the input covered by the node. This is a list containing two locations.
• detail — this attribute is present only for nonterminal nodes. It contains the name of the nonterminal symbol stored in the node.

---

🌸 EXTENDED AST OBJECTS 🌸

Extended AST objects are like AST objects, with additional information. Same vibe, more lore. 📖✨

• detail — this attribute is now present at all nodes. Its contents are unchanged for nonterminal nodes. For terminal nodes it contains a list describing all tokens from the input which are covered by the node.

Each element of the list contains the token name, the associated lexeme attribute, line number, and column index, in this order. Order matters bestie, don't shuffle it. 🙈

• range_lc — this new attribute is defined for all nodes, and contains the locations from attribute range translated into line number and column index. Lines are counted from 1, columns are counted from 0. (Yes, one of them starts at 1 and the other at 0. I know. I know. 😭 That's just how it is.)

---

💀 BUGS, IDEAS, FEEDBACK 💀

This document, and the package it describes, will undoubtedly contain bugs and other problems. Not a maybe, a will. 🫠 Please report such in the category grammar_me of the Tcllib Trackers at http://core.tcl.tk/tcllib/reportlist. Please also report any ideas for enhancements you may have for either package and/or documentation — we're open, we're listening, we're here. 🫶

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

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. Left-most. Don't make me say it again. 👀

---

🔥 KEYWORDS 🔥

AST, abstract syntax tree

---

🌈 CATEGORY 🌈

Grammars and finite automata

---

👑 COPYRIGHT 👑

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

---

Okay and that's the whole page, bestie — this came to you from tcllib, version 0.2, and the manual page itself is grammar::me_ast(n). Go build some trees. Slay. 💅✨