File psl-1983/doc/brief-mini.lpt artifact 98a998ff55 part of check-in 3af273af29





                         MINI BRIEF DEFINITION
                         MINI BRIEF DEFINITION
                         MINI BRIEF DEFINITION


The  MINI  Translator  Writing  System  was developed in two steps.  The
first was the enhancement of the META/REDUCE [Marti79] system  with  the
definition  of  pattern  matching  primitives  to  aid in describing and
performing tree-to-tree transformations.  META/REDUCE is very proficient
at translating an input programming  language  into  LISP  or  LISP-like
trees, but did not have a good method for manipulating the trees nor for
direct  generation  of  target machine code.  PMETA (as it was initially
called) [Kessler79], solved these  problems  and  created  a  very  good
environment  for  the  development  of  compilers.    In fact, the PMETA
enhancements have been fully integrated into META/REDUCE.

The second step was the elimination of META/REDUCE and  the  development
of  a  smaller, faster system (MINI).  Since META/REDUCE was designed to
provide maximum flexibility and full generality,  the  parsers  that  is
creates  are  large  and  slow.  One of its most significant problems is
that it uses its own single character driven LISP  functions  for  token
scanning  and  recognition.  Elimination of this overhead has produced a
faster translator.  MINI uses the hand coded scanner in  the  underlying
RLISP.    The  other  main aspect of MINI was the elimination of various
META/REDUCE features to decrease the size of the system (also decreasing
the flexibility, but MINI has been successful for the  various  purposes
in COG).  MINI is now small enough to run on small LISP systems (as long
as a token scanner is provided).  The META/REDUCE features that MINI has
changed or eliminated include the following:


   1. The  ability  to  backup  the  parser  state  upon failure is
      supported in META/REDUCE.  However, by  modifying  a  grammar
      definition, the need for backup can be mostly avoided and was
      therefore eliminated from MINI

   2. META/REDUCE  has  extensive  mechanisms  to  allow  arbitrary
      length  dipthongs.    MINI  only   supports   two   character
      dipthongs, declared prior to their use

   3. The target machine language and error specification operators
      are  not  supported  because  they  can  be  implemented with
      support routines

   4. REDUCE subsyntax for specification of semantic operations  is
      not supported (only LISP is provided)


Although  MINI  lacks  many of the features of META/REDUCE, it still has
been  quite  sufficient  for  use  in  COG.    It  has  been  used   for
implementation  of  MIDL,  pattern matching ruleblocks and the prototype
parser/semantic analyzer.  The following  is  a  brief  introduction  to
MINI, the reader is referred to [Marti79] for a more detailed discussion
of the META/REDUCE operators, which are very similar to those of MINI.
                                   2


MINI uses a stack to perform parsing.  For example,


  FOO: ID '!- ID +(PLUS2 #2 #1)


defines  a  rule  FOO,  which  recognizes two identifiers separated by a
minus sign (each ID pushes the recognized identifier  onto  the  stack).
The  last  expression  replaces the top 2 elements on the stack (#2 pops
the first ID pushed onto the stack, while #1 pops the other) with a LISP
statement.  Specification of a parser using MINI  consists  of  defining
the syntax with BNF-like rules and semantics with LISP expressions.  The
following is a brief list of the operators:


'               Used  to  designate a terminal symbol (i.e. 'WHILE, 'DO,
                '!=)

Identifier      Specifies a nonterminal

( )             Used for grouping (i.e. (FOO BAR) requires rule  FOO  to
                parse followed immediately by BAR)

< >             Optional  parse,  if  it fails then continue (i.e. <FOO>
                tries to parse FOO)

/               Optional rules (i.e. FOO / BAR allows either FOO or  BAR
                to parse, with FOO tested first)

STMT[ANYTOKEN]* Parse any number of STMT separated by ANYTOKEN, create a
                list  and  push onto the stack (i.e. ID[,]* will parse a
                number of IDentifiers separated by commas,  like  in  an
                argument list)

##n             Reference the nth stack location (n must be an integer)

#n              Pop the nth stack location (n must be an integer)

+(STMT)         Push the unevaluated (STMT) onto the stack

.(SEXPR)        Evaluate the SEXPR and ignore the result

+.(SEXPR)       Evaluate the SEXPR and push the result on the stack

@ANYTOKEN       Specifies  a  statement  terminator,  used  in the error
                recovery mechanism to search for when an error occurs

@@ANYTOKEN      Grammar terminator


The useful files are as follows:
                                   3


MINI.MIN        The self definition of MINI in MINI.

MINI.SL         A  Standard LISP version of MINI.MIN, translated by MINI
                itself.

MINI.RED        The support RLISP for MINI.

SENTER.RED      The META/REDUCE symbol table package.

MINI.BLD        A runfile that builds MINI.FAP from the above 4 files.

MINIME.BLD      A runfile that builds the MINI.SL file  by  loading  and
                translating MINI.MIN.


REDUCE Historical
REDUCE Sourceforge Project | Historical SVN Repository | GitHub Mirror | SourceHut Mirror | NotABug Mirror | Chisel Mirror | Chisel RSS ]