1/101
Looks like no tags are added yet.
Define sentence (in the context of grammars)
A sequence of words
Define grammar
The definition of a language's syntax; any syntactically valid sentence in the language can be "matched" by its grammar
Define terminal symbol
A token, i.e. a literal string in the grammar
Define non-terminal symbol
A name for a grammar rule (production)
Define start symbol
The non-terminal on the left-hand side of the first production rule
Define syntax
Whether a sentence is structurally valid
Define semantics
Whether a sentence is meaningful
Define parsing
Analyzing a sequence of symbols to see if they conform to a grammar
Define natural language
A language developed by people to speak with each other
Define delimiter
A separator character
How do you structure a recursive descent parser for a grammar?
One function per production, with one branch per acceptable expansion
pros + cons of ad hoc string processing?
Quicker and easier to write when the grammar is simple
Less structured and extensible; easier to miss cases
pros and cons of recursive descent parsing
Closely mirrors the grammar; highly structured and easily extensible
Can be longer and harder to write than needed when the grammar is simple
Define language (in the context of regular languages)
Something defined by its syntax and semantics
Define regular language
A language whose syntax can be formally described using a finite state machine
Define finite state machine
An abstract model of computation made up of states and transitions
Define regular expression
A pattern used to search for a match within a string of text
How many starting states can a finite state machine have?
Exactly one
How many accepting states can a finite state machine have?
One or more
When an FSM models a regular language, what does a valid word correspond to?
A sequence of transitions (a path) that starts at the initial state and ends in an accepting state
What two properties must hold for a finite state machine to be deterministic?
(1) Every transition requires an event (a character is consumed); (2) from any state, reading a given character takes you to max one state (not multiple options)
precede
What does concatenation do in a regex, and what is its precedence?
Matches one regex immediately followed by another; precedence 5
What does | do in a regex, and what is its precedence? + fsm
Matches either string; precedence 6 (last)

What does [_] do in a regex, and what is its precedence? + fsm
Matches one single character contained in the brackets; precedence 2

What does [-] do in a regex, and what is its precedence?
Matches one single character from a contiguous range of ASCII characters; precedence 2
What does \_ do in a regex, and what is its precedence? + fsm
Treats the next character literally rather than as an operator; precedence 1 (first)

What does _? do in a regex, and what is its precedence? + fsm
Matches zero or one instances of the preceding character/group; precedence 4

What does _* do in a regex, and what is its precedence? + fsm
Matches zero or more instances of the preceding character/group; precedence 4

What does _+ do in a regex, and what is its precedence? + fsm
Matches one or more instances of the preceding character/group; precedence 4

What does (_) do in a regex, and what is its precedence?
Groups operations in order to make structure clearer or change the order of operations; precedence 3
What is the regex order of operations, first to last?
Escape (\)
brackets ([ ] and [ - ])
parentheses
quantifiers (? * +)
concatenation
alternation (|)
Which String methods from the String Processing video mutate the String they're called on?
None; Java Strings are immutable
Define serialization
Converting an object into a series of bytes
Define deserialization
Converting a series of bytes back into an object
What is the benefit of a standardized serialization format like CSV, YAML, XML, or JSON?
Programs written in different languages can read the serialized object
What is the internal representation of a JSONArray?
List<Object>
What is the internal representation of a JSONObject?
Map<String, Object>
When you build a JSONObject from a Java object (new JSONObject(obj)), what becomes its keys and values?
Its public getters: the key is the getter name without "get" with the first letter lowercased (getValueOfB → "valueOfB"), and the value is whatever the getter returns. Fields without getters are left out
What design patterns are creation patterns? (3)
singleton, factory, builder
What design patterns are structural patterns? (2)
composite, adapter
What design patterns are behavorial patterns? (3)
observer, strategy, visitor
What is the stack region of memory and what’s it?
What is the heap region of memory?
Where objects and arrays (longer-lasting data) are stored; as opposed to the stack, which holds local variable
not the heap data structure!
Where is a primitive-type field (NOT local variable, a field for an object) or array element stored?
Its value is stored directly inside the containing array/object (on the heap)
In reference counting, what does the runtime system do? (4)
Allocates extra space to store reference counts; executes the increment/decrement operations inserted by the compiler; when freeing an object, decrements the counts of its fields or elements; frees objects when their counts hit zero
pros + cons of reference counting
Easy to implement, quick reclamation, good performance
Self-referential garbage: an object that references itself directly or in a cycle never reaches a count of zero, so it's never freed
What is the basic idea of trace-based (mark-sweep/mark-compact) garbage collection?
Find and mark all objects reachable from the root set; everything unmarked is garbage
Allocates extra space to store a mark bit; periodically (implementation-dependent) finds and collects garbage