I'm considering an extension of Sublime Text's syntax definition format. 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. <foo>, and terminated with a close tag, e.g. </foo>. 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.


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


As a basis for building tools check out libvata for a c++ library that handles finite tree automata.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.