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: + a list is empty: [] + a list has a head and tail [H|T], where tail is a list Base cases: + usually empty list, 1-elem list Recursive step: + break into sublists + send tail back as "the new list" and recurse with that Interim examples: ListAdd, MyVector.... ------------------------------------------------------------------------------- 3) Better Ideas for Singly-linked Lists? (see DS&A in Chap 4) public class ThingList { private Thing head; private Thing tail; // getters and setters } public class Thing { private Thing next; private Data data; // getters and setters } ------------------------------------------------------------------------------- 4) Parsing Motivation: + want to be able to analyze a body of text (CORPUS) (decryption, grammar checking, data mining, spying, compiling, etc...) + need to "break apart" (PARSE) a corpus and look/translate/something at/to each piece Language? + HUMAN: alphabet -> words & punctuation -> sentences -> paragraphs... + COMPUTER: characters-> tokens & separators -> statements -> modules... Study of languages? + syntax (structure, grammar) + semantics (meaning) 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 RECURSIVELY DEFINED SET + what? - a statement is defined in terms of itself - the statement "ends" when reaching the base case - other term is NESTED EXPRESSION Better notation: E -> integer E -> (E + E) Legal Examples: 2, (1 + 2), (1 + (2 + 3)) <---- note: must give ()s Illegal Examples: (2 (2) 1+2 How to have a computer do the checking for legality and/or evaluation? ------------------------------------------------------------------------------- 6) Program Development for Case Study in (5) Black box model: I --> BB --> O 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: ( <--------- op 1 <--------- int + <--------- op -1 <--------- int Borknagar: <--- word Constructors inside CS211In? public CS211In (String FileName) // give text filename for input public CS211In (Reader r) // define custom input source public CS211In () // use default for command-line input 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) // give text filename for output public CS211Out () // send output to command window ------------------------------------------------------------------------------- 8) A Bit More Help: Boolean Operators E1 & E2 + evaluate *BOTH* E1 *AND* E2 + if E1 is false, Java *still* evaluates E2 + "&" is called BOOLEAN AND (see Java In A Nutshell) E1 && E2 + evaluate E1 + if E1 is false, the whole expression is false, so do *NOT* evaluate E2 + if E1 is true, then *do* evaluate E2 + "&&" is called CONDITIONAL 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 -------------------------------------------------------------------------------