Semantic

• Semantics of a language provide meaning to its constructs, like tokens and syntax structure. Semantics help interpret symbols, their types, and their relations with each other.

• Semantic analysis judges whether the syntax structure constructed in the source program derives any meaning or not.

  CFG + semantic rules = Syntax Directed Definitions

• For example:

  int a = “value”;

  Should not issue an error in lexical and syntax analysis phase, as it is lexically and structurally correct, but it should generate a semantic error as the type of the assignment differs.

• These rules are set by the grammar of the language and evaluated in semantic analysis.

• The following tasks should be performed in semantic analysis:

  • Scope resolution
  • Type checking
  • Array-bound checking

• There are two ways to represent the semantic rules associated with grammar symbols.

  • Syntax-Directed Definitions (SDD)
  • Syntax-Directed Translation Schemes (SDT)

Syntax-Directed Definitions

• A syntax-directed definition (SDD) is a context-free grammar together with attributes and rules. Attributes are associated with grammar symbols and rules are associated with productions.

Syntax-Directed Translation Schemes (SDT)

• SDT embeds program fragments called semantic actions within production bodies. The position of semantic action in a production body determines the order in which the action is executed.

Attribute Grammar

• Attribute grammar is a special form of context-free grammar where some additional information (attributes) are appended to one or more of its non-terminals in order to provide context-sensitive information.
• Each attribute has well-defined domain of values, such as integer, float, character, string, and expressions.
• Attribute grammar is a medium to provide semantics to the context-free grammar and it can help specify the syntax and semantics of a programming language.

• Attribute grammar (when viewed as a parse-tree) can pass values or information among the nodes of a tree.

  Example

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

• The right part of the CFG contains the semantic rules that specify how the grammar should be interpreted.

• Here, the values of non-terminals E and T are added together and the result is copied to the non-terminal E.
• Semantic attributes may 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 broadly divided into two categories

  1. Synthesized attributes
  2. Inherited attributes.

Synthesized Attributes

• These attributes get values from the attribute values of their child nodes. To illustrate, 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 synthesized attribute, as the values of ABC are synthesized 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.

Inherited Attributes

• In contrast to synthesized attributes, inherited attributes can take values from parent and/or siblings. As in the following production,

  S → ABC

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

  Expansion:

  When a non-terminal is expanded to terminals as per a grammatical rule

Reduction:

• When a terminal is reduced to its corresponding non-terminal according to grammar rules.
• Syntax trees are parsed top-down and left to right. Whenever reduction occurs, we apply its corresponding semantic rules (actions).
• Semantic analysis uses Syntax Directed Translations to perform the above tasks.
• Semantic analyzer receives AST (Abstract Syntax Tree) from its previous stage (syntax analysis).
• Semantic analyzer attaches attribute information with AST, which are called Attributed AST.

• Attributes are two tuple value, <attribute name,="" attribute="" value="">

• For example:

  int value = 5;

  $\text{\lttype, “integer”\gt}$

  $\text{\ltpresent value, “5”\gt}$

• For every production, we attach a semantic rule.

Example for Synthesized Attributes

Let us consider the Grammar for arithmetic expressions. The Syntax Directed Definition associates to each non terminal a synthesized attribute called Val.

Example for Inherited Attributes

Let us consider the syntax directed definition with both inherited and synthesized attributes for the grammar for “type declarations”:

• The non-terminal T has a synthesized attribute, type, determined by the keyword in the declaration.
• The production D → T L is associated with the semantic rule L. in := T .type which set the inherited attribute L.in.
• Note: The production L → L 1, id distinguishes the two occurrences of L.