=========================preview======================
(COMP251)[2010](f)final~441^_10021.pdf
Back to COMP251 Login to download
======================================================
COMP 251 2010 Fall Semester Final Exam

Date: Saturday, Dec 18, 2010
Time: 4:30C7:00pm (2.5 hours)
Instructions: (a) This exam consists of 6 questions on 11 pages. The total mark is 100.

(b)
Attempt ALL questions using pen. NO pencil please.

(c)
Write ALL answers in the space provided on the exam paper.

(d)
The last 3 blank pages may be used for rough work or as extra space for your answer. For the latter use, you MUST put your ID number at the space provided otherwise the page will NOT be graded.

(e)
Unless otherwise stated, for any questions that require writing a Prolog, SML, .ex, or bison program, you may use any library function of the language, or write additional helper functions. However, your program must be complete in the sense that it can be run in the interpreter/tool in our lab. Thus, if you want to use any special library function, make sure you also open/load/include the library in your code to show which library you are using.


Name
Student ID
Lab Section

For T.A. Use Only

Question Score
1 / 22
2 / 16
3 / 16
4 / 10
5 / 22
6 / 14
Total / 100

<Expr> ::= <Expr> <Op> <Term> | <Term>
<Term> ::= (<Expr>) | <Vid>
<Op> ::= + | -<Vid> ::= x | y | z

(a) [8 points] Based on the given grammar, draw the parse tree for the following expression:
x -y + (z -x) .
Answer:
< Expr> >
/|\
/|\
/|\
/|\
/|\
/|\
<Expr> <Op> <Term>

/|\| | /|\| |
<Expr> <Op> <Term> + ( <Expr> ) | || /|\ | || /|\
<Term> -<Vid> <Expr> <Op> <Term> | | ||| | | ||| <Vid> y <Term> -<Vid> | || | || x <Vid> x
| | z
Marking Scheme:
C
3 points for getting the sub-expression x -y

C
3 points for getting the sub-expression (z -x)

C
2 more points for getting the whole expression correct


(b) [14 points] Rewrite the above grammar to support the following two additional constructs. The result should still be an unambiguous CFG.
i. the exponentiation operator ^. The operator has higher precedence than + and -, and is right-associative. For example, the following is a valid expression with the exponentiation operator:
y^z^(x-z+y) -x .
ii. the function call. A function call consists of a function identi.er followed by a tuple of any number of arguments enclosed within a pair of brackets ( and ), and separated by commas ,. Each argument is an expression that can be generated by the nonterminal <Expr> in your .nal grammar. Moreover, a function identi.er can only be, f, g, and h, and a function may have no arguments (in which case, the bracket is still required). For example, the following is a valid expression with a function call:
x + y^f(y, h(z), x^(y+z)) .
Answer:
<Expr> ::= <Expr> + <Term> | <Expr> -<Term> | <Term>
<Term> ::= <Factor> ^ <Term> | <Factor>
<Factor> ::= (<Expr>) | <Vid> | <Fid> <Tuple>
<Tuple> ::= () | (<Args>)
<Args> ::= <Args>,<Expr> | <Expr>
<Vid> ::= a | b | c
<Fid> ::= f | g | h
Marking