parse tree

The parse tree is a tree-like structure that you construct when you apply ️combinators to 🧩parsers. It’s the parser equivalent of a call graph.

• The leaf nodes of this structure are basic parsers, like 🧩int, 🉑ascii, and 🧩float.
• The parent nodes are combinators such as ⚙️map, ⚙️many, and ⚙️then.

The parse tree is an important concept:

• It guides control flow and creates a link between the parser’s structure and user code.
• It describes how failures are propagated.
• It can be used to understand otherwise intractable parser architectures.

In spite of this, there isn’t a single “parse tree” in the implementation.

There’s three of them!

• The 🧩🛠️API Node tree, which is what users work with when constructing parsers.
• The core-node tree, which is the actual parser structure, consisting of closures within closures and no class in sight.
• The meta-node tree, which is a real tree structure with children that can be inspected.

The connections between the nodes in different trees work like this.

graph TB
classDef x fill:#sss
API["API node"]
CORE["CORE node"]
META["META node"]
class API,META,CORE x
API--constructs-->CORE
API--constructs-->META
CORE--references-->META

Loading

Why the split?

A good question here is – why do we need three trees? Why not one?

• Separation of concerns
• Engine-level performance considerations
• Narrowing the public API

To understand that, let’s take a look at what each tree does and is good for.

API Tree

This tree is where the public interface is located and where parser construction happens. It has fancy types, elaborate parser constructors, and can involve doing a lot of processing work.

Meta node

This is the inspectable version of the tree with the tree climbing gear. It has lots of methods for navigating the tree structure, getting all descendants, stuff like that. However, it contains no parser logic at all.

That kind of interface would be really out of place as part of the API node and just confuse users who want to build parsers.

Core node

Core nodes is where the parsing logic resides. A core node is an object with a single apply method, which invokes its parser logic and advances the parsing state. That’s it!

• Functions are deoptimized when they are polymorphic — their code puts different-looking objects into the same variables.

• Core nodes are inherently homogenous — they just consist of an apply function. All the parser logic and parameters are wrapped up in closures.

• This lets parser logic avoid the deoptimization penalty that comes with polymorphism.