Signatures

8 Signatures

This section contains signatures used by ML-Yacc for structures in the file base.sml, functors and structures that it generates, and for the signatures of lexer structures supplied by you.

8.1 Parsing structure signatures

(* STREAM: signature for a lazy stream.*)

signature STREAM =
sig
  type 'a stream
  val streamify : (unit -> 'a) -> 'a stream
  val cons : 'a * 'a stream -> 'a stream
  val get : 'a stream -> 'a * 'a stream
end

(* LR_TABLE: signature for an LR Table.*)

signature LR_TABLE =
sig
  datatype ('a,'b) pairlist
    = EMPTY
    | PAIR of 'a * 'b * ('a,'b) pairlist
  datatype state = STATE of int
  datatype term = T of int
  datatype nonterm = NT of int
  datatype action = SHIFT of state
                  | REDUCE of int
                  | ACCEPT
                  | ERROR
  type table
        
  val numStates : table -> int
  val numRules : table -> int
  val describeActions : table -> state ->
                          (term,action) pairlist * action
  val describeGoto : table -> state ->
                       (nonterm,state) pairlist
  val action : table -> state * term -> action
  val goto : table -> state * nonterm -> state
  val initialState : table -> state
  exception Goto of state * nonterm

  val mkLrTable :
      {actions : ((term,action) pairlist * action) array,
       gotos : (nonterm,state) pairlist array,
       numStates : int, numRules : int,
       initialState : state} -> table
end

(* TOKEN: signature for the internal structure of a token.*)

signature TOKEN =
sig
  structure LrTable : LR_TABLE
  datatype ('a,'b) token = TOKEN of LrTable.term *
                                    ('a * 'b * 'b)
  val sameToken : ('a,'b) token * ('a,'b) token -> bool
end

(* LR_PARSER: signature for a polymorphic LR parser *)

signature LR_PARSER =
sig
  structure Stream: STREAM
  structure LrTable : LR_TABLE
  structure Token : TOKEN

  sharing LrTable = Token.LrTable

  exception ParseError

  val parse:
       {table : LrTable.table,
        lexer : ('b,'c) Token.token Stream.stream,
        arg: 'arg,
        saction : int *
                 'c *
                 (LrTable.state * ('b * 'c * 'c)) list * 
                 'arg ->
                  LrTable.nonterm *
                  ('b * 'c * 'c) *
                  ((LrTable.state *('b * 'c * 'c)) list),
        void : 'b,
        ec: {is_keyword : LrTable.term -> bool,
             noShift : LrTable.term -> bool,
             preferred_subst:LrTable.term -> LrTable.term list,
             preferred_insert : LrTable.term -> bool,
             errtermvalue : LrTable.term -> 'b,
             showTerminal : LrTable.term -> string,
             terms: LrTable.term list,
             error : string * 'c * 'c -> unit
            },
        lookahead : int (* max amount of lookahead used in
                         * error correction *)
       } -> 'b * (('b,'c) Token.token Stream.stream)
end

8.2 Lexers

Lexers for use with ML-Yacc's output must match one of these signatures.

signature LEXER =
sig
  structure UserDeclarations :
    sig
      type ('a,'b) token
      type pos
      type svalue
    end
  val makeLexer : (int -> string) -> unit -> 
       (UserDeclarations.svalue, UserDeclarations.pos)
       UserDeclarations.token
end

(* ARG_LEXER: the %arg option of ML-Lex allows users to
   produce lexers which also take an argument before
   yielding a function from unit to a token.
*)

signature ARG_LEXER =
sig
  structure UserDeclarations :
    sig
      type ('a,'b) token
      type pos
      type svalue
      type arg
    end
  val makeLexer :
      (int -> string) ->
      UserDeclarations.arg ->
      unit -> 
       (UserDeclarations.svalue, UserDeclarations.pos)
       UserDeclarations.token
end

8.3 Signatures for the functor produced by ML-Yacc

The following signature is used in signatures generated by ML-Yacc:

(* PARSER_DATA: the signature of ParserData structures in
   {n}LrValsFun functor produced by ML-Yacc. All such
   structures match this signature. *)

signature PARSER_DATA =
sig
  type pos       (* the type of line numbers *)
  type svalue    (* the type of semantic values *)
  type arg       (* the type of the user-supplied *)
                 (* argument to the parser *)
  type result

  structure LrTable : LR_TABLE
  structure Token : TOKEN
  sharing Token.LrTable = LrTable

  structure Actions : 
    sig
      val actions : int * pos *
       (LrTable.state * (svalue * pos * pos)) list * arg ->
               LrTable.nonterm * (svalue * pos * pos) *
             ((LrTable.state *(svalue * pos * pos)) list)
      val void : svalue
      val extract : svalue -> result
    end

  (* structure EC contains information used to improve
     error recovery in an error-correcting parser *)

  structure EC :
    sig
      val is_keyword : LrTable.term -> bool
      val noShift : LrTable.term -> bool
      val preferred_subst: LrTable.term -> LrTable.term list
      val preferred_insert : LrTable.term -> bool
      val errtermvalue : LrTable.term -> svalue
      val showTerminal : LrTable.term -> string
      val terms: LrTable.term list
    end

  (* table is the LR table for the parser *)

  val table : LrTable.table
end

ML-Yacc generates these two signatures:

(* printed out in .sig file created by parser generator: *)

signature {n}_TOKENS = 
sig
  type ('a,'b) token
  type svalue
  ...
end

signature {n}_LRVALS =
sig
  structure Tokens : {n}_TOKENS
  structure ParserData : PARSER_DATA
  sharing type ParserData.Token.token = Tokens.token
  sharing type ParserData.svalue = Tokens.svalue
end

8.4 User parser signatures

Parsers created by applying the Join functor will match this signature:

signature PARSER =
sig
  structure Token : TOKEN
  structure Stream : STREAM
  exception ParseError

  type pos    (* pos is the type of line numbers *)
  type result (* value returned by the parser *)
  type arg    (* type of the user-supplied argument  *)
  type svalue (* the types of semantic values *)

  val makeLexer : (int -> string) ->
                   (svalue,pos) Token.token Stream.stream

  val parse :
      int * ((svalue,pos) Token.token Stream.stream) *
      (string * pos * pos -> unit) * arg ->
          result * (svalue,pos) Token.token Stream.stream
  val sameToken :
    (svalue,pos) Token.token * (svalue,pos) Token.token ->
        bool
end

Parsers created by applying the JoinWithArg functor will match this signature:

signature ARG_PARSER = 
sig
  structure Token : TOKEN
  structure Stream : STREAM
  exception ParseError

  type arg
  type lexarg
  type pos
  type result
  type svalue

  val makeLexer : (int -> string) -> lexarg ->
                     (svalue,pos) Token.token Stream.stream
  val parse : int *
              ((svalue,pos) Token.token Stream.stream) *
              (string * pos * pos -> unit) *
              arg ->
               result * (svalue,pos) Token.token Stream.stream
  val sameToken :
      (svalue,pos) Token.token * (svalue,pos) Token.token ->
           bool
end