COMP 304B Object-Oriented Software Design - Assignment 2
Due date: Monday 15 March 2004 before 23:55

Marc Provost

Practical information

• Team size == 2 (pair design/programming) !
  
  
• Each team submits only one full solution. Use the index.html template provided on the assignments page. Use exactly this format to specify names and IDs of the team members. The other team member must submit a single index.html file containing only the coordinates of both team members. This will allow us to put in grades for both team members in WebCT. Beware: after the submission deadline there is no way of adding the other team member's index.html file and thus no way of entering a grade !
  
  
• Your submission must be in the form of a simple HTML file (index.html) with explicit references to all submitted files as well as inline inclusion of images. See the general assignments page for an index.html template.
  
  
• The submission medium is WebCT.
  
  

Goals

The front-end

Requirements

• Atomic structures (future leaf nodes of the AST):
  • Numbers (e.g., 5, 3.55, 10)
    
    
  • References (e.g., A4, XBZ16, E123). Note how only upper-case column references are allowed.
    
    
  • Range-references (e.g., A1:B10)
    
    
  
  
  
• Composite structures (nodes having children)
  • Addition, subtraction
    
    
  • Multiplication, division
    
    
  • Exponentiation
    
    
  • Function invocations
    
    
  
  
  

• the parser will convert the parse tree to an AST for you. Have a look at parser.g (or the generated Parser.py to see how this is done.
  
  
• the AST will no longer be a binary tree, but will take into account associativity and commutativity of + and × and turn these into their n-ary form. Note that this requires the introduction of invSum and invMul to encode - and / respectively.
  
  

ASTVisitor

• ASTVisitor is an interface.
  
  
• Contains the visit operations for each of the nodes of an AST.
  
  
• Interface:
  • visitNumber(Number)
    
    
  • visitCellRef(CellRef)
    
    
  • visitRangeRef(RangeRef)
    
    
  • visitFunction(Function)
    
    
  
  
  

StrReprVisitor

• A concrete implementation of the ASTVisitor interface.
  
  
• ProducesOperations to be performed on the nodes of an AST.
  
  
• Interface (in addition to the methods in ASTVisitor):
  • setStrRepr(String strRepr="")
    
    
  • getStrRepr():String
    
    
  
  
  

ASTNode

• The ancestor for all concrete AST nodes. Can not be instantiated.
  
  
• Interface:
  • accept(ASTVisitor)
    
    
  • __str__()
    
    
  
  
  
• Comments: concrete ASTNode sub-classes will specify how they are visited and represented as strings.
  __str__() will instantiate a StrReprVisitor and use it to produce the string representation for a formula AST rooted in the current node. This will follow the visitor pattern (see the collaboration diagram section for a more detailed description).
  
  

Number

• Extends ASTNode
  
  
• Attributes:
  • float value (private)
    
    
  
  
  
• Interface:
  • __init__(int | float)
    
    
  • getValue():float
    
    
  
  
  
• Comments: Take int or float as input of the constructor, but store the value as a float internally.
  
  

CellRef

• Extends ASTNode
  
  
• Attributes:
  • int col (private)
    
    
  • int row (private)
    
    
  • bool isAbsCol (private)
    
    
  • bool isAbsRow (private)
    
    
  
  
  
• Interface:
  • __init__(Int,Int,Bool,Bool)
    
    
  • getColumn():int
    
    
  • getRow():int
    
    
  • isAbsColumn():bool
    
    
  • isAbsRow():bool
    
    
  
  
  
• Comments: isAbsRow, isAbsColumn are True if the reference is absolute with respect to row and column, respectively. Note that bool may be implemented as an int. Recent versions of Python have a builtin bool type (enumeration of True and False with boolean operators defined) however.
  The column value must be smaller than 18278 (due to the fact that "ZZZ" converts to 18278, and that we require the maximal lenght of the string denoting the column value to be 3). The row value must be smaller than 10000.
  ValueError (Python built-in exception) should be raised if col or row < 0. The same exception should be raised when col or row exceed the above upper bounds.
  Thanks to the notation used, it is sufficient to check that row and column references are within the allowed range, irrespective of whether the reference is relative or absolute. When later, using the spreadsheet copy operation, relative references will be copied into a different context, it will be necessary to check that they do not point outside the valid range.
  
  

RangeRef

• Extends ASTNode
  
  
• Attributes:
  • CellRef cornerA (private)
    
    
  • CellRef cornerB (private)
    
    
  
  
  
• Interface:
  • __init__(CellRef,CellRef)
    
    
  • getFirstCorner():CellRef
    
    
  • getSecondCorner():CellRef
    
    
  • getCellRefSet():ListOfCellRef
    
    
  
  
  
• Comments: getCellRefSet returns a list of CellRefs. The content of the list is determined by the range cornerA to cornerB. The order in which CellRefs appear is row by row, from top to bottom and within a row, from left to right.
  When later, a formula will be copied, cornerA and cornerB may be changed in case they contain relative references. It is assumed that getCellRefSet is only called when we want to evaluate a formula. At that time, relative and absolute references refer to that same cells. This is why we choose (rather arbitrarily) to return a list of absolute references. For instance, getCellRefSet called on a RangeRef B3:A1 returns [$A$1,$B$1,$A$2,$B$2,$A$3,$B$3]. Called on a RangeRef $B3:$A$1, getCellRefSet still returns [$A$1,$B$1,$A$2,$B$2,$A$3,$B$3].
  The above detailed specification seems unnecessary as whether absolute or relative references are returned seems irrelevant. This may be true during this stage of the design, but it may no longer during a later stage of the design (for example, when the internal representations of cornerA and cornerB are changed. With the current specification, a caller of getCellRefSet knows exactly what to expect.
  
  

Function

• Extends ASTNode
  
  
• Attributes:
  • String name (private)
    
    
  • ListOfASTNode args (private)
    
    
  
  
  
• Interface:
  • __init__(String,ListOfASTNode)
    
    
  • getName():String
    
    
  • getArgs():ListOfASTNode
    
    
  
  
  
• Comments: getArgs returns a copy of the private list args. You should use the shallow copy method from the Python copy module (http://www.python.org/doc/current/lib/module-copy.html).
  
  

The Design

Class Diagram

Collaboration Diagram

Implementation

Requirements common to all classes

• The implementation must follow the requirements exactly (i.e., same class names, method names etc.). The corrector will run his unit tests on your implementation. Two utility functions are provided (in AST.py) to convert an integer to its column string representation and vice versa.
  
  
• Every argument to a function call (including those passed to a class' constructor) must be type-checked. A TypeError (built-in Python) exception must be raised if an argument with the wrong type is passed.
  
  

Interacting with the parser

        Welcome to the formula parser!
        Enter a formula (e.g. =4+5)
        >>> =3+4-5
        parse result: sum(3.0,4.0,invSum(5.0))
        >>> =2*3+4^3+min($A$1:A2)
        parse result: sum(mul(2.0,3.0),exp(4.0,3.0),min($A$1:A2))
        >>> =3+4*2+min(2,3)
        parse result: sum(3.0,mul(4.0,2.0),min(2.0,3.0))
        >>> quit
      

Files

• parser.g (the specification of the formula language)
  
  
• Parser.py (the lexer/parser generated by Yapps from parser.g)
  
  
• ParseNode.py (generated by Yapps, used by Parser.py)
  
  
• yappsrt.py (required by Parser.py)
  
  
• main.py (a small interactive driver for the formula parser)
  
  

• AST.py (the AST classes)
  
  
• ASTVisitor.py (the ASTVisitor interface)
  
  
• StrReprVisitor.py (the StrReprVisitor class)
  
  

Tools