Example of attribute grammar that is NOT l-ORD but non-circular

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.

• You mean $l$-ordered, right? I and l are painfully ambiguous.
– rici
Sep 14 at 20:19
• 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.
– rici
Sep 14 at 20:26
• Do you have an example? I really appreciate it. Thank you Sep 14 at 20:40
• I didn't have an example but site search found this for me: cs.stackexchange.com/a/90947/4416
– rici
Sep 15 at 2:01

2 Answers

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.

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).