[소소하게2] 9월 23일 소소한 공부

컴파일러 싸강들었다!

 

Bottom-up = 우파스 = 우측유도의 역순

생성규칙의 rhs와 매치되면 lhs로 바꾼다.

Top-dowm보다 좋음.(backtracking 없음)

생성규칙 선택을 더 많은 token이 들어올 때까지 미룰 수 있다.

left-recursive 문법도 파싱가능.(top-down은 못함)

LR(K) : Right-most 유도. 파스트리를 post-order로 순회 및 생성.

S => => 의 과정이 있을 때 를 문장형태 의 handle이라 함.

같은 문장 형태에서 서로 다른 두 개 이상의 handle이 존재하면 모호하다.

Shift : 주어진 입력을 stack으로 옮긴다.

reduce : 스택 top에 있는 handle 를 non-terminal X로 바꾸기. (X-> )

결정적으로 파싱하기 위해 파서 상태를 사용한다.

(shift할지 reduce할지 결정. 스택 top 중 얼만큼을 떼어 handle로 볼건가 결정)

Terminals Non-terminals

파서상태 다음 action + 다음 상태 다음 상태

Action table Goto table

LR(0)파서 : lookahead없이 파싱. shift-reduce형태

LR Conflict : 파싱 테이블에 shift-reduce나 reduce-reduce 가 있으면 모호한 문법

우선순위로 conflict 제어, 먼저 reduce되면 트리의 아래층에 위치.(우선 순위 높음)

reduce-reduce : 생성 규칙 간의 우선순위로 제어.

shift-reduce : reduce할 생성 규칙의 우선순위가 입력 토큰보다 높으면 reduce

좌측 결합 : reduce. 생성규칙 > 입력 토큰

우측 결합 : shift. 생성규칙 < 입력 토큰