Semantic Analysis: Type Checking

2y ago
23 Views
2 Downloads
4.83 MB
147 Pages
Last View : 16d ago
Last Download : 2m ago
Upload by : Kamden Hassan
Transcription

Semantic Analysis:Type CheckingApril 22, 2013Monday, April 22, 13

Where We AreSourceCodeLexical AnalysisSyntax AnalysisSemantic AnalysisIR GenerationIR OptimizationCode GenerationOptimizationMonday, April 22, 13MachineCode

Last Time.Goals&of&a&Seman,c&Analyzer& tence&belongs&to&the&language & e&program&invalid& undefined&variables,&types& type&errors&that&can&be&caught&sta,cally& Terminology& Sta,c&checks&–&done&by&the&compiler& Dynamic&checks&–&done&at&run&,me&Monday, April 22, 13

Why Separate Seman-c Analysis? Parsing cannot catch some errors Why? Some language constructs are not context9free – Example: All used variables must have been declared (scoping) – Example: A method must be invoked with arguments of proper type (typing) Monday, April 22, 13

What%Does%Seman-c%Analysis%Do?% Checks%of%many%kinds:%1. All%iden-fiers%are%declared%2. Types%%3. Inheritance%rela-onships%4. Classes%defined%only%once%5. Methods%in%a%class%defined%only%once%6. .%.% The%requirements%depend%on%the%language%Monday, April 22, 13

Typical(Seman-c(Errors( ((in(the(same(scope)(at(most(once(( (before(being(declared( de( (right(number(and(types(of(arguments(Monday, April 22, 13

A"Sample"Seman*c"Analyzer" Works"in"two"phases""– traverses"the"AST"created"by"the"parser""1. For"each"scope"in"the"program"– process'the'declara-ons" y"variables"that"are"mul*ply"declared"– o"point"to"the"appropriate"symbolFtable"entry.""2. " – "Monday, April 22, 13

Scoping:)General)Rules) The)scope)rules)of)a)language:)– sponds)to)each)use)of)the)object)– :ons) C )and)Java)use)sta c&scoping:)– � C )uses)the)"most)closely)nested")rule) most)closely)enclosing)scope)) such)that)the)declara:on)precedes)the)use)Monday, April 22, 13

