parser를 만들려면 어떻게 공부해야 될까요?

NeutralGray의 이미지

html, xml이나 latex등의 소스 파일을 읽는 parser를 만들고 싶습니다. 뭔가 참고할만한 좋은 책이 없을까요? 지금까진 쌩노가다 주먹구구로 만들었는데, 좀 더 이론을 공부해서 제대로 만들어보고 싶습니다. 어떤 테크트리를 밟아서 공부해야 하는지 알고 싶습니다.

익명 사용자의 이미지

lex/yacc, 정규표현식.

fromdj의 이미지

이론을 공부하시려면 컴파일러 책들을 보시면 좋겠네요
대학강이 교재들을 참고해 보시면 되겠고요
O'Relly 에서 나온 Lex/Yacc 라는 책도 참고가 될것 같습니다.

^^ be cool ~
http://fromdj.pe.kr

익명 사용자의 이미지

그러면 대학의 컴파일러 시간에 주로 쓰는 유명한 교재좀 몇개만 추천해 주십시오.

죠커의 이미지

Drogon Book이 첫 번째로 물망에 오를 것 같습니다.

사실 두 번째부터가 기대됩니다. 어떤 서적들이 추천될지..

ssggkim의 이미지

컴파일러 책이라면 드래곤 북을 가장 많이 보지 않을까요?
http://kangcom.com/common/bookinfo/bookinfo.asp?sku=200012050016

c++을 쓰신다면 boost spirit도 추천드립니다. :)

체스맨의 이미지

저도 드래곤책 봅니다만, 타이거책도 교재로 쓴다는 것 같습니다.

http://kangcom.com/common/bookinfo/bookinfo.asp?sku=199904290001
하지만, 지금은 품절이군요. Java 버젼은 파네요.

드래곤책은 2장까지 이해하면 일단 뭐하자는 얘기 인지는 알 수 있을 거라 생각됩니다.

Orion Project : http://orionids.org

urmajest의 이미지

NeutralGray wrote:
html, xml이나 latex등의 소스 파일을 읽는 parser를 만들고 싶습니다. 뭔가 참고할만한 좋은 책이 없을까요? 지금까진 쌩노가다 주먹구구로 만들었는데, 좀 더 이론을 공부해서 제대로 만들어보고 싶습니다. 어떤 테크트리를 밟아서 공부해야 하는지 알고 싶습니다.

사실 parser를 직접 만드실 필요는 전혀 없을 것 같아요.

Parser generator + grammar 로 parser를 만들게 되는데,

parser generator는 c에서는 yacc(bison) java에서는 javacc등이 있고,

문제는 grammar인데 grammar를 직접 작성하신다는 건 무리일겁니다.

html이나 xml도 디자인 할 때 context-free grammar로 그 뼈대를 잡았겠죠. 그 grammar를 그대로 옮기는게 가장 정확한 parser를 만드는 방법이겠네요 ^^

cinsk의 이미지

문법이 상대적으로 간단한 XML의 경우, bison과 같은 parser generator를 쓰지 않고도 C 코드로 직접 만들 수도 있습니다. 또 연습삼아 직접 만들어보기를 바랍니다. 실제 numerical expression을 parsing하는 수준의 지식만 있어도 도움이 됩니다. The C++ Programming Language를 보시면, Chapter 6 Expressions and Statements장에 간단한 parser 만드는 법이 나와 있습니다. 일단 XML specification을 받아다가 BNF 문법이 나타내는 대로 함수를 만들고 처리하시면 됩니다. 실제로 간단한 문법을 지닌 언어를 parsing하는 것은 bison이나 yacc의 도움을 받는 것보다, 직접 만드시는 것이 훨씬 더 간결하고 빠릅니다. 또한, 이런 식으로 parser를 만들다 보면, 표준 C 함수인 setjmp, longjmp를 잘 쓰시면 도움이 될 것 같습니다. (물론 C 언어로 작성한다는 전제에서, C++이면 당연히 throw/catch.)

또한 lexical analyzer를 직접 만드신다면 속도를 위해 GNU obstack module을 쓸 것을 강력하게 추천합니다. obstack module은 libiberty에 포함되어 있으며, libiberty는 독립적인 GNU software는 아니며, GCC나 GDB의 소스에 포함되어 있습니다.
GCC나 GDB 소스를 따로 복사하지 않더라도, glibc를 이미 설치하셨다면 그냥 쓸 수 있으며, 도움말은 다음 명령으로 바로 볼 수 있습니다:

info libc mem 'memory alloc' obstack

간단한 문자열을 저장하고 다루기 위해서 GNU alloca 함수를 쓰면 좋습니다:

info libc mem 'memory alloc' variable

또한 symbol table을 만드는데 쓰는 문자열은, 당연히 atom 형태로 등록하고 써야, 메모리도 절약되며, 비교할 때도 포인터로 직접 비교할 수 있으니 좋습니다. 여기에 관한 것은, 다음 책의 Chapter 3. Atoms와, Chapter 15, 16에 나온 string 처리 루틴을 참고하기 바랍니다:

C Interfaces and Implementaions -- David R. Hanson, Addison Wesley, ISBN 0-201-49841-3

이쪽에 관심이 있으신 것 같으니, 도움이 될 만한 책을 추천합니다. (개인적으로는 드래곤, 타이거 책보다는 이쪽을 더 추천해 드리고 싶습니다):

Compiler Design in C --- Allen I. Holub, Prentice Hall, ISBN 0-13-155045-4

절판된 것 같은데, 자세히는 잘 모르겠습니다. flex와 bison같은 utility도 직접 소스로 만들고, 이론 뿐만 아니고 모든 것이 코드로 잘 설명되어 있습니다. (강력 추천!!!!!!!!!!!!!!!! 방금 Amazon.com에서 확인했는데, 절판 아닙니다.)

A Retagetable C Compiler Design and Implementation -- Fraser Hanson, Addison Wesley, ISBN 0-8053-1670-1

Open Source인 실제 컴파일러 lcc를 디자인하고 실제 코드를 예로 설명하는 책입니다. http://www.cs.princeton.edu/software/lcc/

그럼 이만.

(책들의 이미지를 빨리 보고 싶으시면 http://www.cinsk.org/books/ 에서 볼 수 있습니다. ;-) )

익명 사용자의 이미지

자세한 답변 감사드립니다 ^^

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.