1
$\begingroup$

While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below.

enter image description here

The above diagram is very helpful in understanding the correlation among the various parser grammars. All the grammar above are context free grammars. From theory of computation texts, I have the following Chomsky hierarchy of grammars in my mind.

enter image description here

Now I wonder, how to correlate these two diagrams - a possible superposition, which shall show where exactly in the Chomsky hierarchy the parser grammars lie, and their extent with respect to the boundaries already defined by Chomsky hierarchy.

If possible, could you please as well suggest the resource from which I can develop more knowledge regarding this.

PS: After the comments and discussion in the answer by Yuval Filmus, I made an attempt to draw the situation:

enter image description here If we consider on the basis of the power of language corresponding to a grammar type

If we consider just on the basis of grammar type

Reference : Theory of Computation Lectures by Prof. Harry Porter

Are the above diagrams which I have constructed as per my understanding correct? If they are not then could anyone please rectify it...

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

All of the grammars in your first figure are context-free grammars. That text seems to identify grammar with context-free grammar.

Improve this answer
$\endgroup$
4
  • $\begingroup$ All of the grammars in your first figure are context-free grammars, yes (I figured it out while self studying, based on the fact that since we are considering parsing, only CFGs have parse trees) but what I was actually looking for is which of the grammars in the first diagram are a part of DCFG and which are not. Which of them are regular etc... I guess I was not above to express myself properly. Sorry.. :( $\endgroup$
    – Abhishek Ghosh
    Sep 18, 2021 at 10:52
  • 1
    $\begingroup$ @AbhishekGhosh: an ambiguous grammar cannot be deterministic because the ambiguity is a non-determinism, by definition. However, not all unambiguous grammars are deterministic. On the other hand, all LR(k) grammars are deterministic, again by definition: the LR parser is a deterministic parser. $\endgroup$
    – rici
    Sep 18, 2021 at 15:27
  • $\begingroup$ @rici, as per your comments, I have made an edit to my question and have included my attempt of drawing the situation. $\endgroup$
    – Abhishek Ghosh
    Sep 19, 2021 at 17:24
  • $\begingroup$ @yuvalfilmus could you please just check my diagram which I have added as a post script? The non deterministic context free grammar set - unambiguous grammar set, contains all the ambiguous grammars as per my understandings. And as you said the entire first picture is now inside the context free grammar set (or shell) $\endgroup$
    – Abhishek Ghosh
    Sep 21, 2021 at 19:25

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.