tly%called.s/ll.ac/ve(func:on( int(i( (1;(void(func()({((((cout( (i( (endl;(}(int(main(()({((((int(i( (2;((((func();((((return(0;(}(Monday, April 22, 13

tly%called.s/ll.ac/ve(func:on( int(i( (1;(void(func()({((((cout( (i( (endl;(}(int(main(()({((((int(i( (2;((((func();((((return(0;(}(Monday, April 22, 13If C useddynamic scoping,this would print out2, not 1

Dynamic(Scoping(Revisited( Each(func8on(has(an(environment(of(defini8ons( (its(environment,(its(caller s(environment(is(searched( hrough(the(chain(of(callers(( Now,(with(that(cleared(up (– put(by(the(following(program?(( Monday, April 22, 13voidvoidvoidvoidmain() { int x 0; f1(); g(); f2(); }f1() { int x 10; g(); }f2() { int x 20; f1(); g(); }g() { print(x); }

Symbol'Tables' purpose:''– keep'track'of'names'declared'in'the'program'– names'of' variables,'classes,'fields,'methods' symbol'table'entry:''– associates'a'name'with'a'set'of'a ributes,'e.g.:' )' type''(int,'float,'etc)' nesBng'level'' nBme)'Monday, April 22, 13

Review from Last Timeclass MyClass implements MyInterface {string myInteger;void doSomething() {int[] x;x new string;x[5] myInteger * y;}void doSomething() {}int fibonacci(int n) {return doSomething() fibonacci(n – 1);}}Monday, April 22, 13

Review from Last Timeclass MyClass implements MyInterface {string myInteger;Interface notCan'tdeclaredvoid doSomething() {int[] x;x new string;multiplystringsWrong typex[5] myInteger * y;}void doSomething() {Variable notCan't redefinedeclaredfunctions}Monday, April 22, 13}int fibonacci(int n) {return doSomething() fibonacci(n – 1);Can't add void}No main function

Review from Last Timeclass MyClass implements MyInterface {string myInteger;Can'tvoid doSomething() {int[] x;x new string;multiplystringsWrong typex[5] myInteger * y;}void doSomething() {Variable notCan't redefinedeclaredfunctions}Monday, April 22, 13}int fibonacci(int n) {return doSomething() fibonacci(n – 1);Can't add void}No main function

Review from Last Timeclass MyClass implements MyInterface {string myInteger;Can'tvoid doSomething() {int[] x;x new string;multiplystringsx[5] myInteger * y;}void doSomething() {}Monday, April 22, 13Wrong typeVariable notdeclared}int fibonacci(int n) {return doSomething() fibonacci(n – 1);Can't add void}No main function

Review from Last Timeclass MyClass implements MyInterface {string myInteger;Can'tvoid doSomething() {int[] x;x new string;multiplystringsWrong typex[5] myInteger * y;}void doSomething() {}Monday, April 22, 13}int fibonacci(int n) {return doSomething() fibonacci(n – 1);Can't add void}No main function

Review from Last Timeclass MyClass implements MyInterface {string myInteger;Can'tvoid doSomething() {int[] x;x new string;multiplystringsWrong typex[5] myInteger * y;}void doSomething() {}Monday, April 22, 13}int fibonacci(int n) {return doSomething() fibonacci(n – 1);Can't add void}

What Remains to Check?Monday, April 22, 13 Type errors. Today: What are types? What is type-checking? A type system for Decaf.

Types& What&is&a&type?&– The&no/on&varies&from&language&to&language& Consensus&– A&set&of&values&– A&set&of&opera/ons&allowed&on&those&values&Monday, April 22, 13

Why Do We Need Type Systems? Consider the assembly language fragment addi r1, r2, r3 What are the types of r1, r2, r3? Monday, April 22, 13

Types&and&Opera,ons& e&– It&doesn er&in&C&– It&does&make&sense&to&add&two&integers&– a,on!&Monday, April 22, 13

Type%Systems% A%language %for%which%types% ons%are%used%with%the%correct%types%– Enforces%intended%interpreta7on%of%values% %seman7c%checking%rules%Monday, April 22, 13

What%Can%Types%do%For%Us?% Can%detect%certain%kinds%of%errors% Memory%errors:%– Reading%from%an%invalid%pointer,%etc.% ViolaAon%of%abstracAon%boundaries%Monday, April 22, 13

Type%Checking%Overview% Three%kinds%of%languages:%– Sta s%done%as%part%of%compila on%(C,%Java)%– %done%as%part%of%program%execu on%(Scheme)% Variable%types%depend%on%the%path%– Untyped:%No%type%checking%(machine%code)%Monday, April 22, 13

The Type Wars Compe.ng views on sta.c vs. dynamic typing Sta.c typing proponents say: – Sta.c checking catches many programming errors at compile .me – Avoids overhead of run?.me type checks Dynamic typing proponents say: – Sta.c type systems are restric.ve – Rapid prototyping easier in a dynamic type system In prac.ce, most code is wriDen in sta.cally typed languages with an escape mechanism – Unsafe casts in C, Java – The best or worst of both worlds? Monday, April 22, 13

Type Systems The rules governing permissibleoperations on types forms a typesystem.Strong type systems are systems thatnever allow for a type error. Weak type systems can allow typeerrors at runtime. Monday, April 22, 13Java, Python, JavaScript, LISP, Haskell, etc.C, C

Type%Checking%and%Type%Inference% ped%programs% ermine%whether%the%opera:on%is%allowed%% ng%type%informa:on% Given%the%type%of%operands,%determine%– the%meaning%of%the%opera:on%– the%type%of%the%opera:on% the%way%the%variable%is%used% ngeably%Monday, April 22, 13

Issues%in%Typing% Does%the%language%have%a%type%system?%– tem%at%all% When%is%typing%performed?%– Sta?c%typing:%At%compile%?me%– Dynamic%typing:%At%run?me% How%strictly%are%the%rules%enforced?%– Strongly%typed:%No%excep?ons%%– Weakly%typed:%With%wellHdefined%excep?ons% Type%equivalence%&%subtyping%– When%are%two%types%equivalent?%% What%does%"equivalent"%mean%anyway?%– When%can%one%type%replace%another?%Monday, April 22, 13

Components)of)a)Type)System) Built3in)types) Rules)for)construc7ng)new)types)– Where)do)we)store)type)informa7on?) Rules)for)determining)if)two)types)are)equivalent) y, April 22, 13

Component:)Built.in)Types) Integer)– usual)opera6ons:)standard)arithme6c)) Floa6ng)point)– usual)opera6ons:)standard)arithme6c)) Character)– – usual)opera6ons:)(lexicographic))comparisons) Boolean)– usual)opera6ons:)not,)and,)or,)xor))Monday, April 22, 13

Component:)Type)Constructors) Pointers)– addresses)– �� issue:)equivalency))) Func4on)types)– al int int))Monday, April 22, 13

Component:)Type)Equivalence) Name)equivalence)– Types)are)equiv)only)when)they)have)the)same)name) Structural)equivalence)– Types)are)equiv)when)they)have)the)same)structure) Example)– )equivalence)for)arrays/pointers))Monday, April 22, 13

Component:)Type)Equivalence) Type)coercion)– If)x)is)float,)is)x 3)acceptable?) Disallow) Allow)and)implicitly)convert)3)to)float) rt)3)to)float)– What)should)be)allowed?) float)to)int)?) int)to)float)?) What)if)mulGple)coercions)are)possible?)– Consider)3) )"4") )Monday, April 22, 13

