Re: tips for writing regular expression interpreter/compiler?

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]

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