[Commit] mint-2004b conclusions.tex, 1.3, 1.4 intro.tex, 1.3, 1.4 lola.tex, 1.2, 1.3

Bart Massey commit at keithp.com
Wed Dec 1 13:18:38 PST 2004


Committed by: bart

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

Modified Files:
	conclusions.tex intro.tex lola.tex 
Log Message:
Fixed conclusions to match intro.  Edited lola discussion.



Index: conclusions.tex
===================================================================
RCS file: /local/src/CVS/mint-2004b/conclusions.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- conclusions.tex	1 Dec 2004 19:17:37 -0000	1.3
+++ conclusions.tex	1 Dec 2004 21:18:35 -0000	1.4
@@ -1,26 +1,29 @@
 \section{Conclusions and Future Work}\label{sec-conclusions}
 
-As experimental as it is, the current implementation of MINT versatile.
+As experimental as it is, the current implementation of MINT
+is versatile.
 The ease with which it has been able to bootstrap itself suggests that
-there will be little applying it to bootstrap nickle, and for future
+there will be little applying it to bootstrap Nickle, and for future
 work with other context-free grammars.  Furthermore, the ability to of tag
 elements of productions simplifies the onerous task of writing tree
-walkers for syntax trees.  In most respects it is already a fairly
+walkers for syntax trees.  In most respects it is already a
 respectable parser generator, if a little rough around the edges.
 
-However, the potential of the most striking feature of MINT --
-its language neutral architecture -- has yet to be fully realized.
-Several uses for the separation of language and grammar are readily
-apparent.  It will allow the programmer the ability to use the same
-grammar for a compiler, syntax highlighting, static analysis tools,
-and interpreters.  It also simplifies the task of writing ``little
-languages'' like the language of regular expressions, which are
-embedded inside other programming languages in such a way that
-the syntax is consistent across all the client languages. 
-
-Further, the possibility exists of providing an additional degree
-of separation in the architecture.  A simple application of MINT
-might read in an input and output a syntax tree represented in XML --
-which allows a user to merely utilize one of the many available 
-XML parsers to manipulate this syntax tree.
+However, the potential of the most striking feature of
+MINT---its language neutral architecture---has yet to be
+fully realized.  Several uses for the separation of language
+and grammar are readily apparent.  This separation will
+allow the programmer the ability to use the same grammar for
+a compiler, syntax highlighting, static analysis tools, and
+interpreters.  It also simplifies the task of writing
+``little languages'' like the language of regular
+expressions, which are embedded inside other programming
+languages: this can be done in such a way that the syntax is
+consistent across all the client languages.
 
+Further, the possibility exists of providing an additional
+degree of separation in the architecture.  A simple
+application of MINT might read in an input and output a
+syntax tree represented in XML.  This would allow a user to
+merely utilize one of the many available XML parsers to
+manipulate this syntax tree.

Index: intro.tex
===================================================================
RCS file: /local/src/CVS/mint-2004b/intro.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- intro.tex	1 Dec 2004 19:17:37 -0000	1.3
+++ intro.tex	1 Dec 2004 21:18:35 -0000	1.4
@@ -59,14 +59,21 @@
 translator to operate in a wide range of languages.  The
 MINT runtime parser and lexer, which are small and simple,
 can thus be implemented in a variety of programming
-languages.  For Nickle, this means that the C-based compiler
-can be used for the time being: the move to Nickle-based
-compilation can be made when appropriate.  For other
-projects, this means that the existing MINT tool can be
-reused, rather than re-implementing this wheel in each new
-language that comes along.  MINT thus also provides a
-platform for experimentation with lexer and parser
-generation techniques.
+languages.
+
+For Nickle, this means that the C-based compiler can be used
+for the time being: the move to Nickle-based compilation can
+be made when appropriate.  For other projects, this means
+that the existing MINT tool can be reused, rather than
+re-implementing this wheel in each new language that comes
+along.  MINT thus also provides a platform for
+experimentation with lexer and parser generation techniques.
+Finally, the separation allows a language implemented across
+a large number of target programming languages to share a
+common grammar.  This should greatly ease software
+engineering of domain-specific languages.  It should also
+ease construction of tools for language work, such as syntax
+highlighting, static analysis, and interpreters.
 
 MINT has already proven to be an effective tool for design
 and construction of language recognizers.  It has been used

