Re: yacc parse tree (Sean T Barrett)
2 Jan 1999 05:01:37 -0500

          From comp.compilers

Related articles
[5 earlier articles]
Re: yacc parse tree (Josh Adams) (1998-12-19)
Re: yacc parse tree (Joachim Durchholz) (1998-12-19)
Re: yacc parse tree (Sukru Cinar) (1998-12-21)
Re: yacc parse tree (Sukru Cinar) (1998-12-22)
Re: yacc parse tree (Alan H. Martin) (1999-01-02)
Re: yacc parse tree (Sukru Cinar) (1999-01-02)
Re: yacc parse tree (1999-01-02)
| List of all articles for this month |

From: (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 ]
>[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
however I have been unable to tell if it is of more than academic

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


Post a followup to this message

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