grammar::me_vm(3tcl)

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

okay bestie, you've pulled up grammar::me_vm(3tcl) from the Grammar operations and usage corner of the manual, and it's a whole vibe. let's get into it. 💅

👑 NAME 👑

grammar::me_vm — virtual machine for parsing token streams 🎀

🦋 DESCRIPTION 🦋

okay so before literally anything else: go read grammar::me_intro first, because it gives you the overview of these various documents and how they all relate. iykyk. 📚

So this doc specifies a virtual machine for the controlled matching and parsing of token streams, and it builds an abstract syntax tree (short AST) that reflects the structure of the input. The special features here? Caching and reuse of partial results, caching of the input it encounters, and the ability to backtrack in both the input and the AST creation. iconic honestly. ✨

All of that makes this virtual machine especially useful for packrat parsers based on parsing expression grammars. But no cap, it is not restricted to this type of parser — normal LL and LR parsers can be implemented with it too. 💪

The next sections go like this: first the abstract state kept by ME virtual machines, and then their instruction set. let's gooo 🚀

💖 MACHINE STATE 💖

A ME virtual machine is out here managing the following state:

  • Current token CT — the token from the input that the machine is currently considering.

This info is used and modified by the instructions in TERMINAL MATCHING.

  • Current location CL — where the current token sits in the input stream, as an offset relative to the beginning of the stream. The first token is considered to be at offset 0.

This info is implicitly used and modified by the instructions in TERMINAL MATCHING and NONTERMINAL MATCHING, and it can be directly queried and modified by the instructions in INPUT LOCATION HANDLING.

  • Location stack LS — on top of all that, a stack of locations, for backtracking. Locations can be put on the stack, removed from it, and removed with setting the current location.

This info is implicitly used and modified by the instructions in TERMINAL MATCHING and NONTERMINAL MATCHING, and it can be directly queried and modified by the instructions in INPUT LOCATION HANDLING.

  • Match status OK — a boolean value, the result of the last attempt at matching input. Set to true if that attempt was successful, and false otherwise.

This info is influenced by the instructions in TERMINAL MATCHING, NONTERMINAL MATCHING, and UNCONDITIONAL MATCHING. It's queried by the instructions in CONTROL FLOW.

  • Semantic value SV — the semantic value associated with (generated by) the last attempt at matching input. Contains either the empty string or a node for the abstract syntax tree constructed from the input.

This info is influenced by the instructions in SEMANTIC VALUES and AST STACK HANDLING.

  • AST stack AS — a stack of partial abstract syntax trees that the machine built during matching.

This info is influenced by the instructions in SEMANTIC VALUES and AST STACK HANDLING.

  • AST Marker stack MS — and on top of that, a stack of stacks, for backtracking. It's actually a stack of markers into the AST stack, so it's implicitly snapshotting the state of the AST stack at some point in time. Markers can be put on the stack, dropped from it, and used to roll the AST stack back to an earlier state.

This info is influenced by the instructions in SEMANTIC VALUES and AST STACK HANDLING.

  • Error status ER — error info associated with the last attempt at matching input. Contains either the empty string or a list of 2 elements: a location in the input and a list of error messages associated with it, in that order.

Heads up bestie, error info can be set even if the last attempt at matching input was successful. For example, the *-operator (matching a sub-expression zero or more times) in a parsing expression grammar is always successful, even if it encounters a problem further in the input and has to backtrack. Those problems must not be forgotten when continuing to match. 😤

This info is queried and influenced by the instructions in TERMINAL MATCHING, NONTERMINAL MATCHING, and ERROR HANDLING.

  • Error stack ES — plus a stack of error information, to allow the merging of current and older error info when performing backtracking in choices after an unsuccessful match.

This info is queried and influenced by the instructions in TERMINAL MATCHING, NONTERMINAL MATCHING, and ERROR HANDLING.

  • Return stack RS — a stack of program counter values, i.e. locations in the code that controls the virtual machine, for the management of subroutine calls, i.e. the matching of nonterminal symbols.

This info is queried and influenced by the instructions in NONTERMINAL MATCHING.

  • Nonterminal cache NC — a cache of machine states (a 4-tuple containing a location in the input, match status OK, semantic value SV, and error status ER) keyed by the name of the nonterminal symbol and the location in the input stream.

The key location is where the machine started the attempt to match the named nonterminal symbol, and the location in the value is where the machine ended up after the attempt completed, independent of the success of the attempt.

This status is queried and influenced by the instructions in NONTERMINAL MATCHING.

🔥 MACHINE INSTRUCTIONS 🔥

Now that the machine state is fully specified, we can explain the instruction set of ME virtual machines. They're grouped roughly by the machine state they influence and/or query. slay. 💅

