UNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionProf. R. FatemanFall, 2002: Sept 26,2002 3:30PMCS 164 Midterm 1 PRINT YOUR LOGIN CS164-Please read all instructions carefully.There are 7 questions in the exam on 5 pages. Some questions have multiple parts.You have 80 minutes to complete this test. The exam is closed book but you may referto your one page (2-sides) handwritten 8.5 by 11 inch paper.Please write your login name ON EVERY PAGE. Place the answers in the space provided.If you may use the backs of the exam pages for answers, clearly direct the grader to the locationof answers. Solutions will be graded on correctness. Please write neatly. Partial credit willbe given.Your family nameYour first nameYour LOGIN NAME PRINTED IN CAPITAL LETTERS CS164-Underline the name of your Teaching Assistant: Shoaib or RyanThe DAY and TIME YOUR SECTION MEETS:READ AND SIGN THIS:I certify that my answers to this exam are all my own work.Signed:question grade out of1 252 43 54 65 56 107 15total 701CS 164 Midterm 1 PRINT YOUR LOGIN CS164- 21. [25 points] Here is a grammar for a simple language that includes array assignments likeid[id]= int+id. We use the same notation for grammars as in lecture and assignments 3and 4.(defparameterG1’((S -> H $) ;;rule 1(H -> lval = E) ;; 2(E -> id) ;; 3(E -> int) ;; 4(E -> E T) ;; 5(T -> + E) ;; 6(T -> ) ;; 7(lval -> id) ;; 8(lval -> id [ E ] );; 9))a. What is the se t of terminal symbols in G1?b. Is L(G1) finite or infinite? (Explain)c. If x is an id, and 34 is an int, then which of these are sentences in L(G1)? Assumethere is a $ following each string.x[34]=xx= x[34]x[x[34]]x= 34)x=(x[34]+34)x=x+x+xd. Why is this grammar not suitable for LL(1) parsing?e. Compute the nee ded First and Follow sets, and then draw the parsing table below.$ + ] id int [-------------------------------------------------------------------------S-------------------------------------------------------------------------H-------------------------------------------------------------------------E-------------------------------------------------------------------------T-------------------------------------------------------------------------lval-------------------------------------------------------------------------CS 164 Midterm 1 PRINT YOUR LOGIN CS164- 3f. Write out a simple grammar for the same language that IS suitable for LL(1) parsing.We were able to do this by changing 3 rules, adding 2 rules and removing one rule.2. [4 points] Define the following terms in complete English sentences.a. Syntax directed parser generationb. Context Free Grammarc. Nondeterministic Finite Automaton. (Assume DFA is defined)d. Leftmost derivation (Assume derivation is defined)3. [5 points]a. For each of the following languages L1, L2 and L3 write out all strings of length lessthan or equal to 4, starting with the shortest. Let the regular expression A denote the set{a}, and B denote {b}. .L1 = A|B∗contains:L2 = A∗B∗A∗contains:L3 = (A∗B∗)∗+ L1 + L2 contains:b. You are told that for a particular regular expression R that R denotes the same set asthe regular expression RR. What can you say about R?c. An extra edge is added to an NFA recognizing the regular expression Q. The edge is an transition from the (single) accepting or final state to the (single) start state. What regularexpression does the new NFA accept?CS 164 Midterm 1 PRINT YOUR LOGIN CS164- 44. [6 points] Any finite state machine can be encoded in a context free grammar by using acertain pattern of rules, where each rule has a restricted form as in the example below:(defparameterG2’((S -> a X)(X -> b X)(X -> c Y)(Y -> c)))))a. Draw a DFA accepting the same language as G2. Be sure to indicate start and finalstates.b. Give an example of a grammar whose language cannot be recognized by a finite statemachine. Use at most 2 rules.5. [4 points] Here are the rules for a grammar G3 with start symbol SS → aSbS → cComplete writing a recursive descent parsing program parse that returns yes, given alisp list that constitutes a sentence in L(G3). We give you two useful parts already.(defun parse (tokens)(s)(if (empty tokens) "yes"))(defun eat(h) (cond((equal h (car tokens))(pop tokens))(t (error "stuck at ~s" tokens))));; sample test: (parse ’(a c b)) ;; acceptable6. [10 points]Write down the result of running your Tiger lexical analysis program fsl on a file con-taining only this m aterial starting on line 1:abc_def 123 "abd\ \ def" if /* "hello */ ( "world")+2 /*/*/ fooCS 164 Midterm 1 PRINT YOUR LOGIN CS164- 57. [15 points]Here is a s imple grammar which is not LR(0). Prove this to be the case by completingthe LR(0) diagram below, adding items, showing reductions and drawing labelled edgesbetween states. Look carefully at state 3 to see the problem, and explain.(defparameter gram4 ’((S -> E $) ;; rule 1(E -> P x E) ;; 2(E -> P) ;; 3(P -> id) ;; 4)State 1: S -> . E $State 2: S -> E . $State 3: E -> P . x EState 4: E -> P x . EState 5: P -> id .State 6: E -> P x E
View Full Document
Unlocking...