1
$\begingroup$

It is said that attributes supply some semantic information to the grammar. Meantime, the same attributes let you to resolve ambiguities. Text books agree that it is worth haveing a CF grammar which admits ambiguities because the ambiguities will go away anyway once you evaluate your AST with attributes anyway. For this reason it is useless to invent an intractable CS grammar for your language.

This strongly associates ambiguities with context sensitivity in my mind. However, there is an expert in the field who states brazen faced that context sensitivity is absolutely irrelevant to ambiguity but supplies no support to ground his statement. Can you untangle the conflicting opinions by some light?

I cannot refrain from asking the same question in the following form. My mind is highly influenced by this description the of grammar type comparison in "Parsing Techniques: A Practical Guide"

Type n grammars are more powerful than Type n+1 grammars, for n = 0,1,2”, and one often reads statements like “A regular (Type 3) grammar is not powerful enough to match parentheses”. It means that more powerful grammars can define more complicated boundaries between correct and incorrect sentences. Some boundaries are so fine that they cannot be described by any grammar (that is, by any generative process). This idea has been depicted metaphorically in Figure 2.33, in which a rose is approximated by increasingly finer outlines. In this metaphor, the rose corresponds to the language (imagine the sentences of the language as molecules in the rose); the grammar serves to delineate its silhouette. A regular grammar only allows us straight horizontal and vertical line segments to describe the flower; the result is a coarse and mechanical-looking picture. A CF grammar would approximate the outline by straight lines at any angle and by circle segments. The result is stilted but recognizable. A CS grammar would present us with a smooth curve tightly enveloping the flower, but the curve is too smooth: it cannot follow all the sharp turns, and it deviates slightly at complicated points; still, a very realistic picture results. An unrestricted phrase structure grammar can represent the outline perfectly. The rose itself cannot be caught in a finite description; its essence remains forever out of our reach.

enter image description here

A more prosaic and practical example can be found in the successive sets of Java programs that can be generated by the various grammar types:

  1. The set of all lexically correct Java programs can be generated by a regular grammar. A Java program is lexically correct if there are no newlines inside strings, comments are terminated before end-of-file, all numerical constants have the right form, etc.
  2. The set of all syntactically correct Java programs can be generated by a context free grammar. These programs conform to the (CF) grammar in the manual.
  3. The set of all semantically correct Java programs can be generated by a CS grammar. These are the programs that pass through a Java compiler without error.
  4. The set of all Java programs that would terminate in finite time when run with a given input can be generated by an unrestricted phrase structure grammar. Such a grammar would incorporate detailed descriptions of the Java lib and the Java run-time system.
  5. The set of all Java programs that solve a given problem cannot be generated by a grammar (although the description of the set is finite).

I see that CF can generate the syntactically valid programs and you need CS grammar to accommodate the semantics of the language. This more complete grammar can resolve if x(y) is a call of a function or type conversion. It will also iron out the associativity ambiguity in a+b+c telling that difference between (a+b)+c and a+(b+c) is immaterial. For this reason I think that CF -> CS also resolves ambiguities. Why telling that context sensitivity and ambiguity are orthogonal after that?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ What book exactly are you referencing? $\endgroup$ – vonbrand Dec 27 '15 at 21:14
  • 2
    $\begingroup$ What kind of attributes are you talking about? $\endgroup$ – Raphael♦ Dec 28 '15 at 11:03
  • $\begingroup$ @Raphael The semantic actions, I guess. You know whenever parser recognizes a node, an action is fired to extract the sense from the syntax (we have the syntactic forms to wrap the content or sense into it). The same actions are normally used for context-sensitive look ahead. The parser can check if a(b) identifier is a function call or type conversion, for instance to choose the proper alternative derivation. $\endgroup$ – Valentin Tihomirov Dec 28 '15 at 19:04
  • $\begingroup$ Note that CSGs are not per se intractable. Many CSLs can be parsed in linear time! $\endgroup$ – Raphael♦ Feb 26 '16 at 21:57
2
$\begingroup$

This is plainly wrong. The set of all Java programs that always terminate is not recursively enumerable (essentially the halting problem), and so can't be generated by any grammar.

Ambiguous context free grammars are hard to parse efficiently, compiler writers prefer unambiguous grammars (or use tricks in the parser to bypass ambiguities). If the underlying grammar is ambiguous, chances are that the attributed grammar won't give a unique meaning either.

