Slump Slimp Slurpy

오랫만에 놀러 간 사이트에 퀴즈가 올라와 있길래 한 번 풀어봤습니다.  컴파일러와도 연관이 있어서 분류를 컴파일러로 해뒀습니다.

문제 : http://codejob.co.kr/code/view/109/

우선 문제를 BNF로 표시해 보면 다음과 같습니다.

<Slurpy> --> <Slimp> <Slump>

<Slimp> --> AH | AB<Slimp>C | A<Slump>C

<Slump> --> D<F>G | E<F>G | D<F><Slump> |  E<F><Slump>

<F> --> F | F<F>

이제 YACC를 이용해서 문제를 가볍게 해결할 수도 있겠지만, 퀴즈를 풀어 보는 것이 목적이므로 직접 코딩을 해보도록 하겠습니다.

코딩을 하기 이전에 위의 BNF가 어떻게 처리되야 하는 지를 [그림 1]과 같이 약간 변칙적인 상태도로 표현해봤습니다.  이전 포스트(http://ryulib.tistory.com/73)에서도 상태도를 이용해서 BNF를 표현하는 방법에 대해서 설명했듯이, 저는 상태도를 이용하여 BNF를 저만의 방식으로 처리하고 있습니다.  이번에는 좌측 결합은 없고 우측 결합만이 있기 때문에 비교적 간단하게 처리할 수가 있습니다.  읽는 방법은 제가 프로젝트에 쫓기고 있어서 생략합니다.  첨부하는 코드를 참고하시기 바랍니다.

[그림 1] BNF를 상태도로 표현

[소스1] 

procedure TfmMain.FormCreate(Sender: TObject);
var
  Slurpy : TSlurpy;
begin
  Slurpy := TSlurpy.Create;
  try
    Slurpy.Source := 'AH';
    moMsg.Lines.Add(Format('%s IsSlimp is %s', [Slurpy.Source, BoolToStr(Slurpy.IsSlimp, true)]));

    Slurpy.Source := 'ABAHC';
    moMsg.Lines.Add(Format('%s IsSlimp is %s', [Slurpy.Source, BoolToStr(Slurpy.IsSlimp, true)]));

    Slurpy.Source := 'ADFGC';
    moMsg.Lines.Add(Format('%s IsSlimp is %s', [Slurpy.Source, BoolToStr(Slurpy.IsSlimp, true)]));

    Slurpy.Source := 'ABAHD';
    moMsg.Lines.Add(Format('%s IsSlimp is %s', [Slurpy.Source, BoolToStr(Slurpy.IsSlimp, true)]));

    Slurpy.Source := 'AHDFG';
    moMsg.Lines.Add(Format('%s IsSlurpy is %s', [Slurpy.Source, BoolToStr(Slurpy.IsSlurpy, true)]));

    Slurpy.Source := 'DFGAH';
    moMsg.Lines.Add(Format('%s IsSlurpy is %s', [Slurpy.Source, BoolToStr(Slurpy.IsSlurpy, true)]));
  finally
    Slurpy.Free;
  end;
end;

[소스 1]은 IsSlump, IsSlimp, IsSlurpy를 판별할 수 있는 TSlurpy 클래스의 사용방법입니다.  7: 라인에서처럼 Source 멤버에 검사할 문자열을 입력하시고,  IsSlump / IsSlimp / IsSlurpy 등의 메소드를 통해서 해당 문자열이 Slump인지, Slimp인지 또는 Slurpy인지를 판별할 수가 있습니다.

[소스 2]

function TSlurpy.IsSlurpy: boolean;
begin
  try
    Result := IsSlimp and IsSlump;
  except
    Result := false;
  end;
end;

function TSlurpy.IsSlimp: boolean;
begin
  try
    FState := FStateSlimpBase;
    FIsFinished := false;
    repeat
      FState.Execute;
    until FIsFinished;

    Result := true;
  except
    Result := false;
  end;
end;

function TSlurpy.IsSlump: boolean;
begin
  try
    FState := FStateSlumpBase;
    FIsFinished := false;
    repeat
      FState.Execute;
    until FIsFinished;

    Result := true;
  except
    Result := false;
  end;
end;

[소스 2]는 TSlurpy 클래스의 일부분 입니다.  IsSlurpy는 간단하여 설명을 생략합니다.  IsSlimp와 IsSlump의 경우에는 동일한 구조이기 때문에 IsSlimp만을 설명하도록 하겠습니다.

13: [그림 1]에서는 모든 시작을 Base라고 표시했으나, IsSlimp를 점검하는 조건만을 보면 처리가 달라지기 때문에 FStateSlimpBase를 기초 상태로 두고 있습니다.

14-17: FIsFinished가 true가 될 때까지 반복을 하고 있습니다.  FIsFinished가 true라는 것은 현재의 검사가 성공적으로 완료되었다는 의미입니다.  반복하는 동안 계속 현재의 State의 Execute 메소드만을 실행합니다.  내부적으로 무엇을 할지는 캡슐화되어 있어서 정확히는 모르겠지만, 조건이 만족되거나 에러가 날 때까지 계속 문자열을 검색한다는 것을 직감적으로 알 수가 있습니다.

21: 만약 파싱 중간에 에러가 있다면 Exception을 발생시킬 에정입니다.  Exception이 발생된다면, 현재의 점검은 false로 리턴합니다.

[소스 3]

procedure TStateSlimpBase.Execute;
begin
  case Next of
    'A': begin
      SetState(FSlurpy.FStateSlimpA);
    end;

    else raise Exception.Create('Error in ' + ClassName);
  end;
end;

3: 다음 문자를 읽어 들입니다.

4-6: 'A'라는 문자열이면 상태를 FStateSlimpA로 옮겨서 검사를 계속 진행합니다.

8: 다른 문자열이 온다면 에러 입니다.

[소스 4]

procedure TStateSlimpA.Execute;
begin
  case Peek(1) of
    'H': begin
      Next;
      FSlurpy.FIsFinished := true;
    end;

    'B': begin
      Next;
      SetState(FSlurpy.FStateSlimpAB);
    end;

    else begin
      if FSlurpy.IsSlump then FSlurpy.FState := FSlurpy.FStateSlimpASlump
      else raise Exception.Create('Error in ' + ClassName);
    end;
  end;
end;

3: 이번에는 다음 문자열을 읽지 않고, 살짜 훔쳐(Peek) 봅니다.

4-7: 'H' 일 경우에는 검사가 완료되고 IsSlimp는 true를 리턴하게 됩니다.  훔쳐보기만 했기 때문에, 문자열 하나를 읽어서 다음 문자를 읽을 준비가 되도록 합니다.

9-12: 'B' 일 경우에는 상태만 계속 옮겨가면서 검사를 하게 됩니다.

14-17: 'B', 'H' 가 아닌 경우에는 다음에 <Slump>가 오게 되는 지 검사하게 됩니다.  이러한 과정들은 당연히 [그림 1]에 표시된 그대로 입니다.  3:에서 Next를 해서 문자를 읽어 버리면, IsSlump가 한 자를 생략한 채로 검사하게 되기 때문에 Peek(1)로 훔쳐보기만 한 것 입니다.  다음에 <Slump>가 오지 않는 다면 에러입니다.

다른 모든 상태에 대해서도 원리는 같습니다.  

이처럼 상태도를 이용해서 State Pattern을 사용하다보면 전체의 줄거리와 각각의 구현이 완전히 분리가 되어 개발이 한층 쉬워지는 것을 알 수가 있습니다.  사실 이 문제 정도의 복잡도라면 State Pattern을 사용하지 않고 재귀 호출만으로도 쉽게 구현되기는 하지만, 코드의 가독성은 State Pattern이 훨씬 앞선다고 생각합니다.

언제가 될 지, 프로젝트가 한가해지면 그 동안 공부했었던 컴파일러 제작에 대한 강좌를 하고 싶지만, 잘 안되네요 ^^;

아래 첨부는 소스 전체와 사용된 비지오 파일입니다.  샘플이 작아서 제대로 동작하고 있는 지는 잘 모르겠습니다 ^^;

Slump Slimp Slurpy.7z