20 Semantic Phase, Dependency Graph, Topological sorting

Rajeswari Sridhar

In this module we discuss the semantic phase of the compiler and understand the changes that happen in the semantic phase of the compiler.

20.1 Functions of the semantic phase of the compiler

The syntax phase of the compiler converted the input into a derivation tree and validated whether the input belongs to the grammar or not. Thus the output of the parser will be a derivation tree. This derivation tree needs to have information to generate code. The information is derived from the grammar of the programming language. The necessary information needs to be added to the derivation tree and this derivation tree is converted to a representation which is easier to generate assembly language code. Syntax Directed Definition (SDD) and Syntax Directed Translation (SDT) helps in converting the parse tree to an annotated parse tree which has information to generate code as well as the order of evaluating the derivation tree.

Thus SDD and SDT are the primary goals of the semantic phase of the compiler. After converting the derivation tree to a parse tree, the semantic phase of the compiler helps in writing semantic rules to verify the semantic correctness of all the statements. Type checking, flow checking are some of the semantic correctness verifying information. Figure 20.1 shows the integration of the lexical and syntactic phase of the compiler with the semantic phase

As can be seen from figure 20.1, the YACC specification file could incorporate the semantic rules associated to perform SDD and SDT. Let us discuss the features of SDD and SDT in detail in this module.

20.2 Syntax Directed Definition

A syntax-directed definition adds set of semantic rules to productions. Terminals and non-terminals have attributes. A depth-first traversal algorithm is used to compute the values of the attributes in the parse tree using the semantic rules. After the traversal is completed, the attributes contain the translated form of the input.  For each production semantic rules are formulated to convert the derivation tree to another representation. The semantic rules for the expression grammar is given in Table 20.1 As an expression evaluates to a value, every grammar symbol is associated with the value and this is described in the semantic rule of the expression grammar