Unit 3 | unit 3 semantic analysis

Compiler Design

Unit - 3

Semantic Analysis

Q1) What do you mean by attribute grammar ?

A1) Attribute Grammar

Attribute grammar is a special type of context-free grammar where certain additional information (attributes) are appended to one or more of its non-terminals in order to provide context-sensitive information. Each attribute has a well-defined domain of values, such as integer, float, character, string, and expressions.

Attribute grammar is a tool to provide semantics to the context-free grammar and it can help define the syntax and semantics of a programming language. Attribute grammar (when viewed as a parse-tree) can transfer values or information among the nodes of a tree.

Example :

E → E + T { E.value = E.value + T.value }

The right section of the CFG contains the semantic rules that determine how the grammar should be read. Here, the values of non-terminals E and T are applied together and the output is copied to the non-terminal E.

Semantic attributes can be assigned to their values from their domain at the time of parsing and evaluated at the time of assignment or conditions. Based on the way the attributes get their values, they can be narrowly divided into two groups : synthesised attributes and inherited attributes.

Synthesized Attribute : These attributes get values from the attribute values of their child nodes. To demonstrate, assume the following production:

S → ABC

If S is taking values from its child nodes (A,B,C), then it is said to be a synthesised attribute, as the values of ABC are synthesised to S.

As in our previous example (E → E + T), the parent node E gets its value from its child node. Synthesized attributes never take values from their parent nodes or any sibling nodes.

2. Inherited Attributes : In comparison to synthesised attributes, inherited attributes may take values from parent and/or siblings. As in the following output,

S → ABC

A can get values from S, B and C. B will take values from S, A, and C. Likewise, C will take values from S, A, and B.

Q2) What is the syntax directed definition ?

A2) Syntax directed definition

A Syntax Driven Description (SSD) is a context-free grammar generalisation in which each grammar symbol has an associated collection of attributes, divided into two subsets of that grammar symbol's synthesised and inherited attributes.

An attribute may represent a string, a number, a type, a position in the memory, or something. A semantic rule associated with the output used on that node determines the value of an attribute at a parse-tree node.

Q3) What are the types of attributes ?

A3) Types of Attributes

Attributes are grouped into two kinds:

1. Synthesized Attributes : These are the attributes that derive their values from their child nodes, i.e. the synthesised attribute value at the node is determined from the attribute values at the child nodes in the parse tree.

Example

E --> E1 + T { E.val = E1.val + T.val}

● Write the SDD using applicable semantic rules in the specified grammar for each production.

● The annotated parse tree is created and bottom-up attribute values are computed.

● The final output will be the value obtained at the root node.

Considering the above example:

S --> E

E --> E1 + T

E --> T

T --> T1 * F

T --> F

F --> digit

You can write the SDD for the above grammar as follows:

Production	Semantic Action
S --> E	Print (E.val)
E --> E1 + T	E.val = E1.val + T.val
E --> T	E.val = T. Val
T --> T1 * F	T. Val = T1.val * F. Val
T --> F	T. Val = F. Val
F --> digit	F. Val = digit.lexval

For arithmetic expressions, let us consider the grammar. The Syntax Directed Description associates a synthesised attribute, called val, to each non-terminal. The semantic rule measures the value of the non-terminal attribute val on the left side of the non-terminal value on the right side of the attribute val.

2. Inherited Attributes : These are the attributes derived from their parent or sibling nodes by their values, i.e. the value of the inherited attributes is determined by the parent or sibling node value.

Example

A --> BCD { C.in = A.in, C.type = B.type }

● Using semantic behaviour, create the SDD.

● The annotated parse tree is created and the values of attributes are computed top-down.

Consider the grammar below

S --> T L

T --> int

T --> float

T --> double

L --> L1, id

L --> id

You can write the SDD for the above grammar as follows:

Production	Semantic Action
S --> T L	L.in = T.type
T --> int	T.type = int
T --> float	T.type = float
T --> double	T.type = double
L --> L1, id	L1.in = L.in Enter_type(id.entry, L.in)
L --> id	Entry _type(id.entry, L.in)

Q4) Write about syntax tree ?

A4) Syntax tree

The abstract syntactic structure of source code written in a programming language is represented by a syntax tree. Rather than elements such as braces, semicolons that end sentences in some languages, it focuses on the laws.

It is also a hierarchy divided into many parts with the elements of programming statements. The tree nodes denote a construct that exists in the source code.

A form id + id * id will have the following tree of syntax: