chapter 5 Flashcards
…………….is the set of tokens that can occur first in sentences derived from g :
FIRST(g) = {t ∈ T | g =>* t d
FIRST
What does it mean if there is a collision in an LL(1) table?
A collision means two rules in the same cell.
This means the grammar is not LL(1).
Why can it be useful to add an end-of-file rule to some grammars?
To know where the input ends.
handle empty input and determine when to accept.
How can we decide if a grammar is LL(1) or not?
f the LL(1) table has no collisions, it is LL(1).
If there are conflicts, it is not LL(1).
………X can become empty (ε).
Nullable
………….First token that can appear in a string derived from X.
FIRST
………..Tokens that can come after X in any valid sentence.
FOLLOW
What is a fixed-point problem?
A problem where we want to find x = f(x).
We keep applying f until the value doesn’t change anymore.
Left Recursion:
Happens when a non-terminal refers to itself on the left side.
Common Prefix:
Two rules start with the same tokens.
A grammar that allows more than one parse tree.
Ambiguous Grammar
Why it’s not LL(1):
LL(1) must have only one entry per cell in the parsing table.
A grammar with a common prefix is not LL(1).
Might be LL(k), but not guaranteed.
done
No Conflict Meaning:
A grammar is LL(1) if the parsing table has no cell with more than one rule.
Nullable(g) is true if g can derive ε (empty string).
Nullable Definition:
Where ε Appears:
In the production: Y -> ε
Push current token to stack, read next
Shift
Replace RHS with LHS rule in stack
Reduce
Parsing is complete
Accept
LR(1) Parsing:
Uses DFA to decide actions: shift, reduce, accept
Shift-Reduce Conflict:
Parser can’t decide between shift and reduce
Reduce-Reduce Conflict:
Parser can’t decide between two reduce rules
Example: A -> B | C, both can reduce at same time
LR Parser Types:
LR(0): No lookahead
SLR: Uses FOLLOW to reduce
LALR(1): Merges similar states (used in practice)
LR(1): Full lookahead, large table
GLR: Parses all CFGs, handles ambiguity
Fix Conflicts
Use operator precedence rules:
- has higher priority than +
Left-associative → reduce first
Right-associative → shift first
