2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ "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. $\endgroup$ – user56834 Apr 4 '20 at 12:34
  • $\begingroup$ 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? $\endgroup$ – user56834 Apr 4 '20 at 12:36
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 4 '20 at 13:05
  • $\begingroup$ 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? $\endgroup$ – user56834 Apr 4 '20 at 13:13
  • $\begingroup$ Same language can have many equivalent grammars —> and the same grammar and input can have many parse trees! $\endgroup$ – D. Ben Knoble Apr 4 '20 at 14:33

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.