Unformatted text preview:

CS 536Midterm Exam1. (25 points) Let AllButFirst be the operator that systematically removes the first character from a set of non- null strings. ...2. (25 points)3. (a) (10 points)4. (25 points) Recall that in building parsers, the first relation is key in making parsing decisions. Define InFirst(A,a), wher...5. (25 points)6. Consider the following three context-free grammars. Which are LL(1)? Why? Which are LALR(1)? Why?CS 536Midterm ExamWednesday, April 2, 200812:30 — 2:20 PM1325 CSSTInstructionsAnswer any four questions. (If you answer more, only the first four will count.) Point values are as indicated. Please try to make your answers neat and coherent. Remember, if we can’t read it, it’s wrong. Partial credit will be given, so try to put something down for each question (a blank answer always gets 0 points!).1. (25 points) Let AllButFirst be the operator that systematically removes the first character from a set of non-null strings. For example, AllButFirst ({abc,xy,a,b,bb}) = {bc,y, λ,b}. Let R be any regular expression that does not generate λ. Show that AllButFirst(R) is a regular set.2. (25 points)Let Double be the set of strings defined as {s|s=ww}. Double contains only strings composed of two identical repeated pieces. For example, if we use a vocabulary consisting of the let-ters a and b, the following strings (and many more!) are in Double: aa, bb abab abbabb, aaaabaaaab.Is Double a regular set? Why? 3. (a) (10 points)Let FA be any finite automaton (my choice). Explain how to decide whether all the strings FAaccepts are exactly two characters in length.(b) (15 points)Let S1 and S2 be sets of strings. Define S1 - S2 to be the set of all strings in S1 that aren’t also in S2. Assume R1 and R2 are regular sets. Show that R1 - R2 is also a regular set.4. (25 points) Recall that in building parsers, the first relation is key in making parsing decisions. Define InFirst(A,a), where A is a nonterminal and a is a terminal, to be true if it is the case that A ⇒+ a…. (and false otherwise) That is, InFirst(A,a) tells us if a string of symbols beginning with the terminal symbol a may be derived from A. Give an algorithm that computes InFirst(A,a) given a grammar G.-2-5. (25 points)Assume we add a simple parameterless macro facility to CSX. The command #define ident string (in the file being scanned) will define identifier ident to be an abbreviation for string, an ordinary CSX quoted string. Whenever ident is scanned (as an identifier) after the #define, it will be replaced with the text of string. This text (with enclosing quotes removed and escaped characters expanded), is immediately scanned. string may contain macro calls. For example, we might use the following to abbreviate calls to println in Java:#define pr "system.out.println" Assume your scanner calls a subroutine getNextChar( ) whenever it wants the next character to be scanned. You may modify getNextChar( ) in any way you wish. Outline how you’d add this macro facility to your CSX scanner.6. Consider the following three context-free grammars. Which are LL(1)? Why? Which are LALR(1)? Why?(i) (8 points)S → A S S → b A → a A →λ (ii) (8 points)S → ( S ) S → [ S ] S → [ S ) S → a (iii) (9 points)S → D P a D → b D →λ P → c P


View Full Document

UW-Madison CS 536 - midterm.s08

Download midterm.s08
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view midterm.s08 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view midterm.s08 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?