=========================preview======================
(COMP231)midterm98S_sol.pdf
Back to COMP231 Login to download
======================================================
Midterm Solutions
COMP 251 - Section 1
28 March, 1998


1.


(a): Give the definition of a context free grammar. Answer: See page 36 of the Sethi book.
(b): Give an unambiguous context free grammar using BNF for each of the following languages over the alphabet {A, B}

1.
All strings beginning and ending with A. One Possible Answer: <start1> ::= A | A <letters> A <letters> ::= <empty> | A <letters> | B <letters>


2.
All strings without two consecutive A's. One Possible Answer: <start2> ::= A <more> | <more> <more> ::= <empty> | B <more> | B A <more>


3.
All strings not containing the substring AB. One Possible Answer: <start3> ::= <first> <second> <first> ::= <empty> | B <first> <second> ::= <empty> | A <second>



2.
Consider the following context free grammar: <bexpr> ::= <bexpr> orelse <bterm> | <bterm> <bterm> ::= <bterm> andalso <bfactor> | <bfactor> <bfactor> ::= not <bterm> | ( <bexpr> ) | true | false

(a): Draw a parse tree for the boolean expression: true andalso false orelse not true Draw the parse tree.
(b): Is the given grammar ambiguous? If so, please find an example and support your arguments with parse trees.
Yes, the grammar is ambiguous. Try not true andalso false, which has two different parse trees.
(c): Extend the given grammar using BNF to support comparison of integer values and variables. For example,
5 > 6 A = 4
The new BNF grammar should be unambiguous, and should support the three comparison operators <, >, and =, which have higher precedence than the boolean operators not, andalso, and orelse. You may assume the existence of the non-terminal <intexpr> for integer expressions and need not write production rules for it.
Add these productions, replacing the given <bfactor> one: <bfactor> ::= not <bfactor> | ( <bexpr> ) | <cexpr> | true | false <cexpr> ::= <intexpr> '<' <intexpr> | <intexpr> '>' <intexpr> | <intexpr> = <intexpr>

3.
Consider the following class definitions, object declarations and main function: Here is sample code, which you can compile and run to get these answers.

(a): What is the value of B1.total after the execution of statement a?
10
(b): What is the value of D2.total after the execution of statement b?
20
(c): What is the value of pb->total after the execution of statement c?
10
(d): What is the value of pb->total after the execution of statement d?
10
(e): What is the value of pb->total after the execution of statement e?
30

4.
Consider the following class definitions: Here is sample code for this question (and the next).

(a): Draw a class hierarchy showing the inheritance relationships between the four classes.
A - B - C - D
(b): For each class, list the member functions that are accessible inside the class (i.e. in the bodies of other member function of that class).
A: p1(), p2(), p3() B: p2(), p3(), p4() C: p2(), p3(), p5() D: p5()
(c): For each