오토마타는 상태(State) 집합과 상태간의 전이(Transition)를 모델링한 것으로 이들이 하나의 시스템을 이루면 "유한상태 기계(Finite-State Machine)"라고 합니다.
실로 현실의 많은 것들이 이 오토마타로 표현될 수 있습니다만 가장 대표적으로 쓰이는 분야가 논리적으로 구성된 프로그래밍 언어를 해석하는 파서(Parser) 분야입니다. 현재 개발할 때 사용하는 C++, Java 등의 언어들은 더 낮은 레벨의 언어로 변환되어야 하는데, 고레벨 언어를 해석하는 역할을 오토마타가 맡고 있습니다.
이 장에서는 오토마타의 기본적인 개념을 살펴 보고, 오토마타를 활용한 예로서 XML 문서를 해석하는 XML 파서를 만들어 보도록 하겠습니다.
이렇게 13년 전에 만들었던 알고리즘 강의를 다시 정리해서 올리는 작업이 끝났습니다. 밀린 숙제를 하는 느낌으로 일단락을 지었고, 조만간 새로운 느낌, 새로운 주제로 다시 IT 분야의 다양한 주제들을 다루어 보겠습니다.
강의 자료
강의 동영상
30.0 오토마타와 XML 파서 - 시작 : 이번 장에서는 XML의 개념과 적용, 오토마타의 개념을 이해하고 이를 이용하여 XML 파서를 만들어 보는 과정을 다룰 것입니다.
30.1 XML의 개요 : XML은 논리적인 형식 구조를 가진 마크업 언어로, 구조적인 데이터를 표현하기 위한 목적을 가지고 있습니다. XML의 개념과 구조에 대해서 알아 봅니다.
30.2 XML의 적용 분야 : XML은 데이터를 표현하는데 적합하고, HTML은 디자인을 표현하는데 적합합니다. 기존의 웹서비스는 이 둘이 혼재됨으로 인해서 개발과 유지보수가 어려웠습니다. XML을 데이터 표현 언어로 사용하고, 이를 렌더링하는 체계적인 방법을 도입함으로서 웹서비스 개발의 패러다임이 바뀌었습니다. 그 외에도 XML은 데이터를 저장하는 용도로도 많이 쓰이고, XML로 정보를 전달하는 프로토콜 본체로도 많이 쓰입니다.
30.3 XML 파서 (XML Parser) : XML 파서는 XML 문서를 분해하여 해석하기 위한 프로그램입니다. W3C에서는 이 파서의 구조를 표준화하였는데, DOM 파서와 SAX 파서로 나뉩니다. 각 파서 구조에 대해 개념적으로 알아 봅니다. (그런데 제가 요즘 많이 쓰는 파서 구조는 Pull Parser 혹은 StAX 파서입니다)
30.4 오토마타(Automata)의 개념 : 오토마타는 상태들이 있고, 그 상태에 어떤 입력이 들어오면 어떤 상태로 변하는지를 규칙으로 정의한 것입니다. 그래서 유한 상태 기계(Finite State Machine)이라고도 합니다. 연속적으로 들어오는 입력에 대한 처리를 위한 모델로 많이 쓰입니다.
30.5 XML 파서 오토마타 : XML 문서는 문자들의 집합 스트링이므로, 연속된 입력입니다. 이 연속된 입력으로 어떻게 XML을 파싱할 수 있는지, 실제로 오토마타를 구성해 봅니다.
30.6 XML 파서 사용법 : 실제로 구현된 XML 파서를 이용하는 법에 대해서 알아 봅니다. 그런데 여기서 제시하는 클래스 구조는 W3C의 표준 SAX 파서 API는 다릅니다. 오히려 StAX 파서 API와 유사합니다. 이 점 참고하시기 바랍니다.
30.9 오토마타와 XML 파서 - 결론 : 데이터를 표현하기 위한 XML 문서, 그리고 이를 파싱하기 위한 오토마타에 대해 알아 보았습니다. 이로서 30강에 걸친 알고리즘 강의가 끝났습니다. 비록 15년 전에 만들어진 강의라 지금의 현실에 맞지 않는 부분들도 있지만, 알고리즘 이라는 분야가 전산학의 기초이다 보니 여전히 유효한 내용이 많을 것 입니다. 여기까지 따라와 오신 분들께 경의를 표합니다.
관련글 |
- C++로 배우는 알고리즘
- 29장 : 알고리즘 개발 방법론 2 (Greedy Method, Backtracking)
댓글 없음:
댓글 쓰기