Compiler Design

Answer: (iii) 11231

Reasoning (shift–reduce with actions executed on reduce)

Grammar:
$$S \to xxW \ \{\text{print }1\}, \qquad S \to y \ \{\text{print }2\}, \qquad S \to Sz \ \{\text{print }3\}$$

Input string: x x x x y z z.

Reducing the string from the input up to $S$ (the actions fire in the order the reductions are performed):

Step	Stack contents (top right)	Action	Printed
1	x x collected, W → … y	reduce xxW → S	1
2	next x x + …	reduce xxW → S	1
3	y	reduce y → S	2
4	S + z	reduce Sz → S	3
5	S + z then top combine	reduce (top-level xxW/final)	1

Collecting the prints in the order the reductions happen:

$$\boxed{11231}$$

Hence the correct choice is (iii).

Answer: (ii) 7

Calculation

$$h(27) = 27 \bmod 10 = 7$$

because $27 = 2 \times 10 + 7$. The key $27$ is initially placed at index $7$ of the hash table.

Note: if slot $7$ is already occupied (a collision, e.g. key $17$), it is resolved by chaining (linked list at slot 7) or open addressing (linear probing to slot 8, 9, ...).

$$\boxed{\text{(ii) } 7}$$

Answer: (iv) Lexical program structure

Explanation

In static (lexical) scoping, a variable reference is bound to the declaration found by looking at the textual nesting of blocks/procedures in the source code: first the innermost enclosing block, then the next one outward, and so on.

• The binding can be decided at compile time, without running the program.
• The call sequence at run time (option i) decides the binding only in dynamic scoping.
• Registers (ii) and heap location (iii) have nothing to do with name resolution.

int x = 10;
void f() { printf("%d", x); }   // x refers to the global x
void g() { int x = 20; f(); }   // still prints 10 under static scoping

$$\boxed{\text{(iv)}}$$

Answer: (iii) children of the node (option (i))

Explanation

Attributes in a syntax-directed definition are classified by the direction of their dependency:

1. Synthesized attribute (S-attribute): computed from the attribute values of the children of a node. Its value at a node is a function of the values at its descendants, so the tree is evaluated bottom-up. A classic example is E.val = E1.val * T.val.

2. Inherited attribute (I-attribute): computed from the parent and/or siblings — flows top-down or sideways.

Since the question is about synthesized attributes, they are calculated:

$$\boxed{\text{from the values of the attributes of the children of the node → option (i)}}$$

What is an activation record? How are local/global variables accessed?

Activation record (AR) — also called a stack frame — is a block of memory pushed onto the run-time stack for each call of a procedure/function. It holds everything needed to return from the call and to run the callee. When the procedure returns, its record is popped (unless it is kept for certain closures).

Typical layout (higher addresses → lower):

   [ actual parameters ]
   [ return value (if any) ]
   [ access link / control link (saved frame pointer) ]
   [ return address (saved PC) ]
   [ saved machine status ]
   [ local data (locals, temporaries) ]
   [ saved top-of-stack pointer ]

Accessing local variables:

• While a procedure is active, the runtime keeps a base pointer (frame pointer) that names the bottom of the current AR.
• Every local variable is stored at a fixed offset from the start of the AR, an offset chosen at compile time.
• So x is accessed as base + offset(x) — no runtime search: just load [base+off].

Accessing global (non-local) variables:

• Globals live in a global/static data area (not on the stack in most compilers). Each global has a fixed compile-time address/offset from a global base register/area, so access is again just an absolute/relative memory load.
• Some compilers (old Pascal-style) used an access link/display to reach enclosing non-locals: each frame holds a pointer to the frame of the statically enclosing procedure; accessing a nonlocal of depth $d$ follows $d$ links. (Dynamic scoping instead uses a dynamic link up the call chain.)

Example (C):

int g = 10;                 /* global */
int f(int p) { int l; l = g + p; return l; }

At run time while inside f:

