Knuth's original attribute grammar paper (title: Semantics of Context-Free Languages) introduced three types of circularity. More specifically section "Testing for circularity" page 134-5 figures 3.1-3. I am wondering if it's possible someone would explain in simple terms the three types of circularities. I am very confused.

I think there should be either direct or indirect dependencies.

By direct, I mean

A.attr := B.attr
B.attr := A.attr

By indirect, I mean

A.attr := B.attr
B.attr := C.attr
... maybe more steps ...
C.attr := A.attr
  • 1
    $\begingroup$ It's important to understand that the problem is not finding a circularity in a particular evaluation. Given a dependency graph on a concrete parse, it's easy to figure out if there is a circularity. Knuth's algorithm determines whether any parse tree which might be generated by the grammar has a circular dependence. $\endgroup$
    – rici
    Oct 15, 2018 at 4:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.