Grammar for a functional language * sestoft@dina.kvl.dk * 2002-02-25
----------------------------------000-------------------------------

Generating and compiling the lexer and parser:

cd ..
mosmlc -c Env.sig Env.sml
cd fun
mosmllex Funlex.lex
mosmlyac -v Funpar.grm
mosmlc -c Absyn.sml
mosmlc -c -liberal Funpar.sig Funpar.sml
mosmlc -c Funlex.sml
mosml -P full -I .. fun.sml parse.sml


First attempt at a grammar
--------------------------

This grammar is for a version of the micro-SML functional language
that allows functions to take one or more arguments.  In contrast, the
abstract syntax in Absyn.sml, the parser specification in Funpar.grm,
and the interpreter in fun.sml, allow functions to take only one
argument, for simplicity.


program ::=                              program
        expr
        
expr ::=
        const                             constant literal
        ID                                local variable or parameter
        let ID = expr in expr end         local binding
        let ID ids1 = expr in expr end    function binding
        ( expr )                          parenthesized expression
        if expr then expr else expr       conditional expressions
        not expr                          logical negation
        expr op expr                      arithmetic, comparison
        ID exprs1                         function call 

ids1 ::= 
        ID                                one parameter
        ID ids1                           more than one parameter

exprs1 ::=                                non-empty expression list
        expr
        expr exprs1

const ::=                                 constant literals
        CSTINT                            integer literal
        CSTBOOL                           boolean literal

This grammar is highly ambiguous because of the function application
syntax without parentheses.  


Second attempt at a grammar 
---------------------------

We therefore rewrite the grammar to distinguish between atomic
expressions and other expressions.  An atomic expression is a
constant, or a variable, or a let-in-end expression, or a
parenthesized expression (so it is easy to see where an atomic
expression begins and ends):

atexpr ::=
        const                             constant literal
        ID                                local variable or parameter
        let ID = expr in expr end         local binding
        let ID ids1 = expr in expr end    function binding
        ( expr )                          parenthesized expression

and then we require the arguments of a function application to be
atomic expressions:

appexpr ::= 
        atexpr atexpr                     one-argument function call
        appexpr atexpr                    multi-argument function call

so that the final syntax for expressions is

expr ::=
        atexpr                            atomic expression
        appexpr                           function call
        if expr then expr else expr       conditional expressions
        not expr                          logical negation
        expr op expr                      arithmetic, comparison

and the nonterminal exprs1 is not needed any longer.


Lexical matters: tokens and comments
------------------------------------

ID:         [`a`-`z``A`-`Z`][`a`-`z``A`-`Z``0`-`9`]*

            except for the keywords, which are:

            else end false if in let not then true

CSTINT:     ~?[0-9]+

CSTBOOL:    false | true

OP:         + - * / % = <> < <= > >= 


Comments (possibly nested):

        (* ... *) delimited comment