Our Focus Decaf is typed statically and weakly: Monday, April 22, 13Type-checking occurs at compile-time.Runtime errors like dereferencing null or aninvalid object are allowed.Decaf uses class-based inheritance.Decaf distinguishes primitive types andclasses.

Typing in DecafMonday, April 22, 13

Static Typing in Decaf Static type checking in Decaf consists oftwo separate processes: Monday, April 22, 13Inferring the type of each expression fromthe types of its components.Confirming that the types of expressions incertain contexts matches what is expected.Logically two steps, but you will probablycombine into one pass.

An Examplewhile (numBitsSet(x 5) 10) {if (1.0 4.0) {/* */}while (5 null) {/* */}}Monday, April 22, 13

An Examplewhile (numBitsSet(x 5) 10) {if (1.0 4.0) {/* */}while (5 null) {/* */}}Monday, April 22, 13

An Examplewhile (numBitsSet(x 5) 10) {if (1.0 4.0) {/* */}while (5 null) {/* */}}Monday, April 22, 13

An Examplewhile (numBitsSet(x 5) 10) {if (1.0 4.0) {/* */}while (5 null) {/* */}}Monday, April 22, 13Well-typedexpression withwrong type.

An Examplewhile (numBitsSet(x 5) 10) {if (1.0 4.0) {/* */}while (5 null) {/* */}}Monday, April 22, 13

An Examplewhile (numBitsSet(x 5) 10) {if (1.0 4.0) {/* */}while (5 null) {/* */}}Monday, April 22, 13Expression withtype error

Inferring Expression Types Monday, April 22, 13How do we determine the type of anexpression?Think of process as logical inference.

Inferring Expression Types How do we determine the type of anexpression?Think of process as logical inference. Monday, April 22, 13IntConstantIntConstant13742

Inferring Expression Types How do we determine the type of anexpression?Think of process as logical inference. intMonday, April 22, 13IntConstantIntConstant13742

Inferring Expression Types How do we determine the type of anexpression?Think of process as logical inference. intIntConstant137Monday, April 22, 13intIntConstant42

Inferring Expression Types How do we determine the type of anexpression?Think of process as logical inference.intintIntConstant137Monday, April 22, 13 intIntConstant42

Inferring Expression Types Monday, April 22, 13How do we determine the type of anexpression?Think of process as logical inference.

Inferring Expression Types How do we determine the type of anexpression?Think of process as logical inference. bool xIdentifierbool yMonday, April 22, 13Identifier bool true BoolConstant

Inferring Expression Types How do we determine the type of anexpression?Think of process as logical inference. bool xIdentifierbool yMonday, April 22, 13Identifierbool bool true BoolConstant

Inferring Expression Types How do we determine the type of anexpression?Think of process as logical inference.bool bool xIdentifierbool yMonday, April 22, 13Identifierbool bool true BoolConstant

Type Checking as Proofs Monday, April 22, 13We can think of syntax analysis asproving claims about the types ofexpressions.We begin with a set of axioms, thenapply our inference rules to determinethe types of expressions.Many type systems can be thought of asproof systems.

Sample Inference Rules Monday, April 22, 13“If x is an identifier that refers to anobject of type t, the expression x hastype t.”“If e is an integer constant, e has typeint.”“If the operands e1 and e2 of e1 e2 areknown to have types int and int, thene1 e2 has type int.”

Formalizing our Notation We will encode our axioms and inferencerules using this syntax:PreconditionsPostconditions Monday, April 22, 13This is read “if preconditions are true, wecan infer postconditions.”

Formal Notation for Type Systems We write e:Tif the expression e has type T. Monday, April 22, 13The symbol means “we can infer.”

Our Starting Axioms true : boolMonday, April 22, 13 false : bool

Some Simple Inference Rulesi is an integer constants is a string constant i : int s : stringd is a double constant d : doubleMonday, April 22, 13

More Complex Inference RulesMonday, April 22, 13 e1 : int e2 : int e1 : double e2 : double e1 e2 : int e1 e2 : double

More Complex Inference RulesIf we can show that e1and e2 have type int Monday, April 22, 13 e1 : int e2 : int e1 : double e2 : double e1 e2 : int e1 e2 : double

More Complex Inference RulesIf we can show that e1and e2 have type int e1 : int e2 : int e1 : double e2 : double e1 e2 : int e1 e2 : double then we can showthat e1 e2 hastype int as wellMonday, April 22, 13

Even More Complex Inference RulesMonday, April 22, 13 e1 : T e2 : TT is a primitive type e1 : T e2 : TT is a primitive type e1 e2 : bool e1 ! e2 : bool

