CMSI 488 - Compiler Construction Quiz 1 Answers ================================ PROBLEM 1 --------Is it possible for the assignment statement x.x = x; to ever legally appear in a Carlos program? If it can, state what it means, semantically. If not, state why it is impossible (technically), hinting at either (1) why allowing it would be stupid (inconsistent with the language design), or (2) the inexplicable oversight or stupidity of the language designer for leaving it out. Answer: It's legal. It makes a field of an object reference the object itself, as in this Carlos program: struct s {s x;} s x; x.x = x;
// This is a TYPE DECLARATION in Carlos // This declares x to be a variable of type s // x.x is also a variable of type s
PROBLEM 2 --------For each of the following Carlos fragments, tell whether it is a lexical error, syntax error, static semantic error, dynamic semantic error, or no error. a) b) c) d) e) f)
int x; int x; int f(int x) {int x = x;} char* `ohana = "family"; string pet = "dog"; pet = "rat"; string pet = "cat"; pet[0] = 'r'; int f(int x) {} int g() {f(1,2,3,4);}
Answer: a) static semantic. b) static semantic (but note this is NOT AN ERROR in C!) c) lexical ("`" is not an allowable character). There is also no char*, so syntax is also a possible answer. d) no error e) static semantic - strings are immutable in Carlos f) static semantic (too many arguments to f) PROBLEM 3 --------Sketch the AST for the Java fragment: void q(String... v) { for (int y : f(x)) { x = p.data[0] * (2< } } Answer:
5|-x
*1);
method / / | \ void q param block / \ | ... v for | // \ \ String __/ | \ \____ / / \ \ int y call = / \ / \ f x x * / \ [] | / | / \ . 0 < * / \ / \ / \ p data 2 5 - 1 | x PROBLEM 4 --------Consider a language for describing turtle graphics. An example program in this language is: deg color 1 0 0 left 90 forward 4 color 0 0 1 [ left 90 forward 1.5 ] right 90 forward 1.5 This program draws the letter T with a red vertical line of size 4 units and topped with a 3 unit blue line. A program is a sequence of instructions. The instructions are: deg - switch to degree mode rad - switch to radians mode left a - turn left by angle a right a - turn right by angle a forward n - draw a line by moving forward n units. backward n - draw a line by moving backward n units. color r g b - set color (r,g,b), values are floats in the range 0 to 1. [ - save current state ] - restore previously saved state Write a macrosyntax in EBNF for this language. Handle the brackets reasonably, please. State whether your grammar is LL(1) (meaning "can be parsed top-down with only one lookahead symbol) or not, and whether it is ambiguous or not. Answer: PROGRAM -> INST+ INST -> deg | rad | left NUM | right NUM | forward NUM | backward NUM | color NUM NUM NUM | "[" INST+ "]" Note that NUM is a primitive token, and note that the value constraint on color arguments is not specified in the syntax; we're leaving that to the static semantic description. The grammar is LL(1) and non-ambiguous.
PROBLEM 5 --------Write a regular expression for the language of "positive hexadecimal numerals divisible by 256". Is it possible to implement a parser for this language in JavaCC using only numeric lookahead values? If so, what is the find the smallest lookahead value you would need? Answer: Well the adjective "positive" had connotations of twos-complement representation I didn't intend. I only meant positive as in "no leading minus sign" and "greater than zero". I should have left it out. Anyway, the regex is: 0*[1-9A-Fa-f][0-9A-Fa-f]*00 That's not LL(1), it's LL(3). You have to lookahead 3 symbols to know whether to take the final two zeros of the right alternative (the third symbol is <EOF>). I think 3 is the minimum we can get. PROBLEM 6 --------Is this grammar an LL grammar? A -> B C B -> a | b?c? C -> c | BA If you find that this grammar is not LL, make one that is (that defines the same language of course). Answer: It's not LL(k) for any k.
You can have a derivation like this:
A => BC => C => BA => A => ... so there's left recursion. do anything useful.
You can expand like that forever until you
Finding an equivalent grammar is easy, since the language being described is all strings ending with a c. So: A -> (a|b|c)*c PROBLEM 7 --------EBNF generally uses * * * *
A B to mean exactly one A followed by exactly one B A? to mean zero or one A A* to mean zero or more As A | B to mean either exactly one A OR exactly one B
Suppose I wanted to add a new one: *
A1 # A2 # ... # An to mean "a non-empty string in which each of the Ais
occurs zero or one times." Show how to write A # B # C using only the conventional EBNF markup. Answer: A(B?C?|C?B?) | B(A?C?|C?A?) | C(A?B?|B?A?)