Index: lola.tex
===================================================================
RCS file: /local/src/CVS/mint-2004b/lola.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- lola.tex	1 Dec 2004 19:17:37 -0000	1.2
+++ lola.tex	1 Dec 2004 21:18:35 -0000	1.3
@@ -1,21 +1,24 @@
 \section{Lola and Flo}\label{sec-lola}
 
-Lola was an LL parser generator written in 1987 in the Kalypso dialect of
-lisp (a research language focusing on functional lisp programming).  As with
+Lola is an LL parser generator written in 1987 in the authors'
+Kalypso programming
+language.  Kalypso is a functional dialect of
+LISP.  As with
 MINT, the output of the parser generator was a language independent data
 structure which could drive parser frameworks in multiple languages.
-Parsers for the Lola output were written in C, Pascal and Kalypso.
+Lola parser runtimes were written in C, Pascal and Kalypso.
 
-The Flo tool was a grammar-to-grammar transformation tool to factor left
+The Flo tool is a grammar-to-grammar transformation tool to factor left
 common sub-expressions out of a grammar to permit more compact and easier to
-understand representations of LL(1) languages.  It was also written in
+understand representations of LL(1) languages.  It is also written in
 Kalypso.  Grammars are represented in lisp s-expressions as in
 Figure~\ref{fig-lola-grammar}, eliminating the need for a custom grammar
 parser and permitting easier grammar-to-grammar transformation tool
-development.  
+development.  Grammar descriptions can also include
+semantic action tokens executed at compile time.
 
 \begin{figure}
-\footnotesize
+\scriptsize
 \begin{verbatim}
 ;
 ; this grammar recognises integer
@@ -51,88 +54,67 @@
 \caption{A sample Lola grammar}\label{fig-lola-grammar}
 \end{figure}
 
-Semantic attributes were attached to the grammar in the form of special
-tokens in the right side of each grammar production.  The parser would then
-perform the semantic operation when the action appeared on the top of the
-stack.
-
-The ability to analyse grammars and systematically catch language design and
-grammar errors long before sample language sentences were applied to the
-parser provided a higher degree of confidence in the correctness of the
-resulting parsing application.  The ability to produce parsers in one of
-many languages encouraged the use of this higher level tool in place of
+Lola and Flo were conceived as an alternative to ad hoc
+recursive-descent parsers.  For this they have worked well,
+producing small, simple descriptions that are automatically
+checked for correctness.
+The ability to produce parsers in one of
+many languages has encouraged the use of this higher level tool in place of
 ad-hoc parsers on several occasions.
 
 \subsection{Configuration Languages with Lola}
 
 Lola and Flo were first used to produce an ANSI X3.64 character terminal
-implementation in Pascal.  Using a parser generator allows the development
-of an implementation artifact much closer in syntax and style to the ANSI
-specification than the traditional maze of twisty low level language code.
+parser in Pascal.  
 Formal testing of this implementation demonstrated that it would correctly
 parse the standard ASCII control sequences.  The lack of parsing correctness
 in many existing adhoc ANSI X3.64 implementations reinforces the use of
 higher level parsing tools in such designs.  As the parser itself was
