Slide 1
Aspects of Programming Languages
Know your paradigms:
OOP
Procedural
Functional
Service Oriented
1
Aspects of Programming Languages
Know your analysis methods
Efficiency
Reliability
Readability
Writeability
Resusability
2
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
3
The Structure of Programs
Know your errors:
Syntax – is it built correctly?
Context – is it built from the right stuff?
Semantic – is it working correctly?
4
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
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: Backus-Naur Form (BNF)
Given a situation you should be able to generate rules and prove validity
Given:
A number can be defined as a number and a digit or just a digit
Our digits are terminals
Example: write some syntax rules for simple arithmetic expressions
+, – , *, /
7
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;
}
8
Does a while-loop’s syntax graph have a loop?
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?
9
Type Equivalence
What is name equivalence?
What is structural equivalence?
Weak type checking vs. Strong type checking
Implicit conversion (Coercion)
Explicit conversion (Type Casting)
10
Data
Understand your aspects of data
Type: what values and operations are allowed
Location: where data are stored in memory
Address: an integer associated to a location
Reference/pointer: a name associate with the variable that holds an address of a location
Variable name: a name associated with a location
Value: what stored in a memory location
Scope: (lifetime) and visibility
11
Know your sizes
32 Bit based:
12
Type Typical Bit Width Typical Range
char 1byte -128 to 127 or 0 to 255
unsigned char 1byte 0 to 255
signed char 1byte -128 to 127
int 4bytes -2147483648 to 2147483647
unsigned int 4bytes 0 to 4294967295
signed int 4bytes -2147483648 to 2147483647
short int 2bytes -32768 to 32767
unsigned short int 2bytes 0 to 65,535
signed short int 2bytes -32768 to 32767
long int 8bytes -2,147,483,648 to 2,147,483,647
signed long int 8bytes -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
unsigned long int 8bytes 0 to 18,446,744,073,709,551,615
float 4bytes +/- 3.4e +/- 38 (~7 digits)
double 8bytes +/- 1.7e +/- 308 (~15 digits)
long double 8bytes +/- 1.7e +/- 308 (~15 digits) / (~19 digits)
wchar_t 2 or 4 bytes 1 wide character
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?
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?
*(“699 S. Mill Avenue”) = Peter; Is it OK?
*(&Brickyard) = Peter; Is it OK?
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
Dynamic Allocation
Make sure you know dynamic allocation
malloc
int* myArray = (int*)malloc(COUNT * sizeof(int));
new
int* myArray = new int[COUNT];
If you dynamically allocate you should release the memory
malloc -> free
new -> delete/delete[]
17
Multidimensional Allocation
Remember when you build a multi dimensional array you need a pointer level for each dimension and you are building arrays of arrays.
int** my2D = new int*[Y_DIM];
for(int i = 0; i < Y_DIM; i++)
my2D[i] = new int[X_DIM];
18
Constants in C/C++
What are constants?
Can the value of a constant be changed? If so, how?
19
Parameters
Know your parameter passing differences
Reference – passes the memory
Pointer – passes a pointer to the memory
Value – passes a copy
20
Parameters
Handy-dandy Guide:
Pass by value when a function does not want to modify the parameter and the value is easy to copy (simple data types and certain things like strings)
Pass by constant pointer when
the value is expensive to copy
the function DOES NOT want to modify the value pointed to
NULL is valid and expected and handled
Pass by pointer when
the value is expensive to copy
the function WANTS to modify the value pointed to
NULL is valid and expected and handled
Pass by constant reference when
the value is expensive to copy
the function DOES NOT want to modify the value
NULL is not valid
Value might not be addressed
Pass by reference when
the value is expensive to copy
the function DOES want to modify the value
NULL is not valid
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?
22
Structs
Make sure you understand how to get the size of the struct and when padding should occur
integers have to address on multiples of 4
doubles on multiples of 8
Struct aligns to its largest DATA TYPE which can cause additional padding
23
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)
24
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();
25
Does the contact struct require padding? How many bytes?
Can we eliminate them?
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;
}
26
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;
27
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
28
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;
}
}
29
Joe
1122334
next
John
1122556
head
Tom
1122667
p
temp
temp->next = p;
Zac
1122889
0
p->next = temp->next;
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.
30
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
31
Recursion
Fibonacci numbers are defined by
Can you write a recursive function for it?
32
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; }
}
33
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
ï
î
ï
í
ì
³
-
+
-
=
=
=
2
)
2
(
)
1
(
1
1
0
0
)
(
n
n
fib
n
fib
n
n
n
fib
/docProps/thumbnail.jpeg