命令式语言

1 .Chapter 5 Names, Bindings, and Scopes

2 .Copyright © 2015 Pearson. All rights reserved. 1- 2 Chapter 5 Topics Introduction Names Variables The Concept of Binding Scope Scope and Lifetime Referencing Environments Named Constants

3 .Copyright © 2015 Pearson. All rights reserved. 1- 3 Introduction Imperative languages are abstractions of von Neumann architecture Memory Processor Variables are characterized by attributes To design a type, must consider scope, lifetime, type checking, initialization, and type compatibility

4 .Copyright © 2015 Pearson. All rights reserved. 1- 4 Names Design issues for names: Are names case sensitive? Are special words reserved words or keywords?

5 .Copyright © 2015 Pearson. All rights reserved. 1- 5 Names (continued) Length If too short, they cannot be connotative Language examples: C99: no limit but only the first 63 are significant; also, external names are limited to a maximum of 31 C# and Java: no limit, and all are significant C++: no limit, but implementers often impose one

6 .Copyright © 2015 Pearson. All rights reserved. 1- 6 Names (continued) Special characters PHP: all variable names must begin with dollar signs Perl: all variable names begin with special characters, which specify the variable’s type Ruby: variable names that begin with @ are instance variables; those that begin with @@ are class variables

7 .Names (continued) Case sensitivity Disadvantage: readability (names that look alike are different) Names in the C-based languages are case sensitive Names in others are not Worse in C++, Java, and C# because predefined names are mixed case (e.g. IndexOutOfBoundsException ) Copyright © 2015 Pearson. All rights reserved. 1- 7

8 .Fortran Variable Fortran variables Fortran IV numbers and letters, at least 6 characters Fortran 77 numbers and letters and “_”, at least 16 characters must start with a letter Up through 77, spaces in a Fortran program are ignored IVALUE and I VAL UE are the same using strange spacing, while acceptable, is bad practice Fortran variables are typed Fortran is case insensitive ivar is the same as Ivar or IvAr Fortran variables are typed INTEGER, REAL, DOUBLE PRECISION, COMPLEX LOGICAL, CHARACTER (77+)

9 .Copyright © 2015 Pearson. All rights reserved. 1- 9 Names (continued) Special words An aid to readability; used to delimit or separate statement clauses A keyword is a word that is special only in certain contexts A reserved word is a special word that cannot be used as a user-defined name Potential problem with reserved words: If there are too many, many collisions occur (e.g., COBOL has 300 reserved words!)

10 .Copyright © 2015 Pearson. All rights reserved. 1- 10 Variables A variable is an abstraction of a memory cell Variables can be characterized as a sextuple of attributes: Name Address Value Type Lifetime Scope

11 .Copyright © 2015 Pearson. All rights reserved. 1- 11 Variables Attributes Name - not all variables have them Address - the memory address with which it is associated A variable may have different addresses at different times during execution A variable may have different addresses at different places in a program If two variable names can be used to access the same memory location, they are called aliases Aliases are created via pointers, reference variables, C and C++ unions Aliases are harmful to readability (program readers must remember all of them)

12 .Copyright © 2015 Pearson. All rights reserved. 1- 12 Variables Attributes (continued) Type - determines the range of values of variables and the set of operations that are defined for values of that type; in the case of floating point, type also determines the precision Value - the contents of the location with which the variable is associated - The l-value of a variable is its address - The r-value of a variable is its value Abstract memory cell - the physical cell or collection of cells associated with a variable

13 .l-value and r-value Information in Program can be Characterized Environment: Maps Name to Storage Loc (l-value) Store: Maps Location to Value it Contains (l-value to an r-value) Environment State Compile Time Run Time

14 .Initial Look at Types What are Types? Base Type Inductive Types What’s a Type System? What are the Components? Relate to Programming Languages? What are Type Expressions Types can be defined inductively Base types (a.k.a. the terminals) Inductive types (a.k.a. grammatical productions) From: Chapters 6 and 7 of Compilers: Principles, Techniques and Tools , Aho , et al., Addison-Wesley

15 .Base Types What are the base types ? int float double char void bool error

16 .Inductive Type Definition Purpose Define a type in terms of other simple/smaller types Example array pointer reference Pair structure function methods classes ...

