Which of the following are true, and which are false?
What is a just-in-time compiler?
A just-in-time compiler is a hybrid between a compiler and an interpreter where an interpreter compiles frequently used blocks or subprograms of a program, and uses the compiled versions of those blocks or subprograms for efficiency.
What is shadowing, and how can it occur? Give an example.
Shadowing occurs when an identifier is bound within the scope of another binding of the same identifier. The more recent binding shadows the older one. Here is an example in C++.
{int x; x = 3; {int x; x = 6; } }The inner binding of x shadows the outer one. (Both bindings of x are to variables, not to numbers.)
An implementation of a programming language is not normally considered to be an adequate definition of the language. Why not? What would be the consequences of using an implementation as a definition?
Possible consequences:
What is an important advantage of the linked representation of sequences over the sequential representation?
It is easy to extend sequences by adding values to the start. Also, the linked representation permits structure sharing, which sometimes greatly reduces memory requirements. There are other advantages, such as the ability to add values into the middle of the sequence.
What is an important advantage of the sequential representation of sequences over the linked representation?
Random access (constant time indexing) and reduced memory requirements for individual lists are important advantages.
Show that the following BNF grammar is ambiguous. The start symbol is <S>.
<S> ::= <S> a | a <S> | a
To show that a grammar is ambiguous, you need to show two different parse trees for the same sequence of tokens. In this case, it suffices to show two different parse trees for aa. Here they are.
S S / \ / \ S a a S | | a a
Show a parse tree for string aacacab according to the following grammar, where the start symbol is <S>.
<S> ::= <F> a <S> | b <F> ::= a <F> | c
S
/|\
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
F a S
/ \ /|\
a F / | \
/ \ F a S
a F | |
| c b
c
Write a BNF grammar for sequences of left and right parentheses that are balanced. A sequence of parentheses is balanced if parentheses match and are well nested. For example, (()(())) is balanced, but )( and ())()( are not balanced.
The following is an ambiguous grammar. The start nonterminal is B.
I am using e for the empty string.
<B> ::= <B> <B>
| ( <B> )
| e
The following is an unambiguous grammar for the same thing.
The start nonterminal is B.
<B> ::= ( <B> ) <B>
| e
What is a solution to pattern match equation [x,y+1] = [7,99]?
x = 7, y = 98.
What is the head of list [2,4,6]? What is the tail of list [2,4,6]?
head([2,4]) = 2 and tail([2,4]) = [4,6].