A context free grammar is called ambiguous if there is a string generated by the grammar with two different derivation trees. Context sensitive grammars don't have any similar description of the derivation that is independent of the order of productions applied, so ambiguity doesn't make sense for them.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Do you have a reference that no generative grammars could enumerate the set of all Java programs that always terminate (BTW the book is Parsing Techniques, A Practical Guide by Grune and Jacobs and references Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman for the difference of power between phrase structure and context sensitive grammars but not in the context where program termination suggested)? $\endgroup$ – AProgrammer Dec 27 '15 at 21:37
  • $\begingroup$ They give a second reference on the difference of power (again, not directly tied to the possibility to generate only terminating programs) is Introduction to Formal Languages by Révész. I've nether of the references to check, but the bibliography of Grune and Jacobs mention computational (im)possibilities and decidability as subjects of those books. $\endgroup$ – AProgrammer Dec 27 '15 at 21:53
  • $\begingroup$ In the end, you actually say that full specification of the context defeats the ambiguity to absolute zero, that they are inconsistent. This confirms our guess that supplying context reduces the ambiguity. Why should I still think that that ambiguity is orthogonal to context, that they are absolutely independent after that? $\endgroup$ – Valentin Tihomirov Dec 27 '15 at 23:10
  • $\begingroup$ @AProgrammer See this question. $\endgroup$ – Raphael♦ Dec 28 '15 at 11:10
  • 1
    $\begingroup$ "The set of all Java programs that always terminate is not recursively enumerable (essentially the halting problem)" -- I find this statement to be misleading. Having a semi-decider for R does not yield a decider for the halting problem, nor does a decider for the Halting problem yield a semi-decider for R. $\endgroup$ – Raphael♦ Dec 28 '15 at 11:12
1
$\begingroup$

First grammars describes languages. Formally context free, context sensitive and ambiguous qualify grammars and not languages (I've never seen ambiguous used to describe a language, I've seen context free and context sensitive used to describe languages with the meaning "there is at least one context free/sensitive grammar describing the language").

Ambiguous means that there are strings which may be analyzed in several ways. It is a term which may describe any kind of formal grammars able to describe the structure of valid string.

Context sensitive on the other hand is a term which, AFAIK, has a meaning only for generative grammars (those which are defined by a set of productions rules of the form $lhs \rightarrow rhs$). It means that all the rules of the grammar are context sensitive. And a rule in a generative grammar is context sensitive if only one symbol in the left hand side is replaced in the right hand side (for instance $A\; B\; C \rightarrow A\; C$ and $A\; B\; C \rightarrow A\; b_1 \; b_2 \;C$ are context sensitive, only $B$ is replaced $A\; B\; C \rightarrow D\; E\; F$ is not). Context free grammars BTW are context sensitive one where the left hand side has only one symbol.

It could be that the language you are interested in can only be described with ambiguous context free grammars and that there is a context sensitive one which is not ambiguous. That does not prevent that the concepts of ambiguous and context sensitive grammars are independent and that there are ambiguous context sensitive grammars (all the ambiguous context free one to start, and then some more).

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Quote: "I've never seen ambiguous used to describe a language". The word 'ambiguous' can be used to describe a language, e.g. in the term 'inherently ambiguous languages': there exist context-free languages for which no unambiguous context-free grammar can exist. $\endgroup$ – Anton Trunov Dec 28 '15 at 7:53
  • $\begingroup$ @AntonTrunov, why would you qualify a language with something which 1/ is a property of only its context free grammars while 2/ it can also be a property of other kinds of grammars? $\endgroup$ – AProgrammer Dec 28 '15 at 8:11
  • 1
    $\begingroup$ Well, why not? It seems like an interesting property (to me and some other people). You can find more links here en.wikipedia.org/wiki/… $\endgroup$ – Anton Trunov Dec 28 '15 at 8:25
  • 1
    $\begingroup$ That seems useful only in contexts where context free grammars are assumed. Using that nomenclature in other contexts seems a source of confusion, especially in the current one where the ambiguity of other kinds of grammars is in question (you can probably write a unambiguous context sensitive grammar, and you can surely write a unambiguous VW grammar, for that "inherently ambiguous language"). $\endgroup$ – AProgrammer Dec 28 '15 at 8:50

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.