CS241 Lecture Notes - Lecture 5: Donald Knuth, Context-Free Grammar, Parse Tree
23 Sep 2015
School
Department
Course
Professor
Document Summary
Additional material by: adriel dean-hall and brad lushman. This handout is intended to accompany the class lectures on bottom. The handout should not be considered a substitute for the lecture. Dissemination of this handout (including posting on a website) is explicitly prohibited unless permission is obtained. We want to state from the input string w and create a reverse derivation to the start symbol s w k k 1 1 s. Shift: consume the next input symbol by pushing it on the stack. Reduce: pop the rhs of a chosen rule o the stack and push its lhs. Input w is: (cid:96) a b y w x (cid:97) At each step in the algorithm there are two choices: shift a character from input to the stack, reduce: take the rhs of some rule o the stack and push the lhs on the stack. The accepting condition is reached when stack contains s" and remaining input is .
