CS241 Study Guide - Final Guide: Parse Tree, Substring, Assembly Language

316 views4 pages

fuchsiahamster182

7 Oct 2015

School

University of Waterloo

Department

Computer Science

Course

CS241

Professor

Gregor Richards

For unlimited access to Study Guides, a Grade+ subscription is required.

Document Summary

Summary: epsilon-nfas, context-free grammars, parsing, error-checking, code generation, optimization, memory management. 1: given the following grammar, s(cid:48) (cid:96) expr (cid:97, expr term, expr expr term, term id, term (expr) Draw a parse tree for each of the following strings. 4. a) (cid:96) id - id - id (cid:97) 4. b) (cid:96) id - (id - id - id) (cid:97: in the above grammar, if rule 2 was changed to expr expr expr, it would be ambiguous. Prove that this is the case - i. e. come up with a string for which there exist multiple parse trees, and show those parse trees. 2 (cid:97) reduce 2 a b a b (cid:97) reduce 3. 4 a shift 5 a b a shift 2 (cid:97) shift 6 a q. 10 (cid:97) shift 11 reduce 4 reduce 4 a a b a (cid:97) shift 9. Each of the following wlp4 programs contains an error.

Related Questions

Part (b) [1 MARK] The list below is shown after each pass of a sorting algorithm. ['M', 'A', 'D', 'E', 'B', 'F', 'C'] # initial list | Which sorting algorithm is being executed? (circle one) (a) bubble sort ('A', 'M', 'D', 'E', 'B', 'F', 'C'] # after one pass ('A', 'B', 'D', 'E', 'M', 'F', 'C'] # after two ['A', 'B', 'C', 'E', 'M', 'F', 'D'] # after three ('A', 'B', 'C', 'D', 'M', 'F', 'E'] # after four ('A', 'B', 'C', 'D', 'E', 'F', 'M'] # after five (b) selection sort (c) insertion sort

Part (a) [1 MARK] The list below is shown after each pass of a sorting algorithm. ['M', 'A', 'D', 'E', 'B', 'F', 'C'] # initial list Which sorting algorithm is being executed? (circle one) (a) bubble sort ['A', 'D', 'E', 'B', 'F', 'C', 'M'] # after one pass ['A', 'D', 'B', 'E', 'C', 'F', 'M'] # after two ['A', 'B', 'D', 'C', 'E', 'F', 'M'] # after three ['A', 'B', 'C', 'D', 'E', 'F', 'M'] # after four (b) selection sort (c) insertion sort

Part (b) [3 MARKS] Complete the function body according to its docstring description. You will be marked only on the parts that need to be different from (a). def count_letter_case_mutate (L): " (list of list of str) -> None Type Precondition: each str in L is non-empty and contains only alphabetic characters Replace each item in L with a two-item tuple in which the first item is the number of words in the list at the corresponding index of L that start with a lowercase letter and the second item is the number of words in the list at the corresponding index of L that start with an uppercase letter >>> data = [['apple', 'Banana'], ['PeAr'], [], ['PEACH', 'aprICot', 'plum']] >>> count_letter_case_mutate (data) >>> data [(1, 1), (0, 1), (0, 0), (2, 1)]

CS241 Study Guide - Final Guide: Parse Tree, Substring, Assembly Language

Document Summary

Get access

Related Documents

CS241 Lecture Notes - Lecture 1: A.Out, Valgrind

CS241 Study Guide - Regular Expression, Substring, Fxx

BIOCHM 383 Lecture 40: Protein Kinase A Activation Signal-Transduction Pathway, Heterotrimeric G Protein, Adenylate Cyclase Activation & Complex Structure, Formation of cAMP & Reaction Structures, Regulation of Protein Kinase A

Related Questions