2
$\begingroup$

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
Improve this question
$\endgroup$
1
  • 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
    Commented Oct 15, 2018 at 4:04

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.