Semantic Analysis
Read: Scott, Chapter 4.1-4.3
1
Lecture Outline
n Syntax vs. static semantics
n Static semantics vs. dynamic semantics
n Attribute Grammars n Attributes and rules
n Synthesized and inherited attributes n S-attributed grammars
n L-attributed grammars
Programming Languages CSCI 4430, A. Milanova 2
Static Semantics
n Earlier we considered syntax analysis n Informally, syntax deals with the form of
programming language constructs
n We now look at static semantic analysis
n Semantics deals with the meaning of programming language constructs
n The distinction between the two is fuzzy
n In practice, anything that is not expressed in
terms of certain CFG (LALR(1), in particular) is
considered semantics
Programming Languages CSCI 4430, A. Milanova 3
Static Semantics vs. Dynamic Semantics
n Static semantic analysis (compile-time)
n Informally, reasons about program properties statically, before program execution
n E.g., determine static types of expressions, detect certain errors
n Dynamic semantic analysis (run-time)
n Reasons about program properties dynamically, during program execution
n E.g., could expression a[i] index out of array bounds, etc.?
Programming Languages CSCI 4430, A. Milanova 4
The Role of Semantic Analysis
n Detect errors in programs! n Static semantic analysis
n Detect as many errors as possible early, before execution n Type inference and type checking
n Dynamic semantic analysis
n Detect errors by performing checks during execution
n Again, detect errors as early as possible. E.g., flagging an array- out-of-bounds at assignment a[i] = … is useful
n Tradeoff: dynamic checks slow program execution
n Languages differ greatly in the amount of static
semantic analysis and dynamic semantic analysis
they perform
Programming Languages CSCI 4430, A. Milanova 5
Examples of Static Semantic Errors
n Type mismatch:
n x = y+z+w: type of left-hand-side does not “match” type of right-hand-side
n A a; … ; a.m(): m() cannot be invoked on a variable of type A
n Definite assignment check in Java: a local variable must be assigned before it is used
Programming Languages CSCI 4430, A. Milanova 6
Examples of Dynamic Semantic Errors
n Null pointer dereference:
n a.m() in Java, and a is null (i.e., uninitialized reference) n What happens?
n Array-index-out-of-bounds:
n a[i], i goes beyond the bounds of a
n What happens in C++? What happens in Java?
n Casting an object to a type of which it is not an instance
n C++? Java? n And more…
Programming Languages CSCI 4430, A. Milanova 7
Static Semantics vs. Dynamic Semantics
n Again, distinction between the two is fuzzy
n For some programs, the compiler can predict
run-time behavior by using static analysis n E.g., there is no need for a nullness check:
x = new X();
x.m(); // x is non-null
n In general, the compiler cannot predict run- time behavior
n Static analysis is limited by the halting problem Programming Languages CSCI 4430, A. Milanova 8
Semantic Analyzer
compiler
character stream
token stream parse trees
optimizer
modified intermediate form
assembly code
scanner
parser
code generator
semantic analyzer
and intermediate code generator
intermediate
form
Semantic analyzer performs static semantic analysis on parse trees and ASTs. Optimizer performs static semantic analysis on intermediate 3-address code.
Programming Languages CSCI 4430, A. Milanova 9
Lecture Outline
n Syntax vs. static semantics
n Static semantics vs. dynamic semantics
n Attribute Grammars n Attributes and rules
n Synthesized and inherited attributes n S-attributed grammars
n L-attributed grammars
Programming Languages CSCI 4430, A. Milanova 10
Attribute Grammars:
Foundation for Static Semantic Analysis
n Attribute Grammars: generalization of Context-Free Grammars
n Associate meaning with parse trees n Attributes
n Each grammar symbol has one or more values called attributes associated with it. Each parse tree node has its own instances of those attributes; attribute value carries the “meaning” of the parse tree rooted at node
n Semantic rules
n Each grammar production has associated rule, which
may refer to and compute the values of attributes Programming Languages CSCI 4430, A. Milanova 11
Example: Attribute Grammar to Compute Value of Expression (denote grammar by AG1)
S®E E®E+T |T T®T*F |F F®num
Production
S ® E
E ® E1+T
E ® T
T ® T1*F
T ® F
F ® num
Semantic Rule print(E.val)
E.val := E1.val + T.val E.val := T.val
T.val := T1.val * F.val T.val := F.val
F.val := num.val val: Attributes
Programming Languages CSCI 4430, A. Milanova
12
Example: Decorated parse tree for input
3*5 + 2*4
S
S ® E
E ® E1+T E ® T
T ® T1*F T ® F
F ® num
print(E.val)
E.val := E1.val+T.val E.val := T.val
T.val := T1.val*F.val T.val := F.val
F.val := num.val
23
E E+T
TT*F
15
8
15
2
4
3
T*F
F num num
F
num
num
5
2
4
3
5
2
3
Programming Languages CSCI 4430, A. Milanova
13
Example
n val: Attributes associated to symbols
n Intuitively, A.val holds the value of the expression,
represented by the subtree rooted at A
n Separate attributes are associated with separate nodes in
the parse tree
n Indices are used to distinguish between symbols with same name within same production
n E.g., E ® E1+T E.val := E1.val+T.val n Attributes of terminals supplied by scanner
n In example, attributes of + and * are never used
Programming Languages CSCI 4430, A. Milanova 14
Building an Abstract Syntax Tree (AST)
n An AST is an abbreviated parse tree
n Operators and keywords do not appear as leaves, but at the interior node that would have been their parent
n Chains of single productions are collapsed n Compilers typically work with ASTs
Programming Languages CSCI 4430, A. Milanova 15
Building ASTs for Expressions
Parse tree for 3*5+2*4 E
E+T TT*F
T*F num:4 FF
num:5
Abstract syntax tree (AST)
+ **
num:3 num:2num:4 num:5
num:3
num:2
How do we construct syntax trees for expressions?
Programming Languages CSCI 4430, A. Milanova
16
Attribute Grammar to build AST for Expression (denote by AG2)
n An attribute grammar:
Attribute “nodepointer” points to AST
Production
E ® E1+T E ® T
T ® T1 *F
T ® F
F ® num
Semantic Rule
E.nptr := mknode(+, E1.nptr, T.nptr) E.nptr := T.nptr
T.nptr := mknode(*, T1.nptr, F.nptr)
T.nptr := F.nptr
F.nptr := mkleaf(num, num.val)
mknode(op,left,right) creates an operator node with label op, and two fields containing pointers left, to left operand and right, to right operand
mkleaf(num,num.val) creates a leaf node with label num, and a field containing the value of the number
17
Constructing ASTs for Expressions
Input:
3*5+2*4
S
E.nptr := mknode(‘+’, E1.nptr, T.nptr) E.nptr := T.nptr
T.nptr := mknode(‘*’, T1.nptr, F.nptr)
T.nptr := F.nptr
F.nptr := mkleaf(‘num’, num.val)
E ® E1+T E ® T
T ® T1 *F
T ® F
F ® num
E E+T
+,
,
*,
,
T T*F
num,4
*,
,
T*F
F F num,5
num,2
num,3
18
Exercise
n We know that the language L = anbncn is not
context free. It can be captured however with an attribute grammar. Give an underlying CFG and a set of attribute rules that associate an attribute ok with the root S of each parse tree, such that S.ok is true if and
only if the string corresponding to the fringe of the tree is in L.
Programming Languages CSCI 4430, A. Milanova 19
Exercise
Programming Languages CSCI 4430, A. Milanova 20
Exercise
n Consider the expression grammar
E®E+T|T T®T*F|F
F ®num|(E)
Give attribute rules to accumulate into the root a count of the maximum depth to which parentheses are nested in the expression. E.g., ((1 + 2)*3 + 4)*5 + 6 has a count of 2.
Programming Languages CSCI 4430, A. Milanova 21
Exercise
Programming Languages CSCI 4430, A. Milanova 22
Another Grammar
E stands for expr
T stands for term
TT stands for term_tail
n Now, the right-recursive LL(1) grammar:
E ® T TT TT ®-T TT
TT ® ε T ® num
n Goal: construct an attribute grammar that computes the value of an expression
n Values must be computed “normally”, i.e., 5-3-2 must be evaluated as (5-3)-2, not as
5-(3-2)
Programming Languages CSCI 4430, A. Milanova 23
Question
n What happens if we wrote a “bottom-up attribute flow” grammar?
E ® T TT
TT ® – T TT1
TT ® ε T ® num
E.val = T.val – TT.val TT.val = T.val – TT1.val
TT.val = 0 T.val = num.val
A hack:
E ® T TT
TT ® – T TT1
TT ® ε T ® num
E.val = T.val – TT.val TT.val = T.val + TT1.val
TT.val = 0 T.val = num.val
Unfortunately, this won’t work if we add TT ® + T TT1
Programming Languages CSCI 4430, A. Milanova 24
Attribute Grammar to Compute Value of Expressions (denote by AG3)
E ® T TT TT ® -T TT | +T TT | ε T ® num
Production Semantic Rules
E ® T TT (1) TT.sub := T.val
TT ® – T TT1 (1) TT1.sub:= TT.sub – T.val TT ® + T TT1 (1) TT1.sub:= TT.sub + T.val TT ® ε (1) TT.val := TT.sub
(2) E.val := TT.val (2) TT.val := TT1.val (2) TT.val := TT1.val
T ® num (1) T.val := num.val (provided by scanner)
Attributes flow from parent to node, and from “siblings” to node! Programming Languages CSCI 4430, A. Milanova 25
Attribute TT1.sub: computed based on parent TT and sibling T: TT.sub – T.val
Attribute Flow
…
TT
24
15
–
T TT1
…
…
TT
3
21
15
E.g., 25–1-3-6
TT holds subtotal 24 (for 25 – 1, computed so far) T holds value 3 (i.e., the value of next term)
TT1 getssubtotal21(for25–1–3)
Passed down the tree of TT1 to next TT on chain Eventually, we hit TT ® ε and value gets subtotal 15
Value 15 is passed back up
26
Example
Programming Languages CSCI 4430, A. Milanova 27
Attribute Flow
n Attribute .val carries the total value
n Attribute .sub is the subtotal carried from left
n Rules for nonterminals E, T do not perform computation
n No need for .sub attribute
n .val attribute is carried to the right
n In E ® T TT : val of T is passed to sibling TT
n In TT ® -T TT1 : val of T is passed to sibling TT1
Programming Languages CSCI 4430, A. Milanova 28
Attribute Flow
n Rules for nonterminal TT do perform computation
n TT needs to carry subtotal in .sub
n E.g., in TT ® – T TT1 the subtotal of TT1 is computed
by subtracting the value of T from the subtotal of TT
Programming Languages CSCI 4430, A. Milanova 29
Lecture Outline
n Syntax vs. static semantics
n Static semantics vs. dynamic semantics
n Attribute Grammars n Attributes and rules
n Synthesized and inherited attributes n S-attributed grammars
n L-attributed grammars
Programming Languages CSCI 4430, A. Milanova 30
Synthesized and Inherited Attributes
n Synthesized attributes
n Attribute value computed from attributes of
descendants in parse tree, and/or attributes of self n E.g., attributes val in AG1, val in AG3
n E.g., attributes nptr in AG2
n Inherited attributes
n Attribute value computed from attributes of parent
in tree and/or attributes of siblings in tree n E.g., attributes sub in AG3
n In order to compute value “normally” we needed to
pass sub down the tree (sub is inherited attribute). Programming Languages CSCI 4430, A. Milanova 31
S-attributed Grammars
n An attribute grammar for which all attributes are synthesized is said to be S-attributed
n “Arguments” of rules are attributes of symbols from the production right-hand-side
n I.e., attributes of children in parse tree
n “Result” is placed in attribute of the symbol on the left-hand-side of the production
n I.e., computes attribute of parent in parse tree
n I.e., attribute values depend only on descendants in tree. They do not depend on parents or
siblings in tree!
32
Questions
n Can you give examples of S-attributed grammars?
n Answer: AG1 and AG2
n How can we evaluate S-attributed
grammars?
n I.e., in what order do we visit nodes of the parse tree and compute attributes, bottom-up or top- down?
n Answer: bottom-up
Programming Languages CSCI 4430, A. Milanova 33
L-attributed Grammar
n An attribute grammar is L-attributed if each inherited attribute of Xj on the right-hand-side of A ® X1 X2 …Xj-1Xj…Xn depends only on
n (1) the attributes of symbols to the left of Xj: X1, X2 ,…, Xj-1
n (2) the inherited attributes of A
Programming Languages CSCI 4430, A. Milanova 34
Questions
n Can you give examples of L-attributed grammars?
n Answer: AG3
n How can we evaluate L-attributed grammars?
n I.e., in what order do we visit the nodes of the parse tree?
n Answer: top-down
Programming Languages CSCI 4430, A. Milanova 35
Question
n An attribute grammar is L-attributed if each inherited attribute of Xj on the right-hand-side of A ® X1 X2 …Xj-1Xj…Xn depends only on
n (1) the attributes of symbols to the left of Xj: X1, X2 ,…, Xj-1
n (2) the inherited attributes of A
n Why the restriction on siblings and kinds of attributes of parent? Why not allow dependence on siblings to the right of Xj,
e.g., Xj+1, etc.?
Programming Languages CSCI 4430, A. Milanova 36
Recursive Descent (sketch)
num S()
case lookahead() of
num: val = E(); match($$); return val otherwise PARSE_ERROR
num E()
case lookahead() of
num: sub = T(); val = TT(sub); return val otherwise PARSE_ERROR
num TT(num sub) case lookahead() of
– : match(‘-’); Tval = T(); val = TT(sub -Tval); return val + : match(‘+’); Tval = T(); val = TT(sub -Tval); return val $$:val = sub; return val
otherwise: PARSE_ERROR
37
S ® E $$
E®TTT TT®-T TT|+T TT|ε T®num
Evaluating Attributes and Attribute Flow
n S-attributed grammars
n A very special case of attribute grammars
n Most important case in practice
n Can be evaluated on-the-fly during a bottom-up
(LR) parse
n L-attributed grammars
n A proper superset of S-attributed grammars n Each S-attributed grammar is also L-attributed
because restriction applies only to inherited attributes
n Can be evaluated on-the-fly during a top-down (LL) parse
38
The End
Programming Languages CSCI 4430, A. Milanova 39