Top-down Parsing

Created

Created

2022 Oct 7 4:6

Editor

Editor

Seonglae Cho

Creator

Creator

Seonglae Cho

Edited

Edited

2022 Oct 26 23:16

Refs

Refs

Bottom-Up Parsing

Derive a parse tree top down, from the start nonterminal

grammar라는게 가지치기를 통해서 여러 방향으로 뻗어나갈 수 있는 건데 Top Down 방식에서는 선택이 맞는지 틀린지를 직접 해보고 path를 결정할 수 있는 것

코딩하기도 쉽고, 코드의 크기도 작다는 장점이 있지만 left recursion이나 Backtracking으로 인한 resource 낭비가 너무 심하다

Top Down 방식에서는 이를 해결하기 위해서 Left Factoring이라는 방법을 제시하지만 이때 새로운 nonterminal을 생성해야 되서 조금 복잡한 경향

Top-down Parsers

Backtracking Parser

Predictive Parser

[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

///////////