midtermB-sol.dvi
Midterm Exam
CS 314, Fall ’17
October 27
SAMPLE SOLUTION
DO NOT OPEN THE EXAM
UNTIL YOU ARE TOLD TO DO SO
Name:
Rutgers ID number:
Section:
WRITE YOUR NAME ON EACH PAGE IN THE UPPER
RIGHT CORNER.
Instructions
We have tried to provide enough information to allow you to answer each of the questions. If you need
additional information, make a reasonable assumption, write down the assumption with your answer, and
answer the question. There are 5 problems, and the exam has 8 pages. Make sure that you have all pages.
The exam is worth 250 points. You have 80 minutes to answer the questions. Good luck!
This table is for grading purposes only
1 / 80
2 / 60
3 / 30
4 / 20
5 / 60
total / 250
1
NAME:
Problem 1 – Regular Expressions, DFA and Context Free Gram-
mars ( 80 pts)
The context-free grammar G is specified in Backus-Naur-Form as follows, with D as the start symbol:
1: D ::= a D |
2: b E
3: E ::= b E |
4: F
5: F ::= c
1. Give a leftmost derivation (⇒L) for the string a b c given the grammar above. (15 pts)
D ⇒L aD ⇒L abE ⇒L abF ⇒L abc
2. Give the LL(1) parse table for the grammar G. Insert the rule number or leave an entry
empty.(35 pts)
a b c eof
F 5
E 3 4
D 1 2
3. Give a regular expression for the language generated by the grammar G. (15 pts)
a∗b+c
4. Specify a DFA by extending the state transition diagram below. The start state is state 1, and the
final (accepting) state is state 3. You are only allowed to add edges with their appropriate labels, i.e.,
valid labels are a, b, and c. Note that an edge may have more than one label. You must not add any
states. (15 pts)
b
cb
a
START 321
2
NAME:
Problem 2 – Context Free Grammars (60 pts)
A context-free language is a language that can be specified using a context-free grammar. A regular language
is a language that can be specified using a regular expression.
For the three languages given below, if the language is context-free, give a compact context-free grammar
in Backus-Naur-Form (BNF). If the language is regular, give a compact regular expression using the regular
expression syntax introduced in class. If a language is context-free and regular, give both specifications, a
BNF and a regular expression. You do not have to justify why you believe a language is not context-free or
not regular.
1. { 0n13n | n ≥ 0 }, with alphabet Σ = {0, 1}
S ::= 0S111 | �
2. { anb3mcn | n ≥ 0, m >0 }, with alphabet Σ = {a, b, c}
S ::= aSc | B
B::= bbbB | bbb
3. { w | w has at least 2 symbols, but no more than 5}, with alphabet Σ={0, 1}
S ::= A A B B B
A ::= 0 | 1
B ::= 0 | 1 | �
Regular expression: (0 | 1) (0 | 1) (0 | 1 | �) (0 | 1 | �) (0 | 1 | �)
3
NAME:
Problem 3 – Pointers and Memory Allocation in C (30 pts)
int main() {
int x;
int *y;
int **z;
z = (int **) malloc (sizeof(int *));
y = (int *) malloc (sizeof(int));
x = 3;
*z = &x;
*y = x;
x = x + 3;
**z = *y + 5;
printf(“x=%d, *y=%d, **z=%d\n”, x, *y, **z);
return 0;
}
stack
heap
x y z
1. What is the output of the above program? (3 pts each)
x= 8 , *y= 3 , **z= 8
2. Specify, whether the following program objects are allocated on the stack (includes global variables),
on the heap, or not defined (2 pts each).
*x is allocated on the not defined *y is allocated on the heap
z is allocated on the stack x is allocated on the stack
y is allocated on the stack *z is allocated on the heap
**y is allocated on the not defined **z is allocated on the stack
3. Assume the following code segment:
int *x;
*x = 5;
printf(“%d\n”, *x);
Is there a problem with this code? Assume that when you ran the code a couple of times, it printed
“5”. If you believe there is a problem, give a possible “fix” for the problem? (5 pts)
4
The content of variable x is not initialized. However, its content is used as an address of a memory
location, and that memory location is assigned the value 5.
To fix the problem, the pointer x should be initialized to NULL in its declaration, and x must point to
an object on the heap before it is dereferenced. This object is allocated as follows:
x = (int ∗) malloc(sizeof(int ∗))
This statement should be placed before statement ∗x = 5, i.e., before the dereference operation on x.
5
NAME:
Problem 4 – Compilers vs. Interpreters (20 pts)
To answer this question, please use the following definitions.
Definition A compiler maps an input program to a semantically equivalent output program. Note that
the input and output language may be the same. 2
Definition An interpreter maps an input program to the answers it computes; In other words, it executes
the program. 2
As part of the C project, we used and/or wrote the following programs/commands:
• gcc – usage: gcc Under Unix/Linux, commands can be entered on a single command line if they are separated by a semicolon. In the project, we used several languages, namely C, tinyL, RISC machine code, and ilab machines object 1. compile test1 Answer (mark one): compiler: X or interpreter input language: tinyL, output language: ILOC RISC machine code 2. compile test1; sim tinyL.out Answer (mark one): compiler: or interpreter X input language: tinyL, output language: 3. gcc Compiler.c Answer (mark one): compiler: X or interpreter input language: C, output language: ilab machine code (executable) 4. constfolding < tinyL.out
Answer (mark one): compiler: X or interpreter
input language: ILOC RISC machine code, output language: ILOC RISC machine code
6
NAME:
Problem 5 – Syntax-Directed Translation (60 pts)
Assume the following partial expression grammar:
instr. format description semantics memory instructions loadI add rx , ry ⇒L rz add contents of registers rx and ry , and rz ← rx + ry mult rx , ry ⇒L rz multiply contents of registers rx and ry , and rz ← rx ∗ ry Here is a recursive descent parser that implements a compiler for the above grammar. Here is the important int expr() { int reg, left_reg, right_reg; switch (token) { case ’+’: next_token(); left_reg = expr(); right_reg = expr(); reg = next_register(); CodeGen(ADD, left_reg, right_reg, reg); return reg; case ’*’: next_token(); left_reg = expr(); right_reg = expr(); reg = next_register(); CodeGen(MULT, left_reg, right_reg, reg); return reg; case ’1’: case ’2’: return const(); } } int const() { int reg; switch (token) { case ’1’: next_token(); reg = next_register(); CodeGen(LOADI, 1, reg); return reg; case ’2’: next_token(); reg = next_register(); CodeGen(LOADI, 2, reg); return reg; } } 7 NAME: • The value of variable “token” has been initialized correctly. other words, the first register that the generated code will be using is register r1. • Your parser “starts” by calling function expr() on the entire input. 1. Show the code that the recursive descent parser generates for input + * 1 2 * 2 2 will produce: + ** 221 2 loadI 1 ⇒ r1 8 NAME: 2. Change the basic recursive-descent parser to implement an interpreter for our example language. You int expr() { int a, b; switch (token) { case ’+’: next_token(); a = expr(); b = expr(); return (a + b); case ’*’: next_token(); a = expr(); b = expr(); return (a * b); case ’1’: case ’2’: return const(); } } int const() { switch (token) { case ’1’: next_token(); return 1 ; case ’2’: next_token(); return 2 ; } } 9
For instance, saying cd foo; ls will change the current directory to subdirectory foo, and will list its files.
code (executables). Classify the following commands or the entire sequence of commands as either
compiler or interpreter. Note that you should treat a sequence of commands as a single unit, i.e., as a single
composed command. If the single or composed command is a compiler, give its input and output language
(e.g.: input language: C, output language: tinyL). For an interpreter, just give its input language.
∗
arithmetic instructions
store result into register rz
store result into register rz
part of the code:
Make the following assumptions:
• The function CodeGen is the one from our first project.
• The first call to function next register() the shown parser returns integer value “1”. In
loadI 2 ⇒ r2
mult r1, r2 ⇒ r3
loadI 2 ⇒ r4
loadI 2 ⇒ r5
mult r4, r5 ⇒ r6
add r3, r6 ⇒ r7
may insert pseudo code in the spaces marked by . No error handling is necessary.