Question 1 [14 marks total]
Context-free grammars. Consider the following context-free grammar, which is written in BNF.
S → ‘a’
S → ‘(’ L ‘)’
L → S L → L ‘*’ L L
→ L ‘#’
(a) [4 marks] Show that the grammar is ambiguous.
Sample solution. [Note on this solution: you are expected when giving the solution to this question
to draw parse trees; here we just indicate the structure of the parse trees.]
The string a*a*a has two possible parse trees: equivalent in structure to (a*a)*a and a*(a*a).
Alternatively, a*a# has two possible parse trees corresponding in structure to a*(a#) and (a*a)#.
(b) [10 marks] Rewrite the above grammar so that it is unambiguous but recognises the same language
(set of strings). Resolve the ambiguities in the grammar so that
• the binary operator ‘*’ is left associative,
• the postfix unary operator ‘#’ is higher precedence than ‘*’.
Your grammar should be written in BNF rather than extended BNF (i.e., it should not use braces for
repetitions or brackets for optionals).
S → ‘a’
S → ‘(’ L ‘)’ L →
L ‘*’ X L → X X
→ X ‘#’ X → S
Question 2 [10 marks total]
(a) [6 marks] Briefly describe the roles of stack frames (or activation records), static links, and dynamic
links in implementing (parameterless) procedure call and return.
Sample solution. A stack frame is an area on the runtime stack which contains all the information
associated with a procedure call. It contains the return address for the call, and the static and dynamic
links, as well as any local variables of the procedure.
The static link in the stack frame for a call on procedure P gives the address of the stack frame for the
most recent activation of the procedure that statically encloses P. The static link is used to access
variables declared in scopes global to P.
The dynamic link in the stack frame for a call on procedure P gives the address of the stack frame for
procedure that called P. The dynamic link is used to restore the frame pointer on return from P. (b) [4 marks] Consider a PL0-like language in which a procedure may be passed as a parameter to a
procedure. When passing a procedure R as a parameter to a procedure P describe what information
associated with R needs to be passed to the procedure P when P is called, and describe how the
passed-in procedure R is called from within P.
Sample solution. When passing a procedure R as a parameter to P as well as passing the address of
the start of the code for R, one must pass a static link to be used for any calls on R. This static link is
the same as the one that would be used for a call on R at the point P is called. Within P a call on the
passed in procedure sets up a static link for the call by copying the static link passed in with R, and
then calls R using the address passed in for it.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: firstname.lastname@example.org 微信:itcsdx