Semantic Analysis

Instructor: Venkata Ramana Badarla

October 11, 2023

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 1 / 68

Introduction

• Semantic consistency that cannot be handled at the parsing stage is handled here
• Parsers cannot handle context-sensitive features of programming languages
• These are static semantics of programming languages and can be checked by the
semantic analyzer
• Variables are declared before use
• Types match on both sides of assignments
• Parameter types and number match in declaration and use
• Compilers can only generate code to check dynamic semantics of programming
languages at runtime
• whether an overflow will occur during an arithmetic operation
• whether array limits will be crossed during execution
• whether recursion will cross stack limits
• whether heap memory will be insufficient

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 2 / 68

Static Semantics

In main
• Types of p and return type of
dot prod match
int dot_prod (int x[], int y[]) • Number and type of the parameters of
{ dot prod are the same in both its
int d, i; declaration and use
d = 0;
for (i = 0; i < 10; i++) • p is declared before use, same for a
d += x[i] * y[i]; and b
return d; In dot_prod
}
• d and i are declared before use
main ()
{ • Type of d matches the return type of
int p; int a[10], b[10]; dot_prod
p = dot_prod (a, b);
• Type of d matches the result type of *
}
• Elements of arrays x and y are
compatible with *

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 3 / 68

Static Semantics: Error shown by gcc compiler

int dot_product (int a[], int b[]) { ...}

