<p>What is this step called to convert a parse tree into a pattern tree?</p>
<p>I need to understand terminologies on the act of conversion/rebalancing the parse tree such that the most simplistic regular expression (regex) are closest to the root node and conversely, the most open-ended regex (wildcard) are located at the end nodes of a pattern tree.</p>
<p>Some actions that I lacked words for that come to mind are:</p>
<ol>
<li><p>Pulling patterns from a parse tree full of token and expressions into a deterministic form of Aho-Corasick-like tree.</p>
</li>
<li><p>Translating large number of Bison/Lexx spec files for a quickest identification of content (ie., Unix <code>file</code> command).</p>
</li>
</ol>
<p>Real world applications are EBNF, <code>VimL</code> (<code>vimscript</code>), <code>TextMate</code> spec files into a low O-order search algorithm.</p>

<parsing><lexing><compiler-inference>
What do you call the act of rebalance an parse tree so simplistic regex are closest to the root node over variables/identifiers?
CC BY-SA 4.0
2024-09-12T09:00:24.880Z
I don't think I understand. Are you trying to implement a parser *that parses regexes*? Or do you have a language *in which regexes are a primitive*, such that there are nodes in your AST that represent individual regexes? Or exactly what?
Karl Knechtel
CC BY-SA 4.0
2024-09-12T11:53:07.073Z
It is about taking all the known concrete syntax trees/graphs and putting together and making something like a Unix file command but with the goal of making a close to O(1) search pattern engine as possible. Many CST/CSG specs have regex expressions. Not even getting to content processing stage here ... yet. Rearranging and regrouping state loops. Theorectical.
John Greene
CC BY-SA 4.0
2024-09-12T12:01:11.237Z
By the way, I recalled that this SE info states that it does not focus on AST.
John Greene
<p>I don’t know if there’s another term of art for this, but it’s a kind of topological sorting by a partial ordering. This comes up in pattern matching, generic function instantiation, and multimethod dispatch, particularly when you want to find the unique most specific matching pattern for a given input. A special case in typechecking is <em>subsumption</em>, where you want to check that a definition’s inferred type is at least as general as its declared type signature.</p>
<p>You have a partially ordered set (poset) of patterns, where <span class="math-container">$P &lt; Q$</span> if <span class="math-container">$P$</span> is <em>less general than</em> <span class="math-container">$Q$</span>, meaning that <span class="math-container">$Q$</span> matches at least everything <span class="math-container">$P$</span> does. In other words <span class="math-container">$P$</span> is <em>more specific than</em> <span class="math-container">$Q$</span>. Incomparable elements are patterns like (regex) <code>a.</code> and <code>.b</code> where neither one matches everything that the other does. All atomic patterns like <code>a</code> and <code>b</code> are incomparable in this way. They’re also “<a href="https://en.wikipedia.org/wiki/Atom_(order_theory)" rel="nofollow noreferrer">atomic elements</a>” of the poset, meaning minimal among the nonzero elements.</p>
<p>You can define this ordering in various ways depending on the pattern language. For a regular language, you can consider <span class="math-container">$P &lt; Q$</span> when their difference (intersection with complement) is empty: <span class="math-container">$P \setminus Q = P \cap \neg Q$</span> and <span class="math-container">$(P \setminus Q = \emptyset) \iff (P \subseteq Q)$</span>. Computing this is decidable in polynomial time, for example using the <a href="https://en.wikipedia.org/wiki/Brzozowski_derivative" rel="nofollow noreferrer">Brzozowski derivative</a>.</p>
<p>However, it’s easy for large inputs or extensions to the pattern language to make that method intractable or undecidable, so it’s more typical to define an ordering recursively. You can handle some cases precisely, like any pattern is less general than a wildcard <span class="math-container">$a &lt; \top$</span>, and ordering distributes over sequences of patterns, <span class="math-container">$ab &lt; cd$</span> if <span class="math-container">$a &lt; b$</span> and <span class="math-container">$c &lt; d$</span>. Other cases like choice <span class="math-container">$a+b \stackrel{?}{&lt;} c+d$</span> you might handle heuristically.</p>
<p>Standard toposort algorithms apply, although I’ll note that if you have a term, you don’t need to sort the whole set of patterns to find the best matching pattern for it. Instead you can just iterate over the patterns while keeping a set of the most specific incomparable matching candidates seen so far. Whenever you find a match more specific than all of them, it becomes the new sole candidate. In the end you’ll have an ambiguity (&gt;1), a unique match (=1), or no match (&lt;1).</p>
<p>You may also be interested in the next step, <a href="https://www.cs.tufts.edu/%7Enr/cs257/archive/luc-maranget/jun08.pdf" rel="nofollow noreferrer">Compiling pattern matching to good decision trees</a><sup>(PDF)</sup> (Maranget 2008).</p>

