semantic-analysis.tex

\section{Semantic Analysis}

\subsection{Overview}

\begin{figure}[H]
    \centering
    \fbox{
    \begin{tikzpicture}
        \node [phantomblock]                            (start)     { \phantom{} };
        \node [block, below=1em of start]               (lexer)     {Lexical Analysis};
        \node [phantomblock, right=0.5em of lexer]                  {Regular Language};
        \node [block, below=1em of lexer]               (parser)    {Syntax Analysis};
        \node [phantomblock, right=0.5em of parser]                 {Context-Free Language};
        \node [block, below=1em of parser]              (semantic)  {Semantic Analysis};
        \node [phantomblock, right=0.5em of semantic]               {Contextual Language};
        \node [phantomblock, below=1em of semantic]     (end)       {};
        \draw [->] (start)      -- (lexer);
        \draw [->] (lexer)      -- (parser);
        \draw [->] (parser)     -- (semantic);
        \draw [->] (semantic)   -- (end);
    \end{tikzpicture}
    }
    \caption{Languages used for different phases}
    \label{fig:language-in-different-phases}
\end{figure}

\begin{remark}
    Up to this point, recall that
    \begin{itemize}
        \item \textit{Lexers} accept \textit{regular} grammar (\textit{Regex}).
        \item \textit{Parsers} accept \textit{context-free} grammar (\textit{CFG}).
        \item But programs are \textit{not context-free}.
    \end{itemize}
    
    That is,
    \begin{itemize}
        \item Programs which are \textit{syntactically correct} are indeed \textit{context-free}.
        \item But being \textit{syntactically correct} does not guarantee that a program can correctly compile -- the program must also be \textit{semantically correct}.
    \end{itemize}
    
    Hence, there exists an important distinction between \textit{Context-Free Grammars} (CFG) and \textit{Context-Sensitive Grammar} (CSG):
    
    \begin{itemize}
        \item The \textit{context} is \textit{not} retained in \textit{Context-Free Grammar}, allowing programs that are \textit{syntactically correct} but make no \textit{semantic} sense. Additionally, the \textit{scope} of variables are not checked.
    \end{itemize}
\end{remark}

\begin{example}
    For example, given the short method
    \begin{figure}[H]
        \centering
        \begin{minted}{java}
public void methodOne()
{
    int x = 2;
    System.out.println(x.getDate());
    y++;
    int y;
    return x;
}
        \end{minted}
        \caption{A program that is synatically correct but semantically wrong}
        \label{prog:syntactically-correct-semantically-wrong}
    \end{figure}
    
    The program is syntactically valid. However, there are multiple semantic errors:
    \begin{itemize}
        \item \texttt{x} is an integer, but an attempt was made to call \texttt{getDate()} on \texttt{x}.
        \item \texttt{y} is used before being declared.
        \item \texttt{methodOne} is declared to have no return value. However, \texttt{x} is returned in the last statement.
    \end{itemize}
\end{example}

\subsection{Context-Sensitive Grammar}

\begin{definition}[Context-Sensitive Grammar (CSG)]
    The \textit{Context-Sensitive Grammar} $G$ can be described by the 4-tuple
    \begin{equation}
        G = \langle
            \mathcal{N},
            \mathcal{T},
            \mathcal{R},
            S
        \rangle
    \end{equation}
    
    Where
    \begin{enumerate}
        \item \textbf{Non-terminals}: $\mathcal{N}$.
        \item \textbf{Terminals}: $\mathcal{T}$.
        \item \textbf{Production Rules}: $\mathcal{R}$.
        \item \textbf{Start Symbol}: $S$.
    \end{enumerate}
    
    The \textit{context-sensitive} property requires that
    \begin{equation}
        \Forall r \in \mathcal{R} \colon r = \alpha A \beta \to \alpha \gamma \beta
    \end{equation}
    
    That each production rule are of such form, where
    \begin{itemize}
        \item $A \in \mathcal{N}$ is a \textit{non-terminal}.
        \item $\alpha, \beta \in (\mathcal{N} \cup \mathcal{T})^\ast$ are strings of \textit{non-terminals} and \textit{terminals}.
        \item $\gamma \in (\mathcal{N} \cup \mathcal{T})^+$ is a \textit{non-empty} string of \textit{non-terminals} and \textit{terminals}.
        \begin{equation}
            \gamma \ne \varnothing
        \end{equation}
    \end{itemize}