🌈 TERMINAL MATCHING 🌈

First up: the instructions to match tokens from the input stream, and by extension all terminal symbols.

These instructions are the only ones that may retrieve a new token from the input stream. That's a may and not a will, because the instructions will retrieve a new token if, and only if, the current location CL is at the head of the stream. If the machine has backtracked (see icl_rewind), the instructions will retrieve the token to compare against from the internal cache. 🧠

  • ict_advance message — tries to advance to the next token in the input stream, i.e. the one after the current location CL. The instruction will fail if, and only if, the end of the input stream is reached, i.e. if there is no next token.

The success/failure of the instruction is remembered in the match status OK. In the case of failure, the error status ER is set to the current location and the message message. In the case of success, the error status ER is cleared, the new token is made the current token CT, and the new location is made the current location CL.

The argument message is a reference to the string to put into the error status ER, if such is needed.

  • ict_match_token tok message — tests the current token CT for equality with the argument tok and records the result in the match status OK. The instruction fails if the current token is not equal to tok.

In case of failure, the error status ER is set to the current location CL and the message message, and the current location CL is moved one token backwards. Otherwise, i.e. upon success, the error status ER is cleared and the current location CL is not touched.

  • ict_match_tokrange tokbegin tokend message — tests the current token CT for being in the range of tokens from tokbegin to tokend (inclusive) and records the result in the match status OK. The instruction fails if the current token is not inside the range.

In case of failure, the error status ER is set to the current location CL and the message message, and the current location CL is moved one token backwards. Otherwise, i.e. upon success, the error status ER is cleared and the current location CL is not touched.

  • ict_match_tokclass code message — tests the current token CT for being a member of the token class code and records the result in the match status OK. The instruction fails if the current token is not a member of the specified class.

In case of failure, the error status ER is set to the current location CL and the message message, and the current location CL is moved one token backwards. Otherwise, i.e. upon success, the error status ER is cleared and the current location CL is not touched.

Currently the following classes are legal:

  • alnum — a token is accepted if it is a unicode alphabetical character, or a digit.
  • alpha — a token is accepted if it is a unicode alphabetical character.
  • digit — a token is accepted if it is a unicode digit character.
  • xdigit — a token is accepted if it is a hexadecimal digit character.
  • punct — a token is accepted if it is a unicode punctuation character.
  • space — a token is accepted if it is a unicode space character.

💅 NONTERMINAL MATCHING 💅

The instructions in this section handle the matching of nonterminal symbols. They query the nonterminal cache NC for saved information, and they put such information into the cache.

Using the cache is a performance aid for backtracking parsers — it lets them avoid an expensive rematch of complex nonterminal symbols if they've been encountered before. obsessed. 💖

  • inc_restore branchlabel nt — checks if the nonterminal cache NC contains information about the nonterminal symbol nt, at the current location CL. If that is the case, the instruction will update the machine state (current location CL, match status OK, semantic value SV, and error status ER) with the found information and continue execution at the instruction referred to by the branchlabel. The new current location CL will be the last token matched by the nonterminal symbol, i.e. belonging to it.

🦋 to be continued, bestie…

okay so if no info was found, the instruction will continue execution at the next instruction. no cap. 💅

Together with icf_ntcall it's possible to generate code for memoized and non-memoized matching of nonterminal symbols, either as subroutine calls, or inlined in the caller. periodt.

  • inc_save nt — this instruction saves the current state of the machine (current location CL, match status OK, semantic value SV, and error status ER) to the nonterminal cache NC. It will also pop an entry from the location stack LS and save it as the start location of the match.

It is expected to be called at the end of matching a nonterminal symbol, with nt the name of the nonterminal symbol the code was working on. This allows the instruction inc_restore to check for and retrieve the data, should we have to match this nonterminal symbol at the same location again, during backtracking. 💖

  • icf_ntcall branchlabel — this instruction invokes the code for matching the nonterminal symbol nt as a subroutine. To this end it stores the current program counter PC on the return stack RS, the current location CL on the location stack LS, and then continues execution at the address branchlabel.

The next matching icf_ntreturn will cause the execution to continue at the instruction coming after the call.

  • icf_ntreturn — this instruction will pop an entry from the return stack RS, assign it to the program counter PC, and then continue execution at the new address.

✨ UNCONDITIONAL MATCHING ✨

The instructions in this section are the remaining match operators. They change the match status OK directly and unconditionally. no filter, just vibes. 💅

  • iok_ok — this instruction sets the match status OK to true, indicating a successful match. slay.
  • iok_fail — this instruction sets the match status OK to false, indicating a failed match. rip.
  • iok_negate — this instruction negates the match status OK, turning a failure into a success and vice versa. it's giving plot twist. 😭

