I have looked at a number of textbooks on computability theory. They typically have the following form:
Define a language class (regular, context-free, context-sensitive, recursively enumerable)
Define an automaton that recognizes the class (finite automaton, pushdown automaton, linear-bounded automaton, turing machine)
However, another fundamental question is how to parse a language. I have not found an treatment of parsing as a computational problem in these textbooks.
Is there a simple relation between an automaton that recognizes a language, and an automaton that parses the language (and outputs a parse tree)?