17 .The Notion of a Type System Logical Placement of Type Checker: Role of Type Checker is to Verify Semantic Contexts Incompatible Operator/Operands Existence of Flow-of Control Info (Goto/Labels) Uniqueness w.r.t. Variable Definition, Case Statement Labels/Ranges, etc. Naming Checks Across Blocks (Begin/End) Function Definition vs. Function Call Type Checking can Occur as “Side-Effect” of Parsing via a Judicious Use of Attribute Grammars! Parser Type Checker Int. Code Generator Token Stream Syntax Tree Syntax Tree Interm. Repres.

18 .The Notion of a Type System Type System/Checker Based on: Syntactic Language Construct The Notion of Types Rules for Assigning Types to Language Constructs Strength of Type Checking (Strong vs. Weak) Strong vs. Weak Dynamic vs. Static OOPLS Offer Many Variants All Expression in Language MUST have Associated Type Basic ( int , real, char, etc.) Constructed (from basic and constructed types)

19 .Copyright © 2015 Pearson. All rights reserved. 1- 19 The Concept of Binding A binding is an association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbol Binding time is the time at which a binding takes place.

20 .Copyright © 2015 Pearson. All rights reserved. 1- 20 Possible Binding Times Language design time -- bind operator symbols to operations Language implementation time -- bind floating point type to a representation Compile time -- bind a variable to a type in C or Java Load time -- bind a C or C++ static variable to a memory cell) Runtime -- bind a nonstatic local variable to a memory cell

21 .Copyright © 2015 Pearson. All rights reserved. 1- 21 Type Binding How is a type specified? When does the binding take place? If static, the type may be specified by either an explicit or an implicit declaration

22 .What are Possible Static Binding Problems? Passing Arrays by Value int x [10000]; char c[20]; abc (t: -----) { . . . zzz (t); . . . } xyz (a: -----) { . . . abc (a); . . . } xyz(x); What Happens to Stack During these multiple calls? What’s the Problem Here? What are two Possible Solutions?

23 .Static and Dynamic Binding Dangling References main() { int *p; p = call_it(); } int *call_it () { int i = 23; return &i } Is there a Problem? What is it? How is it Solved?

24 .Copyright © 2015 Pearson. All rights reserved. 1- 24 Explicit/Implicit Declaration An explicit declaration is a program statement used for declaring the types of variables An implicit declaration is a default mechanism for specifying types of variables through default conventions, rather than declaration statements Basic, Perl, Ruby, JavaScript, and PHP provide implicit declarations Advantage: writability (a minor convenience) Disadvantage: reliability (less trouble with Perl)

25 .Explicit/Implicit Declaration (continued) Some languages use type inferencing to determine types of variables (context) C# - a variable can be declared with var and an initial value. The initial value sets the type Visual Basic 9.0+, ML, Haskell, and F# use type inferencing . The context of the appearance of a variable determines its type Copyright © 2015 Pearson. All rights reserved. 1- 25

26 .Copyright © 2015 Pearson. All rights reserved. 1- 26 Two Languages with Implicit Declarations/Bindings: APL and SNOBOL Characterized by dynamic typing and dynamic storage allocation Variables are untyped A variable acquires a type when it is assigned a value Storage is allocated to a variable when it is assigned a value

27 .Copyright © 2015 Pearson. All rights reserved. 1- 27 Dynamic Type Binding Dynamic Type Binding (JavaScript, Python, Ruby, PHP, and C# (limited)) Specified through an assignment statement e.g., JavaScript list = [2, 4.33, 6, 8]; list = 17.3; Advantage: flexibility (generic program units) Disadvantages: High cost (dynamic type checking and interpretation) Type error detection by the compiler is difficult

28 .Fortran Variable TypeBinding A feature of Fortran – implicit typing when a variable appears that has not been declared previously it is created (at compile time) it is assigned a type based on the first character of the name A-H,O-Z is type REAL I-N is type INTEGER a typo can cause the creation of a new variable – not an error Starting with 77 the implicit statement was added allowed changing the first letter assignments most 77 compilers include the implicit none statement that requires that all variables be explicitly typed – prevents the typo problem It is good practice to use implicit none

29 .Copyright © 2015 Pearson. All rights reserved. 1- 29 Variable Attributes (continued) Storage Bindings & Lifetime Allocation - getting a cell from some pool of available cells Deallocation - putting a cell back into the pool The lifetime of a variable is the time during which it is bound to a particular memory cell