main () {
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int b[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
printf ("%d", dot_product (b));
printf ("%d", dot_product (a, b, a));
int p[10];
p = dotproduct (a, b);
printf ("%d", p);
}

In function ’main’
error in 3:too few arguments to fn ‘dot_product’
error in 4:too many arguments to fn ’dot_product’
error in 5:incompatible types in assignment
warning in 5:format ‘%d’ expects type ‘int’,
but argument 2 has type ‘int *’

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 4 / 68

Dynamic Semantics

int dot_prod (int x[], int y[]) {

int d, i;
d = 0;
for (i = 0; i < 10; i++)
d += x[i] * y[i];
return d;
}
main () {
int p; int a[10], b[10];
p = dot_prod (a, b);
}

Samples of dynamic semantic checks in dot_prod

• Value of i does not exceed the declared range of arrays x and y (both lower and
upper)
• There are no overflows during the operations of * and + in d += x[i]*y[i]

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 5 / 68

Syntax Directed Translation Schemes
• Offers the methods for the source language translation which are completely driven
by the parser (i.e., grammar).
• Actions (or code fragments) are attached to the grammar productions
• The fragments attached to the grammar symbols are executed during parsing
• The combined result of all these fragment executions, in the order induced by the
syntax analysis, produces the translation of the program
• Two types of schemes: SDD and SDT
• Syntax directed definition (SDD)
• Specifies production rules without explicitly specifying evaluation order
• Easy to specify
• Syntax directed translation (SDT)
• Specifies semantic actions or program fragments by explicitly specifying the
order of evaluation
• Easy to implement
• Applications: intermediate code generation, type checking and other kinds of
semantic analysis
Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 6 / 68
Syntax Tree and Parse Tree

• Syntax trees - interior nodes represent

language constructs instead of
grammar symbols in parse trees
• Used by many compilers for
intermediate representation of input
• Solid lines – edges of syntax tree.
Dotted lines – edges of parse tree.
• Abstract syntax tree or simply syntax
tree
• Concrete syntax tree or parse tree

Syntax tree: a - 4 + c

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 7 / 68

Attribute Grammar

• Links syntax with semantics

• Adds context sensitive capabilities to CFGs
• Let G = (N, T, P, S) be a CFG and let V = N U T
• Every symbol X of V has associated with it a set of attributes (denoted by
X.a, X.b, etc.)
• Two types of attributes: inherited i and synthesized s
• Each attribute takes values from a specified domain (finite or infinite), which is its
type
• Typical domains of attributes are, integers, reals, characters, strings,
booleans, structures, etc.
• The strings may even be long sequences of code, say code in the
intermediate language used by a compiler

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 8 / 68

Types of Attributes

• A synthesized attribute at a node N in parse tree is defined only in terms of

attribute values at the children of N and at N itself
• An inherited attribute at a node N in parse tree is defined only in terms of
attribute values at N’s parent, N itself, and N’s siblings
• An inherited attribute at node N can’t be defined in terms of attribute values at
the children of node N
• A synthesized attribute at node N can be defined in terms of inherited attribute
values at node N itself
• Terminals can have synthesized attributes, but not inherited attributes
• Attributes for terminals have lexical values that are supplied by the lexical analyzer
• There are no semantic rules in the SDD itself for computing the value of an
attribute for a terminal

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 9 / 68

Types of Attributed Grammars

• A grammar is an S-attributed grammar (SAG) if every attribute is synthesized.

• In L-Attributed grammar (LAG), each attribute must be either
• Synthesized, or
• Inherited, but suppose that there is a production A → X1 , X2 . . . Xn , and that
there is an inherited attribute Xi computed by a rule associated with this
production. Then the rule may use only:
• Inherited attributes associated with the head A
• Either inherited or synthesized attributes associated with the
occurrences of symbols X1 , X2 , . . . , Xi−1 located to the left of Xi
• Inherited or synthesized attributes associated with this occurrence of Xi
itself, but only in such a way that there are no cycles in a dependency
graph formed by the attributes of this Xi

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 10 / 68

Few Data Structures

• Annotated parse tree shows the values of attributes.

• Dependency graph shows an evaluation order for the attributes.

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 11 / 68

SAG/S-SDD for Expression Evaluation

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 12 / 68

LAG/L-SDD for Expression Evaluation

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 13 / 68

LAG/L-SDD for Type Declarations

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 14 / 68

SAG/S-SDD for Construction of a Syntax Tree

Syntax tree: a - 4 + c
Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 15 / 68
LAG/L-SDD for Construction of a Syntax Tree

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 16 / 68

LAG/L-SDD for Translation of Array Type

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 17 / 68

Exercise Problem 1

1 Given a CFG
S → ABC ,
A → aA | a,
B → bB | b,
C → cC | c
which generate L(G) = {am b n c p |m, n, p ≥ 1}. Define an AG (attribute grammar)
based on this CFG to generate L = {an b n c n |n ≥ 1}

Productions Semantic Rules

S → ABC
A → aA1
A→a
B → bB1
B→b
C → cC1
C →c

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 18 / 68

Exercise Problem 1 - Solution

Assume synthesized attributes status with NT S and count with the NTs
A, B, and C .

Productions Semantic Rules

S → ABC if (A.count == B.count && B.count == C .count)
s.status = true
else s.status = false
A → aA1 A.count = A1 .count + 1
A→a A.count = 1
B → bB1 B.count = B1 .count + 1
B→b B.count = 1
C → cC1 C .count = C1 .count + 1
C →c C .count = 1

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 19 / 68

Exercise Problem 2

1 This grammar generates binary numbers with a ”decimal” point:

S → L.L | L
L → LB | B
B→0|1
Design an L-attributed SDD to compute B.val, the decimal-number value of an
input string. For example, the translation of string 1 0 1 . 10 1 should be the
decimal number 5.625. Hint: use an inherited attribute L.side that tells which side
of the decimal point a bit is on.
2 Design an S-attributed SDD for the grammar and translation described in above
problem.

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 20 / 68

SDT

• SDT is a complementary notation to SDD and all of the applications of SDDs can
be implemented using SDTs.
• Unlike in SDDs, the program fragments (also known as semantic actions) can
appear at any position within a production body.
• By convention, we place curly braces around actions; if braces are needed as
grammar symbols, then we quote them.
• Example,
A → XY {action : a}
A → X {action : a}Y
• Implementation:
• An action a should be executed before proceeding with the execution of
Nonterminals that follow it.
• Transform the grammar adding a marker M symbol A → X MY and using an
empty RHS production M → {action : a}

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 21 / 68

SDD vs SDT: Infix to Postfix

SDD SDT

t is a string valued attribute

|| is string concatenation

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 22 / 68

Conversion of SDD into SDT

S-attributed SDD to an SDT

• Write actions at the end of the production body
• Known as postfix SDT

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 23 / 68

Implementation of Postfix SDT
• Use parser stack (of states/symbols) itself in LR parser
• Attach attributes to corresponding state/symbol

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 24 / 68

L-attributed SDD to an SDT

• Embed actions that compute inherited attributes for non-terminal A immediately

before A in the production body
• Place actions that compute synthesized attributes for a head of the production at
the end of the production body
• Evaluate in left-to-right in depth-first-traversal

Procedure dfvisit(n:node)
Begin
Foreach child m of n from left to right do
Evaluate inherited attributes of m;
dfvisit(m);
End
Evaluate synthesized attributes of n
End

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 25 / 68

Elimination of Left-recursion
• Grammar with left recursion, A → AY |X can’t be parsed by top-down parser.
• Already we know to eliminate left recursion i.e., as A → XR, R → YR | 
• But how to transform the actions computing attributes? For Example
A → AY {action : a}
A → X {action : b}
• Consider the following expression grammar with print action
E → E + T {print 0 +0 }
E →T
• The equivalent left recursion free SDT is
E → TR
R → +T {print 0 +0 }R
R→
Note: This is needed when we need to implement SDT with a top-down parser.

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 26 / 68

Elimination of Left-recursion (Cont.)

Non Left-recursive Grammar

Left-recursive Grammar
A → X {R.i = f (X .x)}R{A.a = R.s}
A → AY {A.a = g (A1 .a, Y .y )}
R → Y {R1 .i = g (R.i, Y .y )}R1 {R.s = R1 .s}
A → X {A.a = f (X .x)}
R → {R.s = R.i}

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 27 / 68

Example: SDD and SDT for while-statement

S → while (C) S1

Inherited attributes
• S.next, points to the code that
label L1:
must be executed after S finishes C.code
• C.true, points to the code to be if(C is false)
executed if C is true goto C.false (i.e. S.next)
else
• C.false, points to the code to be
goto C.true (i.e L2)
executed if C is false label L2:
Synthesized attributes S.code
• C.code, denotes the intermediate goto L1
code for the condition
• S.code, denotes the intermediate
code for statement(s)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 28 / 68

Example: SDD and SDT for while-statement (Cont.)
Production
S → while (C) S1
SDD

SDT

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 29 / 68

Intermediate Code
• Developing compilers of M languages for N target machines:
+ With intermediate code generation: M frontends, 1 code optimizer, N code
generators
- Without intermediate code generation: M frontends, MxN code generators,
MxN code optimizers
• Standard representation: Three address code (TAC)
• At most one operator at right hand side
• No built-up arithmetic expressions permitted
• Built from two basic components
• A TAC contains
• Address, may be
• an address of a source program variable
• constant
• compiler generated temprary
• Instruction

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 30 / 68

TAC: Instruction set
Assignment
• x = y op z
• x = op y, like unary minus, negation, typecast etc.
• Copy x = y

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 31 / 68

TAC: Instruction set
Assignment
• x = y op z
• x = op y, like unary minus, negation, typecast etc.
• Copy x = y
Unconditional jumps goto L

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 31 / 68

TAC: Instruction set
Assignment
• x = y op z
• x = op y, like unary minus, negation, typecast etc.
• Copy x = y
Unconditional jumps goto L
Conditional jumps
• if x goto L
• ifFalse x goto L
• if x relop y goto L

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 31 / 68

TAC: Instruction set
Assignment
• x = y op z
• x = op y, like unary minus, negation, typecast etc.
• Copy x = y
Unconditional jumps goto L
Conditional jumps
• if x goto L
• ifFalse x goto L
• if x relop y goto L
Procedure calls p(x1, x2...xn)
param x1
param x2 ...
param xn
call p, n

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 31 / 68

TAC: Instruction set
Assignment
• x = y op z
• x = op y, like unary minus, negation, typecast etc.
• Copy x = y
Unconditional jumps goto L
Conditional jumps
• if x goto L
• ifFalse x goto L
• if x relop y goto L
Procedure calls p(x1, x2...xn)
param x1
param x2 ...
param xn
call p, n
For function calls y = call p, n

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 31 / 68

TAC: Instruction set
Assignment
• x = y op z
• x = op y, like unary minus, negation, typecast etc.
• Copy x = y
Unconditional jumps goto L
Conditional jumps
• if x goto L
• ifFalse x goto L
• if x relop y goto L
Procedure calls p(x1, x2...xn)
param x1
param x2 ...
param xn
call p, n
For function calls y = call p, n
Indexed copy such as x = y[i], a[i] = b

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 31 / 68

TAC: Instruction set
Assignment
• x = y op z
• x = op y, like unary minus, negation, typecast etc.
• Copy x = y
Unconditional jumps goto L
Conditional jumps
• if x goto L
• ifFalse x goto L
• if x relop y goto L
Procedure calls p(x1, x2...xn)
param x1
param x2 ...
param xn
call p, n
For function calls y = call p, n
Indexed copy such as x = y[i], a[i] = b
Address and pointer assignment such as x = &y, x = *y, *x = y

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 31 / 68

Other representations

• Syntax tree (graphical representations)

• DAG

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 32 / 68

Other representations

• Syntax tree (graphical representations)

• DAG
• Quadruples
• Array of records each record having 4 fields [op, opr1, opr2, res]

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 32 / 68

Other representations

• Syntax tree (graphical representations)

• DAG
• Quadruples
• Array of records each record having 4 fields [op, opr1, opr2, res]
• Triples [op, opr1, opr2]
• Result field is not mentioned explicitely
• Result of a tuple is referred by its position in other tuples
• Issue with reordering of instructions
• Alternative is to use indirect tuple representation

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 32 / 68

Other representations

• Syntax tree (graphical representations)

• DAG
• Quadruples
• Array of records each record having 4 fields [op, opr1, opr2, res]
• Triples [op, opr1, opr2]
• Result field is not mentioned explicitely
• Result of a tuple is referred by its position in other tuples
• Issue with reordering of instructions
• Alternative is to use indirect tuple representation
• Indirect triples

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 32 / 68

DAG and TAC

DAG: a + a * (b - c) + (b - c) * d

TAC: do i = i + 1; while (a[i] < v)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 33 / 68

DAG and TAC
DAG: a + a * (b - c) + (b - c) * d

TAC: do i = i + 1; while (a[i] < v)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 33 / 68

Quadruples and Triples

Quadruples: a = b * - c + b * -c

Triples:

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 34 / 68

Quadruples and Triples
Quadruples: a = b * - c + b * -c

Triples:

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 34 / 68

Triples and Indirect triples

Triples:

Indirect triples:

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 35 / 68

Triples and Indirect triples
Triples:

Indirect triples:

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 35 / 68

Static Single Assignment (SSA)

• SSA: All assignments to variables with

distinct names; hence the name.
• Each variable has one definition
(computed only once)
• More values available at any point in
the program
• Facilitates code optimizations

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 36 / 68

φ function

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 37 / 68

φ function

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 37 / 68

φ function

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 37 / 68

Translation

• Arithmetic expressions
• Arrays
• Boolean Expressions
• Selection Statements
• Iterative Statements
• Procedures
• Etc.

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 38 / 68

Translation of Arithmetic Expressions

• S.code and E.code represent three-address codes for symbols S and E

respectively
• E.addr holds the value of (sub-) expression
• SDT – incremental translation – gets rid of holding long strings

Translation of expressions Incremental translation of expressions

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 39 / 68

Expression Evaluation

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 40 / 68

Translation of Control flow statements (1)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 41 / 68

Translation of Control flow statements (2)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 42 / 68

Translation of Boolean Expression (1)
• Boolean expressions are made of boolean operators operating on boolean variables
or relational expressions
• Relational expressions consists of relational operators operting on arithmetic
expressions

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 43 / 68

Translation of Boolean Expression (2)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 44 / 68

Translation of Boolean Expression (3)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 45 / 68

Translation of Boolean Expression (4)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 46 / 68

Avoiding Redundant Gotos (1)

• Use a special label fall to indicate insignificant gotos

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 47 / 68

Avoiding Redundant Gotos (2)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 48 / 68

Avoiding Redundant Gotos (3)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 49 / 68

Computing Labels in Single Pass

• Labels generated should be attached with address of the target three address code
instruction
• Backword jumps (can be done in single pass) and forward jumps (needs two passes)
• Backpatching – technique to attach the labels to addresses in a single pass

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 50 / 68

Implementation of Backpatching

• Two synthesized attributes truelist and falselist

• turelist – list of jump instructions into which jump target address must be
inserted if conditions is true
• Initially jump target address will be left unspecified

100 if x < 100 goto _______

101 goto _______

• makelist (i) – creates a list containining i which is an index into the array of
instructions, and returns pointer to the list.
• merge (p1, p2) – concatenates two lists pointed by p1 and p2, and returns a
pointer to the concatenated list.
• backpactch(p, i) – inserts target label i for each of the instruction on the list
pointed by p.

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 51 / 68

Implementation of Backpatching (Cont.)

• nextinstr holds the index of the next instruction that follows

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 52 / 68

Implementation of Backpatching (Cont.)

• Marker symbol M is introduced into the production body

• M executes a semantic action at appropriate time
• Action here generates the address (aka index) of the next instruction
• B → B1 || M B2
• M →  M.instr = nextinstr

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 53 / 68

Implementation of Backpatching (Cont.)

• Marker symbol M is introduced into the production body

• M executes a semantic action at appropriate time
• Action here generates the address (aka index) of the next instruction
• B → B1 || M B2
• M →  M.instr = nextinstr

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 53 / 68

Implementation of Backpatching (Cont.)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 54 / 68

Implementation of Backpatching (Cont.)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 55 / 68

Implementation of Backpatching (Cont.)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 55 / 68

Implementation of Backpatching (Cont.)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 56 / 68

Implementation of Backpatching (Cont.)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 57 / 68

Multi-way selection statement (Switch) (1)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 58 / 68

Multi-way selection statement (Switch) (2)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 59 / 68

Multi-way selection statement (Switch) (3)

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 60 / 68

Procedure/Function Calls

1 n = f(a[i])
2 t1 = i*4
3 t2 = a[t1]
4 param t2
5 t3 = call f, 1
6 n = t3

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 61 / 68

Types and Declarations

• Applications of Types: Type Checking and Translation

• Type checking
• Logical rules to ensure operand type matches with the type expected by the
operator
• Translation
• To determine the storage requirements, ex. Arrays, Note: the actual
allocation will be done at runtime
• To determine the storage layout (base address) for composite data types
(Relative address – which is an offset from the start of the data area)
• To insert explicit type conversions

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 62 / 68

Type Expressions

• Types follow a structure which is represented with type expression

• Basic types example, integer, char, float, void ...
• Composite data types
• Arrays ex. int[2][3], array (2, array (3, integers) array of two arrays of
each three integers
• Record example: record{float x; int y; char z;} r;

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 63 / 68

Type Hierarchy and Conversion

Type conversion

Introducing type conversion into expression evaluation

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 64 / 68

Grammar for Declaration of Variables

Grammar for declarations

Syntax-directed translation of array types

Computing types and their widths

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 65 / 68

Sequence of Declarations
• Process all declarations in a single procedure as a group
• offset maintains the next available relative address to be used by a declaration
• top refers to topmost symbol table
nested procedures,
nested blocks,
...
• Requires stack of symbol tables

Computing relative address of declared names

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 66 / 68

Translation of Fields in Records/Structures
• Grammar production
T → record ’{’D ’}’
record{float x; int y; char z;} r;
• Two semantic actions

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 67 / 68

Translation of Fields in Records/Structures
• Grammar production
T → record ’{’D ’}’
record{float x; int y; char z;} r;
• Two semantic actions
• Env implements symbols table

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 67 / 68

Translation of Fields in Records/Structures
• Grammar production
T → record ’{’D ’}’
record{float x; int y; char z;} r;
• Two semantic actions
• Env implements symbols table
• Push the current symbol table, p

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 67 / 68

Translation of Fields in Records/Structures
• Grammar production
T → record ’{’D ’}’
record{float x; int y; char z;} r;
• Two semantic actions
• Env implements symbols table
• Push the current symbol table, p
• Create a new symbol table n

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 67 / 68

Translation of Fields in Records/Structures
• Grammar production
T → record ’{’D ’}’
record{float x; int y; char z;} r;
• Two semantic actions
• Env implements symbols table
• Push the current symbol table, p
• Create a new symbol table n
• Find space requirement

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 67 / 68

Translation of Fields in Records/Structures
• Grammar production
T → record ’{’D ’}’
record{float x; int y; char z;} r;
• Two semantic actions
• Env implements symbols table
• Push the current symbol table, p
• Create a new symbol table n
• Find space requirement
• Store the computed value

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 67 / 68

Translation of Fields in Records/Structures
• Grammar production
T → record ’{’D ’}’
record{float x; int y; char z;} r;
• Two semantic actions
• Env implements symbols table
• Push the current symbol table, p
• Create a new symbol table n
• Find space requirement
• Store the computed value
• Restore the previous symbol table, p

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 67 / 68

Translation of Arrays (of M x N)

Operations on Arrays
1 a[i] = x
2 y = a[j]
3 a[i+1] = a[j*2] + 3
Location of ith element in a[i]
Translation
base + i * width
1 t1 = j*2
2 t2 = a[t1] Multidimensional Arrays
3 t3 = t2 + 3 - Find width of each dimension
4 t4 = i + 1 and add recursively
5 a[t4] = t3 - Find total numbers of elements
x width of element
Array indexing b[i][j](array indices
start from 0)
1 base + i * w1 + j * w2 (OR)
2 base + (i* N + j) * elem_width

Instructor: Venkata Ramana Badarla Semantic Analysis October 11, 2023 68 / 68