\end{definition}

\subsection{Semantic Analysis}

Check outside the grammar for contextual correctness instead of trying to implement constraints within the language, for aspects such as
\begin{itemize}
    \item Undefined variables.
    \item Type errors.
    \item Scope errors.
    \item Duplicate definitions.
    \item Inheritance relationships.
\end{itemize}

\subsubsection{Contextual Constraints}

Important \textit{contextual constraints} include
\begin{enumerate}[itemsep=4pt, parsep=4pt, topsep=8pt, partopsep=4pt]
    \item \textbf{Scoping} rules:
        Checking area of effect of declarations.
    \item \textbf{Typing} rules: 
        Checking expressions have valid types.
\end{enumerate}

\subsubsection{Semantic Analysis Sub-phases}

Note that this list is \textit{non-exhaustive}.

\begin{itemize}[itemsep=4pt, parsep=4pt, topsep=8pt, partopsep=4pt]
    \item \textbf{Name Resolution}:
        Apply scoping rules to correspond identifier to declaration.
    \item \textbf{Type Checking}:
        Apply typing rules to infer type of expressions, and verify that the inferred type is compatible with the expected type.
\end{itemize}

\subsection{Scoping Rules}

\begin{definition}[Declaration]
    A \textit{declaration} associates information with an \textit{identifier}.
    
    There are two types of declarations:
    \begin{itemize}[itemsep=4pt, parsep=4pt, topsep=8pt, partopsep=4pt]
        \item \textbf{Explicit Declaration}. (In Java) 
            \begin{minted}{java}
int i;
            \end{minted}
        \item \textbf{Implicit Declaration}. (In Fortran)
            \begin{minted}{fortran}
i;
            \end{minted}
            In Fortran, some identifiers \texttt{i}, \texttt{j}, ..., \texttt{n} are implicitly assumed to be integers, unless this feature is turned off.
    \end{itemize}
    
    It is possible for the same identifier to have independent declarations in different parts of a program, differentiating via \textit{scoping rules}.
\end{definition}

\begin{definition}[Scoping Rules]
    \textit{Scoping rules} define which declaration an identifier resolves to in each part of the program.
\end{definition}

\begin{definition}[Scope]
    The \textit{scope} of a declaration is the part of the program for which the declaration applies to.
\end{definition}

\subsubsection{Binding}

\begin{definition}[Binding]
    A \textit{binding} is the association between an identifier and the thing it represents.
\end{definition}

\begin{example}
    Given the Java method
    \begin{figure}[H]
        \centering
        \begin{minted}{java}
public boolean foo(int n, int m) {
    boolean tmp;
    if (n<m) tmp = true;
    else tmp = false;
    return tmp;
}
        \end{minted}
        \caption{A Java method}
        \label{prog:example-java-binding}
    \end{figure}
    
    Then its binding $\sigma_{\texttt{foo}}$ is
    \begin{equation}
        \sigma_{\texttt{foo}} = \left\lbrace
            \texttt{foo} \mapsto \texttt{int} \times \texttt{int} \to \texttt{boolean},
            \texttt{n} \mapsto \texttt{int},
            \texttt{m} \mapsto \texttt{int},
            \texttt{tmp} \mapsto \texttt{bool}
        \right\rbrace
    \end{equation}
\end{example}

\subsubsection{Static Scope}

\begin{definition}[Static Scope (Lexical Scope)]
    \textit{Static scope} is when scoping information is available at \textit{compile time} -- the scoping information is available within the source code.
    
    Usually, the \textit{most recent encounter} binds.
\end{definition}

