Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
11 Cards in this Set
- Front
- Back
Grammar
|
Describes the structure of strings/ a set of productions
|
|
Regular Set
|
If a grammar G is a regular expression, then language L(G) is a regular set
|
|
Fundamental Equivalence associated with Regular Sets
|
For every regular set L(G), there exists a DFA that accepts a string S iff S belongs to L(G)
|
|
DFA rules
|
Finite #states,
Exactly one starting state One or more final states (final state is indicated by double border) |
|
Deterministic Quality of DFAs
|
For each state and each input, there exists only one transition.
|
|
Syntax Analysis
|
Discovery of Program Structure
|
|
Syntax Specification
|
Context-free Grammars
|
|
Syntax Recognition
|
How can a compiler discover
if a program conforms to the specification?...LL and LR parsers |
|
Context-free vs. Lexical Grammar
|
In context free grammar, terminal symbols are tokens, not individual characters
|
|
BNF
|
::=
<expr> | space for concatenation |
|
Purpose of Parser
|
construct the parse tree
that corresponds to the input token stream. |