Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!usc!ucsd!helios.ee.lbl.gov!nosc!humu!uhccux!munnari.oz.au!basser!steve
From: steve@basser.oz (Stephen Russell)
Newsgroups: comp.os.minix
Subject: Re: Lex
Message-ID: <2268@basser.oz>
Date: 25 Jun 89 15:21:55 GMT
References: <2796@ast.cs.vu.nl>
Organization: Dept of Comp Sci, Uni of Sydney, Australia
Lines: 58

In article <2796@ast.cs.vu.nl> ast@cs.vu.nl (Andy Tanenbaum) writes:
>
>In comp.sources.unix there is a version of lex posted.
>It has only 7 parts, quite unusual for that group.
>Anybody volunteer to take a look at it and see if it can be ported to
>MINIX? 

I've just moved it MSDOS compiled with Turbo C. As it comes out the
box, it needs a small text/large data model. Sum of the sizes of the
TC object files is:

	text 34686 data 20301 bss 28599 Total 83586

Problem is the large structures allocated dynamically - more details
below. The major bss hogs are some large arrays in main.c and scan.c,
which can be safely shrunk, particularly the 16K of input buffering in
the scanner.

I also compiled it with small text/small data, like Minix split I&D.
It failed allocating those big structures. Object sizes were:

	text 29349 data 20221 bss 27913 Total 77483

Same comments as above.

Here is a condensed summary of running flex on its own scanner
definition.  Note that this is a pretty meaty scanner (114 rules) so
probably represents an upper limit on memory usage.  I've starred the
interesting lines - those showing "n/m" indicate dynamic tables with
"m" initial entries that could be shrunk by changing #defines in the
header file.

	flex version 2.1 (beta) usage statistics:
	*  777/2000 NFA states
	*  315/1000 DFA states (1339 words)
	*  21/40 start conditions
	*  23/100 character classes needed 190/500 words of storage, 38 reused
	   6489 state/nextstate pairs created
	*  374/1000 base-def entries created
	   1291/2000 (peak 3034) nxt-chk entries created
	   649/2500 (peak 2419) template nxt-chk entries created
	   3498 total table entries needed

In fact, flex is written to grow (most of?) these dynamic tables as
needed, so much smaller initial sizes should work on Minix, at least
for medium-sized lex definitions.

A few other things:

- it assumes C compiler supports 32 char external identifiers.
- it uses a YACC generated parser, so would need to ported on some UNIX
  box to get the YACC output.
- generated scanners use large (16K) input buffer. This can be changed
  with an appropriate #define in the skeleton file.
- the documentation assumes you know how to use lex.

Summary: should be possible to port. Code size is reasonable, but
would require some tuning to shrink the tables to fit in 64K.