[컴파일러] 3-1. 구문분석기 구조

구문분석이란

어휘분석기 단계에서의 output인 Token을 가지고 문법 구조를 해석하여 키워드, 식별자, 연산자 등이 유효한 구조를 형성하였는가를 확인하고, 올바르다면 구문 분석 트리를 출력하고, 올바르지 않다면 Error를 출력한다

 

파서 동작방식

하향식 파싱(Top Down parsing)
최상위 노드(Root 또는 Start Symbol)에서 말단 노드(Leaves 또는 단위 String)까지 파싱하는 방법
RD Parser(recursive descent parser), predictive parser 등이 있다.


상향식 파싱(Bottom Up parsing)
말단 노드(Leaves)를 결합하여 최상위 노드(Root) 까지 파싱
precedence parser, shift-reduce parser 등이 있다.

 

 

구문분석기 최종 OUTPUT 단계

1. Parse

Top-down으로 할 시 left parse, Bottom up으로 할 시 right parse가 된다

2. Parse Tree

생성 규칙에 따라 parse Tree를 생성한다.

3. AST(Abstract syntax tree)
Parse Tree를 좀 더 효율적으로 변형시킨 Tree로 필요없는 정보들을 제외하고 OUTPUT을 결정한다.