A parsing method for context-free tree languages
Karl M. Schimpf · 1982
Tree structures (or hierarchies) are commonly used by computer scientists. For example, data bases, theorem proving, or even descriptions of abstract data types use tree structures. This dissertation presents a new, more general form of tree pattern matching which allows one to test if a given tree fits a particular type of pattern. In particular, it presents a new form of tree automaton called a tree pushdown automaton, shows that the class of languages recognized by tree pushdown automata is identical to the class of context-free (outside-in) tree languages, and presents a parser constructor for the tree pushdown automaton which will construct a deterministic parser (called the BUTLR(0) parser) for a subclass of the context-free tree languages. Furthermore, the method of constructing the BUTLR(0) parser mimics LR(0) techniques for context-free string grammars by lifting these techniques up to Hence, the BUTLR(0) parser is constructed by building a bottom-up tree automaton, called the automaton, to recognize the set of characteristic trees. The automaton is then converted to a tree pushdown automaton by augmenting the automaton with internal memory in the form of trees, and the addition of stack-like operations on these