Blog

Syntax Directed Definition

With every symbol present in grammar Syntax Directed Definition (SDD) associates a set of attributes and with each production, a set of semantic rules for computing values of the attributes associated with the symbols appearing in that production. The grammar and the set of semantic rules make SDD.

Syntax Directed Definition (SDD) is a kind of abstract specification. It is generalization of context free grammar in which each grammar production X –> a is associated with it a set of production rules of the form s = f(b1, b2, ……bk) where s is the attribute obtained from function f. The attribute can be a string, number, type or a memory location. Semantic rules are fragments of code which are embedded usually at the end of production and enclosed in curly braces ({ }).

For a given grammar: X –> YZ, Y–>id, Z–>id. The parse tree is as follows.

X.a denotes that node X has an attributes “a”. Value of X.a is found using semantic rule for the X production used at this node.

Annotated Parse Tree: A parse tree with attribute values at each node, is Annotated Parse Tree. Annotated Parse Tree have high level specification, hides implementation details and in this tree explicit order of evaluation is not defined.

Synthesized Attributes: An attribute is said to be a synthesized attribute if its value at a Parse Tree node is determined from the attribute values of the children of the node.

Here, a is the attribute of X, b is the attribute of Y and c is the attribute of Z. Suppose that id1 is assigned to 8 and id2 is assigned to 5. Also let us suppose that attribute b of Y is directly assigned with the value of id1 i.e. 8 and attribute c of Z is directly assigned with the value of id2 i.e. 5. And the value of attribute a of X is assigned with the value which we get by concatenating the values of attributes b and c. Then in a we have 85.

Advantage of Synthesized Attributes is that Synthesized Attributes can be evaluated during a single Bottom-Up Traversal of the Parse Tree.

Example of SDD
  • Symbols E, T and F are associated with an attribute val.
  • The token digit has an attribute lexval (it is assumed that it is evaluated by the lexical analyzer.
  • The program Fragment above represents the implementation of the semantic rule for a bottom-up parser.
  • At each shift of digit, we also push digit.lexval into val.stack.
  • At all other shifts, we do not put anything into val-stack because other terminals do not have attributes (but we increment the stack pointer for val-stack)

Example: Let us assume an input string 4 * 5 + 6 for computing synthesized attributes. The annotated parse tree for the input string is:

Lightbox

For computation of attributes we start from leftmost bottom node. The rule F –> digit is used to reduce digit to F and the value of digit is obtained from lexical analyzer which becomes value of F i.e. from semantic action F.val = digit.lexval. Hence, F.val = 4 and since T is parent node of F so, we get T.val = 4 from semantic action T.val = F.val. Then, for T –> T1 * F production, the corresponding semantic action is T.val = T1.val * F.val . Hence, T.val = 4 * 5 = 20. Similarly, combination of E1.val + T.val becomes E.val i.e. E.val = E1.val + T.val = 26. Then, the production S –> E is applied to reduce E.val = 26 and semantic action associated with it prints the result E.val . Hence, the output will be 26.

Inherited Attributes: These are the attributes which derive their values from their parent or sibling nodes i.e. value of inherited attributes are computed by value of parent or sibling nodes.

Computation of Inherited Attributes: First construct the SDD using semantic rules. Then the annotated parse tree is generated and attribute values are computed in top down manner.

The SDD for the above grammar can be written as follows:

ProductionSemantic Rules
S–>TLL.in = T.type
T–>intT.type = int
T–>floatT.type = float
T–>doubleT.type = double
L–>L1, idL1.in = L.in
Entry_type(id.entry, L.in)
L–>idEntry_type(id.entry, L.in)

Let us assume an input string int a, c for computing inherited attributes. The annotated parse tree for the input string is:

Lightbox

The value of L nodes is obtained from T.type (sibling) which is basically lexical value obtained as int, float or double. Then L node gives type of identifiers a and c. The computation of type is done in top down manner or preorder traversal. Using function Enter_type the type of identifiers a and c is inserted in symbol table at corresponding id.entry.

DEPENDENCY GRAPHS

The parse tree can be annotated with synthesized or inherited attributes. The parse tree can also be indicated with an arrow mark to indicate the manner in which the value gets propagated between the nodes of the parse tree. This graph is called as dependency graph as it indicates the dependency between nodes for deriving the values. This graph is an acyclic graph which doesn’t have a cycle. The presence of a cycle indicates that the graph is incorrect as the dependence of nodes for deriving values cannot be predicted. Edges in the dependence graph show the evaluation order for attribute values and thus the graph is a directed one.

It depicts the path of flow of information. Dependency Graphs are useful for determining evaluation order for attributes in a parse tree. While an annotated parse tree shows the values of attributes, a dependency graph determines how those values can be computed.

For each node in the Parse Tree the Dependency graph has a node for each attribute in the node. For each production of the form X.a=f(Y.a,Z.b,….) create an edge from Y.a node to X.a node, Z.b to X.a and so on. This means Y.a and Z.b are to be evaluated before evaluating X.a.

S & L Attributed Definitions

  • We will look at two sub-classes of the syntax-directed definitions:
    • S-Attributed Definitions : Only synthesized attributes are used in the syntax-directed definitions.
    • L-Attributed Definitions : Both synthesized and inherited attributes are used in a restricted fashion.

Leave a Reply

Your email address will not be published. Required fields are marked *