Please answer ALL questions or none at all. Thank you in advance.

15. Consider the following context-free grammar. G G B G N

B ( E ) E E ( E ) N ( L ] L L E L (

(a) Describe, in English, the language generated by this grammar. (Hint: B stands for balanced; N stands for non-balanced.) (Your description should be a high-level characterization of the languageone that is independent of the particular grammar chosen.)

(b) Give a parse tree for the string ((]().

16. In Fortran 77, local variables were typically allocated statically. In Algol and its descendants (e.g., Ada and C), they are typically allocated in the stack. In Lisp they are typically allocated at least partially in the heap. What accounts for these differences? Give an example of a program in Ada or C that would not work correctly if local variables were allocated statically. Give an example of a program in Scheme or Common Lisp that would not work correctly if local variables were allocated on the stack.

20. Consider mathematical operations in a language like C++, which supports both overloading and coercion. In many cases, it may make sense to provide multiple, overloaded versions of a function, one for each numeric type or combination of types. In other cases, we might use a single versionprobably defined for double-precision floating point argumentsand rely on coercion to allow that function to be used for other numeric types (e.g., integers). Give an example in which overloading is clearly the preferable approach. Give another in which coercion is almost certainly better.