Re: yacc parse tree

buzzard@world.std.com (Sean T Barrett)
2 Jan 1999 05:01:37 -0500

          From comp.compilers
Related articles
[5 earlier articles]
Re: yacc parse tree josh_adams@bmc.com (Josh Adams) (1998-12-19)
Re: yacc parse tree joachim.durchholz@munich.netsurf.de (Joachim Durchholz) (1998-12-19)
Re: yacc parse tree scinar@ug.bcc.bilkent.edu.tr (Sukru Cinar) (1998-12-21)
Re: yacc parse tree scinar@ug.bcc.bilkent.edu.tr (Sukru Cinar) (1998-12-22)
Re: yacc parse tree AMartin@ma.ultranet.com (Alan H. Martin) (1999-01-02)
Re: yacc parse tree scinar@ug.bcc.bilkent.edu.tr (Sukru Cinar) (1999-01-02)
Re: yacc parse tree buzzard@world.std.com (1999-01-02)
| List of all articles for this month |
From: buzzard@world.std.com (Sean T Barrett)
Newsgroups: comp.compilers
Date: 2 Jan 1999 05:01:37 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 98-12-018 98-12-026 99-01-007
Keywords: lex

>Note that while fgrep's pattern language is less expressive than grep or
>egrep's [ it's still interesting enough that it was published ]
[snip]
>[Now that he reminds me, the fgrep algorithm is quite clever, sometimes
>requiring less than one comparison per character. -John]


There are other programs that attempt to do 'sublinear' searching with
more complex search patterns, e.g. perhaps most famously AGREP.


I have 'published' some research on doing full regular-expression
searching (i.e. general NFA/DFA searching) that is 'sublinear' at
      http://world.std.com/~buzzard/sgrep.html
however I have been unable to tell if it is of more than academic
value.


But it's not that interesting in a pure compiler sense, since a
compiler must normally examine every input character anyway.


Sean

Post a followup to this message

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