Re: yacc parse tree

"Alan H. Martin" <AMartin@ma.ultranet.com>
2 Jan 1999 00:23:47 -0500

          From comp.compilers
Related articles
[3 earlier articles]
Re: yacc parse tree bob@werken.com (1998-12-18)
Re: yacc parse tree belinfan@cs.utwente.nl (1998-12-18)
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: "Alan H. Martin" <AMartin@ma.ultranet.com>
Newsgroups: comp.compilers
Date: 2 Jan 1999 00:23:47 -0500
Organization: UltraNet Communications , an RCN Company http://www.ultranet.com/
References: 98-12-018 98-12-026
Keywords: lex, comment

> ... grep is unrelated to lex even though the expression languages
> are similar, lex compiles the patterns to a DFA while the various greps
> either use an NFA (egrep and plain grep) or ad-hoc fixed string matching
> (fgrep). ...
> -John]


Note that while fgrep's pattern language is less expressive than grep or
egrep's, the usual implementation is classical enough to have been published
in CACM:


A. V. Aho and M. J. Corasick.
Efficient string matching: an aid to bibliographic search.
Communications of the ACM, 18(6):333-340, 1975.
/AHM
--
Alan Howard Martin AMartin@MA.UltraNet.Com
[Now that he reminds me, the fgrep algorithm is quite clever, sometimes
requiring less than one comparison per character. -John]

Post a followup to this message

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