Semantic analysis

The semantic analyzer looks for errors in the source file, that are not described by the context-free grammar of the source language.

Errors

1. Static typing
2. Use of undeclared identifiers
3. Dead code detection (statements after return)
4. Array bounds check
5. Double declaration of variables and record fields

Warnings

1. Us of uninitialized variables.

Implementation

The analyzer is given the abstract source tree, which is then traversed depth-first left-to-right. For each node a specific handler is executed which adds annotation and performs checks. This concept is also called syntax-directed translation (SDD)

Checks

Static typing

• All operators define allowed types.
• For assignments, the type of the lvalue must be an upper bound of the type of the rvalue. The type of the rvalue is recursively defined.

Use of undeclared identifiers

• If an identifier node is visited, its literal representation must be contained in the current symbol-table chain.

Dead code detection

1. If a return node is visited, the containing block is marked as dead. All statements after the return in that blocked are marked as dead too.
2. The dead-status is handed upwards, if it reaches to conditional statements, it is ignored if not all branches are also marked as dead.

Array bounds check

• If the index of an array access is a numeric constant or a static expression, the index is checked to be in the bounds of that array.

Us of uninitialized variables.

• The identifier is set to be initialized, if it appears as the lvalue of an assignment.
• If an identifier is visited, and the parent is not an assignment (lvalue), the initialization status is checked.

Details:

• If the assignment was in a while-loop or if, the initialization is ignored outside of the body.
• If the assignment was in a if/else, is has to be in booth branches. If not, it is ignored outside of the branches.