cs164f941CS 164o Please read all instructions (including these) carefully.o Please print your name at the bottom of each page on the exam. io There are seven questions on the exam, each worth between 10 and 20 points. You have I hourand 20 minutes to work on the exam, so you should plan to spend approximately 12 minutes on each question.Midterm Examinationo The exam is closed book, but you may refer to your two sheets of prepared notes.o Please write your answers in the space provided on the exam, and clearly mark your solutions. You may usethe backs of the exam pages as scratch paper. Please do not use any additional scratch paper.o Solutions will be graded on correctness and clarity. There are no "tricky' problems on the exam-eachproblem has a relatively simple and straightforward solution. You may get as few as 0 points for a question ifyour solution is far more complicated than necessary.NAME:SID or SS#:Problem, Max points, Points1 152 153 204 105 206 107 10Fall 94 page 1 of 8CS 164 Handout 11 1. Regular Expressions (15 points) Consider a language where real constants are definedas follows: A real constant contains a decimal point or E notation, or both. For instance, 0.01, 2.71821828,-1.2El2, and 7E-5 are real constants. The symbol '-" denotes unary minus and may appear before the numberor on the exponent. There is no unary '+' operation. There must be at least one digit to left of the decimalcs164f9411point, but there might be no digits to the right of the decimal point. The exponent following the "E" is a(possibly negative) integer. Write a regular expression for such real constants. Use the standard regularexpression notation described by the following grammar: R-->(epsilon|char|R+R|R*|RR|(R) You may definenames for regular expressions you want to use in more than one place (e.g., foo = R). digit =0+1+2+3+4+5+6+7+8+9 posint = digit digit* int = ((epsilon+ -) posint exp = E int frac = .digit* real = (int frac (exp + epsilon)) + (int (frac + epsilon) exp) Fall 94 page 2 of 8CS 164 handout 112. Finite Automata (15 poilats)Consider a DFA with a start state so and a transition function trans. For a state s and input character c, trans(s,c) = s' if there is a transition from state s to state sl on character c. If there is -no transition from s on c thentrans(s, C) = none. The following algorithm simulates the behavior of such a DFA, accepting if the inputstring is accepted by the DFA and rejectingotherwise.state - sowhile there's input left do:char +-- next input characterif trans(state,char) = none then stop and rejectstate <-- trans(state,char)(end of loop)accept if state is a final state, otherwise rejectNow consider an NFA with a start state so and a transition function trans. In this case, for a state s and inputcharacter c (we now allow c = c), trans(s, c) is the set of states s' for which there is a transition from s to s' onc. In the style of the algorithm above, give a (deterministic) algorithm that simulates the behavior of such anNFA. You may use the epsilon-closure operation described in class and in the text.Simulate subset construction.Use state-set instead of state,state-set - c-closure(so)while there's still input left do:char<-- next input characterif esiplon-closure(Union s subset state-set trans(s, char)) = 0 then stop and reject state-set -epsilon-closure(Union s subset state-settxans(s,char))cs164f9412(end of loop)accept if there's a final state in state-set, otherwise reject.Fall 94 page 3 of 8CS 164 Handout 113. Grammars (20 points)Consider the following grammar. The nonterminals are E, T, and L. The terminals are +,id,(,), and ;. The startsymbol is E.E ---> i- E+T|TT ---> id|id()|id(L)L ---> E;L|EGive an LL(l) grammar that generates the same language as this grammar. As part of your work please showthat your grammar is LL(l).(a) Eliminate left recursion:E --->TEE'---> +TE'| epsilonT --->id | id()|id(L)L --->E; L|E(b) Left factor:E --->TE'E'--->+TE'|epsilonT --->id T'T' epsilon|T"T" ---> )| L)L ---> EL'cs164f9413L' ---> ; L|epsilon(c) Check that it's LL(l). For this part you just needed to give enough information to show that there would beno conflicts in the parsing table. The following is sufficient:E --->+TE|epsilon First(+TE) = {+}Follow(E) = {$,),;}T'--->epsilon |(T" First((T")={(}Follow (T)= {+,$,),;}T"--->)|L) First()) ={)}Follow (L))={id}L--->;L|esiplon First(;L) = {;}Follow(L)={)}Fall 94 page 4 of 8CS 164 Handout 114. Parsing (10 points)In both parts of this question, we are looking for clarity and brevity as well as the right idea. Suppose you arewriting a parser for a programming language that includes the following syntax for looping constructs:Loop --> do stmt while expr| do stmt until expr| do stmt forever(a) (5 points) A predictive parser (i.e., a top-down parser with no backtracking) can't use this grammar. Give abrief (a couple of sentences) explanation of this fact.When trying to expand a production for non-terminal "loop I I , the parser cannot decide which of the threeproductions to expand using only the next few input tokens.(b) (5 points) Give a brief explanation of why a bottom-up parser does not have difficulty with this grammar.When a bottom-up parser must decide which of the three productions to choose (reduce), the "while". "until",or "forever" has already been read and shifted onto the stack.cs164f9414Fall 94 page 5 of 8CS 164 Handout 115. Parsing (20 points)Consider the following grammar. The nonterminals are S' and S. The terminals are op and x. The start symbolis S'.S' --> SS --> S OP S|X(a) (15 points) Draw the DFA built from sets of LR(O) items for this grammar. Show thecontents of each state. (Note: Don't augment the grammar with a new start symbol.)(b) (3 points) Is this grammar SLR(l)? Briefly explain why or why not.(c) (2 points) Is this grammar LR(l)? Briefly explain why or why not.Fall 94page 6 of 8CS 164 Handout 116. Bison and Abstract Syntax 'JPrees (10 points)Consider the following constructors for a tree language:Expression app(Expression, Expression); Expression lambda(Expression, Expression); Expression ido;Now consider the following Bison grammar:%token ID LAMBDA%type <Expression> Expr%%Expr : ID{ $$ = id() ; }| '(' LAMBDA ID '.' Expr ')'cs164f9415{$$ = lambda( id(), $5); }| '(' Expr Expr ')'{ $$ = app($2, $3); }Draw the abstract syntax tree that would be produced when parsing the sequence of tokens below. Label aBthe nodes of your AST with the appropriate constructor.(
View Full Document
Unlocking...