[완료] 상태 전이도를 구현하려면 어떻게 해야 할까요? (파싱과 관련)

> 학교 프로젝트로 간단한 Lexical Analizer와 Syntax Analizer가 필요합니다.
>
> Lex를 빌려 쓰지 않구, 정말 간단하게 구현하고 싶은데요. 제가 아직 오토마타를 배우지 못 했습니다.
> 이산수학 형식언어에 나오는 유한상태 그래프를 이용하면 되겠다 싶어서 생각중인데요.
> 먼저 제 생각은 트리를 써서 따라가면 될 듯한데, 정확하지 않아서요. 여러분들의 조언을 듣고 싶습니다.
> 구현이 아닌, 방법이요. 어떤식으로 하면 되는지 알려 주세요.
>
> 저것이 없으면 분기문이 너무 많아서 괴로울것 같네요. ^^;;
>

lexer 와 parser 모두 hand-coding 가능합니다. 각 token 을 인식하는 큰
분기를 기준으로 각 세부 줄기마다 token 인식 및 처리를 담당하는 함수를
구현하시면 됩니다. 예를 들어, 아래는 C 언어 주석을 인식하는 부분을
코드로 나타내 본 것입니다. '/' 문자 이후에 '*' 가 따라오지 않을 경우에
대한 처리도 필요함에 유의하시기 바랍니다.

c = getchar();
 
switch(c) {
    ...
    case '/':
        if ((c = getchar()) == '*')
            comment();
        else if (c == '/')
            cpp_comment();
        else
            ungetc(c),
            divide();
        break;
    ...
}

lexer 를 hand-coding 시 분기가 많아 어렵다기 보다는 각 token 을
올바르게 인식하도록 실수 없이 구성하기가 쉽지 않습니다. 하지만, 시행
착오를 겪으며 몇번 반복하시다 보면 제법 요령도 생깁니다. 개인적으로
lex 같은 도구 사용 이전에 hand-coding 으로 lexer 를 구성해보고 lex
같은 도구가 생성한 코드와 비교하며 공부하시기를 추천합니다.

parser 의 경우 복잡한 문법일 경우에는 여러 파싱 방법 중 recursive
parser 가 hand-coding 에 간단한 편입니다. 문법에 factoring 등으로
최적화까지 적용한다면 parser generator 로 생성한 LALR(1) parser 에
못지 않은 성능을 낼 수도 있습니다 - lcc 와 gcc 4.x 모두 hand-coding 된
recursive parser 를 사용하고 있으며, 탁월한 성능을 보이고 있습니다.
우선 (매우 비효율적인 부분이 많을 수 밖엔 없겠지만) 주어진 문법 그대로
구현을 해보시고 동작을 확인하신 후에 최적화된 문법을 바탕으로
구현하시면 보다 견고한 parser 구현이 가능합니다.

제가 가지고 있는 lexer, parser 모두 hand-coding 되어 있습니다. 처음엔
"이 삽질을 꼭 해야 하는가" 라는 고민을 많이 했지만, 지금은 상당히
자부심이 느껴지는 부분이 되어 있습니다.

건투를 빕니다.

--
Jun, Woong (woong at icu.ac.kr)
Web: http://www.woong.org (서버 공사중)