Re: tips for writing regular expression interpreter/compiler?

jburgy@gmail.com
30 Nov 2005 17:30:27 -0500

          From comp.compilers

Related articles
tips for writing regular expression interpreter/compiler? derekhaas@gmail.com (Derek Haas) (2005-11-26)
Re: tips for writing regular expression interpreter/compiler? jburgy@gmail.com (2005-11-30)
Re: tips for writing regular expression interpreter/compiler? rsc@swtch.com (Russ Cox) (2005-12-02)
Re: tips for writing regular expression interpreter/compiler? jeffrey.kenton@comcast.net (Jeff Kenton) (2005-12-02)
Re: tips for writing regular expression interpreter/compiler? mefrill@yandex.ru (mefrill) (2005-12-02)
Re: tips for writing regular expression interpreter/compiler? markwh04@yahoo.com (2005-12-23)
Re: tips for writing regular expression interpreter/compiler? markwh04@yahoo.com (2005-12-23)
Re: tips for writing regular expression interpreter/compiler? rsc@swtch.com (Russ Cox) (2005-12-23)
| List of all articles for this month |

From: jburgy@gmail.com
Newsgroups: comp.compilers
Date: 30 Nov 2005 17:30:27 -0500
Organization: http://groups.google.com
References: 05-11-119
Keywords: lex, comment

Derek Haas wrote:
> I am trying to implement a small subset of the regular expression
> languages found in perl/python/et cetera (maybe just Kleene closure
> and alternation for now). I hope to use this as a learning experience
> which I can use to work on a larger scale project of a similiar
> nature.
>
> Does anyone have any ideas on where to start with this? Or any
> specific things to read? I've taken a course on compilers and
> interpreters at my university, but I am not sure how useful that was
> beyond a theoretical standpoint.
>
> Thanks,
> Derek
> [There's plenty of source code you can read, starting with Henry Spencer's
> widely used regexp library. -John]


If you want to make it particularly challenging and worth your while, I
suggest the following approach (I tried it with some success): read
this article


@article{Thompson68,
      author = {K. Thompson},
      title = {Regular Expression Search Algorithm},
      journal = {Comm. Assoc. Comp. Mach.},
      volume = {11},
      number = {6},
      pages = {419--422},
      year = {1968},
      keywords = {acm cacm}
}


and reimplement the idea in x86 asm. I'll be happy to give you
tips/pointers. You'll be surprised how much you'll learn


Jan
[This is the original regular expression paper, describing the search in qed, a
predececessor to Unix editors ed, ex and vi. -John]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.