CSCI 431: Exam 1 Review in Outline Form

Part I: The Definition of Programming Languages

Two aspects that define any language:
1. syntax
  1. definition
  2. formal models
    1. type 0 --- type 3 rules and equivalent machines
    2. context-free grammars (e.g. BNF) are used in compilers
      1. parse trees
      2. equivalent machine PDA
    3. regular grammar are used in lexical analyzers
      1. parse trees
      2. FSA
      3. regular expressions
2. semantics
  1. definition
  2. formal models
    1. axiomatic semantics---proofs of program correctness
    2. rules for different statements
Because we study computer languages we also focus on "implementation"
1. hardware computer
  1. read assembly code
  2. fetch-execute cycle
2. software computer (virtual computer)
3. stages in translation
  1. lexical analysis
  2. syntactic analysis
  3. symbol table---used for communication between the syntactic and semantic modules
  4. semantic module
  5. optimization
  6. code generation
  7. linking

Part II: Comparative analysis of languages:

history:
1. objectives and examples of early languages
2. objectives and examples of later languages
language paradigms:
1. Imperative languages
2. Functional languages
3. Object oriented languages
4. Rule-based or declarative
major aspects of a programming language
1. data
  1. l-values and r-values when discussing assignment
  2. binding times for data objects (there are other things besides identifiers that have bindings, e.g. symbols)
    1. environments
    2. compile time --- static
    3. run time --- dynamic
  3. attributes typically associated with data objects
    1. type
    2. value
    3. location
    4. name
    5. membership
  4. type checking (and conversion)
    1. dynamic vs static
      1. definition
      2. pro's and con's
    2. name equivalence vs. structural equivalence
    3. strong typing
  5. storage representations:
    1. elementary data types
      1. integers
      2. floating point
      3. char
      4. enumeration and subtypes
      5. boolean
      6. pointers
    2. structured data types
      1. strings
      2. arrays
      3. records (struct's)
      4. unions and variant records
      5. lists
      6. sets
  6. storage management
    1. run-time stack vs. the heap
    2. dangling pointers
    3. garbage collection
operations
control
storage management
operating environment

Part III: Sample Questions

For each of the languages below provide the following information:
1. what paradigm does the language most closely fit
2. is the language compiled, interpreted or hybrid
3. approximate year when introduced
LISP, PROLOG, C, C++
```
  
```
Explain the meaning of "binding", and "binding time".
```
  
```
Contrast "static type binding" with "dynamic type binding" making sure that you define each term and mention at least one advantage and one disadvantage of each.
```
  
```
What is the purpose of the "symbol table"?
```
  
```
Name 4 attributes that can be associated with an identifier and state their binding times in a language of your choice.
```
  
```
Formulate the machine representation of the following numeric values:
1. the integer 4
2. the floating-point number 1.5 in IEEE format
3. the fixed-point number 225.25
```
  
```
Calculate l-values for:
1. A[i] given the declaration: A:array [3..10] of real;
2. A[i][j] given the declaration: A:array [1..10, -5..5] of real;
```
  
```
What problems are associated with unions and variant records?
```
  
```
Name one advantage and one disadvantage of a packed representation.
```
  
```

Given the context-free grammar for expression:

   E -> c
   E -> id 
   E -> (E)
   E -> E + E
   E -> E * E

construct the parse tree for the following expression:

   id * id + id

Given the regular grammar for binary numbers:
```
  B -> 0 B | 1 B | 0 | 1
```
formulate the equivalent FSA and regular expression.
```
  
```

Classify the following grammars according to their most restrictive type.

   I -> a L | b L | c L | ... z L | a | ... y | z
   L -> 1 L | 2 L | ... | 9 L | 0 L | 1 | ... 9 | 0
        | a L | b L | c L | ... Z L | a | ... y | z

```
   S -> SS | (S) | ()
```
```
   A -> B | Cd 
```
```
   bAd -> bBCd | bCAd 
```

State the weakest preconditon for the following selection statement
```
   if (X > 0)
     X = X - 1;
   else 
     X = X + 1;
```
if the postcondition is {X > 10}.