Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!ut-sally!husc6!hscfvax!mohamedr
From: mohamedr@hscfvax.UUCP (770457@Mohamed Ellozy)
Newsgroups: comp.unix.wizards
Subject: Misuse of lex
Message-ID: <339@hscfvax.UUCP>
Date: Sun, 8-Mar-87 17:45:08 EST
Article-I.D.: hscfvax.339
Posted: Sun Mar  8 17:45:08 1987
Date-Received: Mon, 9-Mar-87 19:38:45 EST
Distribution: world
Organization: Health Sciences Computing Facility, Harvard University
Lines: 53
Keywords: lex binary search timings

It is common to use lex to recognize a long list of reserved words
with constructs like:


options				return (OPTIONS);
precedence			return (PRECEDENCE);
trusted				return (TRUSTED);

		many, many more

[A-Za-z][A-Za-z0-9_-]*		{
				/* store identifiers in symbol table */
				yylval.phe = LookupSymbol (yytext);
				return (IDENT);
				}

This produces huge lexical analysers.  Furthermore, they compile
with agonizing slowness, so they can hardly be considered a
convenience to the developper.  It is easy to recode them to look
up reserved words by binary search in a table.  See Introduction to
Compiler Construction with UNIX by A. T. Schreiner and H. G. Friedman Jr.
Prentice Hall, 1985, ISBN 0-13-474396-2 01 if you need help.

The improvement in compilation speed is remarkable, as the following
timings will show:

	hscfvax# time lex lexan.old.l
	249.7u 14.1s 5:55 74% 49+239k 2+12io 14pf+0w

	hscfvax# mv lex.yy.c lexan.old.c
	hscfvax# time cc -c lexan.old.c
	67.2u 5.5s 1:28 82% 131+243k 70+94io 29pf+0w

	hscfvax# time lex lexan.l
	2.5u 0.7s 0:05 62% 44+199k 1+6io 14pf+0w

	hscfvax# mv lex.yy.c lexan.c
	hscfvax# time cc -c lexan.c
	20.1u 2.6s 0:28 79% 124+224k 16+46io 29pf+0w

	hscfvax# ls -l lex*
	-rw-r--r--  1 root        14240 Mar  8 12:08 lexan.c
	-rw-r--r--  1 root         4761 Mar  8 12:07 lexan.l
	-rw-r--r--  1 root        10873 Mar  8 12:09 lexan.o

	-rw-r--r--  1 root        42495 Mar  8 12:02 lexan.old.c
	-rw-r--r--  1 root         5031 Mar  8 10:55 lexan.old.l
	-rw-r--r--  1 root        37343 Mar  8 12:04 lexan.old.o

Seven and a half minutes of clock time versus half a minute.  As my wife
(a law student) would say: Res ipsa loquitur.

(Must I translate?  Oh well, it means: The thing speaks for itself.)