From c2b22e08bd48278f2cf125f054c9f6286e345ff0 Mon Sep 17 00:00:00 2001 From: Manoj Srivastava Date: Wed, 3 Dec 2003 22:33:17 -0800 Subject: Imported Upstream version 2.5.31 --- examples/fastwc/Makefile.am | 29 +++++ examples/fastwc/Makefile.in | 309 ++++++++++++++++++++++++++++++++++++++++++++ examples/fastwc/README | 56 ++++++++ examples/fastwc/mywc.c | 26 ++++ examples/fastwc/wc1.l | 19 +++ examples/fastwc/wc2.l | 21 +++ examples/fastwc/wc3.l | 25 ++++ examples/fastwc/wc4.l | 28 ++++ examples/fastwc/wc5.l | 25 ++++ 9 files changed, 538 insertions(+) create mode 100644 examples/fastwc/Makefile.am create mode 100644 examples/fastwc/Makefile.in create mode 100644 examples/fastwc/README create mode 100644 examples/fastwc/mywc.c create mode 100644 examples/fastwc/wc1.l create mode 100644 examples/fastwc/wc2.l create mode 100644 examples/fastwc/wc3.l create mode 100644 examples/fastwc/wc4.l create mode 100644 examples/fastwc/wc5.l (limited to 'examples/fastwc') diff --git a/examples/fastwc/Makefile.am b/examples/fastwc/Makefile.am new file mode 100644 index 0000000..b2831d9 --- /dev/null +++ b/examples/fastwc/Makefile.am @@ -0,0 +1,29 @@ +# This file is part of flex. + +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: + +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. + +# Neither the name of the University nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. + +# THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR +# IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +# PURPOSE. + +EXTRA_DIST = \ + wc5.l \ + wc4.l \ + wc3.l \ + wc2.l \ + wc1.l \ + mywc.c \ + README diff --git a/examples/fastwc/Makefile.in b/examples/fastwc/Makefile.in new file mode 100644 index 0000000..7f96510 --- /dev/null +++ b/examples/fastwc/Makefile.in @@ -0,0 +1,309 @@ +# Makefile.in generated by automake 1.7 from Makefile.am. +# @configure_input@ + +# Copyright 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002 +# Free Software Foundation, Inc. +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + +@SET_MAKE@ + +# This file is part of flex. + +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: + +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. + +# Neither the name of the University nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. + +# THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR +# IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +# PURPOSE. + +srcdir = @srcdir@ +top_srcdir = @top_srcdir@ +VPATH = @srcdir@ +pkgdatadir = $(datadir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ +top_builddir = ../.. + +am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd +INSTALL = @INSTALL@ +install_sh_DATA = $(install_sh) -c -m 644 +install_sh_PROGRAM = $(install_sh) -c +install_sh_SCRIPT = $(install_sh) -c +INSTALL_HEADER = $(INSTALL_DATA) +transform = $(program_transform_name) +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +host_triplet = @host@ +ACLOCAL = @ACLOCAL@ +AMDEP_FALSE = @AMDEP_FALSE@ +AMDEP_TRUE = @AMDEP_TRUE@ +AMTAR = @AMTAR@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +BISON = @BISON@ +CC = @CC@ +CCDEPMODE = @CCDEPMODE@ +CFLAGS = @CFLAGS@ +CPP = @CPP@ +CPPFLAGS = @CPPFLAGS@ +CXX = @CXX@ +CXXDEPMODE = @CXXDEPMODE@ +CXXFLAGS = @CXXFLAGS@ +CYGPATH_W = @CYGPATH_W@ +DEFS = @DEFS@ +DEPDIR = @DEPDIR@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EGREP = @EGREP@ +EXEEXT = @EXEEXT@ +GMSGFMT = @GMSGFMT@ +HELP2MAN = @HELP2MAN@ +INDENT = @INDENT@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +INTLLIBS = @INTLLIBS@ +LDFLAGS = @LDFLAGS@ +LEX = @LEX@ +LEXLIB = @LEXLIB@ +LEX_OUTPUT_ROOT = @LEX_OUTPUT_ROOT@ +LIBICONV = @LIBICONV@ +LIBINTL = @LIBINTL@ +LIBS = @LIBS@ +LN_S = @LN_S@ +LTLIBICONV = @LTLIBICONV@ +LTLIBINTL = @LTLIBINTL@ +LTLIBOBJS = @LTLIBOBJS@ +M4 = @M4@ +MAKEINFO = @MAKEINFO@ +MKINSTALLDIRS = @MKINSTALLDIRS@ +MSGFMT = @MSGFMT@ +MSGMERGE = @MSGMERGE@ +OBJEXT = @OBJEXT@ +PACKAGE = @PACKAGE@ +PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@ +PACKAGE_NAME = @PACKAGE_NAME@ +PACKAGE_STRING = @PACKAGE_STRING@ +PACKAGE_TARNAME = @PACKAGE_TARNAME@ +PACKAGE_VERSION = @PACKAGE_VERSION@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +POSUB = @POSUB@ +RANLIB = @RANLIB@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +STRIP = @STRIP@ +USE_NLS = @USE_NLS@ +VERSION = @VERSION@ +XGETTEXT = @XGETTEXT@ +YACC = @YACC@ +ac_ct_CC = @ac_ct_CC@ +ac_ct_CXX = @ac_ct_CXX@ +ac_ct_RANLIB = @ac_ct_RANLIB@ +ac_ct_STRIP = @ac_ct_STRIP@ +am__fastdepCC_FALSE = @am__fastdepCC_FALSE@ +am__fastdepCC_TRUE = @am__fastdepCC_TRUE@ +am__fastdepCXX_FALSE = @am__fastdepCXX_FALSE@ +am__fastdepCXX_TRUE = @am__fastdepCXX_TRUE@ +am__include = @am__include@ +am__quote = @am__quote@ +bindir = @bindir@ +build = @build@ +build_alias = @build_alias@ +build_cpu = @build_cpu@ +build_os = @build_os@ +build_vendor = @build_vendor@ +datadir = @datadir@ +exec_prefix = @exec_prefix@ +host = @host@ +host_alias = @host_alias@ +host_cpu = @host_cpu@ +host_os = @host_os@ +host_vendor = @host_vendor@ +includedir = @includedir@ +infodir = @infodir@ +install_sh = @install_sh@ +libdir = @libdir@ +libexecdir = @libexecdir@ +localstatedir = @localstatedir@ +mandir = @mandir@ +oldincludedir = @oldincludedir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +sysconfdir = @sysconfdir@ +target_alias = @target_alias@ + +EXTRA_DIST = \ + wc5.l \ + wc4.l \ + wc3.l \ + wc2.l \ + wc1.l \ + mywc.c \ + README + +subdir = examples/fastwc +mkinstalldirs = $(SHELL) $(top_srcdir)/mkinstalldirs +CONFIG_HEADER = $(top_builddir)/config.h +CONFIG_CLEAN_FILES = +DIST_SOURCES = +DIST_COMMON = README Makefile.am Makefile.in +all: all-am + +.SUFFIXES: +$(srcdir)/Makefile.in: Makefile.am $(top_srcdir)/configure.in $(ACLOCAL_M4) + cd $(top_srcdir) && \ + $(AUTOMAKE) --gnu examples/fastwc/Makefile +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe) +uninstall-info-am: +tags: TAGS +TAGS: + +ctags: CTAGS +CTAGS: + +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) + +top_distdir = ../.. +distdir = $(top_distdir)/$(PACKAGE)-$(VERSION) + +distdir: $(DISTFILES) + @srcdirstrip=`echo "$(srcdir)" | sed 's|.|.|g'`; \ + list='$(DISTFILES)'; for file in $$list; do \ + case $$file in \ + $(srcdir)/*) file=`echo "$$file" | sed "s|^$$srcdirstrip/||"`;; \ + esac; \ + if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \ + dir=`echo "$$file" | sed -e 's,/[^/]*$$,,'`; \ + if test "$$dir" != "$$file" && test "$$dir" != "."; then \ + dir="/$$dir"; \ + $(mkinstalldirs) "$(distdir)$$dir"; \ + else \ + dir=''; \ + fi; \ + if test -d $$d/$$file; then \ + if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \ + cp -pR $(srcdir)/$$file $(distdir)$$dir || exit 1; \ + fi; \ + cp -pR $$d/$$file $(distdir)$$dir || exit 1; \ + else \ + test -f $(distdir)/$$file \ + || cp -p $$d/$$file $(distdir)/$$file \ + || exit 1; \ + fi; \ + done +check-am: all-am +check: check-am +all-am: Makefile + +installdirs: + +install: install-am +install-exec: install-exec-am +install-data: install-data-am +uninstall: uninstall-am + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am + +installcheck: installcheck-am +install-strip: + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + INSTALL_STRIP_FLAG=-s \ + `test -z '$(STRIP)' || \ + echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install +mostlyclean-generic: + +clean-generic: + +distclean-generic: + -rm -f Makefile $(CONFIG_CLEAN_FILES) + +maintainer-clean-generic: + @echo "This command is intended for maintainers to use" + @echo "it deletes files that may require special tools to rebuild." +clean: clean-am + +clean-am: clean-generic mostlyclean-am + +distclean: distclean-am + +distclean-am: clean-am distclean-generic + +dvi: dvi-am + +dvi-am: + +info: info-am + +info-am: + +install-data-am: + +install-exec-am: + +install-info: install-info-am + +install-man: + +installcheck-am: + +maintainer-clean: maintainer-clean-am + +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-am + +mostlyclean-am: mostlyclean-generic + +pdf: pdf-am + +pdf-am: + +ps: ps-am + +ps-am: + +uninstall-am: uninstall-info-am + +.PHONY: all all-am check check-am clean clean-generic distclean \ + distclean-generic distdir dvi dvi-am info info-am install \ + install-am install-data install-data-am install-exec \ + install-exec-am install-info install-info-am install-man \ + install-strip installcheck installcheck-am installdirs \ + maintainer-clean maintainer-clean-generic mostlyclean \ + mostlyclean-generic pdf pdf-am ps ps-am uninstall uninstall-am \ + uninstall-info-am + +# Tell versions [3.59,3.63) of GNU make to not export all variables. +# Otherwise a system limit (for SysV at least) may be exceeded. +.NOEXPORT: diff --git a/examples/fastwc/README b/examples/fastwc/README new file mode 100644 index 0000000..0dd3afe --- /dev/null +++ b/examples/fastwc/README @@ -0,0 +1,56 @@ +This directory contains some examples illustrating techniques for extracting +high-performance from flex scanners. Each program implements a simplified +version of the Unix "wc" tool: read text from stdin and print the number of +characters, words, and lines present in the text. All programs were compiled +using gcc (version unavailable, sorry) with the -O flag, and run on a +SPARCstation 1+. The input used was a PostScript file, mainly containing +figures, with the following "wc" counts: + + lines words characters + 214217 635954 2592172 + + +The basic principles illustrated by these programs are: + + - match as much text with each rule as possible + - adding rules does not slow you down! + - avoid backing up + +and the big caveat that comes with them is: + + - you buy performance with decreased maintainability; make + sure you really need it before applying the above techniques. + +See the "Performance Considerations" section of flexdoc for more +details regarding these principles. + + +The different versions of "wc": + + mywc.c + a simple but fairly efficient C version + + wc1.l a naive flex "wc" implementation + + wc2.l somewhat faster; adds rules to match multiple tokens at once + + wc3.l faster still; adds more rules to match longer runs of tokens + + wc4.l fastest; still more rules added; hard to do much better + using flex (or, I suspect, hand-coding) + + wc5.l identical to wc3.l except one rule has been slightly + shortened, introducing backing-up + +Timing results (all times in user CPU seconds): + + program time notes + ------- ---- ----- + wc1 16.4 default flex table compression (= -Cem) + wc1 6.7 -Cf compression option + /bin/wc 5.8 Sun's standard "wc" tool + mywc 4.6 simple but better C implementation! + wc2 4.6 as good as C implementation; built using -Cf + wc3 3.8 -Cf + wc4 3.3 -Cf + wc5 5.7 -Cf; ouch, backing up is expensive diff --git a/examples/fastwc/mywc.c b/examples/fastwc/mywc.c new file mode 100644 index 0000000..92e5a36 --- /dev/null +++ b/examples/fastwc/mywc.c @@ -0,0 +1,26 @@ +/* A simple but fairly efficient C version of the Unix "wc" tool */ + +#include +#include + +main() +{ + register int c, cc = 0, wc = 0, lc = 0; + FILE *f = stdin; + + while ((c = getc(f)) != EOF) { + ++cc; + if (isgraph(c)) { + ++wc; + do { + c = getc(f); + if (c == EOF) + goto done; + ++cc; + } while (isgraph(c)); + } + if (c == '\n') + ++lc; + } +done: printf( "%8d%8d%8d\n", lc, wc, cc ); +} diff --git a/examples/fastwc/wc1.l b/examples/fastwc/wc1.l new file mode 100644 index 0000000..0d4fcf2 --- /dev/null +++ b/examples/fastwc/wc1.l @@ -0,0 +1,19 @@ +/* First cut at a flex-based "wc" tool. */ + +ws [ \t] +nonws [^ \t\n] + +%option main noyywrap +%% + int cc = 0, wc = 0, lc = 0; + +{nonws}+ cc += yyleng; ++wc; + +{ws}+ cc += yyleng; + +\n ++lc; ++cc; + +<> { + printf( "%8d %8d %8d\n", lc, wc, cc ); + yyterminate(); + } diff --git a/examples/fastwc/wc2.l b/examples/fastwc/wc2.l new file mode 100644 index 0000000..0da9953 --- /dev/null +++ b/examples/fastwc/wc2.l @@ -0,0 +1,21 @@ +/* Somewhat faster "wc" tool: match more text with each rule */ + +ws [ \t] +nonws [^ \t\n] +word {ws}*{nonws}+ + +%option main noyywrap +%% + int cc = 0, wc = 0, lc = 0; + +{word}{ws}* cc += yyleng; ++wc; +{word}{ws}*\n cc += yyleng; ++wc; ++lc; + +{ws}+ cc += yyleng; + +\n+ cc += yyleng; lc += yyleng; + +<> { + printf( "%8d %8d %8d\n", lc, wc, cc ); + yyterminate(); + } diff --git a/examples/fastwc/wc3.l b/examples/fastwc/wc3.l new file mode 100644 index 0000000..3cc5d57 --- /dev/null +++ b/examples/fastwc/wc3.l @@ -0,0 +1,25 @@ +/* Somewhat faster still: potentially match a lot of text with each rule */ + +ws [ \t] +nonws [^ \t\n] +word {ws}*{nonws}+ +words {word}{ws}+ + +%option main noyywrap +%% + int cc = 0, wc = 0, lc = 0; + +{word}{ws}* cc += yyleng; ++wc; +{word}{ws}*\n cc += yyleng; ++wc; ++lc; +{words}{word}{ws}* cc += yyleng; wc += 2; +{words}{2}{word}{ws}* cc += yyleng; wc += 3; +{words}{3}{word}{ws}* cc += yyleng; wc += 4; + +{ws}+ cc += yyleng; + +\n+ cc += yyleng; lc += yyleng; + +<> { + printf( "%8d %8d %8d\n", lc, wc, cc ); + yyterminate(); + } diff --git a/examples/fastwc/wc4.l b/examples/fastwc/wc4.l new file mode 100644 index 0000000..90c36ee --- /dev/null +++ b/examples/fastwc/wc4.l @@ -0,0 +1,28 @@ +/* Fastest version of wc: add rules to pick up newlines, too */ + +ws [ \t] +nonws [^ \t\n] +word {ws}*{nonws}+ +words {word}{ws}+ + +%option main noyywrap +%% + int cc = 0, wc = 0, lc = 0; + +{word}{ws}* ++wc; cc += yyleng; +{word}{ws}*\n ++wc; cc += yyleng; ++lc; +{words}{word}{ws}* wc += 2; cc += yyleng; +{words}{word}{ws}*\n wc += 2; cc += yyleng; ++lc; +{words}{2}{word}{ws}* wc += 3; cc += yyleng; +{words}{2}{word}{ws}*\n wc += 3; cc += yyleng; ++lc; +{words}{3}{word}{ws}* wc += 4; cc += yyleng; +{words}{3}{word}{ws}*\n wc += 4; cc += yyleng; ++lc; + +{ws}+ cc += yyleng; + +\n+ cc += yyleng; lc += yyleng; + +<> { + printf( "%8d %8d %8d\n", lc, wc, cc ); + yyterminate(); + } diff --git a/examples/fastwc/wc5.l b/examples/fastwc/wc5.l new file mode 100644 index 0000000..c479480 --- /dev/null +++ b/examples/fastwc/wc5.l @@ -0,0 +1,25 @@ +/* Oops; slight change from wc3.l introduces backtracking */ + +ws [ \t] +nonws [^ \t\n] +word {ws}*{nonws}+ +words {word}{ws}+ + +%option main noyywrap +%% + int cc = 0, wc = 0, lc = 0; + +{word}{ws}* cc += yyleng; ++wc; +{word}{ws}*\n cc += yyleng; ++wc; ++lc; +{words}{word} cc += yyleng; wc += 2; /* oops */ +{words}{2}{word}{ws}* cc += yyleng; wc += 3; +{words}{3}{word}{ws}* cc += yyleng; wc += 4; + +{ws}+ cc += yyleng; + +\n+ cc += yyleng; lc += yyleng; + +<> { + printf( "%8d %8d %8d\n", lc, wc, cc ); + yyterminate(); + } -- cgit v1.2.3