• p and l are at FP + offset_p and FP + offset_l (local, in the AR).
• g is at its fixed global-area address (single load).

Conclusion

• Locals → offsets within the current activation record on the run-time stack (FP + offset).
• Globals → fixed addresses in a global data region, known at compile time.

Annotated parse tree for $(3+4)\times(5+6)$

Syntax-directed definition (synthesized val):

• $L \to E$, $\ L.val = E.val$
• $E \to T$, $E.val = T.val$
• $E \to E_1+T$, $E.val = E_1.val + T.val$
• $T \to F$, $T.val = F.val$
• $T \to T_1*F$, $T.val = T_1.val \times F.val$
• $F \to (E)$, $F.val = E.val$
• $F \to \text{digit}$, $F.val = \text{digit.lexval}$

Parse tree with every node's val annotated (evaluated bottom-up):

              L ─ E.val = 77                    (L → E, L.val = E.val)
                  |
                  E.val = 77                    (E → T,   E.val = T.val)
                  |
                  T.val = 77                    (T → T1 * F,  T.val = 7 * 11)
                 /         \
        T1.val = 7          F.val = 11
             |                    |
             F.val = 7           F → ( E )  .val = 11
             F → ( E ) .val=7         |
                |                    E → E1 + T  .val = 5 + 6 = 11
                E.val = 7            /        \
              E1.val = 3          T.val = 3   ?  ... (details below)

To avoid a confusing drawing, here is the node-by-node annotated tree (the expected exam answer):

L → E            : val = 77
E → T            : val = 77
T → T1 * F       : val = T1.val * F.val = 7 * 11 = 77

Left subtree  (3+4):
  T1 → F                          : val = 7
  F → (E)                         : val = 7      [parenthesized]
     E → E1 + T
        E1 → T → F → digit(3)     : val = 3
        T  → F → digit(4)         : val = 4
        E.val = 3 + 4 = 7
  ⇒ T1 (left factor) val = 7

Right subtree  (5+6):
  F → ( E )                       : val = 11     [parenthesized]
     E → E1 + T
        E1 → T → F → digit(5)     : val = 5
        T → F → digit(6)          : val = 6
        E.val = 5 + 6 = 11
  ⇒ F (right factor) val = 11

Root:
  T.val = 7 * 11 = 77,  E.val = 77,  L.val = 77

Each digit is a leaf via $F\to\text{digit}$, with $F.val = \text{digit.lexval}$ (3, 4, 5, 6).

$$\boxed{E.val = 7 \times 11 = 77}$$

Type checking, error reporting, and the syntax tree / DAG for
$$a = (a*b + c) \uparrow (b+c)*b + c$$

Part 1 — Type checking

• Type checking verifies each operator's operands have the expected type and computes/infers the result type while traversing the syntax tree.
• It is typically performed in the semantic-analysis phase using a syntax-directed definition where each expression node carries a synthesized type attribute, e.g. $T_E = f(T_{E_1}, T_T)$ for $E \to E_1+T$.
• Type synthesis: int + int → int, float op … → float; conversions (e.g. int → float) may be inserted automatically as a unary node inttofloat (type coercion).
• Checking can be static (compile time) or dynamic (run time).

Part 2 — Error reporting

• Each phase reports its errors to a central error handler: lexical (illegal token), syntactic (parse errors, e.g. mismatched brackets), semantic (type mismatch, undeclared/unused variable).
• The parser uses error-recovery strategies (panic mode, error productions, phrase-level recovery) so it can report more than one syntax error in a single run.
• Semantic errors are reported with line number, offending token, and message; code generation is attempted only when there are no fatal errors.

Part 3 — Syntax tree for the statement

a = (a*b + c) ↑ (b + c)*b + c

Precedence order: ↑ > * > +. So the RHS reads as:

$$(a*b + c)\ \uparrow\ ((b+c)*b)\ +\ c$$