\begin{definition}[Static Scope Design]
    Two \textit{static scope} designs exist:
    \begin{enumerate}
        \item Global.
        \item Local to function.
    \end{enumerate}
    
    Allowing nested functions introduce further complications as each nested function can begin a new scope.
\end{definition}

\begin{definition}[Closest Nested Scope Rule]
    The \textit{Closest Nested Scope} rule is defined as follows
    \begin{itemize}
        \item An identifier introduced in a declaration is known
        \begin{itemize}
            \item in the scope where the identifier is declared in, or
            \item in each internal scope that is nested after the declaration,
            \item \textit{unless} it is hidden by another declaration of the same identifier in one or more of the nested scope (known as \enquote{\textit{name shadowing}}).
        \end{itemize}
    \end{itemize}
\end{definition}

\begin{example}
    In the code fragment
    \begin{figure}[H]
        \centering
        \begin{minted}{javascript}
let x = 4;                  // Outermost scope L1
if (x > 0)
{                           // Inner scope L2
    let x = 3;              // L2's x shadows / 
                            //     hides x from L1
    if (x > 1)
    {                       // Innermost scope L3
        x = x + 1;          // L3's x modifies x from L2
        print(x)            // => 4
    }
    
    print(x);               // => 4 because L2's
                            //     x modified in L3
}       
print(x);                   // => 4 L1's x
        \end{minted}
        \caption{Closest nested scope in effect}
        \label{prog:closest-nested-scope-rule}
    \end{figure}
\end{example}

\begin{definition}[Hole]
    A \textit{hole} in the scope of a binding occurs when the declaration of an identifier is \textit{hidden} or \textit{shadowed} by a nested declaration of the same identifier.
    
    In figure \ref{prog:closest-nested-scope-rule}, binding of \texttt{x} in $L_1$ is hidden by the declaration of the same name in the nested scope $L_2$.
\end{definition}

\begin{definition}[Qualifier]
    Some programming languages allow references to declarations in outer scopes that are shadowed by providing \textit{qualifiers} or \textit{scope resolution operators}.
\end{definition}

\begin{example}
    The \textit{scope resolution operator} $::$ is provided in C++
    \begin{figure}[H]
        \centering
        \begin{subfigure}{0.45\textwidth}
            \centering
            \begin{minted}{c++}
#include <iostream>
int main(void)
{
    int cout = 42;
    cout << cout;
}
            \end{minted}
        \end{subfigure}
        \begin{subfigure}{0.45\textwidth}
            \centering
            \begin{minted}{c++}
#include <iostream>
int main(void)
{
    int cout = 42;
    std::cout << cout;
}
            \end{minted}
        \end{subfigure}
        \caption{Scope resolution operator in C++}
        \label{fig:cpp-scope-resolution-operator}
    \end{figure}
\end{example}

\subsubsection{Dynamic Scope}

\begin{definition}[Dynamic Scope]
    \textit{Dynamic scope} refers to binding that is determined at run-time, depending on the flow of execution.
    \begin{itemize}
        \item Most recent declaration takes precedence.
        \item Binding expires when execution flow leaves lexical scope.
    \end{itemize}
    
    Generally execution flow cannot be predicted at compile time and so dynamic scope is usually implemented within \textit{interpreted} languages.
\end{definition}

\begin{remark}
    \textit{Static} scoping versus \textit{dynamic} scoping can be analogous to \textit{spatial} scoping versus \textit{temporal} scoping:
    \begin{itemize}
        \item \textit{Static} scoping looks for the lexically-closest declaration.
        \item \textit{Dynamic} scoping looks for the most recent declaration with regard to the run time flow of execution.
    \end{itemize}
\end{remark}

\subsection{Referencing Environment}

\begin{definition}[Referencing Environment]
    The sequence of scopes which needs to be examined in order for the current binding of a given identifier to be found is the \textit{referencing environment}.
\end{definition}

\begin{definition}[Shallow Binding (Late Binding, Dynamic Binding)]
    \textit{Shallow binding} refers to delaying the creation of the reference environment until a routine is called.
\end{definition}

\begin{definition}[Deep Binding (Static Binding, Early Binding)]
    \textit{Deep binding} refers to creating the reference environment upon making the first reference.
