컴파일러 만들기 2부

스캐너(scanner)와 파서(parser)

컴파일러를 만들때, 어휘분석을 위해서 스캐너(scanner)가 필요하고, 어휘분석을 통해 만들어진 토큰(token)열을 구문분석 하기 위해서는 파서(parser)가 필요합니다.

이러한 스캐너와 파서를 일일이 직접 작성하는 일은 만만치가 않습니다. 아마도 정규표현식으로 도배가 되어, 나중에는 어디가 어딘지 분간이 안되겠지요. "여긴 어딘가. 나는 누구인가?"

이런 이유로 스캐너(scanner)와 파서(parser)를 자동으로 생성해 주는 제너레이터(generator)가 있으면 참 편리할 것입니다.

그리고 예상하셨겠지만, 이런 제너레이터(generator)가 이미 존재합니다.

각각을 스캐너 제너레이터(scanner generator), 파서 제너레이터(parser generator)라고 부릅니다.

그런데, 실제로 스캐너 제너레이터(scanner generator) 라는 말 대신 어휘 분석기 제너레이터(lexical analyzer generator) 라고 더 많이 쓰는 것 같습니다. 그리고 이 어휘분석기 제너레이터는 줄여서 렉서 제너레이터(lexer generator)라고 합니다.

어찌되었건, 렉서 제너레이터(lexer generator)는 일반적으로 대부분 비슷합니다. 이에 반해, 파서 제너레이터(parser generator)는 몇 가지 타입으로 나누어 집니다.

LL 파서 제너레이터 (지원문법이 비교적 적음 / 속도 비교적 빠름)

http://en.wikipedia.org/wiki/LL_parser#Concrete_example

LR 파서 제너레이터 (지원문법이 넓음 / 속도 느림)

http://en.wikipedia.org/wiki/LR_parser#Concrete_example

Canonical LR 파서 제너레이터 (지원문법이 넓음 / 속도 느림)

http://en.wikipedia.org/wiki/Canonical_LR_parser

LALR 파서 제너레이터 (지원문법이 비교적 넓음 / 속도는 평균적)

http://en.wikipedia.org/wiki/LALR_parser

각 파서(parser)마다 파싱하는 방식이 다르기 때문에, 취급할 수 있는 문법의 범위와 속도가 달라집니다.

자세한 내용은 아래에서 다시 설명하도록 하겠습니다.

렉서 제너레이터(lexer generator)와 파서 제너레이터(parser generator)의 종류는 많이 있습니다.

각 렉서 제너레이터(lexer generator), 파서 제너레이터(parser generator)마다 생성하는 파서의 언어와 취급하는 파서 제너레이터 타입이 다르므로,  자신의 상황에 맞게 적절히 사용하면 될 것 같습니다.

개인적으로 제가 학교 다닐때, 컴파일러 수업에서 사용했던 렉서 제너레이터(lexer generator)로는 렉스(Lex)라는 녀석을 사용했습니다. 그리고 파서 제너레이터(parser generator)로는 YACC(Yet Another Compiler Compiler)였던걸로 기억합니다.

YACC 는 생성하는 파서의 언어는 C 이고, 취급문법은 LALR(1) 이라고 하네요.

이쯤되면, 어휘 분석기 제너레이터(lexical analyzer generator)는 뭐고 파서 제너레이터(parser generator)는 뭐고 파서랑 무슨관계고, 정신이 없으신 분들이 게실것 같습니다.

정리를 해 드리면 간단합니다.

우리가 정의한 언어의 어휘분석(lexical analysis)과 구문분석(syntax analysis)을 해야 합니다.

그러기 위해서는 어휘분석을 해 주는 어휘분석기가 필요합니다.

이를 스캐너(scanner) 라고 부릅니다.

그리고 구문분석을 해 주는 구문분석기가 필요합니다.

이를 파서(parser)라고 부릅니다.

그런데, 문제는 이런 렉서(lexer)와 파서(parser)를 일일이 직접 코딩해서 만드는건 너무나 힘이 듭니다.

양이 방대하고 복잡합니다. 실수가 생길수 밖에 없지요.

그렇기 때문에, 이 스캐너(scanner)와 파서(parser) 소스코드를 자동으로 생성해 주는 제너레이터(generator)라는 녀석을 사용하는 것입니다. 이를 각각 렉서 제너레이터(lexer generator)와 파서 제너레이터(parser generator) 라고 합니다.

