| Term |
Focus in the course |
|
Formal language
Links to an external site.
|
Definition, operations on languages |
|
Regular expression
Links to an external site.
|
Describing sets of words using regular expressions, converting DFAs to regular expressions |
|
Deterministic finite automaton (DFA)
Links to an external site.
|
Definition, accepting/not accepting input strings, converting between DFAs and regular expressions |
|
Regular language
Links to an external site.
|
Expressive power, properties, operations on regular languages, limitations |
|
Context-free grammar
Links to an external site.
|
Definition, derivations, usage for general-purpose programming languages, parse trees, ambiguous grammars |
|
Lexical analysis
Links to an external site.
|
Goals, input/output, tokens |
|
Recursive Descent Parsing
Links to an external site.
|
Parser construction based on grammar, properties of recursive descent parsers |
|
Deterministic Push-Down Automaton (DPDA)
Links to an external site.
|
Definition, accepting/not accepting input strings, relationship between context-free grammars and DPDAs |
|
LL grammar
Links to an external site.
|
Definition |
|
Deterministic context-free grammar
Links to an external site.
|
Definition |
|
Parser generator
Links to an external site.
|
Definition, examples |