home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / TOOLS / PARSER.DOC < prev    next >
Text File  |  1996-06-04  |  6KB  |  189 lines
  1. #    $Id: Parser.doc,v 1.2 1994/12/08 23:47:20 duchier Exp $    
  2.  
  3.                             A PARSER FOR LIFE            
  4.  
  5.   
  6.   NAME
  7.  
  8.   parser: A complete parser for Life, including extensions to the standard
  9.           syntax of Life (the standard syntax being that defined by the
  10.           wild_LIFE parser), and the possibility to use local functions. 
  11.  
  12.  
  13.   USAGE
  14.  
  15.       syntax(filename) ? 
  16.  
  17.   parses the file filename and writes the obtained psi-terms in the file
  18.   filename_expr.
  19.   Beware: the obtained file cannot necessarily be loaded by wild_LIFE, because
  20.   ':' is not always printed out correctly by writeq.
  21.     
  22.   All the necessary files are automatically loaded if they are in the same
  23.   directory.
  24.  
  25.  
  26.   FILES
  27.  
  28.   The file parser.lf contains the parser.
  29.  
  30.   The other files are:
  31.   - tokenizer.lf  : the tokenizer used to provide inputs to the parser
  32.   - accumulators.lf, std_expander.lf and acc_declarations.lf  
  33.  
  34.   All these files are automatically loaded if they are in the same directory. 
  35.  
  36.   They must be loaded with expand_load(true). 
  37.  
  38.   DESCRIPTION  
  39.  
  40.   This parser is written like an attribute grammar, and translated in a Life
  41.   program by the grammar translator (file expander.lf). The inputs of
  42.   this grammars are the tokens produced by the tokenizer in Life (file
  43.   tokenizer.lf). This grammar needs to know one token in advance to work.
  44.  
  45.   Extensions of the standard syntax:
  46.  
  47.   - Expressions may be used at label places:
  48.      foo( expr => bar ) 
  49.            where expr is any life expression is syntactic sugar for:
  50.      ( X:foo | project(expr,X) = bar )
  51.  
  52.   - expr1.expr2 is syntactic sugar for project(expr2,expr1). It is an infix,
  53.     left associative operator of precedence 300 ( more than & and :, but less
  54.     than any other operator).
  55.     conditions of use:
  56.     - after a sequence of digits, . is first considered as the floating point,
  57.       then as project:
  58.         152.143 is parsed as the real 152.143
  59.         152.(143) is parsed as project(143,152)
  60.         152.143.345 is parsed as project(345,152.143)
  61.         152 .143    is parsed as project(143,145)
  62.     - . is considered as an operator iff it is not followed by a void
  63.       character (space, tab, nl, )
  64.     - . cannot be defined by op.
  65.   - if <expr1> then <expr2> else <expr3> 
  66.        can be used instead of
  67.     cond(<expr1> , <expr2> ,<expr3>); 
  68.     The then and the else branches may be omitted; any expression of precedence
  69.     less than 999 (, is of precedence 1000) is allowed:
  70.     there is no maximum precedence; "if" "then" and "else" are tokens; 
  71.     predicates are allowed in the if branch.
  72.  
  73.   Local Functions:
  74.   - lambda(attributes)(expr) defines a local function where all the
  75.     variables appearing in attributes are local to the expression. This works
  76.     also with recursive functions. For instance, factorial could be defined
  77.     by :
  78.     Fact = '*lambda*'(X)(cond(X =:= 0, 1, X*Fact(X-1))) ?
  79.   - The possible syntaxes for application are the following:
  80.     - X(args) 
  81.         where X is a variable that has to be instantiated to a function
  82.         (local or not) at runtime, and args the list of arguments of the
  83.         function. 
  84.     - (expr)(args) 
  85.   - let X = expr in expr2 
  86.       is syntactic sugar for 
  87.       (lambda(X)(expr2))(expr)
  88.  
  89.  
  90.   A Grammar for Life
  91.   Here is an informal presentation of the grammar used in the parser.
  92.   
  93.   %%%%%%%%%%%%%%%%% Terms %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  94.   
  95.   term --> 
  96.     [construct],
  97.     (attributes ; []).
  98.   term --> 
  99.     [variable],
  100.     ( attributes ;  %% application
  101.       [] ).
  102.   term --> 
  103.     liste,
  104.     (attributes ; []). 
  105.   term -->
  106.     disjunction,
  107.     (attributes ; []).      
  108.   term -->                     
  109.     ["lambda"],
  110.     attributes,        %% all variables inside attributes are made local 
  111.                            %% to the term 
  112.     expression.
  113.   term --> 
  114.     ["let"],
  115.     [variable],[atom(=)],expression, %% variable is local
  116.         ["in"],
  117.     expression.
  118.  
  119.   attributes -->     %% , is not considered as an operator in this context,
  120.                      %% but as a syntactic object 
  121.     ["("],
  122.     list_attributes.
  123.   list_attributes -->     
  124.     attribute,
  125.     ( [] ; atom(,), list_attributes).
  126.   attribute -->
  127.     expression,
  128.     ( [atom(=>)], expression ; []).
  129.  
  130.   liste -->          %% , and | are not considered as operators in this
  131.                      %% context, but as syntactic objects 
  132.     ["["],
  133.     ( ["]"] ; end_list ).
  134.   end_list -->
  135.     expression,
  136.     ( ["]"] ; [atom(,)], end_list ; [atom(|)],expression, ["]"] ).
  137.  
  138.   disjunction -->    %% ; is not considered as an operator in this context,
  139.                      %% but as a syntactic object 
  140.     ["{"],
  141.     ( ["}"] ; end_disjunction ).
  142.   end_disjunction -->
  143.     expression,
  144.     ( ["}"] ; end_disjunction ).
  145.  
  146.  
  147.   %%%%%%%%%%%%%%%%% Expressions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  148.   
  149.   expression -->                      
  150.     start_expression,
  151.     end_expression.     %% precedence of end_expression is greater than
  152.                             %% that of start_expression
  153.   start_expression -->
  154.     ["("],expression,[")"],
  155.     (
  156.        attributes       %% application
  157.         ;
  158.            []
  159.     ).
  160.   start_expression -->
  161.     prefix_operator,
  162.     (  
  163.             expression      %% accepted precedence depends on the operator
  164.         ; 
  165.             attributes      %% the operator is used as a constructor
  166.         ; 
  167.             [] ).
  168.   start_expression --> term.
  169.   end_expression -->
  170.     sub_expression,  
  171.     end_expression.     %% precedence of end_expression is greater than 
  172.                             %% that of sub_expression
  173.   end_expression --> [].
  174.   sub_expression -->
  175.     operator,
  176.     (
  177.        []               %% postfix operator
  178.         ;
  179.            expression       %% infix operator
  180.     ).  
  181.  
  182.  
  183.   AUTHOR 
  184.  
  185.   Bruno Dumant
  186.  
  187.   Copyright 1992 Digital Equipment Corporation
  188.   All Rights Reserved
  189.