즉, 스캐너(scanner)와 파서(parser)의 소스코드를 자동으로 만들어 주는 프로그램인 것입니다.

참고로 왜 스캐너 제너레이터(scanner generator) 라고 안하고 렉서 제너레이터(lexer generator)라고 하는지는 저도 모르겠습니다. 괜히 헷갈리게 말이죠...

LL 파서(LL pasrser)

---

LL parser 는 자유문맥문법(context-free grammars)의 일부분을 지원합니다.

관련 공부를 하셨던 분들은 기억이 새록새록 날거에요.

잠깐 LL 이 의미를 살펴보고 넘어가죠.

Left to right : 입력 문자열을 왼쪽에서부터 오른쪽으로 파싱

Leftmost derivation : 좌측 유도방식

무슨 말인지 잘 이해가 안 갑니다. 하지만 걱정할 필요가 없습니다.

예제를 보면 금방 이해하게 될거니까요. :)

예제

Grammars

  1. S -> F

  2. S -> ( S + F )

  3. F -> a

문법이 위와 같다고 가정합니다.

그리고 입력 문자열 ( a + a ) 를 파싱해 보도록 하겠습니다.

초기 스택은 아래와 같습니다. 시작은 S 로 표시하고, 끝은 $ 로 표시합니다.

S $

이제 파싱을 해 봅시다.

S 는 (a + a) 겠지요.

( 가 있으니, 두번째 문법에 적용됩니다.

S -> (S + F) 인 셈이죠.

즉, (S + F) 가 (a + a) 인 것입니다.

괄호는 문자(Literal)이므로 상쇄됩니다.

이런 식으로 진행되는데, == 를 기점으로, 좌측은 스택, 우측은 입력 문자열을 표현해 내려가면..

S $ == ( a + a )

( S + F ) $ == ( a + a )

S + F ) $ == a + a )

F + F ) $ == a + a )

a + F ) $ == a + a )

+ F ) $ == + a )

F ) $ == a )

a ) $ == a )

) $ == )

$ == 

$

이렇게 문자열의 좌측부터 우측으로 파싱을 진행해 나갑니다.

그러면, 과연 Leftmost derivation 이란 무슨 의미일까요?

간단히 말하면, 좌측부터 변형해 나간다는 의미입니다.

Grammars

1. S -> S + S

2. S -> 1

3. S -> a

Input String

1 + 1 + a

문법과 입력 문자열이 위와 같다고 생각해 봅시다.

한번 파싱해 보도록 하죠

S $ -> S + S $ // 규칙 1을 적용

S + S $ -> ???

S + S 중에서 어느쪽에 있는 S 를 먼저 규칙적용 해야 할까요??

좌측인가요? 우측인가요?

이때, 좌측부터 하게되면 다음과 같이 됩니다.

S + S $ -> 1 + S $

1 + S $ -> 1 + S + S $

1 + S + S $ -> 1 + 1 + S $

1 + 1 + S $ -> 1 + 1 + a $

이것이 바로, Leftmost derivation 방식입니다.

반대로, 우측부터 하게되면 다음과 같습니다.

S + S $ -> S + a $

S + 1 $ -> S + S + a $

S + S + a $ -> S + 1 + a $

S + 1 + a $ -> 1 + 1 + a $

이런 방식이, Rightmost derivation 방식입니다.

Leftmost derivation 방식에 의해 만들어진, 구문트리(syntax tree)는 아래와 같은 모양을 합니다.

           S
          /|\
         / | \
        /  |  \
       S  '+'  S
       |      /|\
       |     / | \
      '1'   S '+' S
            |     |
           '1'   'a'

반면, Rightmost derivation 방식에 의해 만들어진, 구문트리(syntax tree)는 아래와 같은 모양을 하게 됩니다.

           S 
          /|\
         / | \
        /  |  \
       S  '+'  S
      /|\      |
     / | \     |
    S '+' S   'a'
    |     |
   '1'   '1'

나머지 파서(parser) 방식에 대해서는 링크해둔 wikipedia 를 참고하시기 바랍니다.

전부 정리해서 적으려고 했는데, 너무나 양이 많네요 =_=;;

나중에 시간이 되면 다시 정리하든지 해야 겠습니다.

모쪼록, 실제 렉서 제너레이터(lexer generator)를 통해서 스캐너(scanner)를 만드는 부분은 다음 강좌에서 계속하도록 하겠습니다.