CMPS 274 Final, Fall 1996

Math 274 Final Exam AMENEAN PENT LIBRARY OF Betney Fall 1996-97 G. Jalloul IL Describe how lex generates lexical analyzers for regular expressions. Illustrate this on the regular expression a (alb)*. IL. Consider the following grammar Decl ~> Type id, List; List > id, Listle Type ~> integer! real 1. Is the given grammar LL(1)? Prove or disprove. If it is not LL(1) modify it so that it becomes LL(1). 2. Is the given grammar operator precedence? Explain. If it is not suggest modifications that will make it operator precedence. 3. Identify programming language constructs that have been included in grammars as a result of using operator precedence parsing technique. III. Consider the following augmented grammar for a form of relational expressions: Ubune amMAADA and the following subset of the collection of LR(0) items lbh: RO.R lL : goto(h ,<) R > .E<E R > .E>DE Is : goto(], ,>) E > . digit E>.R I, : goto(Ip ,R) Is : goto(l, ,E) ROR. R > E<E. ROR. R DE.<E R DME.>E I, : goto(lb ,E) R DE.<E I, : goto(Is ,E) R XE.<E R DME>E R DE.<E I, : goto(Ip , digit ) R DE.>E E > digit. 1. Find the states I, and I; 2. Find the follow sets of the non terminal symbols of the grammar 3. Is the given grammar SLR? Explain 4. Define the following entries of the SLR parse table to give < a higher precedence than >, make < right associative and > left associative. Explain action (I; , <]_ = action [I; , >] W action [ , <] action [I]; , >] 5. Modify the given set of items to form the canonical collection of LR (1). Is the grammar LR(1) Ih: R>D.R Is: goto(], ,>) R > .E<E R > .E>E E > . digit E>.R I, : goto(Ip ,R) I; : goto(l, ,E) R OR. R > E<E. ROR R DE.<E R DE.>E ary goto (Ip , E) R DE.«<E L goto (I; ,E) R XE.<E R DE>E. R DE.<E I; : goto (Ip , digit ) R DE.>E E > digit. lL, : goto(h ,<) 6. Find the LALR(1) collection of items. Is the grammar LALR 7. What is the advantage of using the LALR parsing technique over the canonical LR , knowing that the LR technique is more powerful. 8. Compare the LL and LR parsing techniques in terms of their parsing approach, ease of implementation and the set of grammars they recognize IV. Consider the following grammar for boolean expressions: E> EandE | EorE | not (E) | true | false 1. Give a syntax directed definition that retums the value of E in the attribute val. Is val a synthesized or inherited attribute? Explain 2. Write a yacc program that will evaluate boolean expressions- generated by the above grammar - - with the following precedence rules: not — highest precedence and is right associative and second precedence and is left associative or least precedence and is left associative What are the steps and corresponding instructions need to produce an executable object code equivalent to a yacc program The case statement of Pascal seems to be a redundant construct since the effect of executing a case statement can be programmed using an if statement. Give a justification for why including the case in the grammar might be beneficial. What is meant by the Front and Back Ends of a compiler? What is meant by a cross compiler? Give an example 4. Assume that you have access to a Pascal compiler, that runs on intel 486 and produces intel 486 code. Explain how you might obtain move your compiler for SPL — without writing one — to an intel 486.