CS211 Spring 2002 Lecture 6: Recursion 2/6/2003 ------------------------------------------------------------------------------- 0) Announcements: + Just added? See http://www.cs.cornell.edu/courses/cs211/2003sp/ Read syllabus! Do everything in "What To Do First"!!! + signup list for extra help (someone pls remind me) + reading: DS&SD: 2.12, Chap 3, 13.1-13.4; DS&A: Chap 9 Topics: finish up recursion today, do more w/Trees on Tues, then start inheritance on Thurs Objectives/Topics of Lecture 6: + continuing lists: iteration and recursion + another application of recursion: expression parsing (DS&SD: 13.5.2) ------------------------------------------------------------------------------- 1) Fibonacci Numbers http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html ------------------------------------------------------------------------------- 2) Recursive definition of a list: Base cases: Recursive step: Interim examples: ListAdd, MyVector.... ------------------------------------------------------------------------------- 3) Better Ideas for Singly-linked Lists? (see DS&A in Chap 4) ------------------------------------------------------------------------------- 4) Parsing Motivation: + want to be able to analyze a body of text (________________) (decryption, grammar checking, data mining, spying, compiling, etc...) + need to "break apart" (________) a corpus and look/translate/something at/to each piece Language? + HUMAN: + COMPUTER: Study of languages? GRAMMAR: set of rules for generating sentences ------------------------------------------------------------------------------- 5) Simple Case Study of Parsing A grammar for simple addition of integers (integer expressions) + every int is an expr (E) + if E1 and E2 are expr, so is (E1 + E2) How to make methematical? + the set of all legal sentences in this grammar is a _______________________________ + what? - a statement is defined in terms of itself - the statement "ends" when reaching the base case - other term is _________________________ Better notation: Legal Examples: Illegal Examples: How to have a computer do the checking for legality and/or evaluation? ------------------------------------------------------------------------------- 6) Program Development for Case Study in (5) Black box model: Input contains expressions + could be 1 line or more (will deal with just 1 for now) + could be command-line or file input or GUI or printer... Output depends on need + target: command window or file or GUI or printer.... + type: legality? evaluation? both? more? Structure: + classes for I/O + class for expression parsing ------------------------------------------------------------------------------- 7) CS211In CS211In implements CS211InInterface + CS211In must give bodies to all functions in CS211InInterface + "gains" (inherits) constants in CS211InInterface CS211InInterface.java has constants to give integer "types" to tokens: int INTEGER = -1, WORD = -2, OPERATOR = -3, EOF = -4; + We will be processing tokens! That means looking at them, reading them, checking them, and sometimes putting them back. + To do so, CS211InInterface.java defines these methods: int peekAtKind(); // returns "type" (int!) of token w/o "eating" it int getInt(); // reads an int and returns it ; else complains String getWord(); // reads a word and returns it ; else complains char getOp(); // reads an op and returns it ; else complains void match(char c); // verify that the next thing is c void match(String s); // verify that the next thing is s boolean check(char c); // is the next thing c? boolean check(String s); // is the next thing s? void pushBack(); // back up by one token int lineNo(); // where are we? void close(); // close file/input stream How does CS211In "see" tokens? + CS211In tokens: int, words (include colons), operators, EOF (end-of+file) + whitespace is "eaten up" ex) (1 + -1 Borkanagar: ( <--------- 1 <--------- + <--------- -1 <--------- Borknagar: <--- Constructors inside CS211In? public CS211In (String FileName) // public CS211In (Reader r) // public CS211In () // More? + see Common Notes for Section 3 + advice? ------------------------------------------------------------------------------- 7) CS211Out Essentially a "wrapper class" for System.out... Cool thing: allows you to send output to a file See CS211OutInterface for methods and descriptions Constructors in CS211Out? public CS211Out (String FileName) // public CS211Out () // ------------------------------------------------------------------------------- 8) A Bit More Help: Boolean Operators E1 & E2 + evaluate _______________________________ + if E1 is false, Java *still* evaluates E2 + "&" is called _____________ AND (see Java In A Nutshell) E1 && E2 + evaluate E1 + if E1 is false, + if E1 is true, + "&&" is called ______________ AND (see Java In A Nutshell) We will use && example) if source.check('(') fails (start of an expr) then we don't continue analyzing the expression ------------------------------------------------------------------------------- 9) The Program -------------------------------------------------------------------------------