0
$\begingroup$

I am trying to understand "On the complexity of general context-free language parsing and recognition" by Walter L. Ruzzo. One of the results from the paper is about generating a parse tree when only a (blackbox) recognizer is given. Unfortunately, I am stuck at the sentence "Given recognizers for these languages, we can implement the "divide and conquer" parsing strategy outlined above." from the paper (p 491).

The question is, where do these recognizers (that the paper mentions in that sentence) suddenly come from? Given the rather succinct explanation in the paper, I am also finding it difficult to form an intuition about how this algorithm works. What is required out of the blackbox recognizer to derive a parse tree using this algorithm? Do I need to keep information about which nonterminals recognize which parts of the input? (Given that multiple grammars can recognize the same language, this seems like a requirement, but the paper doesn't seem to say so) If not, how does this work?

Editing to provide additional context: The confusing aspect of this paper is its claim: "We will show how to construct from any recognizer a parser which is only about $log n$ times slower than the recognizer (on strings of length $n$)." A recognizer is an oracle that tells you whether a particular input is in the language or not. Given such a recognizer, and assuming the grammar is given, there is no mention in the paper anywhere about constructing additional recognizers for substrings of the language. Without such additional recognizers, I am not clear how the parse tree construction works in this algorithm.

My reference for background research as requested by D.W: Dick Grune and Ceriel J. H. Jacobs. Parsing Techniques: A Practical Guide (Second Edition). Springer, 2008.

Improve this question
$\endgroup$
4
  • $\begingroup$ 1. Do you have a link to a freely available PDF of the paper? Can you edit your question to link to it? 2. Recognizers for what? What research have you done? Have you read a standard textbook on context-free languages and testing membership of a word in a CFL? $\endgroup$
    – D.W. ♦
    Jan 20 at 6:47
  • $\begingroup$ Unfortunately, I do not see a non-paywalled version of the PDF. I have edited the question. The sentence containing "recognizers" are what I do not understand in the paper. I have added the text I use for reference. $\endgroup$
    – Rahul Gopinath
    Jan 20 at 7:08
  • $\begingroup$ Let me clarify this; I understand what the recognizers are. I do not understand where the particular recognizers mentioned in the paper comes from because we start with a single recognizer for a language. $\endgroup$
    – Rahul Gopinath
    Jan 20 at 9:06
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/156978/755, cstheory.stackexchange.com/q/52394/5038. Please do not post the same question on multiple sites. $\endgroup$
    – D.W. ♦
    Jan 22 at 4:26

1 Answer 1

Reset to default
0
$\begingroup$

A recognizer is any algorithm that, given a context-free grammar $G$ and a word $x \in \Sigma^*$, tests whether $x \in L(G)$. There are standard algorithms to do that, e.g., Earley parsers or CYK parser.

The paper appears to essentially be saying: "given any recognizer (I don't care where you got it from), we can extend it to also provide the functionality of parsing".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.