3_parsing
PARSING
Baishakhi Ray
Programming Languages & Translators
These slides are motivated from Prof. Alex Aiken: Compilers (Stanford)
▪
▪ Is it a valid token stream in C language?
▪ Is it a valid statement in C language?
Intro to Parsing
▪ Not every strings of tokens are
valid
▪ Parser must distinguish between
valid and invalid token strings.
▪We need
▪ A Language: to describe what is valid
string?
▪ A method: to determine membership
of inputs in this language.
Lexical Analysis
Parser
Semantic Analysis
Code Generation
Character stream
Token stream
Syntax trees
Syntax trees
Intro to Parsing
▪ Input: if(x==y) 1 else 2;
▪ Parser Input (Lexical Input):
KEY(IF) ‘(‘ ID(x) OP(‘==‘) ‘)’ INT(1) KEY(ELSE) INT(2) ‘;’
▪ Parser Output IF-THEN-ELSE
==
ID ID
=
INT
=
INT
Intro to Parsing
▪ Not every strings of tokens are
valid
▪ Parser must distinguish between
valid and invalid token strings.
▪We need
▪ A Language: to describe what is valid
string?
▪ Context Free Grammar
▪ Capture Language Syntax
▪ A method: to determine membership
of inputs in this language.
Lexical Analysis
Parser
Semantic Analysis
Code Generation
Character stream
Token stream
Syntax trees
Syntax trees
Context Free Grammar
▪ A CFG consists of
▪ A set of terminal T
▪ A set of non-terminal N
▪ A start symbol S (S N)
▪ A set of production rules
▪ X -> Y1…..YN
▪ X N
▪
▪ Ex: S -> ( S ) |
▪ N = {S}
▪ T = { ( , ) , }
𝜖
𝜖
Yi ϵ {N, T, ε}
𝜀
𝜀
Context Free Grammar
1. Begin with a string with only the start symbol S
2. Replace a non-terminal X with in the string by the RHS of some production rule:
X->Y1…..Yn
3. Repeat 2 again and again until there are no non-terminals
X1……Xi X Xi+1 …. Xn -> X1……Xi Y1…..Yk Xi+1 …. Xn
For the production rule X -> Y1…..Yk
α0 → α1 → α2 → α3 . . . → αn
α0
* αn, n ≥ 0
Context Free Grammar
▪ Let G be a CFG with start symbol S. Then the language L(G) of G is:
{a1 . . . ai . . . an |∀iai ∈ T ∧ S
* a1 . . . ai . . . an}
Context Free Grammar
▪ There are no rules to replace terminals.
▪ Once generated, terminals are permanent
▪ Terminals ought to be tokens of programming languages
▪ Context-free grammars are a natural notation for this recursive structure
Languages and Automata
▪ Formal languages are very important in programming languages
▪ Regular Languages
▪ Weakest formal languages that are widely used
▪ Many applications
▪ Many Languages are not regular
1
1
0
0
Automata that accept odd numbers of 1
How many 1s it has accepted?
Automata do not have any memory
– Only solution is duplicate state
Intro to Parsing
▪ Regular Languages
▪ Weakest formal languages that are widely used
▪ Many applications
▪ Consider the language {(i )i | i 0}
▪ (), (( )), ((( )))
▪ ((1 + 2) * 3)
▪ Nesting structures
▪ if .. if.. else.. else..
≥
Regular languages
cannot handle well
CFG: Simple Arithmetic expression
E ! E + E
| E * E
| ( E )
| id
Languages can be generated: id, ( id ), ( id + id ) * id, …
CFG: Exercise
Some Valid Strings are: aba, abcca, …
S → aXa
X → ε |bY
Y → ε |cXc
Derivation
▪ A derivation is a sequence of production
▪ S -> … -> … ->
▪ A derivation can be drawn as a tree
▪ Start symbol is tree’s root
▪ For a production X -> Y1….Yn, add children Y1….Yn to node X
▪ Grammar
▪ E -> E + E | E * E | (E) | id
▪ String
▪ id * id + id
▪ Derivation
E -> E + E
-> E * E + E
-> id * E + E
-> id * id + E
-> id * id + id
E
E
E
id
* E
id
+ E
id
Parse
Tree
Parse Tree
▪ A parse tree has
▪ Terminals at the leaves
▪ Non-terminals at the interior nodes
▪ An in-order traversal of the leaves is the original input
▪ The parse tree shows the association of operations, the input string does not
Parse Tree
▪ Left-most derivation
▪ At each step, replace the left-most non-
terminal
E -> E + E
-> E * E + E
-> id * E + E
-> id * id + E
-> id * id + id
▪ Right-most derivation
▪ At each step, replace the right-most non-
terminal
E -> E + E
-> E + id
-> E * E + id
-> E * id + id
-> id * id + id
Note that, right-most and left-most derivations have the same parse tree
Ambiguity
▪ Grammar
▪ E -> E + E | E * E | (E) | id
▪ String
▪ id * id + id
E
E
E
id
* E
id
+ E
id
E
E
id
* E
E
id
+ E
id
Ambiguity
▪ A grammar is ambiguous if it has more than one parse tree for a string
▪ There are more than one right-most or left-most derivation for some
string
▪Ambiguity is bad
▪ Leaves meaning for some programs ill-defined
Example of Ambiguous Grammar
▪ S->SS | a | b
Resolving Ambiguity
▪ Most direct way to rewrite the grammar unambiguously
id * id + id
E = E′ + E |E′
E′ = id * E′ | id | (E) * E′ | (E)
Resolving Ambiguity
▪ Impossible to convert ambiguous to unambiguous grammar automatically
▪ Instead of rewriting
▪ Use ambiguous grammar
▪ Along with disambiguating rules
▪ Eg, precedence and associativity rules
▪ Enforces precedence of * over +
▪ associativity: %left +
Abstract Syntax Trees
▪ A parser traces the derivation of a sequence of tokens
▪ But the rest of the compiler needs a structural representation of the
program
▪ Abstract Syntax Trees
▪ Like parse trees but ignore some details
▪ Abbreviated as AST
Abstract Syntax Trees
▪ Grammar
▪ E -> int | ( E ) | E + E
▪String
▪ 5 + (2 + 3)
▪After lexical analysis
▪ Int<5> ‘+’ ‘(‘ Int<2> ‘+’ Int<3> ‘)’
Abstract Syntax Trees: 5 + ( 2 + 3)
E
E
Int<5>
+ E
( E
E
Int<2>
+ E
Int<3>
)
Parse Trees
Abstract Syntax Trees: 5 + ( 2 + 3)
Parse Trees
• Have too much information
• Parentheses
• Single-successor nodes
E
E
Int<5>
+ E
( E
E
Int<2>
+ E
Int<3>
)
Abstract Syntax Trees: 5 + ( 2 + 3)
+
Int<5> +
Int<2>
Int<3>
Parse Trees AST
• ASTs capture the nesting structure
• But abstracts from the concrete syntax
• More compact and easier to use
• Have too much information
• Parentheses
• Single-successor nodes
E
E
Int<5>
+ E
( E
E
Int<2>
+ E
Int<3>
)
Error Handling
▪ Purpose of the compiler is
▪ To detect non-valid programs
▪ To translate the valid ones
▪ Many kinds of possible errors (e.g., in C)
Error Kind Example Detected by
Lexical Misspelling of identifiers, keywords, or
operators.
… $ … Lexer
Syntax Misplaced operators, semicolons,
braces, switch-case statements, etc.
… x*%… Parser
Semantic Type mismatches between operators
and operands
… int x; y =
x(3);…
Type Checker
Correctness Incorrect reasoning Using = instead
of ==
tester/user
Error Handling
▪ Error Handler should
▪ Discover errors accurately and quickly
▪ Recover from an error quickly
▪ Not slow down compilation of valid code
▪ Types of Error Handling
▪ Panic mode
▪ Error productions
▪ Automatic local or global correction
Panic Mode Error Handling
▪ Panic mode is simplest and most popular method
▪ When an error is detected
▪ Discard tokens until one with a clear role is found
▪ Typically looks for “synchronizing” tokens
▪ Typically the statement of expression terminators
▪ Example: delimiters (; }, etc.)
▪ Continue from there
Panic Mode Error Handling
▪ Example:
▪ (1 + + 2 ) + 3
▪ Panic-mode recovery:
▪ Skip ahead to the next integer and then continue
▪ Bison: use the special terminal error to describe how much input to skip
▪ E -> int | E + E | ( E ) | error int | ( error )
Normal mode Error mode
Error Productions
▪ Specify known common mistakes in the grammar
▪ Example:
▪ Write 5x instead of 5 * x
▪ Add production rule E -> .. | E E
▪ Disadvantages
▪ complicates the grammar
Error Corrections
▪ Idea: find a correct “nearby” program
▪ Try token insertions and deletions (goal: minimize edit distance)
▪ Exhaustive search
▪ Disadvantages
▪ Hard to implement
▪ Slows down parsing of correct programs
▪ “Nearby” is not necessarily “the intended” program
Error Corrections
▪ Past
▪ Slow recompilation cycle (even once a day)
▪ Find as many errors in once cycle as possible
▪ Disadvantages
▪ Quick recompilation cycle
▪ Users tend to correct one error/cycle
▪ Complex error recovery is less compelling
Parsing algorithm: Recursive Descent Parsing
▪ The parse tree is constructed
▪ From the top
▪ From left to right
▪ Terminals are seen in order of appearance in the token stream
Parsing algorithm: Recursive Descent Parsing
▪ Grammar:
▪ E -> T | T + E
▪ T -> int | int * T | ( E )
▪ Token Stream: ( int<5> )
▪ Start with top level non-terminal E
▪ Try the rules for E in order
E -> T | T + E
T -> int | int * T | ( E )
( int<5> )
Recursive Descent Parsing Example
E
T
int
mismatch: int does not match arrowhead (
backtrack
E -> T | T + E
T -> int | int * T | ( E )
( int<5> )
Recursive Descent Parsing Example
E
T
int * T
backtrack
E -> T | T + E
T -> int | int * T | ( E )
( int<5> )
Recursive Descent Parsing Example
E
T
( E )
Match! Advance input
E -> T | T + E
T -> int | int * T | ( E )
( int<5> )
Recursive Descent Parsing Example
E
T
( E )
Match! Advance input
T
int
E -> T | T + E
T -> int | int * T | ( E )
( int<5> )
Recursive Descent Parsing Example
Match! Advance input
E
T
( E )
T
int
𝐸→𝐸′ | 𝐸′+𝐸
𝐸′→−𝐸′ | 𝑖𝑑 | (𝐸)
Input: id + id
A Recursive Descent Parser. Preliminaries
▪ TOKEN be the type of tokens
▪ Special tokens INT, OPEN, CLOSE, PLUS, TIMES
▪ The global next point to the next token
A Top Down Parsing Algorithm
void A() {
Choose an A-production:
for (i=1 or k) {
if ( is a nonterminal)
Call ;
else if ( == current input TOKEN tok). /*terminal*/
next++;
else
/* Error */
}
}
A − > S1S2 . . . Sk;
Si
Si()
Xi
Recursion without
backtracking
A (Limited) Recursive Descent Parser
▪ Define boolean functions that check the token string for a match of
▪ A given token terminal
bool term (TOKEN tok) { return *next++ == tok; }
▪ The nth production of S:
bool Sn() { … }
▪ Try all productions of S:
bool S() { … }
A (Limited) Recursive Descent Parser
▪ For production E → T
bool E1() { return T(); }
▪ For production E → T + E
bool E2() { return T() && term(PLUS) && E(); }
▪ For all productions of E (with backtracking)
bool E() {
TOKEN *save = next;
return (next = save, E1( )) || (next = save, E2( ));
}
Grammar:
E -> T | T + E
T -> int | int * T | ( E )
A (Limited) Recursive Descent Parser (4)
▪ Functions for non-terminal T
bool T1() { return term(INT); }
bool T2() { return term(INT) && term(TIMES) && T(); }
bool T3() { return term(OPEN) && E() && term(CLOSE); }
bool T() {
TOKEN *save = next;
return (next = save, T1()) || (next = save, T2()) || (next = save, T3());
}
Grammar:
E -> T | T + E
T -> int | int * T | ( E )
Recursive Descent Parsing
▪ To start the parser
▪ Initialize next to point to first token
▪ Invoke E() (start symbol)
Example
Grammar:
E → T |T + E
T → int | int * T | ( E )
Input: ( int )
Code:
bool term(TOKEN tok) { return *next++ == tok; }
bool E1() { return T(); }
bool E2() { return T() && term(PLUS) && E(); }
bool E() {TOKEN *save = next;
return (next = save, E1()) || (next = save, E2()); }
bool T1() { return term(INT); }
bool T2() { return term(INT) && term(TIMES) && T(); }
bool T3() { return term(OPEN) && E() && term(CLOSE); }
bool T() { TOKEN *save = next;
return (next = save, T1())
|| (next = save, T2())
|| (next = save, T3()); }
E
T
( E )
T
int
Example
Grammar:
E → T |T + E
T → int | int * T | ( E )
Input: int
Code:
bool term(TOKEN tok) { return *next++ == tok; }
bool E1() { return T(); }
bool E2() { return T() && term(PLUS) && E(); }
bool E() {TOKEN *save = next;
return (next = save, E1()) || (next = save, E2()); }
bool T1() { return term(INT); }
bool T2() { return term(INT) && term(TIMES) && T(); }
bool T3() { return term(OPEN) && E() && term(CLOSE); }
bool T() { TOKEN *save = next;
return (next = save, T1())
|| (next = save, T2())
|| (next = save, T3()); }
When Recursive Descent Does Not Work
Grammar:
E → T |T + E
T → int | int * T | ( E )
Input: int * int
Code:
bool term(TOKEN tok) { return *next++ == tok; }
bool E1() { return T(); }
bool E2() { return T() && term(PLUS) && E(); }
bool E() {TOKEN *save = next;
return (next = save, E1()) || (next = save, E2()); }
bool T1() { return term(INT); }
bool T2() { return term(INT) && term(TIMES) && T(); }
bool T3() { return term(OPEN) && E() && term(CLOSE); }
bool T() { TOKEN *save = next;
return (next = save, T1())
|| (next = save, T2())
|| (next = save, T3()); }
Recursive Descent Parsing: Limitation
▪ If production for non-terminal X succeeds
▪ Cannot backtrack to try different production for X later
▪ General recursive descent algorithms support such full backtracking
▪ Can implement any grammar
▪ Presented RDA is not general
▪ But easy to implement
▪ Sufficient for grammars where for any non-terminal at most one production can
succeed
▪ The grammar can be rewritten to work with the presented algorithm
▪ By left factoring
Left Factoring
A -> I
▪ The input begins with a nonempty string derived from , we do not know whether to
expand A to .
▪ We can defer the decision by expanding A to A’.
▪ Then, after seeing the input derived from , we expand A’ to or (left-factored)
▪ The original productions become:
A -> , A’ -> I
𝛼𝛽1 𝛼𝛽2
𝛼
𝛼𝛽1 or 𝛼𝛽2
𝛼
𝛼 𝛽1 𝛽2
𝛼𝐴′ 𝛽1 𝛽2
When Recursive Descent Does Not Work
▪ Consider a production S → S a
bool S1() { return S() && term(a); }
bool S() { return S1(); }
▪ S() goes into an infinite loop
▪ A left-recursive grammar has a non-terminal S
S →+ Sα for some α
▪ Recursive descent does not work for left recursive grammar
Elimination of Left Recursion
▪ Consider the left-recursive grammar
S → S α | β
▪ S generates all strings starting with a β and followed by a number of α
▪ Can rewrite using right-recursion
S → β S’
S’ → α S’ | ε
More Elimination of Left-Recursion
▪ In general
S → S α1 | … | S αn | β1 | … | βm
▪ All strings derived from S start with one of β1,…,βm and continue with
several instances of α1,…,αn
▪ Rewrite as
S → β1 S’ | … | βm S’
S’ → α1 S’ | … | αn S’ | ε
General Left Recursion
▪ The grammar
S → A α | δ
A → S β
is also left-recursive because
S →+ S β α
▪ This left-recursion can also be eliminated
Announcement
▪ Midterm Next Wednesday (October 21)
▪ Lexical and Syntactic Analysis
Break Out Session
▪ S-> Aa | b
▪ A —> A c | S d |
▪ Remove Recursion.
ϵ
▪ S – > A a | b.
▪ A -> b d A’ | A’
▪ A’ -> cA’ | a d A’ | a | ϵ
Summary of Recursive Descent
▪ Simple and general parsing strategy
▪ Left-recursion must be eliminated first
▪ … but that can be done automatically
▪ Unpopular because of backtracking
▪ Thought to be too inefficient
▪ In practice, backtracking is eliminated by restricting the grammar
Predictive Parsers
▪ Like recursive-descent but parser can “predict” which production to use
▪ By looking at the next few tokens
▪ No backtracking
▪ Predictive parsers accept LL(k) grammars
▪ L means “left-to-right” scan of input
▪ L means “leftmost derivation”
▪ k means “predict based on k tokens of lookahead”
▪ In practice, LL(1) is used
LL(1) vs. Recursive Descent
▪ In recursive-descent
▪ At each step, many choices of production to use
▪ Backtracking used to undo bad choices
▪ In LL(1)
▪ At each step, only one choice of production
▪ That is
▪ When a non-terminal A is leftmost in a derivation
▪ The next input symbol is t
▪ There is a unique production A → α to use
▪ Or no production to use (an error state)
▪ LL(1) is a recursive descent variant without backtracking
Predictive Parsing and Left Factoring
▪ Recall the grammar
E → T + E | T
T → int | int * T | ( E )
▪ Hard to predict because
▪ For T two productions start with int
▪ For E it is not clear how to predict
▪We need to left-factor the grammar
Left-Factoring Example
▪ Grammar
E → T + E | T
T → int | int * T | ( E )
▪ Factor out common prefixes of productions
E → T X
X → + E | ε
T → ( E ) | int Y
Y → * T | ε
LL(1) Parsing Table Example
▪ Left-factored grammar
E → T X
X → + E | ε
T → ( E ) | int Y
Y → * T | ε
▪ The LL(1) parsing table:
Left-most
non-
terminals
next input tokens
int * + ( ) $
E TX TX
X +E ε ε
T int Y ( E )
Y *T ε ε ε
LL(1) Parsing Table Example (Cont.)
▪ Consider the [E, int] entry
▪ “When current non-terminal is E and next input is int, use production
E → T X”
▪ This can generate an int in the first position
▪Consider the [Y,+] entry
▪ “When current non-terminal is Y and current token is +, get rid of Y”
▪ Y can be followed by + only if Y → ε
LL(1) Parsing Tables. Errors
▪ Blank entries indicate error situations
▪ Consider the [E,*] entry
▪ “There is no way to derive a string starting with * from non-terminal
E”
Using Parsing Tables
▪ Method similar to recursive descent, except
▪ For the leftmost non-terminal S
▪ We look at the next input token a
▪ And choose the production shown at [S,a]
▪ A stack records frontier of parse tree
▪ Non-terminals that have yet to be expanded
▪ Terminals that have yet to match against the input
▪ Top of stack = leftmost pending terminal or non-terminal
▪ Reject on reaching error state
▪ Accept on end of input & empty stack
First & Follow
▪ During top down parsing, FIRST and FOLLOW allow us to choose which production to
apply, based on the next input symbol.
▪ FIRST( ), is any string of grammar symbols
▪ A set of terminals that begin strings derived from .
▪ If , then is in FIRST( ).
▪ if , the c is in FIRST( ).
▪ FOLLOW(A), A is a nonterminal
▪ the set of terminals that can appear immediately to the right of A.
▪ A set of terminals “a” such that S for some and .
𝛼 𝛼
𝛼
𝛼 ∗ 𝜖 𝜖 𝛼
𝛼 ∗ 𝑐𝑌 𝛼
∗ 𝛼𝐴𝑎𝛽 𝛼 𝛽
Constructing Parsing Tables: The Intuition
▪ Consider non-terminal A, production A → α, & token t
▪ T[A,t] = α in two cases:
▪ If α →* t β
▪ α can derive a t in the first position
▪We say that t ∈ First(α)
▪ If A → α and α →* ε and S →* β A t δ
▪ Useful if stack has A, input is t, and A cannot derive t
▪ In this case only option is to get rid of A (by deriving ε)
▪We say t ∈ Follow(A)
First Sets. Example
▪ grammar
E → T X
X → + E | ε
T → ( E ) | int Y
Y → * T | ε
▪ First sets : Breakout room
First( ( ) = { ( }
First( ) ) = { ) }
First( int) = { int }
First( + ) = { + }
First( * ) = { * }
First( E ) = ?
First ( T ) = ?
First( X ) = ?
First( Y ) = ?
Computing Follow Sets
▪ Definition:
Follow(X) = { t | S →* β X t δ }
▪ Intuition:
▪ If X → A B then First(B) ⊆ Follow(A) and
Follow(X) ⊆ Follow(B)
▪ If B →* ε then Follow(X) ⊆ Follow(A)
▪ If S is the start symbol then $ ∈ Follow(S)
Follow Sets. Example
▪ Recall the grammar
E → T X X → + E | ε
T → ( E ) | int Y Y → * T | ε
▪ Follow sets
Follow( + ) = { int, ( }
Follow( ( ) = { int, ( } Follow( E ) = {), $}
Follow( * ) = { int, ( } Follow( T ) = {+, ) , $}
Follow( ) ) = {+, ) , $} Follow( Y ) = {+, ) , $}
Follow( int) = {*, +, ) , $}. Follow( X ) = {$, ) }
Constructing LL(1) Parsing Tables
▪ Construct a parsing table T for CFG G
▪ For each production A → α in G do:
▪ For each terminal t ∈ First(α) do
▪ T[A, t] = α
▪ If ε ∈ First(α), for each t ∈ Follow(A) do
▪ T[A, t] = α
▪ If ε ∈ First(α) and $ ∈ Follow(A) do
▪ T[A, $] = α
LL(1) Parsing Table Example
▪ Left-factored grammar
E → T X
X → + E | ε
T → ( E ) | int Y
Y → * T | ε
▪ The LL(1) parsing table:
Left-most
non-
terminals
next input tokens
int * + ( ) $
E TX TX
X +E ε ε
T int Y ( E )
Y *T ε ε ε
Rules:
For each production A → α in G do:
For each terminal t ∈ First(α) do
T[A, t] = α
If ε ∈ First(α), for each t ∈ Follow(A) do
T[A, t] = α
If ε ∈ First(α) and $ ∈ Follow(A) do
T[A, $] = α
Follow( + ) = { int, ( }
Follow( ( ) = { int, ( } Follow( E ) = {), $}
Follow( * ) = { int, ( } Follow( T ) = {+, ) , $}
Follow( ) ) = {+, ) , $} Follow( Y ) = {+, ) , $}
Follow( int) = {*, +, ) , $}. Follow( X ) = {$, ) }
Left-most
non-
terminals
next input tokens
int * + ( ) $
E TX TX
X +E ε ε
T int Y ( E )
Y *T ε ε ε
E → T X
X → + E | ε
T → ( E ) | int Y
Y → * T | ε
If ε ∈ First(α), for each t ∈ Follow(A) do
T[A, t] = α
Notes on LL(1) Parsing Tables
▪ If any entry is multiple defined then G is not LL(1) [Eg: S->Sa|b]
▪ If G is ambiguous
▪ If G is left recursive
▪ If G is not left-factored
▪ other: e.g., LL(2)
▪ Most programming language CFGs are not LL(1)
▪ too weak
▪ However they build on these basic ideas
Bottom-Up Parsing
▪ Bottom-up parsing is more general than (deterministic) top-down parsing
▪ just as efficient
▪ Builds on ideas in top-down parsing
▪ Bottom-up parsers don’t need left-factored grammars
▪ Revert to the “natural” grammar for our example:
E → T + E | T
T → int * T | int | (E) •
▪ Consider the string: int * int + int
Bottom-Up Parsing
▪ Revert to the “natural” grammar for our example:
E → T + E | T
T → int * T | int | (E) •
▪ Consider the string: int * int + int
▪ Bottom-up parsing reduces a string to the start symbol by inverting productions:
int * int + int T → int
int * T + int T → int * T
T + int T → int
T + T E → T
T + E E → T + E
E
Observation
▪ Read the productions in reverse (from bottom to top)
▪ This is a rightmost derivation!
int * int + int T → int
int * T + int T → int * T
T + int T → int
T + T E → T
T + E E → T + E
E
Bottom-Up Parsing
▪ A bottom-up parser traces a rightmost derivation in reverse
int * int + int T → int
int * T + int T → int * T
T + int T → int
T + T E → T
T + E E → T + E
E
L, R, and all that
▪ LR parser: “Bottom-up parser”
▪ L = Left-to-right scan, R = Rightmost derivation
▪ RR parser: R = Right-to-left scan (from end)
▪ nobody uses these
▪ LL parser: “Top-down parser”:
▪ L = Left-to-right scan: L = Leftmost derivation
▪ LR(1): LR parser that considers next token (lookahead of 1)
▪ LR(0): Only considers stack to decide shift/reduce
▪ SLR(1): Simple LR: lookahead from first/follow rules Derived from LR(0) automaton
▪ LALR(1): Lookahead LR(1): fancier lookahead analysis Uses same LR(0) automaton as SLR(1)