LL, LR, LALR, GLR ...

• Top-down parser

Beginning with the start symbol, try to guess the productions to apply to end up at the user's program. An example from this slide is shown below

 


First it starts from E and guesses "E --> T + E" to apply, then "T --> int", and "E --> T", " T -> (E)", "E --> T + E", "T --> int", "E --> T", finally "T --> int"


•  LL(1) 
• first 'L' - read the input from left to right.
• second 'L' - descend into parse tree children from left to right (Leftmost derivation).
• 1 - a single lookahead token 
• Predict/match parser

• LL(2)
• 2 - two lookahead tokens

• Bottom-Up parser

Beginning with the user's program, try to apply productions in reverse to convert the program back into the start symbol. Another example from this slide is illustrated.

 

 Start from "int + (int + int + int)", apply the reverse of the production "T -> int": "int -> T" and get 

• int -> T :           T + (int + int + int)
• T -> E:              E + (int + int + int)
• int -> T:            E + (T + int + int)
• T -> E:              E + (E + int + int)  
• int -> T:            E + (E + T + int)
• E + T -> E:       E + (E + int)
• int -> T:            E + (E + T)
• E + T -> E:       E + (E)
• (E) -> T:           E + T
• E + T -> E:       E

• SLR
• Simple LR(1)
• LR(0), LR(1), LR(k)...
• first 'L' - read the input from left to right.
• second 'R' - reversed Rightmost derivation.
• 1 - a single lookahead token 
• LR(1) is very powerful
•  LALR
• Look-Ahead LR parser is a variant of LR
• LALR(1): Look-Ahead (1) LR(0)

•  GLR
• generalized LR: an extension of LR
• handle nondeterministic and ambiguous grammars

• Shift/reduce parser 
• A parsing method for LR parser
• Split input stream into two substrings: only process left substring and right substring is unseen.
• Shift: move the separate bar in the input stream by one token (left to right)
• Reduce: apply productions to left substring to get a new parser tree
• Shift/Reduce conflict: an error where a shift/reduce parser cannot tell whether to shift a token or perform a reduction.
• Often happens when two productions overlap.
• Reduce/Reduce conflict: an error where a shift/reduce parser cannot tell which of many reductions to perform.
• Often the result of ambiguous grammars.
• Reference: this slide and this video