1. LL Parsing(Left Leftmost derivation) : 왼쪽에서 시작하며 좌측유도 방식으로 파싱
- ANTLR에서 사용
- TopDown 방식이다
- Example
규칙은 아래의 3가지
1) S -> C
2) S -> ( S * C )
3) C -> n
입력 문자열 : ( n * n )
파싱은 다음과 같은 순서로 진행된다.
1. S 초기상태
2. ( S * C ) 규칙 2 적용
3. ( C * C ) 규칙 1 적용
4. ( n * C ) 규칙 3 적용
5. ( n * n ) 규칙 3 적용
2. LR Parsing(Left Rightmost derivation) : 왼쪽에서 시작하며 우측유도 방식으로 파싱
- Yacc, Bison에서 사용
- BottomUp 방식이다.
- Example
위 LL Parsing 예제의 문법과 입력 문자열이 동일할 때 다음과 같은 차이가 있다.
Parse Stack input action
( n * n ) shift
( n * n ) shift
( C * n ) 규칙 3
( C * n ) shift
( C * C ) 규칙3
( S * C ) 규칙1
S 규칙2
LL 방식은 TopDown 답게 큰 그림을 미리 그려놓고 채워 놓는 방식 LR 방식은 BottomUp 답게 작은 그림들을 만들어 놓고 합쳐준다.