Syntax tree (AST):

                  =
                 / \
                a   +
                   / \
                ↑     c
               / \
        (a*b + c)  ( (b+c) * b )
          /   \         /  \
      (a*b)  + c     (b+c)  b
      / \           /  \
     a   b         b    c

 Equivalently, using operator-labelled nodes:

                  =
                 / \
                a   +
                   / \
             (↑)      c
             /   \
          (a*b+c)   * (mul)
             |        / \
          (a*b)+c    (b+c)  b
          /  \      / \
        (a*b) c   b   c
        /   \
       a     b

DAG (Directed Acyclic Graph)

In the DAG, each unique subexpression appears exactly once; repeated uses share the same node.

The statement contains these distinct nodes (reading bottom-up):

1. a*b — node * with leaves (a, b)
2. (a*b)+c — node + over (1) and leaf c
3. b+c — node + with leaves (b, c)
4. (b+c)*b — node * over (3) and leaf b
5. ↑ — node ↑ over (2) and (4)
6. RHS + c — node + over (5) and leaf c
7. a = RHS — node = with leaves (a, 6)

                =
               / \
              a   +                     ← (6)
                 / \
              ↑     c
             / \
        (a*b)+c   (b+c)*b               ← nodes (2), (4)
          / \         / \
       (a*b) c     (b+c) b              ← nodes (1), (3)
        / \          / \
       a   b        b   c

Note the leaf b and c are each single nodes shared by all their uses (this is what makes it a DAG rather than a tree).

S-attribute SDT vs L-attribute SDT

S-Attribute (Synthesized) SDTs

• An SDT is S-attributed ("synthesized") if every attribute is a synthesized attribute — computed from the children of a nonterminal.
• All the evaluation is bottom-up.
• An S-attributed SDT can be evaluated during a bottom-up parse — the semantic action is placed at the right end of the production: A → α { do action }.
• Supported: only bottom-up based LL/LR? Precisely: LR parser can implement any S-attributed SDD without changing the parsing stack (just attach the attributes value with each stack symbol).

L-Attributed SDTs

• An SDT is L-attributed when:
  1. each attribute is either synthesized, or inherited, and
  2. inherited attributes depend only on: attributes of the left siblings, the parent, and attributes of the symbols themselves (i.e. dependencies can flow from left to right, and from parent → children).
• Condition: In the production $A \to X_1 X_2 \dots X_n$, an inherited attribute of $X_i$ can only depend on:
  • attributes of $X_1,X_2,\dots, X_{i-1}$ (the symbols to its left), and
  • inherited attributes of $A$ (the parent).
• Evaluation is basically top-down / left-to-right — works with LL / predictive parsers too, and can be implemented in a top-down or LR parser with suitable actions.

Key differences:

Point	S-attributed	L-attributed
Attributes	All synthesized	synthesized + inherited (with L- constraint)
Evaluation pass	bottom–up	depth-first left-to-right following structure
Parser suitable	any LR / bottom-up	LL / top-down (recursive-descent; LR also if aug.)
Action placement	can move to the end of RHS	must keep in position (actions constrained)
Which is larger	—	L is a superset of S

Every S-attributed definition is also L-attributed, but not vice versa.

Example

S-attribute example: grammar with val
$$E \to E_1+T \quad E.val=E_1.val+T.val$$
All attributes synthesized ⇒ S-attributed (also L).

L-attribute (non-S) example: an inherited attribute such as in a C float conversion
$$Y \to X_1 X_2 \quad Y.inh=...\,;\ X_1.inh=..., X_2.inh=f(Y.inh, X_1.att)$$
For instance, declaring arrays:
D → T L, L → id , L_1; L.inh = T.type; L1.inh = L.inh. The inherited attribute inh must always be computed before the symbol is parsed — that's the left-to-right constraint.

Summary: an S-SDT = simply synthesized attributes; evaluate bottom-up. L-SDT = a wider class, allows inherited attributes under the restriction that they use only attributes from the left (or inherited from context above) — evaluated in a depth-first left-first traversal. Since L is a superset of S, any S-scheme is a special case of L.