What is the relation between parsing languages and checking languages?

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)?

There is a simple relation between the two problems, but it goes in only one side: if you can parse, then you can recognize. Indeed, if you run the parser and it outputs failure, then the input is not in the language; if the parser produces a parse tree, the input is in the language.

Note, however, that a parser and a recognizer are not only solving different problems, but are also given different specs. A recognizer is given a language in some abstract form. In contrast, a parser is given a grammar, which not only implicitly defines a language, but also instructs the parser how to convert a valid input into a parse tree. Since the same language can have many equivalent grammars, it's not clear what it even means to convert a recognizer to a parser – what grammar should the parser use?

Why are recognizers interesting, then? Precisely because of the one-sided connection, which states that a parser can be converted to a recognizer. This relation implies that if your language is hard to recognize, then you won't be able to parse it (using a certain class of algorithms).

StackExchange Computer Science Q#123593, answer score: 4