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]
.

Relevant Pages

  • Re: Boolean search in Dialog?
    ... >> How would you do a regular expression search that was equivalent to the ... > Dialog's inbuilt Help covers this topic fairly well, ... any search engine will quickly lead you to them. ... wyzwyz posted the Regular Expression ...
    (news.software.readers)
  • VBA and regular expression to search for ranges of text
    ... I'd be very grateful for help with the following. ... I would like to convert it to a Word Range object ...
    (microsoft.public.word.vba.general)
  • Re: Regular expression problem
    ... includes all the strings in A, but excludes all the strings in B. ... In order to find a regular expression of minimal length, though, I ... certainly will need Kleene closure. ... but they don't meet the "shortest" requirement. ...
    (comp.theory)
  • Re: Regular Expression Parsing In Java
    ... ArdGre wrote: ... My program must take a regular expression as input and be able to tell ... The regular expression can contain parantheses, kleene closure and ... union operator. ...
    (comp.lang.java.programmer)
  • Re: Regular Expression Parsing In Java
    ... My program must take a regular expression as input and be able to tell ... The regular expression can contain parantheses, kleene closure and ... union operator. ... Investigate the parsing techniques your class has recently studied. ...
    (comp.lang.java.programmer)