Semantic Analysis

after passing the lexical and syntax analysis, there are still errors. so correcting usage of variables, objects and function... are needed.

Semantic Analysis ensures the program satisfies a set of rules regarding the usage of programming constructs:

identifiers declared before used
types
inheritance relationships
single definition

There are two main categories of semantic analysis:

Scopes
Types

Scope

Lexical Scope: textual region in the program

Symbol Tables

Symantic checks refer to properties of identifier in the program; it need an environment to store identifier info: symbol table.

name	kind	type
foo	func	`int -> int`
m	arg	`int`
n	arg	`int`
tmp	var	char

Each scope has symbol tables. And program has hierachy of symbol tables(scope).

if the identifier is used traverse the hierachy of symbol tables upward until finding the identifier with the same name to determine the declaration from the current scope.

Build a Symbol Table

there are five operations:

insert scope
exit scope
find symbol(x)
add symbol(x)
check scope(x)

Type

Type checking
Type inferencing

Three Language Types:

Statically typed
Dynamically typed
Untyped(machine code)

Static Type Checking Does not require additional type checking instructions at runtime. and guarantees that the executions are safe at compile time. modern languages require both static and dynamic type checking(union, void ptr)

So what is types?

A type indicates a description of a set of values and a set of allowed operations on those values.

Type Expressions: Describe the possible typse in the program, e.g., int, char*, array[], object.
Type System: Defines types for language constructs (think about nodes in AST)

Type Comparision Implementation

Implement a method Equals(T1, T2)
- must compare type trees of T1 and T2
Use unique objects for each distinct type
- each type expression resolved to same type object everywhere
- faster type comparision(use ==)
- object-oriendted: check subtyping of type objects

for option 1

Type Checking Methodology

Inferecnce Rules

Soundness

\frac{i\text{ is an integer literal}}{\vdash i: \texttt{int}}[\texttt{int}]

Some rules are sound but not necessary for a language: (not giving meanings)

\frac{i\text{ is an integer literal}}{\vdash i \text{ is object} } \frac{e_1: \texttt{bool} \quad e_2: T}{\vdash \texttt{while} (e_1) \{ e_2 \} : \texttt{void}}[\texttt{while}]

2.6 KiB Raw Permalink Blame History