Eric Roberts Handout #44CS 106B May 13, 2009Expression TreesExpression TreesEric RobertsCS 106BMay 13, 2009Outline for TodayReview the structure of expressions1.Discuss how inheritance is represented in C++3.Design the expression hierarchy4.Implement eval for each of the subclasses5.Explore the relationship between parsing and grammars6.Look at the final version of parser.cpp7.Review the idea of inheritance in general2.Play with the BASIC interpreter8.Recursive Structure of Expressions• An arithmetic expression in a programming language is arecursive structure that can be thought of as a tree.• In the simple model I use in Chapter 14, every expression fallsinto one of the following forms:– An integer constant– A variable name that holds an integer value– Two expressions joined by an operator– An expression enclosed in parentheses• This structure can be represented in the form of a grammar.E  constantE  identifierE  E op EE  ( E )Expression Trees• When the C++ compiler looks at an expression, it needs tounderstand what the expression means by translating it into aninternal form. This process generally consists of two steps:– Lexical analysis, in which the line is broken up into units– Parsing, in which the tokens are assembled into a tree thatembodies the expression structureClasses Hierarchies• In any object-oriented language, classes serve as templates forindividual objects. Each object is an instance of a particularclass, which can serve as a pattern for many different objects.• One of the defining characteristics of the object-orientedparadigm is that classes form hierarchies. Any class can bedesignated as a subclass of some other class, which is calledits superclass. As noted on this week’s section handout, mostclass hierarchies are tree-structured even though C++ permitsmore complicated structures.• A class represents a specialization of its superclass. If youcreate an object that is an instance of a class, that object isalso an instance of all other classes in the hierarchy above itin the superclass chain.• When you define a new class in C++, that class automaticallyinherits the behavior of its superclass.Biological Class HierarchyClassification of the red antIridomyrmex purpureusNote that there can be manyindividual red ants, each ofwhich is an instance of thesame basic class.– 2 –Inheritance Hierarchies• Because expressions have more than one form, a C++ classthat represents expressions can be represented most easily by aclass hierarchy in which each of the expression types is aseparate subclass, as shown in the following diagram:• Even though the class hierarchy is organized in terms of thedifferent types of nodes, clients of the expression package willalmost always work with pointers to nodes instead. As I didlast time, I will therefore give the pointer type the nameexpressionT.Representing Inheritance in C++• The first step in creating a C++ subclass is to indicate thesuperclass on the header line, using the following syntax:class subclass: public subclass { body of class definition}• In contrast to Java, a subclass cannot automatically overridethe definition of a method in its superclass. To permit suchoverriding, both classes must mark the prototype for thatmethod with the keyword virtual.•An abstract class is a class that doesn’t actually represent anyobjects but instead serves only as a common superclass forconcrete classes that do generate objects. In C++, methods foran abstract class that are always implemented by the concretesubclasses are indicated by including = 0 before the semicolonon the prototype line./* * File: exp.h * ----------- * This interface defines a class hierarchy for expressions, * which allows the client to represent and manipulate simple * binary expression trees. */#ifndef _exp_h#define _exp_h#include "genlib.h"#include "map.h"/* * Type: expressionT * ----------------- * For clients, the most important type exported by this interface * is the expressionT type, which is defined as a pointer to an * ExpNode object. This is the type used by all other functions * and methods in the expression package. */class ExpNode;typedef ExpNode *expressionT;The exp.h Interface/* * Class: EvalState * ---------------- * This class is passed by reference through the recursive levels * of the evaluator and contains information from the evaluation * environment that the evaluator may need to know. The only * such information implemented here is a symbol table that maps * variable names into their values. */class EvalState {public: EvalState(); ~EvalState(); void setValue(string var, int value); int getValue(string var); bool isDefined(string var);private: Map<int> symbolTable;};The exp.h Interface/* * Class: ExpNode * -------------- * This class is used to represent a node in an expression tree. * ExpNode is an example of an abstract class, which defines the * structure and behavior of a set of classes but has no objects * of its own. Any object must be one of the three concrete * subclasses of ExpNode: * * 1. ConstantNode -- an integer constant * 2. IdentifierNode -- a string representing an identifier * 3. CompoundNode -- two expressions combined by an operator * * The ExpNode class defines the interface common to all ExpNode * objects; each subclass provides its own specific implementation * of the common interface. * * Note on syntax: Each of the virtual methods in the ExpNode class * is marked with the designation = 0 on the prototype line. This * notation is used in C++ to indicate that this method is purely * virtual and will always be supplied by the subclass. */The exp.h Interface/* Enumeration type for the three expression types */enum expTypeT { ConstantType, IdentifierType, CompoundType };/* Interface entry for ExpNode class */class ExpNode {public: ExpNode(); virtual ~ExpNode(); virtual expTypeT type() = 0; virtual int eval(EvalState & state) = 0; virtual string toString() = 0;};The exp.h Interface– 3 –/* * Class: ConstantNode * ------------------- * This subclass represents a constant integer expression. */class ConstantNode: public ExpNode {public: ConstantNode(int val); virtual expTypeT type(); virtual int eval(EvalState & state); virtual string toString();/* * Method: getValue * Usage: value = ((ConstantNode *) exp)->getValue(); * -------------------------------------------------- * This method returns the value