Use of Stack

Use stack to save statements

Four Actions of Shift-Reduce Parser

• Shift : Shift the current input onto the stack and go to the specified next state s.
• Reduce : Given the production r : A -> b, remove enough items from the stack to match b, produce output structure from those items, and put the resulting structure A back on the stack. The next state is found from the goto table.
• Accept : Parsing is completed! return top of stack as result.
• Error : The input cannot be parsed according to the grammar; call an error recovery routine. Error entries are denoted by blanks in the parsing table.

Relationship to Canonical Derivation

x

How Parse Tree is Constructed Using Shift-Reduce Parser

Conflicts

• Reduce/reduce: resolved by choosing the first listed production
• Shift/reduce: resolved in favor of shift
  Reduce if the precedence of the production is greater than that of the terminal or if they are equal and the associativity of the production is left.
• reduce의 결과가 터미널의 결과보다 우선순위가 높을 때.
• 만약 그 결과들이 같으면 associativity는 왼 쪽.
  Shift otherwise.

Citation:

• Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools
• UT Austin CS375: Compilers by G.Novak.