\end{definition}

\subsection{Symbol Table}

\begin{definition}[Symbol Table]
    A \textit{Symbol Table} stores binding information, helping to enforce scoping rules.
\end{definition}

\begin{example}
    Given the Java method
    \begin{figure}[H]
        \centering
        \begin{subfigure}{\textwidth}
            \centering
            \begin{minted}{java}
public boolean foo(int n, int m)
{
    boolean tmp;
    if (n < m) tmp = true;
    else tmp = false;
    return tmp;
}
            \end{minted}
            \caption{Java method}
        \end{subfigure}
        \begin{subfigure}{\textwidth}
            \centering
            \begin{tabular}{@{} c c c c @{}}
                \toprule
                Identifier & Kind & Type & Attributes \\
                \midrule
                \texttt{foo} & method & $\texttt{int} \times \texttt{int} \to \texttt{boolean}$ & $\dots$ \\
                \texttt{n} & parameter & $\texttt{int}$ & $\dots$ \\
                \texttt{m} & parameter & $\texttt{int}$ & $\dots$ \\
                \texttt{tmp} & local variable & $\texttt{boolean}$ & $\dots$ \\
                \bottomrule
            \end{tabular}
            \caption{Symbol table}
        \end{subfigure}
        \caption{Java code and its corresponding symbol table}
        \label{prog:symbol-table}
    \end{figure}
\end{example}

\subsubsection{Checking for Undefined Variables}

\begin{definition}[Abstract Syntax Tree and Symbol Table]
    Adding entries and querying entries between the Abtract Syntax Tree (AST) ad the Symbol Table involves two operations
    \begin{enumerate}
        \item \textbf{Insert}. A new binding is added to the currently active Symbol Table when a new identifier is declared.
        \item \textbf{Lookup}. Traverse AST hierarchy from the current scope upwards.
    \end{enumerate}
\end{definition}

\begin{remark}
    A single Symbol Table, however, is insufficient for
    \begin{itemize}
        \item Nested scoping, when inner bindings hide outer bindings.
        \item Forward references, when identifiers can be referenced before they are declared.
    \end{itemize}
\end{remark}

\begin{definition}[Symbol Table Hierarchy]
    A \textit{hierarchy} of \textit{Symbol Tables} can be used to implement nested scoping.
    
    \begin{enumerate}
        \item When entering a new nested scope, a new Symbol Table is created.
        \item When exiting a nested scope, the Symbol Table for the nested scope is destroyed.
    \end{enumerate}
\end{definition}

\begin{example}
    For the Java code
    \begin{figure}[H]
        \centering
        \begin{minted}{java}
public class Circle
{
    double PI = 3.141;
    
    public double circumference(double radius)
    {
        double diameter = 2 * radius;
        double circ = PI * diameter;
        return circ;
    }
    
    public double area(double radius)
    {
        double a = PI * radius * radius;
        return a;
    }
}
        \end{minted}
        \caption{Nested scoping and hierarchy of Symbol Tables}
        \label{prog:java-nested-scope}
    \end{figure}
    
    There are three Symbol Tables
    \begin{align*}
        \sigma_0 &= \set{
            \mathtt{PI} \mapsto \mathtt{double},
            \mathtt{circumference} \mapsto \mathtt{double} \to \mathtt{double},
            \mathtt{area} \mapsto \mathtt{double} \to \mathtt{double}
        } \\
        \sigma_1 &= \sigma_0 \cup \set{
            \mathtt{diameter} \mapsto \mathtt{double},
            \mathtt{circ} \mapsto \mathtt{double}
        } \\
        \sigma_2 &= \sigma_0 \cup \set{
            \mathtt{a} \mapsto \mathtt{double}
        }
    \end{align*}
    
    Note that
    \begin{figure}[H]
        \centering
        \begin{forest}
            [$\sigma_0$
                [$\sigma_1$]
                [$\sigma_2$]
            ]
        \end{forest}
        \caption{Hierarchical Symbol Table}
        \label{fig:hierarchical-symbol-table}
    \end{figure}
