본문 바로가기
이론/컴파일러

LL Parsing과 LR Parsing

by 사과잼빵 2018. 6. 27.

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 답게 작은 그림들을 만들어 놓고 합쳐준다.