Compiler Tutorial

Compiler Introduction Phase of Compiler Symbol Table Lexical Analyser Evoluation of Programming Language Regular Expression Finite Automata Syntax Analysis Derivation and Parse Tree Bottom – Up Parsing LR parser YACC in Compiler Design LALR 1 Parsing | Compiler Design

Misc

Parsing in Compiler Design Shift Reduce Parsing in Compiler Design Refractive Index and Its types 6 Phases of Compiler Compiler Construction Tools in Compiler Design

S-attributed and L-attributed SDTs
2021-01-12 03:20:16

S-attributed and L-attributed SDTs

S-attributed and L-attributed SDTs

STD stands for Syntax Directed Translation. When we associate some informal notations called semantic rules and the grammar, they are known as STD. So we can say that:

Grammar + Semantic Rule = SDT

In compiler design, we have mainly two attributes: Synthesized or Inherited. Now, we will discuss s-attributed SDT and l-attributed SDT.

1) S-attributed SDT:

  • If every attribute is synthesized, then an SDT is called S-attributed SDT.
  • If the value of parent nodes depends upon the value of the child nodes, then S-attributed SDT is evaluated in bottom-up parsing.
  • The right-most place of RHS holds the semantic action.

Example 1

PRODUCTION SEMANTIC RULES
L => E n E => E1 + T E => T  T => T1 * F T => F F => ( E ) F => digitL.val = E.val E.val = E1.val + T.val E: val = T: val T: val = T 1 : val # F: val T: val = F: val F.val =  E.val F.val = digit.lexval

The SDD of the above example is an S-attributed SDT because each attribute, L.val, E.val, T.val, and F.val, is synthesized.

2) L-attributed SDT:

  • If an attribute of an SDT is synthesized or inherited with some restriction on inherited attributes, it can inherit values from left siblings only. It is known as L-attributed SDT.
  • Attributes of this SDT are evaluated by depth-first and left-to-right parsing methods.
  • Semantic actions are placed anywhere in RHS.

Example:

X => ABC {B.P = X.P, B.P = A.P, B.P = C.P}

This is not an L-attributed SDT because B.P = X.P and B.P = A.P are allowed, but B.P = C.P doesn't follow the rule of L-attributed SDT definition.