\end{example}

\subsubsection{Finding Active Declaration of Identifier in Symbol Table Hierarchy}

Finding the active declaration of identifier in Symbol Table involves
\begin{itemize}
    \item Being from current scope.
    \item Keep going up the hierarchy until the identifier is found.
    \item Never traverse downwards.
    \item If the identifier is not found even at the root of the hierarchy, the identifier is being used without being defined, which is an error.
\end{itemize}

\begin{remark}
    Hierarchical Symbol Tables also have the benefit of resolving name collisions -- the deepest nested scope with the identifier takes precedence.
\end{remark}

\subsubsection{Symbol Table Implementation}

A symbol table could be implemented via a \textit{Hash Table}, given that the \textit{hashing function} has good spread and minimal primary or secondary clustering.

To visit the hierarchical Abstract Syntax Tree, one may utilize the \textit{Visitor} design pattern, which decouples the tree's structural representation from any algorithms traversing it.

\subsection{Type Checking}

\begin{definition}[Type]
    A \textit{type} refers to a set of \textit{values} with some \textit{operations} defined on it.
\end{definition}

\begin{definition}[Type System]
    A \textit{type system} consists of \textit{type expressions} and corresponding \textit{type-checking rules}.
\end{definition}

\begin{definition}[Type Expression]
    A \textit{type expression} is one of the possible types in a program.
\end{definition}

\begin{example}
    For instance, a \textit{type expression} in Java could be
    \begin{itemize}
        \item \texttt{int},
        \item \texttt{boolean},
        \item or a user-defined type such as \texttt{Bag<Integer>}.
    \end{itemize}
\end{example}

\begin{definition}[Type Rules]
    \textit{Type rules} are semantic constraints for which program constructs must satisfy in order to successfully compile.
\end{definition}

\subsubsection{Type Expressions}

\textit{Type Expressions} consists of \textit{primitive types} and \textit{compound types}.
\begin{itemize}
    \item \textbf{Primitive Types}
    \begin{enumerate}
        \item \texttt{int}
        \item \texttt{double}
        \item \texttt{boolean}
        \item \texttt{long}
        \item \texttt{float}
        \item \texttt{double}
        \item \texttt{char}
        \item \texttt{short}
    \end{enumerate}
    \item \textbf{Compound Types} \\
        \textit{Compound types} are constructed from combining primitive types. For example,
        \begin{enumerate}
            \item Pointer types. \texttt{char *}
            \item Struct types. \texttt{struct point { int x; int y; };}
            \item Array types. \texttt{char[]}
            \item Generic types. \texttt{List<Integer>}
        \end{enumerate}
\end{itemize}

\subsubsection{Type Information in Symbol Table}

The Symbol Table usually also includes type information
\begin{itemize}
    \item Bindings between identifier and type.
    \item Bindings between formal parameter and type.
    \item Bindings between method name, parameters and return type.
    \item Bindings between class name, class variables and method declarations.
\end{itemize}

\subsubsection{Type-Checking Rules}

\begin{example}
A type-checking rule could require that \textit{the type of the left-hand side of an assignment must have the same type as the right-hand side of the assignment}.
    
For a very simple expression \texttt{int a = 2 * 2;}, it fulfills the type-checking rule because
\begin{figure}[H]
    \centering
    \begin{prooftree}
        \hypo{ \Gamma \vdash \mathtt{int\ a} }
        \infer1{ \Gamma \vdash \mathtt{a} \colon int }
        \hypo{ \Gamma \vdash \mathtt{2} \colon int }
        \infer1{ \Gamma \vdash \mathtt{2 * 2} \colon int }
        \infer2{ \Gamma \vdash \mathtt{int\ a = 2 * 2;} \colon int }
    \end{prooftree}
    \caption{Assignment type-checking rule}
    \label{fig:assignment-type-checking-rule}
\end{figure}
\end{example}

\subsubsection{Type-Checking Implementation}

