Slide 1
Midterm Review
1
CSE240
Introduction to Programming Languages
The Structure of Programs
Different levels of analyses:
lexical:
variable name, symbol, begin … end, { … };
syntactic:
if … then … else …, switch, for … Do structures
contextual:
Variable type and initialization, etc.
semantic:
meaning of a program, dynamic execution
2
Syntactic Analyses: Backus-Naur Form (BNF)
BNF: Meta-language for describing languages, context free language:
non-terminal symbol: symbols in grammar — don’t appear in final program
terminal symbol: symbols that appear in actual program — go no further in translating from grammar
3
Syntactic Analyses : BNF Example
What are the terminal symbols? Which are non-terminal symbols?
Which are valid?
Aidlw ((01001 AND 0111111) XOR (000000 NOR 01111)).
Result2 = 1244 NOR 0000.
hEl0 1 AND 0 OR 0 NOR 1.
H (1001 XOR ( 00000 NAND 1)).
4
Answers:
First three lines have terminal symbols. The rest are non-terminal except (), and period.
Yes
No
No
Yes
5
Syntactic Analyses : BNF Example
Programming Language Example
< expr > ::= < variable>
| (
Which are valid?
sum4 = (a1 + a2) * (3b % 4*b);
2sum = 2+3;
3p4rd2 = ((1a + a2) * (b3 % b4)) / (c7 – c8);
foo_bar = (a1 + a2 – b3 – b4);
(a1 / a2) = (c3 – c4);
6
Syntactic Analyses: Syntax Graph
A language can also be defined by a syntax graph
if (condition) statements ;
else statements ;
if (a < 0) return -a;
if (a < 0) return -a; else return a;
switch (expr) { case value: statements ;
default: statements;
}
switch (ch) {
case '+': x = a + b; break;
case '-': x = a - b; break;
case '*': x = a * b; break;
case '': x = a / b; x = round(x); break;
default: printf("invalid operator"); break;
}
7
Macro, Inlining, and Function
Compare and contrast macros, inlinings, and funtions
How are macros used? And what are macro side-effects? (Can you provide some examples?)
In term of execution, which has better performance? And why?
8
Macro, Inlining, and Function
Macros:
The programmer decides if to optimize the program;
The programmer is responsible for the correctness;
Macro is a forced in-lining and the programmer can predict the performance.
Inlining:
The compiler decides if to optimize the code;
The compiler is responsible for the correctness;
Programmer does not know if the optimization is done and cannot predict the performance.
Functions:
Uses a stack frame and memory to execute some value.
It does not replace code
How are macros used? And what are macro side-effects? (Can you provide some examples?)
Copy and paste leads to issues when using post/pre-increments
In term of execution, which has better performance? And why?
Macro can be ten times faster but takes up more space
Functions require lookup and thus have overhead
9
10
#include
#define TESTER(x,y)( ( x == y ) ? x : y)
void main(){
int result1, result2, result3, a, b, c, d;
a=2,b=2,c=10,d=11;
result1 = TESTER(a++, b);
result2 = TESTER(++c, d);
printf(“Result 1 is %d.\n”, result1);
printf(“Result 2 is %d.\n”, result2);
printf(“a: %d, b: %d, c: %d, d: %d\n”,a,b,c,d);
a = 0, b=2, c = 0 , d = 11;
result1 = TESTER(a++, b);
result2 = TESTER(++c, d);
printf(“Result 1 is %d.\n”, result1);
printf(“Result 2 is %d.\n”, result2);
printf(“a: %d, b: %d, c: %d, d: %d\n”,a,b,c,d);
}
Result 1 is 2.
Result 2 is 11.
a: 1, b: 2, c: 1, d: 11
Result 1 is 3.
Result 2 is 12.
a: 4, b: 2, c: 12, d: 11
Type Equivalence
What is name equivalence?
Two types are equivalent if they have the same name (e.g. C-structure). Anonymous types are not equivalent.
What is structural equivalence?
Two types are equivalent if they have the same set of values and operations. (e.g. non-structured C types).
Weak type checking vs. Strong type checking
Implicit conversion (Coercion)
Explicit conversion (Type Casting)
Assume int x = 5;
Coercion: Implicit type conversion,
e.g., float f = 3.14 + x;
Casting: Explicit type conversion
e.g., int i = (int) f + x;
11
Array, string, and pointers
In C, a string is an array of characters.
char Name[] = “Mary”; // How many elements?
char Name[6] = {‘C’, ‘h’, ‘a’, ‘r’, ‘l’, ‘e’, ‘s’} // Is this possible? What are some side effects?
char *p = “Charles”; // Is this possible?
// How can we print each of the individual char?
* Assume “p” is a pointer and “Name” is a character array…
p = Name; // Is this possible?
Name = p; // Is this possible?
12
Pointers in C/C++
What are the two pointer-specific operations?
& is a referencing function that returns the address value of the variable it precedes. Note, &x is r-value.
* represents the name of the memory location of the address it precedes. Note, *y is a l-value.
Example:
Brickyard is the name of ASU Engineering Building
“699 S. Mill Avenue” is the address of the building
People can enter and leave the building and are value.
Brickyard = Peter; means Peter enters the building;
&Brickyard is the string: “699 S. Mill Avenue”;
&Brickyard = Peter; Is it OK? What does the statement mean?
*(“699 S. Mill Avenue”) = Peter; Is it OK?
*(&Brickyard) = Peter; Is it OK?
13
Pointers in C/C++
What are the two pointer-specific operations?
& is a referencing function that returns the address value of the variable it precedes. Note, &x is r-value.
* represents the name of the memory location of the address it precedes. Note, *y is a l-value.
Example:
Brickyard is the name of ASU Engineering Building
“699 S. Mill Avenue” is the address of the building
People can enter and leave the building and are value.
Brickyard = Peter; means Peter enters the building;
&Brickyard is the string: “699 S. Mill Avenue”;
&Brickyard = Peter; Is it OK? What does the statement mean? No
*(“699 S. Mill Avenue”) = Peter; Is it OK? Yes
*(&Brickyard) = Peter; Is it OK? Yes
14
Pointers Example
#include
int main() {
int i1 = 0, i2 = 10, *p1, *p2, **p3;
p1 = &i1; // What is the value *p1?
p2 = &i2; // What is the value *p2?
p3 = &p2; // What is the value **p3?
**p3 = 20; // What variable is changed?
return 0;
}
15
&i1 = 5; Is it OK? What does the statement mean?
7000 = 5; Is it OK? What does the statement mean?
*(7000) = 5; Is it OK?
*(&i1 ) = 5; Is it OK?
What is &p1?
p3 = &p1; Is it OK?
Pointers Example
#include
int main() {
int ma[2][4], *p;
p = &ma[0][0];
*p = 5; // What is the value of ma?
*(p + 2) = 10; // What is the value of ma?
*(p + 5) = 20; // What is the value of ma?
return 0;
}
16
5
10
20
20
Constants in C/C++
What are constants?
Can the value of a constant be changed? If so, how?
17
Constants in C/C++
What are constants?
-Constants are “variables” that the program may not modify
Can the value of a constant be changed? If so, how?
-Constants can be changed in C.. POINTERS!
-Constants defined as macros cannot be modified ever
-If you try to change a constant by accessing variable directly then compiler will throw error
18
Structures and Unions
What is a structure?
struct contact { // a node to hold personal details
char name[30];
int phone;
char email[30];
} x;
Is padding required?
Can the padding be removed?
19
Structures and Unions
What is a structure?
struct contact { // a node to hold personal details
char name[30];
int phone;
char email[30];
} x;
Is padding required? Yes, (2 bytes + 2 bytes)padding + 64 bytes = 68 bytes
Can the padding be removed? Yes, (group char arrays together), then 30+30 bytes+4 bytes = 64 bytes
20
Linked List Example (using Pointer)
#include
#include
#include
struct contact { // define a node holding a person’s details
char name[30];
int phone;
char email[30];
struct contact *next; // pointer to contact structure
} *head = NULL; //head is a global pointer to the first entry
void branching(char c); // function forward declaration
int insertion();
struct contact *search();
void delete();
21
Linked List Example (Cont’d)
int insertion() { // insert a new entry
struct contact *p;
p = (struct contact *) malloc(sizeof(struct contact));
if (p == 0) {
printf(“out of memory\n”); return -1;
}
printf(“Enter name, phone, email: \n”);
scanf(“%s”, p->name);
scanf(“%d”, &p->phone);
scanf(“%s”, p->email);
p->next = head; // Where is the new node inserted?
head = p;
return 0;
}
22
Linked List Example (Cont’d)
How can we modify the insertion code so that the new node is inserted upon the sorted?
Joe
1122334
next
John
1122556
head
Tom
1122667
p
temp
temp->next = p;
Zac
1122889
0
p->next = temp->next;
23
Linked List Example (Cont’d)
void insertion() { // insert a new entry
struct contact *p, *temp;
p = (struct contact *) malloc(sizeof(struct contact));
if (p == 0) { printf(“out of memory\n”); return; }
printf(“Enter name, phone, email: \n”);
scanf(“%s”, p->name); // p->name is array
scanf(“%d”, &p->phone);
scanf(“%s”, p->email);
temp = head;
if ((head == 0)||(stricmp(p->name, temp->name) <=0)) {
p->next = head;
head = p;
}
// continued next page
24
Linked List Example (Cont’d)
else { while (temp->next != 0) {
if (stricmp(p->name, temp->next->name) <=0) {
p->next = temp->next;
temp->next = p;
return;
} else
temp = temp->next;
}
p->next = 0;
temp->next = p;
}
}
25
Joe
1122334
next
John
1122556
head
Tom
1122667
p
temp
temp->next = p;
Zac
1122889
0
p->next = temp->next;
Parameter Passing
What are different type of parameter passing mechanism?
Call-by-value
Call-by-reference
Call-by-address
What are the differences between each parameter passing mechanism? (Advantages and Disadvantages)
26
Parameter Passing
What are different type of parameter passing mechanism?
Call-by-value
Advantages: no side effects
Disadvantages: less powerful/flexible
Call-by-reference (call-by-alias)
Advantages: powerful, one value used
Disadvantages: only C++
Call-by-address (call-by-pointer) cannot be a value must be a variable since values don’t have aliases
Advantages: powerful, both C/C++, can return multiple values (how??)
Disadvantages: two values used
27
Recursion
What are the four-steps abstract approach for solving recursive problems?
Formulate the size-n problem.
Find the stopping condition and the corresponding return value.
Formulate the size-m problem and find m. In many cases, m = n – 1;
Construct the solution of size-n problem from size-m problem.
28
Recursion
What does the tail-recursive program resemble?
while-loop
1
2
n
condition
Jump to
tail-recursion
part 1
1
2
n
recursive call
condition
loop-body
29
Recursion
Fibonacci numbers are defined by
fib(n) :
if n == 0: return 0
if n == 1 return 1
else if n >=2 return fib(n-1)+fib(n-2)
Can you write a recursive function for it? Yes!
30
Recursion
// construct size-n problem (function prototype)
int fib(int n) {
// stopping condition (n == 0)
if (n == 0) {
return 0; // return value
}
// stopping condition (n == 1)
else if (n == 1) {
return 1; // return value
}
// size m problem (n >= 2)
else {
return fib(n-1) + fib(n-2); // construct solution to size n problem from size m problem(s)
}
}
31
Merge Short (pseudo code textbook Section 2.8.5)
mergesort (A, L,R) {
if R > L then
{ M = (R+L)//2; // integer division
mergesort (A, L, M);
mergesort (A, M+1,R);
merge(A, L, M, R); }
else Return A
}
merge (A, L, M, R) {
for i = M down to L do B[i] = A[i];
for j = M+1 to R do B[R+M+1-j] = A[j];
i = L; j = R;
for k=L to R do {
if B[i] < B[j] then
{ A[k]=B[i]; i = i+1; }
else
{ A[k]=B[j]; j = j-1; }
}
32
L
R
M
R
M+1
L
M
Identify the code for defining :
size-n problem
stopping condition and return value
size-m problems
the size-n solution from the size-m solutions
/docProps/thumbnail.jpeg