Question:
Give an example of a trade off between reliability and cost of execution.
Answer:
- Exception handling - You sacrifice cost of execution by enabling exception handling but increase program reliability, particularly important in the case of embedded systems.
- Recursive methods - Recursive methods may often be more reliable than iterative methods, but you will sometimes sacrifice performance using a recursive method as there can be much more overhead involved in pushing multiple method calls to the runtime stack.
- Dynamic typing - Utilizing dynamic type checking will favor the cost of execution but sacrifice reliability if the program runs into a type check error during runtime.
- Array bounds - Bound checking on arrays. If the bounds are checked invalid memory accesses can be caught but slow down execution time (it has to check the bounds for every access to the array).
Question:
What is orthogonality in regard to programing languages?
Answer:
Orthogonality is when two distinct features in a language can be used together in a way that enhances what each individual feature can do.
Example:
Using an array of structs in C. Structures are flexible in what they can contain, and arrays provide an easy way of traversing constructs. When used together, an array of structures allows easy traversal of structures which may contain any type of information.
Question:
What does the compiler do on its first pass?
Answer:
It tokenizes the sources code.
Example:
The first stage of a compiler is called the scanner. It takes a character stream (source code) and performs a lexical analysis on it. When its done, it outputs a Token stream.
Question:
What do we use to implement a DFA (Deterministic Finite state Automata)
Example:
A transition table
Example:
A transition table has all the states on one axis (vertical), and all the possible inputs on the other axis (horizontal). Then each entry on each row holds the value for the next state taking into consideration the state it started with and the input it obtained.
Question:
For the sentences within the Language Grammar, what are they from the prospective of the software?
Answer:
That is the program. In other words, a sentence is the entire program.
Question:
Using the Context Free Grammar given on slide 8, construct a valid grammar.
Answer:
One example
a = b + c
Question:
What are the four components of a grammar?
Answer:
Terminals (T), Non-terminals (N), a start symbol (S), and productions or rules (P)
Question:
What is the distinctive charactersitic of associativity in a grammar
Answer:
A recursive definition.
Example:
<expr> -> <expr> + const | const
Question:
What characteristic of a grammar can keep it from being top down parsable?
Answer:
- Left recursive (indirect and direct)
- Common prefixes or pairwise disjoint (A->bcD, A->bxM)
Question:
Why doe having static binding and dynamic type checking does not make sense?
Answer:
Because that would be that all the binding is done at compile time but no error checking is done until run time, even though you have all the necessary information at compile time
Question:
What is strong typing? How does casting affect strong typing?
Answer:
Strong typing means that all type errors can be caught either statically or dynamically. Casting allows you to circumvent the type of a variable so language is not strongly typed if casting is allowed.
Question:
What are the two attributes of a grammar?
Answer:
Inherited (top down), and synthetic (bottom up)
I vaguely remember the first question. It had something to do with giving an example of something that is reliable but costs execution time. The example I gave was when using an array in C, since there is no bounds checking for accessing elements in arrays, when accessing one element past the array, as long as the user has access to the value at that memory address, there will be no segfault. However, if the user doesn’t have access to the value at that memory address, then a segfault will occur. With no bounds checking, there is no cost in execution if we are accessing a valid memory address and there is a cost if we aren’t allowed to access that address. The program may segfault or it may not segfault so the program is not reliable