There are two steps to \textit{type-checking}
\begin{enumerate}
    \item \textbf{Symbol Table Construction}.
    \begin{itemize}
        \item Visit AST.
        \item Store type information in Symbol Table(s).
    \end{itemize}
    \item \textbf{Scope and Type Checks}.
    \begin{itemize}
        \item Visit AST and access Symbol Table(s).
        \item Verify program conforms with scope and type rules.
    \end{itemize}
\end{enumerate}

\begin{definition}[Types and Symbol Table Construction]
    Each \textit{type expression} can be represented as a class, with the Symbol Table binding each identifier to a specific \textit{type object}. Semantic analysis can then convert \textit{type expressions} to corresponding \textit{type objects}.
    
    \begin{figure}[H]
        \centering
        \begin{forest}
            for tree={
                draw=black,
                edge={->},
                edge from parent/.style={draw=black}
            }
            [Type
                [PrimitiveType
                    [IntType
                        [CharType]
                        [BoolType]
                    ]
                    [FloatingPointType
                        [FloatType]
                        [DoubleType]
                    ]
                ]
                [ReferenceType]
            ]
        \end{forest}
        \caption{Type Objects}
        \label{fig:type-objects}
    \end{figure}
    
    Alternatively, each type can also be represented by a string with a predifined format.
    \begin{figure}[H]
        \centering
        \begin{align*}
            \mathtt{int} &\mapsto "\mathtt{I;}" \\
            \mathtt{int[\ ]} &\mapsto "\mathtt{[I;}" \\
        \end{align*}
        \caption{Type String}
        \label{fig:type-string}
    \end{figure}
\end{definition}

\begin{definition}[Type Comparison Implementation]
    With the two possible type implementations, \textit{type comparison} can also be implemented with
    \begin{itemize}
        \item Implement \texttt{T1.equals(T2)} object comparison method if types are implemented with objects.
        \item String comparison if types are implemented with strings.
    \end{itemize}
\end{definition}

\begin{definition}[Type Checking Implementation]
    \textit{Type Checking} can be implemented via a Visitor to the AST hierarchy; type rules are checked during the recursive traversal.
\end{definition}

\subsubsection{Type Error Reporting}

\begin{definition}[Type Error Handling]
    When a \textit{type-checking error} is discovered during analysis, the error should be reported and the semantic analysis should continue.
    
    Correct types may have to be inferred to avoid \textit{cascading failures}.
\end{definition}

\subsubsection{Simple Semantic Analyzer}

\begin{definition}[Simple Semantic Analyzer]
    A simple semantic analyzer can be implemented via two phases
    
    \begin{algorithm}[H]
        \begin{algorithmic}[1]
            \Procedure{DoSemanticAnalysis}{$Program$}
                \ForAll{$DeclarativeRegion \in Program$}
                    \State \Call{ProcessDeclarations}{$DeclarativeRegion$}
                    \State \Call{ProcessStatements}{$DeclarativeRegion$}
                \EndFor
                \ForAll{$DeclarativeRegion \in Program$}
                    \State \Call{InferTypes}{$DeclarativeRegion$}
                    \State \Call{FindTypeErrors}{$DeclarativeRegion$}
                \EndFor
            \EndProcedure
            \Procedure{ProcessDeclarations}{$DeclarativeRegion$}
                \ForAll{$Declaration \in DeclarativeRegion$}
                    \State \Call{SymbolTable.AddEntry}{$Declaration$}
                    \If{ \Call{IsDuplicateDeclaration}{$Declaration$} }
                        \State \Call{ReportTypeError}{$Declaration$}
                    \EndIf
                \EndFor
            \EndProcedure
            \Procedure{ProcessStatements}{$DeclarativeRegion$}
                \ForAll{$Statement \in DeclarativeRegion$}
                    \State \Call{FindUndeclaredVariables}{$Statement$}
                    \State \Call{UpdateAstIdNodes}{SymbolTable}
                \EndFor
            \EndProcedure
        \end{algorithmic}
        \caption{Simple Semantic Analyzer}
        \label{algo:simple-semantic-analyzer}
    \end{algorithm}
\end{definition}