-written in a fairly low-level language (Pascal), performance of the
-resulting implementation easily met the performance requirements.
-
-From that point forward, Lola and Flo were used together to produce parsers
-for a variety of domain-specific languages supporting application
-configuration and customization.  These implementations were characterized
-by:
-\begin{itemize}
-\item Incomplete and changing specifications. Not only were the elements of
-the configuration constantly changing as the specification for the
-application was adjusted with reference to the ongoing implementation, but
-the syntax of the language changed as whole new classes of configuration
-information were incorporated into the system.
-\item Unknown parsability.  The configuration requirements for some pieces
-of the system were provided by developers ignorant of the limitations of a
-context free grammar.
-\item Target platform under development.  With the final execution location
-of the parser still in the hardware design phase, having many existing
-parser implementations provide for unit testing during initial development.
-\item Lexer also under constant development.  Without an automatic lexer
-generator, the hand-crafted lexer turned out to be a significant development
-effort.  Using an existing simplistic tokenizing lexer allowed grammar
-changes to be tested in advance of lexer reimplementation.
-\end{itemize}
-
-With the grammar validated by the automatic parser generator, the possiblity
-for parser errors due to changes in the input language was greatly reduced.
-This allowed changes to be rolled into the system late in the development
-process.
-
-\subsection{Parser Implementation Languages}
-
-With parsers available in several languages, LL language grammars could be
-rapidly tested in the command-line environment provided by Kalypso and only
-when working properly would they be transferred to a parser written in the
-target execution language.  Not only did this reduce development time of the
-parser by speeding the turn-around from change to test, it also provide a
-built-in lexer in the form of the lisp s-expression recognition code.
+written in Pascal, performance
+of the resulting system was more than adequate.
 
-In the case of the X3.64 parser, a Kalypso lexer was built enabling
-end-to-end regression testing against the final Pascal implementation.
+Lola and Flo were used together to produce parsers for a
+variety of domain-specific languages supporting application
+configuration and customization.  These implementations were
+typically characterized by any of several elements.  The
+specifications of the languages were often incomplete and
+changing.  The configuration requirements for some pieces of
+the system were often provided by developers ignorant of the
+limitations of a context free grammar.  The target platform
+was often under development and needed testing.  Given these
+sorts of situations, Lola and Flo proved invaluable.
 
 \subsection{Limitations of Lola and Flo}
 
-Lola and Flo were designed for LL languages.  This domain restriction was
-acceptable for the tasks it was originally designed for in 1987, but as a
-general purpose parser generator, the restriction is onerous today.  An LL
-parser requires significantly less table space and processing than the
-typical LR or even LALR parser, something occasionally relevant on the
+Lola and Flo were designed for LL(1) languages.  Indeed, the sole
+purpose of the Flo tool was to help transform grammars to
+LL(1) form.  This domain restriction was
+acceptable for the tasks it was originally designed for in 1987.
+An LL(1)
+parser required significantly less table space and processing than the
+typical LALR parser, something often relevant on the
 machines common in that era.
 
-As can be seen in the example grammar above, even the Flo tool which could
-factor common left sub-expressions wasn't sufficient to present grammars in
-their most natural form (cf the awkward int/digits productions).  Also, the
-semantic action mechanism is as context-free as the grammar itself,
-requiring the parser track significant language state on its own, in
-particular it does not provide a mechanism for producing a parse tree.
-
-Probably the most significant limitation for these tools today is that the
-implementation language, Kalypso, has been effectively retired from general
-use, making further development and improvement problematic.
+However, LL(1) remains an onerous restriction.  The awkward
+int/digits productions in the example grammar of
+figure~\ref{fig-lola-grammar} illustrate that grammars
+suitable for Lola and Flo tended toward the unnatural.
+Also, the semantic action mechanism is as context-free as
+the grammar itself, requiring the parser track significant
+language state on its own. In particular, Lola does not
+provide an automatic mechanism for producing a parse tree.
 
+In many projects, the lexer was also often undergoing
+concurrent development.  Building hand-crafted lexers turned
+out to be a significant development effort.  Using an
+existing simplistic tokenizing lexer allowed grammar changes
+to be tested in advance of lexer reimplementation, but this
+mechanism had obvious drawbacks.  The need for an automated
+lexer generator was clear.
 
+Another significant limitation for Lola and Flo today is
+that the implementation language, Kalypso, has been
+effectively retired from general use, making further
+development and improvement problematic.  In any case,
+Kalypso exemplified the problems inherent in software
+engineering in a small, non-modular research language.




More information about the Commit mailing list