0
$\begingroup$

I am wondering if there exists an example attribute grammar that is non-circular but not l-ordered (l-ORD) as well.

The reason I am asking this is one can find an attribute grammar that is circular, then it will obviously not be an l-ORD. But I am wondering if there even exists a non-circular AG that is also not l-ORD.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You mean $l$-ordered, right? I and l are painfully ambiguous. $\endgroup$
    – rici
    Sep 14, 2021 at 20:19
  • $\begingroup$ There are non-circular AGs which are not strongly non-circular. Any of those would work. My memory is that a strongly non-circular AG might not be $l$-ordered but can be transformed into an essentially equivalent $l$-ordered AG. It's been a while, though, so I might be wrong. $\endgroup$
    – rici
    Sep 14, 2021 at 20:26
  • $\begingroup$ Do you have an example? I really appreciate it. Thank you $\endgroup$
    – Node.JS
    Sep 14, 2021 at 20:40
  • $\begingroup$ I didn't have an example but site search found this for me: cs.stackexchange.com/a/90947/4416 $\endgroup$
    – rici
    Sep 15, 2021 at 2:01

3 Answers 3

Reset to default
1
$\begingroup$

In Figure 12 of my paper on conditional attribute grammars, it gives the following strongly non-circular attribute grammar that is not doubly non-circular (and therefore not l-ORD):

S -> 0 L
    L.inh1 = 0
    L.inh2 = L.syn1
    S.result = L.syn2

S -> 1 L
    L.inh2 = 0
    L.inh1 = L.syn2
    S.result = L.syn1

L ->
    L.syn1 = L.inh1
    L.syn2 = L.syn2

It is non-circular (even strongly non-circular) since each synthesized attribute of L depends only on the corresponding inherited attribute, but depending on the context, each may need to be done before the other. Hence no fixed order of attributes can be required.

Improve this answer
$\endgroup$
0
$\begingroup$

You could take an L-Ord Attribute Grammar, replace all inherit attributes by synthetic attributes and all synthetic attributes by inherit ones and reverse all assignments... then you have a grammar that isn't L-Ord and still non-circular. I would call that R-Ord, because you have reversed all arrows and can traverse it right-to-left instead of left-to-right.

Improve this answer
$\endgroup$
0
$\begingroup$

The Grammar in my answer to Full circularity vs strong circularity for attribute grammars (that you had already found) is also not L-Ord, because L-Ord Attribute Grammars are strongly-non-circular. Since said grammar isn't strongly-non-circular, it's not L-Ord. (And it's also not circular).

Improve this answer
$\endgroup$

Your Answer

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

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