[Commit] mint-2004b mint.tex,1.6,1.7 translators.tex,1.5,1.6

Bart Massey commit at keithp.com
Wed Dec 1 22:00:36 PST 2004

Committed by: bart

Update of /local/src/CVS/mint-2004b
In directory home.keithp.com:/tmp/cvs-serv1581

Modified Files:
	mint.tex translators.tex 
Log Message:
Finished evaluation section, etc.

Index: mint.tex
RCS file: /local/src/CVS/mint-2004b/mint.tex,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- mint.tex	1 Dec 2004 23:20:49 -0000	1.6
+++ mint.tex	2 Dec 2004 06:00:33 -0000	1.7
@@ -7,6 +7,8 @@
 \newcommand{\id}[1]{{\tt #1}}

Index: translators.tex
RCS file: /local/src/CVS/mint-2004b/translators.tex,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- translators.tex	2 Dec 2004 05:19:14 -0000	1.5
+++ translators.tex	2 Dec 2004 06:00:33 -0000	1.6
@@ -50,17 +50,43 @@
-For some grammars, particularly ambiguous ones involving precedence, the 
-implementation of parser generator performed extremely poorly even for
-a modestly-sized grammar.  It seems the structure of the grammar had more
-to do with the degraded performance than size did, suggesting that an
-opportunity for further optimization exists.
+Although the MINT tool is still in the late stages of
+development, it is complete enough to do some preliminary
+analysis of its performance and usability.  All of the
+sample grammars of the Appendix were timed over 5 runs on a
+3GHz Pentium laptop: the median runtime is reported here.
+The results are summarized in table~\ref{tab-perf}.  The
+length reported for each grammar is the average
+length  in tokens of a production rule in that grammar.
+Lex and parse table size is measured in terms of tokens, to
+account for the fact that the ASCII serialization is much
+larger than the expected in-memory set size.  By this
+measure, sizes appear to be quite reasonable.
-The parse table size, however, did seem to correspond with the generation
-time fairly closely, suggesting a complexity endemic to the task at hand.
-Some good results were achieved by the careful application of memoization
-to the inner loop of the LR(1) closure algorithm.  Various statistics
-on the performance of the generator with respect to the examples grammars
-given in this paper can be found (wherever).
+\caption{MINT Performance}\label{tab-perf}
+The MINT lexer generator is quite fast, and did not
+contribute significantly to reported MINT runtimes.  The
+MINT parser generator seems to perform a bit disappointingly
+for grammars involving ambiguity resolved by precedence.  It
+seems the structure of the grammar has more to do with the
+degraded performance than does size.  Known opportunities
+for further optimization exist: the performance of
+production MINT is expected to be much improved.  Some good
+speedups have already been achieved by the careful
+application of memoization to the inner loop of the LR(1)
+closure algorithm.

More information about the Commit mailing list