CC BY-SA 4.0
2024-09-10T15:40:54.497Z
2024-09-10T15:51:31.760Z
2024-09-10T15:51:31.760Z
Jon Purdy
CC BY-SA 4.0
2024-09-10T17:51:57.993Z
Really nailed it.  Pattern matching, generic function instantiation, poset, and multimethod dispatch with topsort is the coverage that does what I have embarked upon.  Good decision tree, too (was aiming for minimal tree over naive tree).
John Greene
# What do you call the act of rebalance an parse tree so simplistic regex are closest to the root node over variables/identifiers?
Posted by: username_0 on 2024-09-10
What is this step called to convert a parse tree into a pattern tree?

I need to understand terminologies on the act of conversion/rebalancing the parse tree such that the most simplistic regular expression (regex) are closest to the root node and conversely, the most open-ended regex (wildcard) are located at the end nodes of a pattern tree.

Some actions that I lacked words for that come to mind are:

1. Pulling patterns from a parse tree full of token and expressions into a deterministic form of Aho-Corasick-like tree.
2. Translating large number of Bison/Lexx spec files for a quickest identification of content (ie., Unix `file` command).

Real world applications are EBNF, `VimL` (`vimscript`), `TextMate` spec files into a low O-order search algorithm.
**Tags:** parsing lexing compiler-inference
> **Comments:**
> **username_1**: I don't think I understand. Are you trying to implement a parser *that parses regexes*? Or do you have a language *in which regexes are a primitive*, such that there are nodes in your AST that represent individual regexes? Or exactly what?  
> **username_0**: It is about taking all the known concrete syntax trees/graphs and putting together and making something like a Unix file command but with the goal of making a close to O(1) search pattern engine as possible. Many CST/CSG specs have regex expressions. Not even getting to content processing stage here ... yet. Rearranging and regrouping state loops. Theorectical.  
> **username_0**: By the way, I recalled that this SE info states that it does not focus on AST.  
---
## 1 answers
### Answer by username_2 on 2024-09-10. Score: 4 | Accepted answer
I don’t know if there’s another term of art for this, but it’s a kind of topological sorting by a partial ordering. This comes up in pattern matching, generic function instantiation, and multimethod dispatch, particularly when you want to find the unique most specific matching pattern for a given input. A special case in typechecking is *subsumption*, where you want to check that a definition’s inferred type is at least as general as its declared type signature.

You have a partially ordered set (poset) of patterns, where $P < Q$ if $P$ is *less general than* $Q$, meaning that $Q$ matches at least everything $P$ does. In other words $P$ is *more specific than* $Q$. Incomparable elements are patterns like (regex) `a.` and `.b` where neither one matches everything that the other does. All atomic patterns like `a` and `b` are incomparable in this way. They’re also “[atomic elements](https://en.wikipedia.org/wiki/Atom_(order_theory))” of the poset, meaning minimal among the nonzero elements.

You can define this ordering in various ways depending on the pattern language. For a regular language, you can consider $P < Q$ when their difference (intersection with complement) is empty: $P \setminus Q = P \cap \neg Q$ and $(P \setminus Q = \emptyset) \iff (P \subseteq Q)$. Computing this is decidable in polynomial time, for example using the [Brzozowski derivative](https://en.wikipedia.org/wiki/Brzozowski_derivative).

However, it’s easy for large inputs or extensions to the pattern language to make that method intractable or undecidable, so it’s more typical to define an ordering recursively. You can handle some cases precisely, like any pattern is less general than a wildcard $a < \top$, and ordering distributes over sequences of patterns, $ab < cd$ if $a < b$ and $c < d$. Other cases like choice $a+b \stackrel{?}{<} c+d$ you might handle heuristically.

Standard toposort algorithms apply, although I’ll note that if you have a term, you don’t need to sort the whole set of patterns to find the best matching pattern for it. Instead you can just iterate over the patterns while keeping a set of the most specific incomparable matching candidates seen so far. Whenever you find a match more specific than all of them, it becomes the new sole candidate. In the end you’ll have an ambiguity (>1), a unique match (=1), or no match (<1).

You may also be interested in the next step, [Compiling pattern matching to good decision trees](https://www.cs.tufts.edu/%7Enr/cs257/archive/luc-maranget/jun08.pdf)(PDF) (Maranget 2008).
> **Comments:**
> **username_0** (2024-09-10): Really nailed it.  Pattern matching, generic function instantiation, poset, and multimethod dispatch with topsort is the coverage that does what I have embarked upon.  Good decision tree, too (was aiming for minimal tree over naive tree).  
---
