Semantic Analysis
Chapter 4
Role of Semantic Analysis
§ Syntax
§ “form” of a program
§ “easy”: check membership for CFG § linear time
§ Semantics
§ meaning of a program
§ impossible: program correctness undecidable! § we do whatever we can
2
Role of Semantic Analysis
§Static semantics – compile time
§ enforces static semantic rules at compile time
§ generates code to enforce dynamic semantic rules § constructs a syntax tree
§ information gathered for the code generator
§Dynamic semantics – run time § division by zero
§ index out of bounds
§ Semantic analysis (and intermediate code generation) – described in terms of annotation (decoration) or parse or syntax tree
§ annotations are attributes – attribute grammars
3
Role of Semantic Analysis
§ Parse tree …
4
Role of Semantic Analysis
§… parse tree …
5
Role of Semantic Analysis
§ … can be replaced by the much smaller syntax tree
6
Role of Semantic Analysis
§Dynamic checks
§ compiler generates code for dynamic checking
§ can be disabled for increased speed
§ Tony Hoare: “The programmer who disables semantic checks is like a sailing enthusiast who wears a life jacket when training on dry land but removes it when going to sea.”
§ C – almost no checks
§ Java – as many checks as possible § trend is towards stricter rules
§ Example: 3 + “four”
§ Perl – attempts to infer meaning § Python – run-time error
7
Role of Semantic Analysis
§Logical Assertions § Java:
assert denominator != 0;
AssertionError – exception thrown if semantic check fails
§C:
assert(denominator != 0);
myprog.c:42: failed assertion ‘denominator != 0’
§ Python:
assert denominator != 0, “Zero denominator!” AssertionError: Zero denominator!
§ Invariants, preconditions, postconditions
§ Euclid, Eiffel, Ada
§ invariant: expected to be true at all check points
§ pre/postconditions: true at beginning/end of subroutines
8
Role of Semantic Analysis
§Static analysis
§ compile-time algorithms that predict run-time behavior
§ extensive static analysis eliminates the need for some dynamic checks
§ precise type checking
§ enforced initialization of variables
9
Attribute Grammars
§Attribute grammar:
§ formal framework for decorating the parse or syntax tree § for semantic analysis
§ for (intermediate) code generation
§ Implementation
§ automatic
§ tools that construct semantic analyzers (attribute evaluator)
§ad hoc
§ action routines
10
Attribute Grammars
§Example: LR (bottom-up) grammar
§ arithmetic expr. with constants, precedence, associativity
§ the grammar alone says nothing about the meaning § attributes: connection with mathematical concept
1. E1 → E2+T 2. E1 → E2-T
3. E → T
4. T1 → T2*F 5. T1 → T2/F 6. T → F
7. F1 →-F2 8. F → (E) 9. F → const
11
Attribute Grammars
§Attribute grammar
§ S.val: the arithmetic value of the string derived from S §const.val: provided by the scanner
§copy rules: 3, 6, 8, 9
§ semantic functions: sum , diff , prod , quot, add_inv § use only attributes of the current production
1. E1 →E2+T
2. E1 →E2-T
3. E→T
4. T1 →T2*F
5. T1 →T2/F
6. T→F
7. F1 → – F2
8. F→(E)
9. F → const
⊳ E1.val := sum(E2.val, T.val) ⊳ E1.val := diff(E2.val, T.val) ⊳ E.val := T.val
⊳ T1.val := prod(T2.val, F.val) ⊳ T1.val := quot(T2.val, F.val) ⊳ T1.val := F.val
⊳ F1.val := add_inv(F2.val)
⊳ F.val := E.val
⊳ F.val := const.val
12
Attribute Grammars
§Example: LL (top-down) grammar § count the elements of a list
§ “in-line” notation of semantic functions
L→ id LT LT→ , L LT→ ε
⊳L.c:=1+LT.c ⊳LT.c:=L.c ⊳LT.c:=0
13
Evaluating Attributes
§Annotation of parse tree: § evaluation of attributes
§ also called decoration § Example:
§ LR(1) grammar (arithm. exp.)
§ string: (1+3)*2
§ val attribute of root will hold the value of the expression
14
Evaluating Attributes
§Types of attributes: § synthesized
§ inherited
§ Synthesized attributes:
§ values calculated only in productions where they appear only on the left-hand side
§ attribute flow: bottom-up only
§ S-attributed grammar: all attributes are synthesized
15
Evaluating Attributes
§ Inherited attributes:
§ values calculated when their symbol is on RHS of the production
§ Example: LL(1) grammar for subtraction
expr → const expr_tail expr_tail → – const expr_tail
→ε
§ string: 9 – 4 – 3
§‘-’ left-associative means cannot have only bottom-up
§ need to pass 9 to expr_tail to combine with 4
16
Evaluating Attributes
expr → const expr_tail
⊳ expr_tail.st := const.val ⊳ expr.val := expr_tail.val
expr_tail1 → – const expr_tail2
⊳ expr_tail2.st := expr_tail1.st − const.val ⊳ expr_tail1.val := expr_tail2.val
expr_tail → ε
⊳ expr_tail.val := expr_tail.st
17
Evaluating Attributes
§ Example: Complete LL(1) grammar for arithmetic expressions § Complicated because:
§ Operators are left-associative but grammar cannot be left-recursive § Left and right operands of an operator are in separate productions
18
Evaluating Attributes
§ Example: Complete LL(1) grammar for arithmetic expressions
19
Evaluating Attributes
§ Example: Annotated parse tree for the string (1+3)*2
20
Evaluating Attributes
§Attribute flow
§ Declarative notation:
§ no evaluation order specified for attributes § Well-defined grammar:
§ its rules determine unique values for attributes in any parse tree § Non-circular grammar:
§ no attribute depends on itself in any parse tree § Translation scheme:
§ algorithm that decorates parse tree in agreement with the attribute flow
21
Evaluating Attributes
§ Translation scheme:
§ Obvious scheme: repeated passes until no further changes § halts only if well defined
§ Dynamic scheme: better performance
§ topologically sort the attribute flow graph
§ Static scheme: fastest, O(n)
§ based on the structure of the grammar
§ S-attributed grammar – simplest static scheme
§ flow is strictly bottom-up; attributes can be evaluated in the
same order the nodes are generated by an LR-parser
§ L-attributed grammar
§ attributes can be evaluated by a single left-to-right depth-first traversal
22
Evaluating Attributes
§ Attribute A.s is said to depend on attribute B.t if B.t is ever passed to a semantic function that returns a value for A.s
§ L-attributed grammar:
§ each synthesized attribute of a LHS symbol depends only on that symbol’s own inherited attributes or on attributes (synthesized or inherited) of the RHS symbols
§ each inherited attribute of a RHS symbol depends only on inherited attributes of the LHS symbol or on attributes (synthesized or inherited) of symbols to its left in the RHS
23
Evaluating Attributes
§ S-attributed implies L-attributed (but not vice versa)
§ S-attributed grammar: the most general class of attribute grammars for which evaluation can be implemented on the fly during an LR parse
§ L-attributed grammar: the most general class of attribute grammars for which evaluation can be implemented on the fly during an LL parse
§ If semantic analysis interleaved with parsing:
§ bottom-up parser paired with S-attribute translation scheme § top-down parser paired with L-attributed translation scheme
24
Syntax Tree
§One-pass compiler
§ interleaved: parsing, semantic analysis, code generation § saves space (older computers)
§ no need to build parse tree or syntax tree
§Multi-pass compiler
§ possible due to increases in speed and memory § more flexible
§ better code improvement
§ Example: forward references
§ declaration before use no longer necessary
25
Syntax Tree
§Syntax Tree
§ separate parsing and semantics analysis
§ attribute rules for CFG are used to build the syntax tree § semantics easier on syntax tree
§ syntax tree reflects semantic structure better
§ can pass the tree in different order than that of parser
26
Syntax Trees Construction
§ Bottom-up (S-attributed) attribute grammar to construct syntax tree
27
Syntax Trees Construction
§ Bottom-up (S-attributed) attribute grammar to construct syntax tree (cont’d)
28
Syntax Trees Construction
§ Syntax tree construction for (1+3)*2
29
Syntax Trees Construction
§ Syntax tree construction for (1+3)*2 (cont’d)
30
Syntax Trees Construction
§ Top-down (L-attributed) attribute grammar to construct syntax tree
31
Syntax Trees Construction
§ Top-down (L-attributed) attribute grammar to construct syntax tree (cont’d)
32
Syntax Trees Construction
§ Syntax tree for (1+3)*2
33
Syntax Trees Construction
§ Syntax tree for (1+3)*2 (cont’d)
34
Action Routines
§ There are automatic tools for:
§ Context-free grammar ⟹ parser
§ Attribute grammar ⟹ semantic analyzer (attrib. eval.)
§ Automatic tools used in: § syntax-based editors
§ incremental compilers
§ Action routines
§ ad-hoc approach; most ordinary compilers use
§ Interleave parsing, syntax tree construction, other aspects of semantic analysis, code generation
§ Action routine: Semantic function that the programmer (grammar writer) instructs the compiler to execute at some point in the parse
§ In an LL grammar, can appear anywhere in the RHS; called as soon as the parser matched the (yield of the) symbol to the left
35
Action Routines – Example
§LL(1) grammar for expressions
§ with action routines for building the syntax tree
§ only difference from before: actions embedded in RHS
36
Action Routines – Example
§ Recursive descent parsing with embedded action routines:
§ does the same job as productions 2-4:
37
Action Routines – Example
§ Bottom up evaluation
§ In LR-parser action routines cannot be embedded at arbitrary
places in the RHS
§ the parser needs to see enough to identify the production, i.e., the RHS suffix that identifies the production uniquely
§ Previous examples are identical with the action routine versions
38
Syntax Tree Decoration
§ Bottom-up CFG for calculator language with types:
§ what’s new: declarations intermixed with statements; integer
and real constants; explicit conversion required
§ semantics: identifiers declared before used, types not mixed
39
Syntax Tree Decoration
§ Action routines to construct syntax tree – as before
§ Example: sum and avg. of integer and real
40
Syntax Tree Decoration
§ CFG
§ parse tree structure
§ generate strings as yields of parse trees
§ Tree grammar:
§ syntax tree structure
§ generate trees
§ decorate syntax trees using
semantic rules
§ Example (right):
§ parent – LHS symbol
§ children – RHS symbols §A: B –Ais a variant of B
§ A may appear anywhere a B is expected on a RHS
41
Syntax Tree Decoration
§ Goal: program (root) computes a list of all static semantic errors in a synthesized attribute (errors)
42
Syntax Tree Decoration
§ Attributes:
§ symtab – list (with types) of all identifiers declared to the
left in the tree
§ errors_in – a list of all static semantic errors found to its left in the tree
§ errors_out – propagate the final error list back to the root
§ Preventing cascading errors (in order to continue looking for errors): must provide values for attributes that would have been set in the absence of error
§error – pseudotype for each entry for which we generated a message
43
Tree Attribute Grammar
44
Tree Attribute Grammar
45
Tree Attribute Grammar
46
Tree Attribute Grammar
47
Tree Attribute Grammar
48
Tree Attribute Grammar
49
Syntax Tree Decoration
50