Scanning, LL Parsing, LR Parsing Flashcards
What do the following mean with regards to regular expressions:
- Token
- Alphabet
- Epsilon
The arrow in regular expressions means?
Can be
What is the precedence order for the following in regular expressions:
|
.
*
What is a CFG?
A CFG is a Context Free Grammar
What is a CFG derivation?
A production from a CFG, what can be replaced in the LHS of a sentence (non-terminals) with RHS non-terminals and terminals as productions.
Note in the following example how expr is replaced
What does a parse tree do?
Represents a derivation graphically
What is the difference between right-most derivation and left-most derivation?
When a grammar can have two parse trees for the same sentence, what is it called?
Ambiguous grammar
What is an ambiguous grammar?
When there can be two difference parse trees for the same grammar
What is lexical analysis
Scanning:
Tokenizing the source code
Removing comments
Saving text of identifiers, numbers, strings
Saving source locations
What is ad-hoc
Ad-hoc simply means it was created by a human for the specific purpose of what it is being used for
What is a DFA? What does it mean? What do they look like?
A DFA is a deterministic finite automaton which means each state goes to one other state based on its current state and input.
What is a NFA? What do they look like?
How do you construct DFA from regular expressions?
Build NFA from regular expressions
Convert to DFA
Minimize DFA
Examine this NFA example:
Examine the following example for minimizing an NFA to DFA, dont move on until you understand
What is the “longest-possible token” rule?
Return only when the next character cannot continue the current token
What is look-ahead?
How many characters you need to look forward to deterine the production being used
Examine the following table-driven scanner:
What is parsing?
What is the difference between LL and LR parsing?
Is LL parsing top-down or bottom-up?
Top-down
Is LR parsing top-down or bottom-up
Bottom-up
Top-down parsers are also called ____, the employ _____
Top-down parsers are also called LL parsers, the employ recursive descent
LL / top-down parsers are ____ ____
Table driven
A prediction in L parsing is based on
The current state and the input token
With a current state and a given input token, a LL parser can take the following actions:
- match a terminal
- predict a production
- Announce a syntax error
Examine the following LL(1) parse table and understand what it means FULLY
Review the following LL(1) parse stack and how it works
How do you construct First(a) and Follow(A)?
What are some common problems with making a grammar LL(1)? What are their fixes?
Is there a LL(1) grammar for the dangling-else problem?
NO
What is the premise of an LR parser?
Read from input until you find a RHS, continue until you have fully reduced
Examine how the dot productions work with LR parsing:
Examine the following LR parse table:
Examine the following parse table:
Examine the following LR parse stack
What is a shift/reduce conflict?
What are two SLR conflicts?
Examine the following for LL Left-recursion elimination:
