S-attributed, L-attributed and evaluation orders

Why it exists

An SDD says what each attribute equals but not in which order to compute them, nor when during compilation. The most useful answer is: while parsing, in a single pass, with no explicit tree and no dependency graph. That works only if the rules are written so that every value is available when it is needed. The two classes of definitions that allow this, S-attributed and L-attributed, are what GATE asks about.

Prerequisites

You need attributes, annotated parse trees and the dependency graph (syntax-directed definitions).

Precise definitions

Evaluation order in general. For a given parse tree, any topological order of the dependency graph is a valid order; if the graph has a cycle there is none. The compiler could build the tree and the graph and sort them, but that is slow and memory-hungry, so practical compilers restrict the SDD.

S-attributed definition. An SDD in which all attributes are synthesized. Every rule defines an attribute of the left-hand symbol from attributes of the right-hand symbols. Evaluation: any bottom-up order works, for example the postorder of the tree. Consequently an S-attributed SDD can be evaluated by an LR parser: keep the attribute values on the parse stack next to the symbols (a value stack), and when the parser reduces by $A \to X_1 \cdots X_k$ it computes the attributes of $A$ from the values of $X_1, \dots, X_k$ that lie on top of the stack and replaces them by the value of $A$. The desk calculator is the standard example.

L-attributed definition ("left to right"). An SDD in which, in every production $A \to X_1 X_2 \cdots X_n$, each inherited attribute of $X_j$ depends only on

1. the inherited attributes of the left-hand side $A$, and
2. any attributes (inherited or synthesized) of the symbols $X_1, \dots, X_{j-1}$ to the left of $X_j$ in the production, and
3. the attributes of $X_j$ itself, provided they do not form a cycle.

Synthesized attributes are unrestricted (they may depend on anything in the production). In words: information may flow up, and down or to the right, but never from the right to the left and never from the left-hand side's synthesized attributes down to a child.

Containment. Every S-attributed SDD is L-attributed (it has no inherited attributes, so condition 1 to 3 hold vacuously). Not every L-attributed SDD is S-attributed. So S-attributed $\subset$ L-attributed $\subset$ (acyclic SDDs). There are definitions that are acyclic and well defined but not L-attributed (the example below).

Evaluating an L-attributed SDD in one pass. Visit the tree depth first, children left to right: before visiting a child $X_j$ compute its inherited attributes (they depend only on things already known); after all children have been visited compute the synthesized attributes of the node. This is exactly what a recursive-descent parser does naturally:

• a procedure for nonterminal $A$ takes the inherited attributes of $A$ as parameters;
• it returns the synthesized attributes of $A$ as its result (or through output parameters);
• before calling the procedure of $X_j$ it computes the arguments (the inherited attributes of $X_j$).

The same holds for LL(1) predictive parsing. L-attributed SDDs can also be evaluated during bottom-up parsing by first converting them to translation schemes and introducing marker nonterminals for the inherited attributes (translation schemes), but the details are beyond what is usually asked.

Removing left recursion changes the attributes. The expression grammar $E \to E_1 + T \mid T$ is S-attributed with E.val = E1.val + T.val. After left recursion is removed ($E \to T R$, $R \to + T R_1 \mid \varepsilon$) the value is accumulated with an inherited attribute R.i: R.i = T.val in $E \to T R$; R1.i = R.i + T.val in $R \to + T R_1$; R.s = R.i in $R \to \varepsilon$; R.s = R1.s in $R \to + T R_1$; E.val = R.s. The result is L-attributed, so it can be evaluated by the LL(1) parser.

How it works

The animation evaluates exactly these rules on the tree of 3 + 4 + 5. The sum so far travels down as the inherited attribute R.i: 3, then 7, then 12; when the input is exhausted ($R \to \varepsilon$) it is turned into the synthesized R.s, which is copied up to E.val. Note the shape: the tree leans to the right, yet the grouping is still $(3 + 4) + 5$, because the inherited attribute adds from the left.

Now a definition that is not L-attributed. In $S \to A B$ the rule A.i = B.s makes the inherited attribute of $A$ depend on the synthesized attribute of its right sibling. A left-to-right pass reaches $A$ before $B$ is known and fails. The dependency graph is acyclic though, so a topological order exists (and the animation follows it): B.s, then A.i, then A.s, then S.val.

The recursive-descent program below implements the L-attributed definition of the sum. R has the inherited attribute R.i as its parameter and returns R.s; E computes the argument of R from T. Note how every rule of the SDD corresponds to a line of C.

#include <ctype.h>
#include <stdio.h>
 
static const char *p;                       /* the input */
 
static int T(void) {                        /* T -> num   { T.val = num.lexval } */
    int v = 0;
    while (isdigit((unsigned char)*p)) {
        v = v * 10 + (*p - '0');
        p++;
    }
    return v;
}
 
static int R(int i) {                       /* i is the inherited attribute R.i; the result is R.s */
    if (*p == '+') {                        /* R -> + T R1 */
        p++;
        int t = T();
        return R(i + t);                    /* R1.i = R.i + T.val;  R.s = R1.s */
    }
    return i;                               /* R -> epsilon:  R.s = R.i */
}
 
static int E(void) {                        /* E -> T R */
    int t = T();
    return R(t);                            /* R.i = T.val;  E.val = R.s */
}
 
static int eval(const char *s) {
    p = s;
    return E();
}
 
int main(void) {
    printf("%d\n", eval("3+4+5"));
    printf("%d\n", eval("10+20"));
    printf("%d\n", eval("7"));
    return 0;
}

12
30
7

Worked examples

Cheat box

Traps and GATE patterns

Connections

The definitions evaluated here are those of syntax-directed definitions. Executing the semantic rules as actions during parsing is translation schemes. The parsers involved are LL(1) and LR; the grammar transformation that creates the inherited attribute is in left recursion removal. Code generation uses these ideas in intermediate code generation.

PYQs

Given the following syntax-directed translation rules:

Rule 1:

R → AB { B.i = R.i - 1;  A.i = B.i;  R.i = A.i + 1; }

Rule 2:

P → CD { P.i = C.i + D.i;  D.i = C.i + 2; }

Rule 3:

Q → EF { Q.i = E.i + F.i; }

Which ONE is the CORRECT option among the
following?

Which of the following statements is/are FALSE?

Consider the production A ⟶ PQ and A ⟶  XY.
Each of the five non-terminals A, P, Q, X and Y has
two attributes:s is a synthesized attribute, and i is an
inherited attribute. Consider the following rules:-

 Rule 1 : P.i = A.i + 2, Q.i = P.i + A.i and A.s = P.s + Q.s
 Rule 2 : X.i = A.i + Y.s and Y.i = X.s + A.i

Which one of the following is TRUE?

Consider the following grammar and the semantic
actions to support the inherited type declaration
attributes. Let X1, X2, X3, X4, X5 and X6 be the
placeholders for the non-terminals D, T, L or L1 in
the following table :
Production Rule
Semantic Action
D → TL
X1.type = X2.type
T → int
T.type = int
T →float
T.type = float
L →  L1, id
X3.type = X4.type
addType(id.entry,
X5.type)
L → id
addType(id.entry,
X6.type)
     Which one of the following are the appropriate choices
for X1, X2, X3 and X4?

Self-check

Revision card

References