Static Semantics RulesVarious RestrictionsScope rulesTypesThe Standard PreludeOutput and TestingWhat to turn inWhat We SupplyAssorted AdviceUNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionCS 164 P. N. HilfingerSpring 2005Project #2: Static Analyzer for Pyth∗Due: Wednesday, 6 April 2 005The second project picks up where the last left off. Beginning with the AST we pro-duced in Project #1, you are to perform a number of static checks on its correctness, and“decorate” it with information about the meanings of identifiers.When the directory ~cs164/hw/proj2 becomes readable, you can copy the files wehave placed there to help with this project. We will a lso update the pyc.ast package (andits C++ counterpart) to give you places to “hang” decorations on the tree. Specifically,you will be able to connect every variable to a definition that contains (among otherinformation) what you know about its type.1 Static Semantics RulesThe semantics of Pyth are largely those of Python, but with some significant changes thatmake a certain amount of static checking po ssible. Assume the rules of Python, therefore,except as otherwise indicated. Since this is the first offering of the project, a nd we mayyet make clarifications and simplify things to avoid problems we discover, you should besure to check the entry for this project on the homework page for updates (and watch thenewsgroup, of course).1.1 Various RestrictionsThe context-free grammar from Project #1 allows certain things that Pyth disallows. Someof these could be enforced in the grammar, but weren’t for convenience. In any case, theymust be enforced in the static semantic analyzer.∗Updated 5 April 2005. Corrections shown in red.1Project #2 21. Class definitions may appear only at the outer level—that is, a program is a sequenceof classdefs and other statements, none of which may contain a classdef nested withinit.2. A break or continue statement may occur only in a loop (for or while).3. A return statement may only occur in a def.4. An identifier, C, that refers to a class (in the scope of a a class definition) may beused only in the following ways:a. In the inheritance clause of another class definition;b. On the left of an attribute reference: C.x;c. As the function name in a call (i.e., in an object creation): C(). In this version,we deal only with parameterless constructors.d. As a type name in a type assertion.Thus, constructs like x = C, f (C), or if C are all illegal.5. An inheritance clause in a class must reference a class defined previously in theprogram. There may not be a circular chain of inheritance: a class may not inheritdirectly or indirectly from itself.1.2 Scope rulesIn Pyth, the declarative regions (called namespaces in Python documentation) are as fol-lows:• The global region, consisting of the source file that is input to the compiler and thebuilt-in definitions or standard prelude (in Python, these a r e two nested regions);• A class region for each class definition;• A local regi on including the parameters and body of each function or method defini-tion (def) and each lambda.Local regions nest inside each o t her and inside the global region. Class regions nest in theglobal region.The scope of a def is the entire declarative region in which it occurs, except wherehidden in a nested scope. Likewise, the scope of a class definition is the entire globalregion. A name defined by def or class may not be redefined in the same declarativeregion. Since a n assignment in Pyth, as in Python, causes a declaration, this means thefollowing are illegal:Project #2 3f = 3def f (x): ... # Illegal redefinition.def f (y): ... # Another illegal redefinitionclass f: ... # And still anotherThe scope of a parameter is the entire lambda or function definition in which it occurs,except where hidden by inner declarations of the same name.If there is an assignment or augmented assignment to a variable in a declarative region,or if it is implicitly assigned by being used as a control variable in a for statement, thenthere is (one) implicit definition o f that variable in the innermost region containing theassignment, unless there is a global declaration of that variable in the region. The scopeof such an implicit definition is the entire innermost region containing it (before and afterthe assignment), except where hidden by inner declarations, as usual. There is at most oneimplicit definition of a variable generated by this rule; multiple assignments have the sameeffect as one. If there is a global definition of a name in a certain region, then all uses ofthat name in the region (again, except where hidden) refer t o the definition of the namein the global region. A name defined as global must also be defined by def or (implicitly)by assignment in the global region. Thus, the following program is illegal:def f ():global a # Illegal: no assignment to a in the global regiona = 3# a = 0 # Program WOULD be legal if this statement were uncommented.f ()print a # Illegal: a is not defined.The following are illegal:class foo:global a # Illegal: no assignment or def a in the global regionglobal bdef b (): ... # Illegal: b already declared as global.def b (): ...# def a (): ... # global a WOULD be legal if this were uncommentedThe nesting rules already given imply that if a name is not assigned to or defed in somefunction body o r lambda, then any use o f it in that body refers to a def, or to an implicitdefinition caused by an assignment, in some surrounding region; there must be one for theprogram to be legal.A variable is implicitly defined by the presence of an assignment statement even if,during execution, that assignment never happens. Thus, the following is a statically legalprogram that may cause a runtime error when executed (if a is used but never initialized)Project #2 4def f (x):if x > 3:a = "Answer is %d" % xprint aIn other words, your static analyzer never considers whether a variable will be initialized(assigned to) before it is used when a program is run.When the innermost declarative region surrounding an assignment is a class definition,the assigned-to variable is an instance variable of the class. The class also inherits allinstance varia bles of its parent (if any). An assignment to an instance variable of theparent does not create a second instance variable of the same name; it refers to the parent’svariable. These are the only legal instance
View Full Document
Unlocking...