Top-down parsing, Bottom-up parsing

Top-down parsing(=Recursive descent Parsing)

정의 : 트리의 맨위에서부터 차례로 파싱

LL(1) Parsing : LL이란 'Left to Right' 와 'Leftmost Derivation'의 앞글자를 딴것이다, (1)은 'lookahead가 한개'를 의미한다.
backtracking이 발생하지 않도록 하려면, 뒤에 올문자를 예측할 수 있는 parsing table을 만들면 된다.


Bottom-up parsing

정의 : 트리의 맨아래에서부터 차례로 파싱

SLR(1) = simple LR : LR(0)와는 달리 완료 아이템일때 무조건 reduce 하는것이 아니라, 완료 아이템(예:A->r.)이면서 lookahead가 Follow(A)에 포함될 때에만 reduce

LALR(1) = Look Ahead LR : LR(0) item은 같지만 ,lookahead만 다른 state가 많은데, 이러한 state를 통합하여 LR(0)의 DFA와 같은 모양을 만될되, 다른점은 lookahead set이 추가로 표현된다는 점이다.

LR(1) Parsing : LR이란 'Left to Right'와 'Right-most Derivation의 역순' 그리고 (1)은 'lookahead가 한개'를 의미한다.

*Handle

정의 : viable prefix가 production의 right hand side와 일치할경우, viable prefix와 production rule이 handle이 된다. (예를들어, E->n+n이라는 production이 있을때, handle은 "n+n"과 "E->"n+n"이 된다.