Combinatoric한 Lexer

blitzerg의 이미지

많은 분들이 Combinatoric하게 프로그램을 작성하는 방법을 모르시는게 아닌가 해서 한번 올려봅니다.

이 기법은 Combinatory Logic에서 나왔는데, 간단한 구조임에도 불구하고, 프로그램이 해결하고자하는 본질적이고 근본적인 특징를 뽑아낼 수 있는 방법입니다.

원래 소스는 Haskell이라는 언어로 아주 간략하게 작성될 수 있는 것인데, C++버전으로 바꿔봤습니다.

functor 같은 걸 사용하면 조금더 보기 좋아졌을지는 모르겠는데 일단은 대충 끼워맞췄네요.

윗부분의 namespace 부분이 lexer를 돌리는데 필요한 루틴 모음이고, 그 아래쪽에 선언된 부분이 lexer입니다.

이 프로그램은 파라미터로 지정된 파일을 읽어들여서, identifier, whitespace, symbol, number를 추출해냅니다.

스펙은 잘 아시는 context-free grammer구요. c++로 context-free grammer에 최대한 근접하게 문법을 만들려고 노력했으나, 좀 많이 부족한 것 같네요.

작성은 VC++6.0에서 작성했습니다. emacs 설정이 잘 안맞아서 grammer에서 표현하는 tab indentation이 너무 보기 싫어서요. ㅡ_ㅡ;; 테스트는 안해봤지만 아마 몇 줄만 수정하시면 g++에서도 잘 돌아갈겁니다.

한번 돌려보시면 속도는 조금 느립니다만, flex 같은 툴을 사용하지 않고도 얼마든지 간단하게(?) lexer를 만들 수 있는 방법입니다.

이 방법을 그대로 응용하면 parser를 만드는 것도 어렵지 않습니다. 단지 입력 Chars 대신 Tokens가 들어가게 하면 되겠죠?

File attachments: 
첨부파일 크기
파일 lexer.cpp5.07 KB
Forums: 
익명 사용자의 이미지

파서에 관해서라면 이제 걱정을 많이 덜어도 될 듯 합니다.

아래 사이트도 참고하시길..

see http://www.boost.org/libs/spirit/doc/introduction.html

blitzerg의 이미지

호... 이런 방법도 있군요.

boost 라이브러리는 이야기는 많이 들었지만 볼 기회가 없어서 못봤었는데 특이하군요. ^^

잠시 읽어봤는데 이 spirit이라는 거(?) 상당히 멋지군요!!!

함수가 아니라 오브젝트에 assign하는 방식으로 규칙을 해석하네요...

제가 하려고 하는 프로젝트에 이용하는 것을 심각하게 고민해봐야할 듯 하군요.

좋은 정보 감사드립니다. (__)

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.