[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [Samples] / ml.syntax
[Index] [Contents] [Source Text] [About] [Notation] [Copyright] [Comment/Contact] [Search ]
Mon Jan 24 14:41:41 PST 2011

Contents


    Description of Standard ML

      Syntax of Standard ML

        Introduction

        Sources

          This message presents syntax rules for the full Standard ML language. These rules are intended to serve as documentation for programmers, and could be useful to compiler writers. They are slightly too liberal, in that they do not take account of syntactic restrictions or the precedence of certain constructs. I believe that they are complete.

          Source: Larry Paulson

          The above message was translated into MATHS by Dick Botting and some extra terms were introduced to simplify some definitions. Any errors that have crept in are mine, all mine. Mail me and they will be fixed!

          Source: Corrections by Dave Berry, Simon Finn, Kent Karlsson, David N. Turner, and Konstantin Tcholokachvili.

        . . . . . . . . . ( end of section Sources) <<Contents | End>>

        Notes on meta-notation


          [ math_64_Meta_Macros.html ]

        1. Empty::="", -- the null string.

          O(...) encloses an optional phrase so

        2. O(A)::=(A|Empty).

          #(A) - zero or more occurences of A, and N(A) - one or more occurrences of A, so

        3. #(A)::= O(N(A)).
        4. N(A)::= (A) #(A).

          L(A, B) encloses a repetitive phrase of the form ABABA...BA -- 1 or more repetitions of A, separated by B.

        5. L(A,B)::= A #(B A).
        6. List(A)::=L(A, ","),
        7. (-1)|-List(A)= A #("," A).
        8. And_List(A)::=L(A, "and"),
        9. (-1)|-And_List(A)= A #("and" A).
        10. Sequence(A)::=L(A, ";"),
        11. (-1)|-Sequence(A) = A #(";" A).
        12. O_List(A)::= O(List(A)), An optional List of A's.

          Items below may be separated by spaces, newlines, and comments.

          Consecutive keywords and identifiers of the same sort (alphanumeric/symbolic) must be separated to avoid ambiguity.


        Programs and Modules

      1. Program::= #(Top_Level_Declaration ";" ).

      2. Top_Level_Declaration::= Expression | Object_Declaration | Signature_Declaration | Functor_Declaration.

      3. Object_Declaration::= Empty | Declaration | "structure" And_List( Ident O(":" Signature) "=" Structure ) | "local" Object_Declaration "in" Object_Declaration "end" | Object_Declaration O(";") Object_Declaration.

      4. Module::glossary=A separably compilable unit - typically a file - containing module systems.

      5. Module_system::glossary=Made of structure, signatures, and functors.

      6. Structure::glossary=a collection of types, datatypes, functions, exceptions, etc we wish to encapsulate.

      7. Signature_Declaration::= Empty | "signature" And_List(Ident "=" Signature ) | Signature_Declaration O(";") Signature_Declaration.
      8. Signature::glossary=A collection of info describing and specifying some elements of a structure.

      9. Functor_Declaration::= Empty | "functor" And_List(Functor_Binding ) | Functor_Declaration O(";") Functor_Declaration.
      10. Functor::Glossary=An Operation that takes one or more structures and produces another one.

        The ML Functor meets the same need to generate special cases of code from a general form that generics do in Ada and templates do in C++.

      11. Functor_Binding::= Ident "(" Functor_Arguments ")" O(":" Signature) "=" Structure.

      12. Functor_Arguments::= Ident ":" Signature | Specification.

      13. Functor_Application::= Ident "(" Structure | Sequence(structure_declaration) ")".

      14. Structure::= "struct" Object_Declaration "end" | Compound_Ident | Functor_Application | Ident "(" Object_Declaration ")" | "let" Object_Declaration "in" Structure "end".

      15. Signature::= "sig" Specification "end" | Ident.

      16. Specification::= Empty | value_spec | various_type_spec | exception_spec | structure_spec | other_spec | inclusion | Specification O(";") Specification.
      17. value_specification::="val" And_List(Ident ":" Type ).
      18. various_type_spec::=("type" | "eqtype") And_List(Type_Var_List Ident ) | "datatype" And_List(Datatype_Binding )
      19. exception_spec::="exception" And_List(Ident O("of" Type) ).
      20. structure_spec::="structure" And_List(Ident ":" Signature ).
      21. other_spec::="sharing" And_List( O("type") Ident "=" L(Ident , "=") ) | "local" Specification "in" Specification "end" | "open" List(Compound_Ident ).
      22. inclusions::= "include" N(Ident ) .

        Declarations

      23. Declaration::= Empty | simple_declaration #(O(";")simple_declaration).
      24. simple_declaration::= value_declaration | function_declaration | type_declaration | abstract_data_type_declaration | abstract_type_declaration | exception_declaraion | local_declaration | open_declaration | operator_declaration.

      25. value_declaration::="val" And_List( O("rec") Pattern "=" Expression ) .
      26. function_declaration::="fun" And_List( L(Function_Heading O(":" Type) "=" Expression , "|") ).
      27. structure_declaration::="structure" And_list( Ident O(":" Signature) "=" Structure ) | Declaration | "local" structure_declaration "in" Sequence(Structure_Declarations).

      28. type_declaration::="type" Type_Binding.
      29. abstract_data_type_declaration::="datatype" Datatype_Binding O("withtype" Type_Binding).
      30. abstract_type_declaration::="abstype" Datatype_Binding O("withtype" Type_Binding) "with" Declaration "end". In the above the Datatype_Binding defiing the structure of the data is hidden from all but the functions etc in the part of the declaration after the "withs".

      31. exception_declaration::="exception" And_List( Name O( "of" Type | "=" Compound_Name ) ).
      32. local_declaration::="local" Declaration "in" Declaration "end".

      33. open_declaration::="open" N(Compound_Ident ). An Open declaration allows you to refer to the contents of a structure without having to include the name of the structure each time. The names of parts of the openned structure override those declared before the open.

      34. operator_declaration::=infix_declaration | "nonfix" N(Ident ).
      35. infix_declaration::=("infix" | "infixr") O(priority) N(Ident).
      36. priority::=integer.

      37. infix_operator::=Ident & visible in an infix declaration & (declared as or in a function of two parameters|declared as constructor with two parts).

      38. Function_Heading::= Name N(Atomic_Pattern) | "(" Atomic_Pattern Infix_Operator Atomic_Pattern ")" #(Atomic_Pattern) | Atomic_Pattern Infix_Operator Atomic_Pattern.

      39. Type_Binding::= And_List(Type_Var_List Ident "=" Type ).

      40. Datatype_Binding::= And_List( Type_Var_List Ident "=" L( constructor O("of" Type) , "|" ) ).
      41. constructor::=Ident & visible in a datatype_binding.

        Expressions

      42. Expression::= Infix_Expression | Expression ":" Type | Expression boolean_operator Expression | Expression "handle" Match | "raise" Expression | selection| loop | "fn" Match.

      43. boolean_operator::="andalso" | "orelse".
      44. loop::= "while" Expression "do" Expression.
      45. selection::= "if" Expression "then" Expression "else" Expression | "case" Expression "of" Match.

      46. Infix_Expression::= N(Atomic_Expression ) | Infix_Expression Infix_Operator Infix_Expression.

      47. Atomic_Expression::= Compound_Name | Constant | "(" O_List(Expression ) ")" | "[" List(Expression ) "]" | "{" O_List(Label "=" Expression ) "}" | "#" Label | "(" L(Expression , ";") ")" | "let" Declaration "in" L(Expression , ";") "end".

        Patterns">Matches and Patterns

      48. Match::= L(Pattern "=>" Expression , "|").

      49. Pattern::= Atomic_Pattern | Compound_Name Atomic_Pattern | Pattern infix_constructor Pattern | Pattern ":" Type | Name O(":" Type) "as" Pattern.

      50. infix_constructor::=Infix_Operator & constructor.

      51. Atomic_Pattern::= "_" | Compound_Name | Constant | "(" O_List(Pattern ) ")" | "[" List(Pattern ) "]" | "{" O_List(Field_Pattern ) O("...") "}".

      52. Field_Pattern::= Label "=" Pattern | Ident O(":" Type) O("as" Pattern).

        Types

      53. Type::= Type_Var | Type_Var_List Compound_Ident | Type "*" L(Type , "*") | Type "->" Type | "{" O_List( Label ":" Type ) "}" | "(" Type ")".

      54. Type_Var_List::= Empty | Type_Var | "(" List(Type_Var ) ")".

        Lexicon

        Use MATHS.Lexemes

      55. Compound_Ident::lexeme= L(Ident , ".") .

      56. Compound_Name::lexeme= Compound_Ident | "op" Infix_Operator.

      57. Name::lexeme= Ident | "op" Infix_Operator.

      58. Infix_Operator::lexeme= any identifier that has been declared to be infix.

      59. Constant::lexeme= Numeral O( "." N(digit ) ) O("E" Numeral) | double_quotes #String_Character double_quotes.

      60. String_Character::=character ~ (backslash | double_quotes) | backslash String_Escape.

      61. String_Escape::lexeme= "n" | "t" | "^" img("@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_") | digit digit digit | double_quote | "\" | N( SP | HT | EOLN | FF ) "\".

      62. Numeral::lexeme= O("~") N(digit ).

      63. Type_Var::lexeme= "'" O("'") O("_") Alphanumeric_Ident.

      64. Ident::lexeme= Alphanumeric_Ident | N(Symbol).

      65. Label::lexeme= Ident | (digit~"0") #(digit).

      66. Alphanumeric_Ident::lexeme= letter #( letter | digit | "_" | "'").

      67. Symbol::lexeme= img("!%&$#+-/:<=>?@\~`^|*").

        Some predefined infix operators with their predefined precedence levels:

          Precedenc 0: Precedence 3: Precedence 4: Precedence 5: Precedence 6: Presedence 7:


      68. Comment::lexeme= "(*" L(Commentary, Comment) "*)".
      69. Commentary::= any text that does not include (* or *) as a substring.

      70. Infix_list_constructor::lexeme= ":" ":".

      71. type::lexeme, introduces a type_declaration.

      See Also...

        Functions of SML-NJ

        [ ml.functions.html ]

        Syntax Diagrams

        Tobias Nipkow(nipkow@informatik.tu-muenchen.de) has translated Larry Paulson's BNF syntax for Standard ML into diagram form. The result is available as a compressed DVI file from Germany: [ ml-syntax.dvi.gz ] (Thanks to Tobias.Nipkow@informatik.tu-muenchen.de for updating this link and Maurício for updating it in 2010).

        Source

        Source: Used with permission from Larry.Paulson@cl.cam.ac.uk from the Usenet SML Archives for 1991, message # [ 2.txt ]

      . . . . . . . . . ( end of section See Also...) <<Contents | End>>

    . . . . . . . . . ( end of section Description of Standard ML) <<Contents | End>>

End