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

1 Answer

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

• "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)." this is clarifying. Thanks. – user56834 Apr 4 '20 at 12:34
• Cntd. But it doesnt answer the other direction: given a grammar that generates a type n language, we can construct a type n automaton that recognizes it, but can we also construct a type n automaton that parses it? Or is it sometimes the case that you need for example a turing machine to parse a context free grammar even though you can have a pushdown automaton to recognize it? – user56834 Apr 4 '20 at 12:36
• As I explained in my answer, given just a language, you cannot possibly parse it, since parsing requires a grammar. The Chomsky hierarchy is a hierarchy of recognizers, not a hierarchy of parsers. A "type $n$ automaton" is a recognizer. It cannot possibly parse anything. – Yuval Filmus Apr 4 '20 at 13:05
• Yes I understand that you need a grammar to parse a string as you explained in the answer. But parsing is ALSO a task to be performed, and at least a Turing machine can do this for arbitrary grammars. I am asking: if we know that the language of a grammar G is recognizable by e.g. a pushdown automaton (so we know G is a context-free grammar), does that also tell us something about the automaton that we need to parse G? e.g. could we construct a pushdown automaton (a different one from the one used to recognize L(G) ) to parse G? – user56834 Apr 4 '20 at 13:13
• Same language can have many equivalent grammars —> and the same grammar and input can have many parse trees! – D. Ben Knoble Apr 4 '20 at 14:33