Bottom-Up Parsing

Created

Created

2022 Oct 25 2:0

Editor

Editor

Seonglae Cho

Creator

Creator

Seonglae Cho

Edited

Edited

2022 Oct 27 23:53

Refs

Refs

Top-down Parsing

Reduce a parse tree bottom up, from the leaf nodes

followed by a series of shift and reduce actions

Left Recursion으로 인한 infinite loop가 발생하지 않는다

결과로부터 뿌리를 찾는 것이기 때문에 다음에 무엇이 나올지에 대해서 고민하지 않아도 되는 것

DFA 만들때 뒤에 nonterminal 있으면 그거 재생성까지 고려해서 recursive하게

Shift a terminal from the front of the input to the stack top

Reduce the stack top ⍺ to A, based on the rule A à ⍺ until parsing stack has only start symbol

Bottom-Up Parsers

Bottom-Up Parsing Notion

Botton-up Parsing Reduction

Right Sentential Form

Botton-up Parsing Handle

[Compiler] Bottom-Up Parsing

이번에 다룰 내용은 Bottom up Approach를 통해서 Parsing하는 Bottom up Parsing이다. 말 그대로 아래에서 위로, leaves에서 root를 찾아가는 방식이다. 그런데 사실 다른 compiler의 내부 구조는 거진 Top Down이 아닌 Bottom up 방식으로 구현되어 있다. 사실 Top Down 방식에서 직관적으로 봤을 때 가장 풀기 어려웠던 점이 무엇인지를 생각해보자.

[Compiler] Bottom-Up Parsing

https://talkingaboutme.tistory.com/entry/Compiler-Bottom-Up-Parsing

[Compiler] Bottom-Up Parsing

Recommendations

///////////