<p>Yes, there are lots of automata models for processing XML: I recommend you look into (extensions of) finite tree automata, see e.g. this text book as an intro</p>

<p><a href="https://www.worldcat.org/title/foundations-of-xml-processing-the-tree-automata-approach/oclc/692197553" rel="nofollow noreferrer">https://www.worldcat.org/title/foundations-of-xml-processing-the-tree-automata-approach/oclc/692197553</a></p>

<p>As a basis for building tools check out <a href="https://github.com/ondrik/libvata" rel="nofollow noreferrer">libvata</a> 
for a c++ library that handles finite tree automata.</p>

CC BY-SA 4.0
2019-08-02T07:59:23.350Z
2019-08-02T07:59:23.350Z
Patrick Totzke
<p>I'm considering an extension of <a href="https://www.sublimetext.com/docs/3/syntax.html" rel="nofollow noreferrer">Sublime Text's syntax definition format</a>. A syntax definition is, in essence, a specification of a deterministic pushdown automaton. I would like to extend the system to handle some non-context-free language features, such as indentation, heredocs, and tag matching. (The system actually has some odd special-cased support for this sort of thing, but I'm looking to create a general extension.)</p>

<p>For a motivating example, consider XML. An XML element is introduced with an opening tag, e.g. <code>&lt;foo&gt;</code>, and terminated with a close tag, e.g. <code>&lt;/foo&gt;</code>. If an XML document is valid, then when we see a close tag we can take on faith that it is the correct match for the currently open element, but in practice we would like to (say) only pop the current state if we see a matching tag.</p>

<p>In essence, rather than finitely many states, we have infinitely many, including one state representing the interior of an element for each possible tag name. The transition relation would need to somehow capture the tag name and send it to the next state.</p>

<p>I haven't worked out the formal details; what I'm looking for at this point is prior art. Is there any literature on pushdown-like automata with “extra features” that would allow them to recognize languages like XML? A full LBA would be going too far, but it's not clear to me whether, say, an embedded pushdown automaton could recognize XML.</p>

<automata-theory><parsing>
DPDA with parameterized states
Thom Smith
# DPDA with parameterized states

(Asked by: username_0 on 2019-07-31)

I'm considering an extension of [Sublime Text's syntax definition format](https://www.sublimetext.com/docs/3/syntax.html). A syntax definition is, in essence, a specification of a deterministic pushdown automaton. I would like to extend the system to handle some non-context-free language features, such as indentation, heredocs, and tag matching. (The system actually has some odd special-cased support for this sort of thing, but I'm looking to create a general extension.)

For a motivating example, consider XML. An XML element is introduced with an opening tag, e.g. , and terminated with a close tag, e.g. . If an XML document is valid, then when we see a close tag we can take on faith that it is the correct match for the currently open element, but in practice we would like to (say) only pop the current state if we see a matching tag.

In essence, rather than finitely many states, we have infinitely many, including one state representing the interior of an element for each possible tag name. The transition relation would need to somehow capture the tag name and send it to the next state.

I haven't worked out the formal details; what I'm looking for at this point is prior art. Is there any literature on pushdown-like automata with “extra features” that would allow them to recognize languages like XML? A full LBA would be going too far, but it's not clear to me whether, say, an embedded pushdown automaton could recognize XML.

**Tags:** automata-theory, parsing


---

## 1 answers

### Answer by username_1 on 2019-08-02. Score: 4 | Accepted answer

Yes, there are lots of automata models for processing XML: I recommend you look into (extensions of) finite tree automata, see e.g. this text book as an intro

<https://www.worldcat.org/title/foundations-of-xml-processing-the-tree-automata-approach/oclc/692197553>

As a basis for building tools check out [libvata](https://github.com/ondrik/libvata)
for a c++ library that handles finite tree automata.


---

