>HW1 -- Due 4/21/98 in class. > >1) Evaluate your favorite language based on the criteria given in (15 points) >class. Answers may vary. See criteria listed in class notes. >2) Grammar : (18 points) > > -> := > -> A | B | C > -> + > | * > | () > | >Given the above grammar, show a parse tree and leftmost derivation for >each of the following statements: [TA's comment] Some of you omitted some nodes (especially parenthesis) in the parse tree, and omitted some steps in derivation (expanding while deriving ). It is illegal to do this. Some used the notion and so on, that's the notion for compiler. Here, we only consider the given grammar. Nothing about compilation is involved. Also worth noting is that parse tree is different from derivation. A proof might be that some of you can do parse tree correctly but derivations are wrong, and some did vice versa. >a) A := A * (B + (C * A)) / | \ := / / | \ A * / / | \ A ( ) / | \ + / / | \ B ( ) / | \ + / / C | A => := => A := => A := * => A := A * => A := A * () => A := A * ( + ) => A := A * (B + ) => A := A * (B + ()) => A := A * (B + ) => A := A * (B + ( * )) => A := A * (B + (C * )) => A := A * (B + (C * )) => A := A * (B + (C * A)) >b) B := C * (A * C + B) [TA's comment] The grammar given is a little contraintuitive. So some of you followed their intuition to group A*C together. But the derivation might follow the grammar. You should adhere to the grammar. / | \ := / / | \ B * / / | \ C ( ) / | \ * / / | \ A + / | C | B => := => B := => B := * => B := C * => B := C * () => B := C * ( * => B := C * (A * ) => B := C * (A * + ) => B := C * (A * C + ) => B := C * (A * C + ) => B := C * (A * C + B) >c) A := A * (B + (C)) / | \ := / / | \ A * / / | \ A ( ) / | \ + / / | \ B ( ) | | C => := => A := => A := * => A := A * => A := A * () => A := A * ( + ) => A := A * (B + ) => A := A * (B + ()) => A := A * (B + ()) => A := A * (B + (C)) >3) Give an unambiguous grammar that generates the same language as: (15 points) > > S -> SS | (S) | () One rule only: S -> ()S | (S)S | () | (S) or S -> S() | S(S) | () | (S) Two rules: S -> TS|T T -> ()|(S) or S -> ST|T T -> ()|(S) [TA's comment] Actually, there are infinitely many solutions, but I think only these listed can be obtained without much difficulty and with simplicity. The idea of doing this conversion is to commit the grammar to a specific parsing way, for example, always expanding the leftmost non-terminal first, which leads to the first solution. One way of doing this is to draw an imcomplete parse tree of 2-3 levels, and collect the current "leaf" nodes, (a handle, in terminology of parsing, I think). Some also used two rules, but with T -> ()|(T) This is not right because it cannot parse (()()). Some used S -> S() | (S)S | () | (S) This is wrong because (())()() is still ambiguous. Certainly there is a mirrored case. >4) Give regular expressions for: (16 points) > >a) Binary strings ending in 01 (0 | 1)* (01) >b) Decimal integers divisible by 5 ((1-9) (0-9)* (0|5)) | 5 | 0 [TA's comment] Integers cannot start with 0's. >c) C identifiers ( _ | (a-z) | (A-Z)) ((0-9) | (a-z) | (A-Z) | _)* [TA's comment] '_' can start an identifier. Specifically, you can have '_' as an identifier. >d) Binary strings consisting of either an odd number of 1's or an odd >number of 0's (1)* (0) (1)* ((0 1* 0 1*)* ) (1)* // odd zeros | or (0)* (1) (0)* ((1 0* 1 0*)* ) (0)* // odd ones >5) Given the following virtual machine (18 points) > > ident := var > ident := ident + 1 > ident := ident - 1 > goto label > if var relop var goto label > > where relop = { = , <>, >, <, >=, <= }, > >give the operational semantic definition of the following: > >a) Pascal repeat Consider the following code segment: repeat ... until a > b; Then the operational semantic equivalent would be: START_LABEL: a := a + 1 if a <= b goto START_LABEL >b) Pascal for-downto Consider the following code segment: for a := 10 downto 1 do ... loop Then the operational semantic equivalent would be: a := 10 START_LABEL: if a = 1 goto FINISH_LABEL a := a - 1 goto START_LABEL FINISH_LABEL: >c) FORTRAN DO of the form: DO LABEL K = start, end, step Consider the following code segment: DO 10 K = 1, 2, 1: ... 10 CONTINUE Then the operational semantic equivalent would be: K := 1 BEGIN_LOOP: if K = 2 goto END_LOOP: ... K := K + 1 goto BEGIN_LOOP END_LOOP: >d) Pascal if-then-else Consider the following code segment: if a > b then a := b else b := a; Then the operational semantic equivalent would be: if b <= a goto ELSE_LABEL a := b goto END_LABEL ELSE_LABEL: b := a END_LABEL: >e) C for Consider the following code segment: for (i=0; i < 20; i++) { ... } Then the operational semantic equivalent would be: i := 0 START_LABEL: if i >= 20 goto END_LABEL i := i + 1 goto START_LABEL: END_LABEL: >d) C switch Consider the following code segment: switch(a) { 5 : ...; break; 6 : 7 : ...; break; default : break; } Then the operational semantic equivalent would be: if a = 5 goto LABEL_5 if a = 6 goto LABEL_6 if a = 7 goto LABEL_7 goto END_LABEL LABEL_5: ... goto END_LABEL LABEL_6: LABEL_7: ... goto END_LABEL END_LABEL: >6) Compute the weakest precondition for each of the following (16 points) >assignment statements and postconditions > >a) a := 2 * (b -1) - 1 {a > 0} b > 1.5 >b) b := (c + 10) / 3 {b > 6} c > 8 >c) a := a + 2 * b - 1 {a > 1} b > (2 - a) / 2 >d) x := 2 * y + x - 1 {x > 11} y > (12 - x) / 2