Why Specify Types this Way? Gives a rigorous definition of types independent of anyparticular implementation. Gives maximum flexibility in implementation. Can do inductive proofs on the structure of the program.This is what's used in the literature. Monday, April 22, 13Can implement type-checking however you want, as long as youobey the rules.Allows formal verification of program properties. No need to say “you should have the same type rules as myreference compiler.”Good practice if you want to study types.

A Problemx is an identifier. x : ?Monday, April 22, 13

A Problemx is an identifier. x : ?How do we know thetype of x if we don'tknow what it refers to?Monday, April 22, 13

An Incorrect Solutionx is an identifier.x is in scope with type T. x:TMonday, April 22, 13

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x :x double: double

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x :x double: double

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int

An Incorrect Solutionx is an identifier.x is in scope with type T.d is a double constant x:T d : doubleint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int

An Incorrect Solutionx is an identifier.x is in scope with type T.d is a double constant x:T d : doubleint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int 1.5 : double

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int 1.5 : double

An Incorrect Solutionx is an identifier.x is in scope with type T. x:Tint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int 1.5 : double

An Incorrect Solutionx is an identifier.x is in scope with type T. e1 : T e2 : TT is a primitive type x:T e1 e2 : boolint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int 1.5 : double

An Incorrect Solutionx is an identifier.x is in scope with type T. e1 : T e2 : TT is a primitive type x:T e1 e2 : boolint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int 1.5 : double x 1.5 : bool

An Incorrect Solutionx is an identifier.x is in scope with type T. e1 : T e2 : TT is a primitive type x:T e1 e2 : boolint MyFunction(int x) {{double x;}}Monday, April 22, 13if (x 1.5) {/* */}Facts x : double x : int 1.5 : double x 1.5 : bool

Strengthening our Inference Rules Monday, April 22, 13The facts we're proving have no context.We need to strengthen our inferencerules to remember under whatcircumstances the results are valid.

Adding Scope We writeS e:Tif, in scope S, expression e has type T. Monday, April 22, 13Types are now proven relative to thescope they are in.

Old Rules RevisitedS true : boolS false : booli is an integer constants is a string constantS i : intS s : stringd is a double constantS d : doubleMonday, April 22, 13S e1 : doubleS e2 : doubleS e1 : intS e2 : intS e1 e2 : doubleS e1 e2 : i

Semantic Analysis: Type Checking April 22, 2013 Monday, April 22, 13. Where We Are Lexical Analysis Semantic Analysis Syntax Analysis IR Generation IR Optimization Code Generation Optimizati

Related Documents:

Semantic Analysis Chapter 4 Role of Semantic Analysis Following parsing, the next two phases of the "typical" compiler are –semantic analysis –(intermediate) code generation The principal job of the semantic analyzer is to enforce static semantic rules –constructs a syntax tree (usua

5 The Role of Semantic Analysis nDetect errors in programs! nStatic semantic analysis n Detect as many errorsas possible early, before execution n Type inference and type checking nDynamic semantic analysis n Detect errors by performing checks during execution n Again, detect errors as early as possible. E.g., flagging an ar

tive for patients with semantic impairments, and phono-logical tasks are effective for those with phonological impairments [4,5]. One of the techniques that focus on semantic impair-ments is Semantic Feature Analysis (SFA). SFA helps patients with describing the semantic features which ac-tivate the most distinguishing features of the semantic

WibKE – Wiki-based Knowledge Engineering @WikiSym2006 Our Goals: Why are we doing this? zWhat is the semantic web? yIntroducing the semantic web to the wiki community zWhere do semantic technologies help? yState of the art in semantic wikis zFrom Wiki to Semantic Wiki yTalk: „Doing Scie

(semantic) properties of objects to place additional constraints on snapping. Semantic snapping also provides more complex lexical feedback which reflects potential semantic consequences of a snap. This paper motivates the use of semantic snapping and describes how this technique has been implemented in a window-based toolkit. This

Conventional Semantic Analysis Compile-time analysis and run-time “actions” that enforce language-defined semantics –Static semantic rules are enforced at compile time by the compiler oType checking –Dynamic semantic rules are enforced at runtime b

What is semantic analysis? Type systems What to check? Type Systems 17 A type ssystem ystem iis s uused sed to for tthe he type checking A type system incorporates – syntactic cconstructs onstructs

Calculus , Henry Weisbecker, 2000, Calculus, 1088 pages. Each Problem Solver is an insightful and essential study and solution guide chock-full of clear, concise problem-solving gems. All your questions can be found in one convenient. Calculus Early Transcendentals, Dale Varberg, Edwin J. Purcell, Steve E. Rigdon, 2007, Mathematics, 790 pages .