2
$\begingroup$

Attributes of an attribute grammar can have a circular dependency. In my compiler construction course I learned, that there are two types of circularity for attribute grammars:

  • full circularity can be checked in exponential time
  • strong circularity can be checked in polynomial time

Full circularity implies strong circularity, but not vice versa, so if there is an attribute grammar that is strong circular, it might still not be full circular. Thus, if I reject all strong circular attribute grammars, I might reject some grammars even though they are not full circular. I tried to come up with a dividing example to better understand this case, that is an attribute grammar that is strong circular but not full circular, but with no luck yet.

Question

  • Is there a dividing example that makes the difference clear?
  • Are there well known real-world attribute grammars that are strong circular but not full circular?
  • Would it be a real limitation for a tool to accept only strong non-circular grammars?

I assume the terms strong circularity and full circularity are well known. If they are not you can find the lecture notes here (lecture 12, 13 and 14).

$\endgroup$
3
$\begingroup$

You are using the terms in a weird way. A grammar can be circular or non-circular. Since FULLY testing this property is EXPTIME, one wants a simpler (easier to test) property. This is where strong NON-circularity comes in. In strong non-circularity, you basically combine the dependencies of all possible sub-trees, even for combinations that can't appear together. So if a grammar is strong non-circular, it particularly rules out the combinations that CAN happen together. I.e. the grammar is non-circular.

So this means that strong NON-circularity implies NON-circularity. Sure you can invert implications by negating both sides of it. I think this is what you did when you say that "Full circularity implies strong circularity". But I don't think it makes sense to call a grammar that is NOT strongly NON-circular "strong circular". IMHO that would be a confusing term, because it sounds like such a grammar was "even more circular" than other grammars, but it is the opposite - it only fails the strong-non-circularity test which isn't a necessary condition. So such a grammar would rather be "less circular" than other grammars, because it "looks circular" without necessarily being circular. But that doesn't sound right either (because in the end, it is either circular or not). If anything, I would call it "weakly circular", because that property doesn't guarantee anything - to be certain, you still need to apply the full circularity test.

To adress the question: in practice you usually only work with S-Attribute Grammars, which don't even need to be tested for circularity, because they can't be circular.

I dug out this example (attributes starting with i are inherit attributes, attributes starting with s are synthetic ones):

S -> A
    ix.1 = 1        (1)
    iy.1 = 2        (2)
    sx.0 = sz.1     (3)
A -> A a
    ix.1 = sy.1     (4)
    iy.1 = ix.0     (5)
    sy.0 = sz.1     (6)
    sz.0 = 0        (7)
A -> a
    sy.0 = 0        (8)
    sz.0 = ix.0     (9)
A -> b
    sy.0 = iy.0     (10)
    sz.0 = 0        (11)

this grammar is non-circular, but it fails the strong-non-circularity test, because in the strong-non-circularity test, you take the union of the dependency-sets for the productions of the same nonterminal. So you have the edges for both A->a and A->b together, although they can't appear together (because you can't apply both productions at the same time).

The production of A -> A a then yields the following dependency-graph: let Q and R be the prefixes for the two A's in the production, then you have the nodes

{ Qia, Qib, Qsb, Qsc, Ria, Rib, Rsb, Rsc }

and the edges

{ (Qsb, Qia),     from (4)
  (Qia, Rib),     from (5)
  (Rib, Rsb),     from (10)
  (Rsb, Ria),     from (4)
  (Ria, Rsc),     from (9)
  (Rsc, Qsb)      from (6)
}

this is a cycle and therefore the strong-non-circularity test fails. The point why the strong-non-circularity test is wrong here, is because the edges (Rib, Rsb) and (Ria, Rsc) come from different productions.

$\endgroup$
  • $\begingroup$ Note: the production S -> A seems useless, but it is there, because we use start-separated grammars by convention and the (unique) start-production isn't allowed to have inherit attributes. $\endgroup$ – Algoman Apr 22 '18 at 12:20

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.