🔥 CONTROL FLOW 🔥

The instructions in this section implement both conditional and unconditional control flow. The conditional jumps query the match status OK. iykyk.

  • icf_jalways branchlabel — this instruction sets the program counter PC to the address specified by branchlabel and then continues execution from there. This is an unconditional jump. no questions asked. 💅
  • icf_jok branchlabel — this instruction sets the program counter PC to the address specified by branchlabel. This happens if, and only if the match status OK indicates a success. Otherwise it simply continues execution at the next instruction. This is a conditional jump.
  • icf_jfail branchlabel — this instruction sets the program counter PC to the address specified by branchlabel. This happens if, and only if the match status OK indicates a failure. Otherwise it simply continues execution at the next instruction. This is a conditional jump.
  • icf_halt — this instruction halts the machine and blocks any further execution. full stop. ✋

🎀 INPUT LOCATION HANDLING 🎀

The instructions in this section are for backtracking, they manipulate the current location CL of the machine state. They allow a user of the machine to query and save locations in the input, and to rewind the current location CL to saved locations, making them one of the components enabling the implementation of backtracking parsers. iconic behavior. 💖

  • icl_push — this instruction pushes a copy of the current location CL on the location stack LS.
  • icl_rewind — this instruction pops an entry from the location stack LS and then moves the current location CL back to this point in the input. rewind time bestie. ⏪
  • icl_pop — this instruction pops an entry from the location stack LS and discards it. bye felicia. 👋

🦋 ERROR HANDLING 🦋

The instructions in this section provide read and write access to the error status ER of the machine. let's get into it.

  • ier_push — this instruction pushes a copy of the current error status ER on the error stack ES.
  • ier_clear — this instruction clears the error status ER.
  • ier_nonterminal message — this instruction checks if the error status ER contains an error whose location is just past the location found in the top entry of the location stack LS. Nothing happens if no such error is found. Otherwise the found error is replaced by an error at the location found on the stack, having the message message.
  • ier_merge — this instruction pops an entry from the error stack ES, merges it with the current error status ER and stores the result of the merge as the new error status ER.

The merge is performed as described below:

If one of the two error states is empty the other is chosen. If neither error state is empty, and referring to different locations, then the error state with the location further in the input is chosen. If both error states refer to the same location their messages are merged (with removing duplicates).

🌸 SEMANTIC VALUES 🌸

The instructions in this section manipulate the semantic value SV. so important.

  • isv_clear — this instruction clears the semantic value SV.
  • isv_terminal — this instruction creates a terminal AST node for the current token CT, makes it the semantic value SV, and also pushes the node on the AST stack AS.
  • isv_nonterminal_leaf nt — this instruction creates a nonterminal AST node without any children for the nonterminal nt, and makes it the semantic value SV.

This instruction should be executed if, and only if the match status OK indicates a success. In the case of a failure isv_clear should be called. 💅

  • isv_nonterminal_range nt — this instruction creates a nonterminal AST node for the nonterminal nt, with a single terminal node as its child, and makes this AST the semantic value SV. The terminal node refers to the input string from the location found on top of the location stack LS to the current location CL (both inclusive).

This instruction should be executed if, and only if the match status OK indicates a success. In the case of a failure isv_clear should be called.

  • isv_nonterminal_reduce nt — this instruction creates a nonterminal AST node for the nonterminal nt and makes it the semantic value SV.

All entries on the AST stack AS above the marker found in the top entry of the AST Marker stack MS become children of the new node, with the entry at the stack top becoming the rightmost child. If the AST Marker stack MS is empty the whole stack is used. The AST marker stack MS is left unchanged.

This instruction should be executed if, and only if the match status OK indicates a success. In the case of a failure isv_clear should be called.

💜 AST STACK HANDLING 💜

The instructions in this section manipulate the AST stack AS, and the AST Marker stack MS. let's go.

  • ias_push — this instruction pushes the semantic value SV on the AST stack AS.
  • ias_mark — this instruction pushes a marker for the current state of the AST stack AS on the AST Marker stack MS.
  • ias_mrewind — this instruction pops an entry from the AST Marker stack MS and then proceeds to pop entries from the AST stack AS until the state represented by the popped marker has been reached again. Nothing is done if the AST stack AS is already smaller than indicated by the popped marker.
  • ias_mpop — this instruction pops an entry from the AST Marker stack MS and discards it.

💀 BUGS, IDEAS, FEEDBACK 💀

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category grammar_me 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.

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.

⭐ KEYWORDS ⭐

grammar, parsing, virtual machine

👑 CATEGORY 👑

Grammars and finite automata

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

that's the tea from tcllib version 0.2, page grammar::me_vm(3tcl). stay iconic bestie 💅✨

📦 where this page comes from