CS 143 Midterm: CS143 Midterm Spring 2015 Solutions
9 Jan 2019
School
Department
Course
Professor
Document Summary
2. (5 points) draw a line through each useless production in the following grammar (hint: Note: useless has a speci c mathematical de nition that was presented in the lecture and notes. Compute the fne, follow, and first sets for the nonterminals of the context-free grammar below, and write them in the spaces provided. Is the grammar ll(1) [answer without building the ll(1) parse table]? (explain brie y below) Answer: consider the parse tree for the single string a . We don"t know if the rst or second a should expand to the "a", so the grammar is ambiguous. Note: many students claimed that because the grammar is regular that it was ll(1). For any regular language there exists a grammar that is ll(1), but that doesn"t mean that every grammar for that language is ll(1). 4. (10 points) left factor and eliminate immediate left recursion in the following cfg:
