|
|
|
|
|
|
Semantic Analysis
Semantic Analysis is the compiler's phases in which the valid (correct) syntax tree
(exhibiting the input structure) is traversed in order to validate the input compliance against
the language's semantic rules (declarations, scope, type, etc).
|
| Go up |
|
| Symbol Table
During semantic analysis (scope or type checking),
it is necessary to remember declarations (variables, types, functions, etc) so that we can detect inconsistencies
and misuses of the identifiers.
This identifiers memorization is the task of a symbol table.
Note that a symbol table is a compile-time data structure;
it's not used during run time.
Formally, a symbol table (also called identifiers table) maps names into
declarations (called attributes), such as mapping the variable name x to its type int.
More specifically, a symbol table stores:
- for each "type name", its type definition (eg. for the C type declaration
typedef int* mytype, it maps the name mytype to a data structure that
represents the type int*).
- for "each variable name", its type. If the variable is an array,
it also stores dimension information. It may also store storage class, offset in activation record etc.
- for each "constant name", its type and value.
- for each "function and procedure", its formal parameter list and its output type.
Each formal parameter must have name, type, type of passing (by-reference or by-value), etc.
Due to its very efficient search/retrieval algorithm,
one convenient data structure for symbol tables is a hash table,
that maps names (the hash table keys) to attributs.
|
| Go up |
|
|
Syntatic Analysis
Syntatic Analysis is the compiler's phases in which the sequence of tokens
(provided by the lexical analysis) is parsed, this is,
is compared against the grammar structured rules in order to find out the production used to derive
the input sentence.
The hierarchical set of productions, called the syntax tree,
gives the structure of the input.
|
| Go up |
|
|
Syntax Tree
A syntax tree is a compressed representation of the
parse tree in which the operators appears as the interior nodes, and the operands of an operator
are the children of the node for that operator.
The construction of a syntax tree for an expression is similar to the translation of the expression
into postfix form. We construct subtrees for the subexpressions by creating a node for each operator
and operand. The children of an operator node are the roots of the nodes representing the subexpressions
constituing the operands of that operator.
Each node in a syntax tree can be implemented as a record with several fields. In the node for
an operator, onde field identifies the operator and the remaining fields contain pointers to the nodes
for the operand. The operator is often called the label of the node. When used for translation,
the nodes in a syntax tree may have additional fields to hold the values (or pointers to values)
of attributes attached to the node.
in "Compilers: Principles, Techniques and Tools"
Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman
|
| Go up |
|
|
Synthesized Attributes
An attribute is said to be synthesized if its value at a parse
tree node is determined from attribute values at the children of the node. Synthesized attributes
have the desirable property that they can be evaluated during a single bottom-up traversal of
the parse tree.
in "Compilers: Principles, Techniques and Tools"
Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman
See also: Inherited attributes
|
| Go up |
|
|
Source Language
In a compiler, the source language is the language used to write the compiler's input, this is,
the program we want to check and translate into a target language.
|
| Go up |
|
|
|
| |
|
|
