TEST 3 Flashcards
Language
language defines a set of strings of comprised of characters from an “alphabet” of symbols – defines valid words and combos of words in a sentence
Regular language
a language that can be formally described using a finite state machine
Finite state machine
an abstract model of computation comprised of states + transitions
Regular expression
a pattern used to search for a match within a string of text
What two properties must hold in order for a finite state machine to be considered deterministic?
- Every transition requires that an event occur (char. be consumed)
2.There is at most one transition on the same event (character) out
of a particular state
|
or
[]
any single letter in word brackets
[-]
match one single character from contgious range **a-c valid but c-a is not
\
treat the next character literally, rather than as an operator; ie \“[cat]”\ then [cat] will be accepted
why double \ not single
bc \ has special meaning as an example ie if we want to do a literal double qoute in a string and not end the string there we use \ to escape the literal
?
match 0 or 1 instances of the preceding character or group;
*
match 0 or more instances of the preceding character or group;
+
match 1 or more instances of the preceding character or group;
what is difference between + and *
+ means at least 1 * means can be 0
Order of operations
- \
- [] including -
- ()
- ?
- concatenation (valid regex back to back)
- |
public String substring(int startIdx)
returns the substring
from startIdx (inclusive) to the end
String substring(int startIdx, int endIdx)
returns the substring from startIdx (inclusive) to endIdx (exclusive)
public int indexOf(String str)
returns the start index of the
first occurrence of str in the string; returns -1 if str is not found
public String replaceAll(String regex, String new)
a copy of the original string with every substring that matches regex replaced by new– can pass string literal or reg ex – reg ex adds additonal flexibality
sentence
a sequence of strings in the language
language
defines a set of strings of comprised of characters from an “alphabet” of symbols (does not have to be A-Z)
sentence
a sequence of strings in the language
grammar
definition of the structure of a valid sentence in the language
syntax
the structural validity of a sentence
semantics
the meaning of a sentence
int x = “abc is
is syntactically valid, but semantically invalid
syntax analysis
the process of analyzing a sequence of symbols to see if they conform to a grammar
To implement a recursive descent parser for a given grammar, you need to define one function per [Your answer] , and each function should have one branch per [Your answer] .
production rule, delimiter
ad hoc pros and cons
Pros: often quicker & easier to write
when the grammar is simple
● Cons: less structured; less extensible; difficult to cover all cases for a more complex grammar
Recursive Descent
Pros: closely mirrors the grammar; highly
structured and easily extensible
● Cons: can be longer and more difficult to write if the grammar is simple (or if the grammar isn’t formally expressed)
Why JSON
Pros:
● Lightweight syntax (unlike XML)
● Designed to represent program data (unlike all others shown)
● Human readable (unlike protocol buffers)
hierarchal structure (unlike csv)
clear and concise way to rep arrays (unlike XML)
what are the internal representations of each of the following Java classes?
JSONArray: List<object>
Map<String, Object></object>
Creational Patterns:
Singleton, Factory, Builder
Patterns concerning creation of objects;
alternatives to invoking a constructor using new
Singleton Pattern:
Structural Patterns:
Composite, Adapter
Patterns concerning how objects and
components are structured
Behavioral Patterns:
Observer, Strategy, Visitor
Patterns concerning how responsibilities and algorithms are assigned and/or distributed across objects
Override:
Overload:
What is double dispatch? and why is it important?
Storage:
Long-term (files)
Memory:
Short-term (program data)
How is memory allocated?
Memory TO a program: done by OS
Memory WITHIN a program:
Manual: Programmer asks
Automatic: Runtime does it
Memory Organization:
Code: Instructions to be executed
Stack: One frame per function
Heap: Chunk of memory for longer-lasting data
How are primitive types stored?
Local variables value in stack frame
Fields/elements value in array/object
How are reference types stored?
Array/object always on heap
local variables address in stack frame
Fields/elements address in array/object
How is memory deallocated/freed?
Stack automatically after each function terminates
Heap:
Manual: Programmer frees memory
Automatic: Runtime detects and frees
variables not in use
Reference Counting:
Compiler: Inserts operations for incrementation
Runtime: Allocates, executes, frees
Reference Counting pros and cons:
Pros: Easy, happens immediately, good performance.
Cons: Single self-referencing, cycles
factory pattern
When to use it? When you want to create multiple instances, but
want to abstract away details of the creation process
KEYWORDS: method to use instead of constructor
builder
When to use it? When the logic for creating an instance of type T
involves many steps, including instantiating many objects
KEYWORDS: streamline, hierarchy, components
Composite Pattern
When to use it? When many parts comprise a whole, and you
want to define a functionality across the entirety of the structure
think about a figure composed of multiple shapes– tree like structure
KEYWORDS: delegate
adapter pattern
When to use it? When you want to connect two incompatible
classes or interfaces (A and B)
■ Helps improve flexibility and reusability
■ If A interacts with B, you can change how one works without
changing the other
Trace-Based (Mark-Sweep):
Compiler: does nothing
Runtime: Allocates marks and sweeps
Trace-Based (Mark-Sweep) pros and cons:
Pros: Handles self-references, no overhead
Cons: “Stop the world” causes delays
Fragmentation:
Free space becomes non-contiguous
Mark-Sweep Compacts:
Removes dead objects and readdresses live objects so freed space is contiguous
observer pattern
When to use it? When you want one or more components to
“subscribe” to automatic updates from another component
KEYWORD: updates, notifies
strategy
When to use it? When you want to be able to choose from one of
multiple interchangeable algorithms or implementations
■ Decouples the algorithm from the class that it operates on
KEYWORD: single metric
visitor
When to use it? When you want to decouple an algorithm from
the structures that it operates on
■ Similar to the strategy pattern in this decoupling, but targets
algorithms that are distributed across multiple data types
■ More complex but more flexible than the strategy pattern
decouple, contiguous , multiple data types
double dispatch
instead of directly calling the method that encapsulates the algorithms we go through an extra layer of indirection thus 2 methods call are made to ensure correct algorithms executes
override
use the same signature (name + parameter types);
can optionally make the return type more specific
■ Multiple implementations within the same hierarchy
overload
use the same signature (name + parameter types);
can optionally make the return type more specific
■ Multiple implementations within the same hierarchy
difference between overriding and overloading
overloading differs in that one implenmentation isnt replacing another but rather they are coexisting with the context of the same class
The factory and builder patterns are similar in that they are each designed to
make it easier to construct a new instance of an object. What is the key
difference between them? (Hint: It has to do with the nature of the object being
constructed!)
The factory pattern is more focused on creating objects with a simple and
uniform construction process and provides a way to address the creation of
different related objects. On the other hand, the builder pattern is designed for
more complex object construction with a complex internal structure.
The strategy and visitor patterns are similar in that they both decouple an algorithm from the class on which it operates. What is the key difference between them?
The key difference lies in how the nature of the object influences the algorithm. In the strategy pattern, the algorithm’s behavior is influenced by the strategy chosen at runtime for a specific context. In contrast, the visitor pattern is designed for scenarios where the algorithm needs to operate on various types of objects, and the double dispatch mechanism ensures that the correct algorithm is executed based on both the type of the object and the type of the visitor.
What is double dispatch, and why is it necessary in the visitor pattern? You should address the need for the accept() method as well as the need to re-define the accept() method within each concrete subclass of IVisitable.
Double dispatch in the Visitor pattern involves making two method calls to ensure the correct algorithm is executed. The first dispatch occurs when the accept() method is called on the object being visited, and the second dispatch happens when the visit() method is invoked on the visitor. This mechanism is necessary because the algorithm is distributed across multiple data types. The accept() method is crucial for the first dispatch, and re-defining it in each concrete subclass ensures polymorphic behavior, allowing the correct visit() method to be bound at runtime based on the types of both the object and the visitor.
how java determines between overriding and overloading
Overriding: The method to be executed is determined at runtime based on the actual type of the object. It’s called dynamic dispatch. The JVM decides which version of the method to execute based on the actual type of the object at runtime.
Overloading: The method to be called is determined at compile time based on the method signature. The compiler selects the appropriate method to call based on the number and types of arguments used in the method invocation.
